“第三方代管”参与下的共享单车回收路线优化问题

徐国勋, 王书伟, 郭 强, 赵 达

(1.海南大学 旅游学院,海南 海口 570228; 2.山东科技大学 经济管理学院,山东 青岛 266590; 3.海南大学 管理学院,海南 海口 570228)

0 引言

在中国，共享单车已成为第三大公共交通系统，仅2017年便为人们节约出行时间0.76亿小时，减少雾霾成本13亿元，提高平均出行效率15%[1]。然而根据调查研究发现，由于故意损坏、机械故障和零配件老化等原因，过去三年全国各城市损坏共享单车数量快速增加[2]。这些损坏的共享单车带来了严重的资源浪费问题[3]，用户满意度下降问题[4]，用户骑行安全问题等[1]。因此，及时召回损坏单车成为共享单车系统可持续发展的关键因素之一。

除法律法规建设之外[5]，利用卡车进行高效回收是目前共享单车回收问题研究的重点。一些研究者[6～8]考虑再平衡整个共享单车网络时加入损坏单车回收的操作，即卡车在各个站点既转运可用单车又同时回收损坏单车。徐国勋等[9]认为很难同时实现这两个目标，需要均衡考虑损坏单车的回收数量和可用单车的转运数量，并通过增大回收惩罚系数来提高回收需求的优先级。一些研究者提出在回收过程中应考虑时间因素的制约。例如王涵霄等[10]认为部分损坏单车可以当场维修，将维修时间加入到某些站点的服务时间内，并规定维修成功的单车可即刻转运到别的站点。Lu等[11]以最小化总时间为目标建立了一种基于真实数据的回收模型，并在模型中同时考虑了调度人员的开车时间、行走时间和损坏单车查找时间。还有一些研究者考虑了损坏单车的分布情况。例如张巍[12]等提出站点损坏单车近似服从正态分布，并选择合适的成本阈值来作为站点选取的标准。

当共享单车系统规模不是很大时，或可满足完全基于卡车进行回收。而我国大中城市的共享单车系统规模普遍很大，回收任务非常繁重，派遣卡车回收的成本又很高，运营商没有足够的资源及时回收损坏单车，从而导致城市公共空间被损坏单车挤占的问题很突出。因此政府与社会在呼吁共享单车用户参与损坏单车的回收利用，但由于并没有找到有效的激励机制，效果不尽人意[13]。鉴于此，近年来多地开始推出“第三方代管”这一新措施，由城管部门牵头，联合运营商聘请第三方代管员在路面巡查。代管员除了规范车辆停放外，还使用电动三轮车将零散分布的损坏单车运送至指定地点，以协助运营商完成回收操作。第三方代管具有成本低和灵活度高的优点，很快成为共享单车回收的重要补充力量。但同时也存在着效率和可靠性相对较低等问题，因此仅适合短距离小批量操作，而中长距离大批量操作仍需要派遣调度卡车来完成。然而在实际中却经常出现：代管员被委派将损坏单车运送至较远距离的维修地，导致其单个操作周期大大变长，进而丧失性价比；卡车被委派去回收操作困难的地点(例如零散分布的居民小区、拥堵的街道等)，回收成本与回收数量不成比例，丧失性价比。

以往研究全部基于有足够数量的调度卡车完成回收任务这一前提，仅考虑部署调度卡车进行回收，并没有针对实际中存在的第三方代管参与回收的情况来制定回收策略。鉴于此，本文提出第三方代管参与下的共享单车回收路线优化问题，并聚焦于将问题建模成混合整数规划，以及设计高效智能优化算法，为共享单车的回收管理提供重要的科学理论依据。

1 问题描述和模型建立

在本问题中，网络中的站点被划分为回收需求点和中转点。回收需求点是存在若干损坏单车的站点，而中转点是普通的租还车站点，用来临时停放从别处运送过来的损坏单车。运营商调派第三方代管员进行短距离小批量回收操作，同时派遣调度卡车进行中长距离大批量操作。回收任务则分成两部分：首先激励代管员将损坏单车从回收需求点运送至附近的中转点，然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。实际中运营商采用购买服务的方式来雇佣代管员，为衡量其完成一次任务应获得的奖励，需考虑以下因素：

(1)运送距离。由于工作成本(例如时间花费)与回收需求点至中转点的距离成正比，因此奖励大小与运送距离正相关，以体现代管员的工作成本。

(2)回收需求点损坏单车数量。回收需求点内共享单车损坏数量越多，公共空间被挤占情况越严重，因此奖励大小与回收需求点损坏单车数量正相关，以激励代管员及时将损坏单车运走，解决这些站点公共空间被损坏单车挤占的问题。

(3)对中转点租还车服务的影响。运送到中转点的损坏单车过多，会影响其正常租还车服务[4]，因此奖励大小与对中转点正常业务的影响程度负相关，以限制代管员出于各种原因(例如图方便省事)将损坏单车堆积在某些站点。而中转点容量越大，运送过来一辆损坏单车的占比则越小，则对正常业务的影响就相对越小，故可用中转点容量的倒数来表示对租还车服务的影响程度。

根据以上分析，代管员从回收需求点s运送一辆损坏单车至中转点i获得的奖励rsi可由公式(1)计算得到。其中ω表示单位奖励系数，csi表示回收需求点至中转点的距离，Is表示回收需求点s内损坏单车数量，rmin表示奖励下限，Li表示中转点的可用容量(由于Li≥0且为整数，为防止分母为0，采用Li+1来表示)。

(1)

为表示数学模型，用到了以下符号：

集合

K:运营商派遣的调度卡车集合；U:代管员集合；M:回收需求点集合；N:中转点集合；N0=N∪{0}，其中0点表示车场(即维修中心)；V=M∪N∪{0}。

参数

Is:回收需求点s的初始库存，即待回收单车数量；Li:中转点i的容量；cij:点i和j之间的距离；μ:卡车的单位距离成本；C:卡车的容量上限；H:代管员运送能力上限；T:用于激励代管员的总预算；M0:一个很大的正数。

决策变量

数学模型

(2)

(19)

目标函数(2)包含两部分，第一部分是卡车将中转点损坏单车回收至维修中心的总成本，第二部分是代管员将损坏单车集中至中转点后给予的总奖励。约束条件(3)限定了奖励支出预算。这是由于在实际中，一般是采用购买服务的方式来雇佣代管员，因此受到预算约束。约束条件(4)确保代管员将每个回收需求点内的损坏单车全部运出。约束条件(5)表明在中转点，代管员运送来的损坏单车总量不超过该中转点容量。约束条件(6)是代管员运送能力上限。约束条件(7)确保由代管员运送至中转点的这些损坏单车最终全部被回收至维修中心。约束条件(8)确保若卡车未服务某中转点，则相应的装载数量为0。约束条件(9)～(11)确保每辆卡车在整个回收行程中的装载量不超过容量限制。约束条件(9)确保每辆卡车空载状态从维修中心出发。约束条件(10)表示卡车在该中转点回收数量等于访问该点前后对应的装载数量之差。约束(11)限定了卡车装载量取值范围。约束条件(12)～(13)确保卡车从维修中心出发，并最后返回维修中心。约束条件(14)确保卡车服务过某中转点后必须从该点离开。约束条件(15)是子环消除条件，防止卡车路线中出现不包括维修中心的回路。约束条件(16)～(19)限定变量取值范围。

2 求解算法

由于本问题中包含的卡车路线问题是车辆路径问题这一经典的NP-Hard，这意味着本问题是更难求解的NP-Hard，当规模较小的时候采用求解器(如CPLEX, Gurobi, Ipsolver, MOSEK等)可有效对问题进行求解。但是Ho和Szeto[14]指出这些求解器的性能与问题规模呈负相关关系，不适合处理大规模问题，而智能优化算法更适合处理这类问题。鉴于共享单车网络规模很大，本文选择设计智能优化算法求解所提问题。

2.1 解的评估

2.2 教育与修复

为提高子代个体的质量，引入了教育算子。在教育算子中，包含随机删除，半径破坏，最小贡献移除，随机插入，最优插入，多点插入，随机交换和随机逆序八种局部搜索方法：

(4)随机插入。从未被访问过的站点中随机选择一个点，然后插入到解中。

(5)最优插入。随机选择未访问过的点t，并将t插入解中最小成本位置。例如若t被插入至点i和j之间，若i,j=arc min(μcit+μctj-μcij)(i,j)∈A，则该插入位置为最小成本位置。

(6)多点插入。从未访问站点中随机挑选两个点，然后将二者随机插入到解中。

(7)随机交换。从解随机选择两个点并交换它们在解中的位置。

(8)随机逆序。随机选择一条子序列并将该子序列逆序。

教育算子的具体流程如下：

经过教育操作后的解如果变得可行则将其置于可行子种群中，如果仍然不可行则将其置于不可行子种群中，然后进行概率为Prepair的修复操作。每个不可行解最多可以修复两次，第一次将F(p)中的系数α乘 (1+γ)倍，第二次将系数α乘10(1+γ)，其中γ于区间(0,1]随机取值。如果修复之后，原来的不可行解成为可行解，则将修复后的新可行解置于可行子种群中，与此同时在非可行子种群中保留原不可行解。

教育算子1:将所有方法的编号放置在集合Ω中;2:随机在Ω中挑出一种方法;3:如果该方法能够改进当前解,则重复使用该方法对当前解进行改进。如果连续进行ITedu次迭代都无法改进当前解,则教育算子需被终止;4:从Ω中将该局部搜索方法剔除;5:如果Ω不为空集,则转步骤2,否则结束教育算子。

2.3 嵌入算法

步骤1.1将剩余库存不为零的回收需求点和剩余可用容量不为零中转点对应的OD对全部置于集合Ω；

步骤1.2根据rsi的数值，按照由小到大的顺序对集合Ω中全部OD对排序；

步骤1.3确定Ω中第一个OD对可运送的损坏单车最大数量Zsi=min{Is,Li}；

步骤1.4更新回收需求点的剩余库存和中转点的剩余可用容量。Is←Is-Zsi，Li←Li-Zsi。如果Is=0，则从Ω中将包含s点的OD对全部移除；如果Li=0，将包含i点的OD对全部移除；

步骤1.5重复执行步骤1.3和步骤1.4，直到Ω中元素全部被清空，于是全部Zsi便可确定；

步骤1.6把运送任务(Zsi辆损坏单车)分给v=[1+Zsi/H]个代管员，其中[.]表示取整。

步骤2.1令k=1；

步骤2.2将卡车k的剩余载重空间表示为Cleft；

步骤2.5若k≥|K|，转步骤3。否则更新k←k+1，转步骤2.2。

3 数值实验

3.1 回收需求点内损坏单车数量与回收成本之间的关系

一般情况下，出于种种原因(调度车辆不足、预算限制等)原因，运营商并不会及时回收损坏单车，常常导致损坏单车在站点内逐渐积压。本节论证在本文所提回收策略下及时回收损坏单车反而会减少运营成本。为方便求出最优解，令C=20,T=100,ω=0.5,μ=1,H=4,rmin=0,|K|=1,|U|=5。坐标={(12,10);(8,20);(14,7);(10,15);(1,3);(5,6);(2,2);(0,0)}。其中前三个点为中转点，其容量分别为{5,7,9}，最后一个点为没有任何需求的车场，其余点为回收需求点，损坏单车数量分别为{4,4,2,2,1}。实验结果如图1所示。

图1 回收需求点内损坏单车数量与回收成本的关系

以回收需求点1 为例论证损坏单车数量对运营成本的影响。在横坐标(损坏单车数量)由0至10的变化过程中，卡车运输成本呈增加趋势。这是由于中转点存在容量上限，当某个中转点达到容量上限后，需要把损坏单车存放到其它中转点。相应地，卡车在回收过程中需要访问的中转点数量增加，进而使得其运输成本增加。由图1还可得，“第三方代管”的奖励支出关于损坏单车数量的曲线斜率为正。这表明随着站点内积压的损坏单车数量的增加，导致回收每辆损坏单车的单位奖励增加也在增加，即需要支付给代管员更多的奖励来激励其将损坏单车运走，以解决站点公共空间被损坏单车挤占的问题。由于总回收成本为卡车运输成本和“第三方代管”的奖励支出之和，因此总回收成本亦随着损坏单车数量的增加。其余回收需求点可以得到类似结论。

综上所述，在本文所提回收策略下，回收需求点内损坏单车数量与总回收成本是正相关关系。这意味着本文所提回收策略下及时回收损坏单车，不仅能够减轻站点公共空间被损坏单车挤占的问题，还能有效减少回收成本。

3.2 算法性能测试

数值实验环境是i7-2600CPU主频3.40GHz内存16GB的PC电脑，编程语言为C#。为了测试所设计HGA算法性能，采用Gurobi 8.0和遗传算法(GA)作为比对算法。由于没有针对本文所研究问题的算例，因此依据Ii均匀分布于[1,5]，Li均匀分布于[5,10]，T设为1000，站点坐标均匀分布于[0,50]，C=20，H=10，rmin=0，ω=1和μ=1生成规模不同的数据组。HGA参数中，μ=25,Nindiv=25,Nelite=10,Prepair=0.5,ξ=0.2,λ=40,Itdiv=0.4ItNI。

表1最左侧展示了Gurobi求解结果，包括了上界(UB)，下界(LB)以及反应求解质量的gap(数值越小则表明解的质量越高)。表1中间和最右侧分别展示了GA和HGA运行20次求得的结果，包括平均目标函数值(Avg)，最好的解(Min)，相应的gap(数值越小则表明解的质量越高)以及终止时间(CPU/s)。

表1 算法性能比较

首先，与Gurobi求解结果进行比较。从算例3至算例6，发现在规定求解时间内Gurobi只能得到一个上界和下界，已无法确定最优解。从算例7至算例9，Gurobi在规定时间内已无法确定一个上界和下界。对于算例1，HGA求解时间比Gurobi求解时间要长，这是由于只要没有达到终止条件，HGA即使找到了最优解也不会终止算法，这是智能优化算法常见的问题。从算例3至算例6，HGA求解的gap与Gurobi求解的gap差距越来越大，这表明HGA求解质量显著超过了Gurobi。从算例7至算例9，相比Gurobi已无法确定一个可行解，HGA仍然能在短时间内求得可行解。

其次，与GA求解结果进行比较。从算例1至算例9，HGA全部指标性能均超过GA。在相同的运算时间内，HGA平均目标函数值比GA降低约4.3%，以HGA最好的解数值比GA平均减少约0.66%。

4 结束语

基于实际中第三方代管参与短距离小批量共享单车回收这一情况，本文提出激励代管员将损坏单车从回收需求点运送至附近的中转点，然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。为衡量代管员完成一次任务应获得的奖励，考虑运送距离、回收需求点损坏单车数量和对中转点正常业务的影响程度。并把问题建模为混合整数规划模型，同时针对问题特征设计了一种改进遗传算法。其中遗传算法用来确定卡车路线和中转点，嵌入的启发式算法用来确定代管员的路线和运送数量以及卡车在每个中转点的回收数量。

本文通过数值实验论证了所设计算法的高效性，并验证了第三方代管参与的回收策略不仅能够减轻站点公共空间被损坏单车挤占的问题，还能有效减少回收成本，对改进共享单车回收管理(包括提高回收效率和降低回收成本)具有重要的实际意义。未来研究可考虑将本问题扩展到多重图网络中。