考虑故障车回收的共享单车静态重平衡问题

丁飞阳，张 思

（上海大学 管理学院，上海 200444）

0 引言

共享单车给人民带来便利的同时，其快速发展也带来了一系列问题。在一些城市，共享单车被随处停放，导致有些区域形成交通拥堵，有些区域又一车难求，造成了供需不平衡的局面。此外，由于共享单车长时间接受风吹日晒，其故障率也远远高于普通自行车，影响用户体验。

共享单车系统的平稳运行通常需要满足用户波动出行需求的能力。为了保证系统可靠性和提高用户的满意度，运营商需要对共享单车系统进行重平衡。重平衡问题旨在研究如何调度各个站点间不平衡的共享单车数量，以更好地满足客户需求。其调度通常有两种策略，一是客户激励：运营商根据系统的当前和预测状态，计算出停放共享单车在各个站点的奖励，并提供给顾客，具体可参考文献[1]、[2]。二是运营商利用卡车将自行车从过剩（供应）站运到不足（需求）站，以实现理想的平衡。基于运营商的重新平衡有两种类型：静态重平衡和动态重平衡。

静态重平衡侧重于在夜间进行平衡过程，此时用户使用和道路拥堵情况可以忽略不计，主要包含静态完全重平衡问题（SCRP）和静态部分重平衡问题（SPRP）。对于SCRP，Dell'Amico，等[3]首次完整定义了共享单车静态重平衡问题；为了求解该问题，Forma，等[4]提出了一种三步启发式算法。Erdogan，等[5]提出了带需求区间的共享单车重平衡，将其视为1-PDTSP的变种。刘喜梅，等[6]和吕畅，等[7]分别用改进启发式算法进行求解。Pal和Zhang[8]提出了一种混合嵌套的大邻域搜索与可变邻域下降算法，在大规模问题上表现高效。秦冰芳[9]以最小化总成本和车辆工作时间为目标建立了分批配送车辆路径模型。陈植元，等[10]根据共享单车的时空分布将具有相似时空属性的站点进行聚类，将问题转化为带时间窗和容量约束的VRP问题。对于SPRP，Ravia，等[11]首次提出了多调度车辆问题。Ho和Szeto[12]提出一种迭代的禁忌搜索算法来求解。Li，等[13]考虑了多种单车类型的重平衡问题。Mohammadi，等[14]设计了一个基于旅行商的多目标、多商品、多时期的数学模型，对其小规模问题进行精确求解。Szeto和Shui[15]引入了总需求不满意（TDD）的概念，目标函数首先最小化系统总需求不满度的正偏差，然后使车辆的总服务时间最小。于德新，等[16]以最小化总成本和最大化投放率（投放与需求的比值）为目标,其创新点在于采用TOPSIS法在遗传算法求解出的有效路线中选择最优路线。汪慎文，等[17]设计了一种离散差分进化算法来求解该问题。许媛媛[18]构建了多目标混合整数规划模型，采用混合遗传算法和变邻域搜索算法的粒子群算法进行求解。

动态重平衡则与白天操作的平衡有关，此时系统处于高使用率，车站的需求会在重平衡期间发生变化。Kloimullner，等[19]将每个累积的需求函数分割成弱单调片段，用四种启发式方法对实例进行了测试。冯麟博[20]提出了一种BP神经网络算法对共享单车需求进行预测，引入虚拟调度中心的概念，从而将动态问题转化为静态问题。张徐[21]提出了改进的随机森林预测方法对需求进行预测，之后利用K-means对区域进行划分，将问题从全局最优转化为局部最优，采用改进蚁群算法求解。但是人们出行充满不确定性，因此多数动态问题转化为静态问题时对需求的预测也会存在一定偏差。此外在需求高位波动的白天，运营商调度成本更高的同时还易受到交通拥堵等外界影响。因此本文选择静态重平衡为研究对象。

以上研究只考虑到了对好车的重平衡，未考虑到对故障车的回收。近年来，逐步有学者开始考虑到故障车的回收。徐国勋，等[22]在调度中考虑了损坏自行车的回收，设计了混合禁忌搜索算法求解。Wang 和Szeto[23-24]首次提出了考虑CO2排放的带故障车回收的重平衡问题，采用增强型人工蜂群算法求解该绿色BRP问题。Du，等[25]研究了多中心、多车型、允许多次访问的带故障车回收的重平衡问题，其结果量化了带故障车回收的综合重平衡相比于单独重平衡的好处。王涵霄，等[26]首次提出了小故障单车当场维修、大故障单车回收、好单车调度的概念，其采用蚁群算法来求解。

现阶段的研究多为考虑故障车回收的静态完全重平衡问题，由多车辆进行工作，这势必会增加车辆运行的固定成本。本文的研究考虑故障车回收的共享单车静态部分重平衡问题，由单车辆进行多车次工作，将全部故障单车进行回收，下一次作业车辆上的初始单车数受到上一次作业最终状态的影响。为此，提出了一种改进遗传算法，引入了精英个体爬山、自适应交叉、变异等操作来求解该问题。

1 模型建立

在共享单车系统中一个调度中心通常服务多个站点，多车次具有相同容量的调度车从调度中心出发，在供应站提取正常的单车，并将它们送到需求站。同时每个站点的故障单车会被装载到调度车上。当调度车的容量已满或调度车的容量不足以服务下个站点时，返回调度中心进行卸货。直到所有站点均被服务一次后任务结束。一个典型示例如图1所示，包含一个调度中心和七个站点，车辆的容量为10。调度车返回调度中心，所有故障单车均被卸下，再次出发时允许调度车上存在不超过确定数量的好单车。

图1 共享单车调度和回收故障车辆示意图

本模型提出如下假设：

（1）站点调度与回收故障车工作发生于深夜，此时不考虑站点单车数量的变动，为静态重平衡；

（2）只存在一个调度中心，调度车辆从该处出发，最后需返回该处；

（3）每个站点好车和坏车的数量已知；

（4）调度车辆的行驶成本只与距离成线性相关，不考虑其他因素；

（5）调度车第一次从调度中心出发时为空车，第二次及之后从调度中心出发时允许调度车上存在不多于一定数量的好单车；

（6）站点所存在的多余好车、坏车需全部被回收，但允许站点的好车需求数不被满足。

在有向图G=(V,A)上，其中V= {0,1,2,...,n} 表示所有节点的集合，0表示调度中心，0,1,2,...,n表示调度点，A表示弧的集合，A={(i,j):i,j ∈V,i ≠j} 。表示调度点的集合。

变量符号及其含义见表1。

表1 变量符号及含义

模型建立如下：

目标函数（1）表示最小化总成本，包括调度车辆的行驶成本，偏离好车需求期望的惩罚成本。约束条件（2）表示各个调度点的好车转移方程，好车有装有卸。约束条件（3）表示各个调度点的好车需先满足自身期望后，多余的好车才可装到调度车上。约束条件（4）表示各个调度点装到调度车上的坏车数需等于该站点初始坏车数。约束条件（5）（6）表示服务点i 前后，调度车上所拥有的好车数和坏车数较刚到达站点i时的数量变化情况，其数值等于在站点i的装卸量。约束条件（7）表示调度车到达与离开的是同一个站点，确保流守恒。约束条件（8）（9）表示调度车从调度中心出发时，第一次为空车，第二次车上允许存在一定数量好车。约束条件（10）表示车辆的容量约束。约束条件（11）表示每个站点只能被一辆调度车辆服务一次。约束条件（12）（13）表示每辆调度车均从调度中心出发，工作完后都返回调度中心。约束条件（14）（15）表示调度车在站点i所卸载的好车数要满足该站点的需求和调度车容量的较小值。约束条件（16）表示消除子回路，避免不经过调度中心的回路出现。约束条件（17）-（21）分别定义了变量的定义域。

2 算法设计

遗传算法最早由美国John Holland 教授于1975年提出,其灵感来自于自然进化的规律。在遗传算法中，每个染色体需要定义一个适应度函数来进行评价，使适应度值好的染色体有更多的繁殖机会，从而形成下一代新种群。对这个新种群进行下一轮进化，如此往复直到找到满意解。

在求解一些较为复杂的优化问题时，遗传算法的计算效率高，全局搜索性强，能在较短时间内求出问题的满意解，因此本问题采用遗传算法进行求解。但经典遗传算法局部搜索性能较差，容易过早收敛而陷入局部最优，因此本文在遗传算法中引入了精英个体爬山操作、自适应交叉和变异操作，从而提高了其鲁棒性。

2.1 初始解的生成

本文采用自然数编码方式，每一条染色体由自然数0至N（待服务站点数目）所组成，代表调度车辆的行驶路径。其中0代表调度中心，其余自然数代表每个待服务的站点。

如其中一条染色体为：0—3—7—5—0—2—4—6—0—1—8—0 表示共出动了三个车次，包含三条路径。路径1：0—3—7—5—0 路径2：0—2—4—6—0 路径3：0—1—8—0。

2.2 适应度函数

上述编码方式不能保证解码的染色体使用不超过规定的车次数，所以提出惩罚函数来解决这一问题。配送方案总成本的计算公式如下：

式中，X(i)为目标函数（1）的总成本，w(i)为使用超过规定数目车次的惩罚成本。γ为违反车次数量约束的惩罚因子，di为第i条染色体使用的车次数，ni为规定的最大车次数。

2.3 选择与爬山操作

本文采用二元锦标赛与精英个体爬山操作相结合，具体如图2所示。为了避免过早陷入局部最优，本文对选择操作后的染色体进行去重操作，并与父代染色体相结合形成新种群。对该代染色体中适应度函数最高的精英个体进行爬山，采用2-opt领域搜索法，随机交换染色体中两个位置的基因，计算其适应度，若适应度提高，则互换基因后的个体替代原来的个体保存到下一代，跳出循环。若适应度未增加，则最优染色体不变。重复以上步骤，直到达到指定次数为止。

图2 选择操作流程图

2.4 遗传自适应操作

为保证算法的高效性，设置交叉概率为：

式中，fi表示待交叉的两个染色体中适应度的较大值，fave表示该代种群适应度的平均值，fmax表示该代种群中适应度函数的最大值，Pc1表示较小的交叉概率，Pc2 表示较大的交叉概率。改进的交叉操作如下所示。

设置变异概率为：

式中，fi表示待变异的两个染色体中适应度的较大值，fave表示该代种群适应度的平均值，Pm1 表示较小的变异概率，Pm2 表示较大的变异概率。其中变异操作采用两互换方法。

改进遗传算法运行流程如图3所示。

图3 算法流程图

3 算例分析

现有一调度中心和若干个待服务的站点（小规模算例R1001-R1010 表示有10 个算例，每个算例有10 个待服务的站点，中规模算例R2001-R2010 表示有10 个算例，每个算例有20 个待服务的站点，大规模算例R4001-R4010 表示有10 个算例，每个算例有40 个待服务的站点），其中调度车辆的容量为40，好单车不足的惩罚成本为2，车辆行驶单位距离成本为1.5，使用过多调度车时的惩罚成本为10。每个案例的好单车需求期望均设置为15，未经服务前的好单车数设置为0到30的随机数，坏单车数设置为0到10的随机数。

3.1 参数设计

采用中规模R2001 算例来进行参数设置。首先设 定NIND=200，Pc1=0.4，Pc2=0.8，Pm1=0.1，Pm2=0.3，MAXGEN=2 000。

之后依次优化NIND、Pc1、Pc2、Pm1、Pm2。例如，当其他参数固定时，NIND需要设置80-440来比较优化效果，每个不同的NIND数都需进行五次运行来确定目标函数的平均值，如果优化效果最好时NIND 为200，固定此参数继续优化其他参数。优化结果如图4所示。最后优化后的参数为NIND=400，Pc1=0.3，Pc2=0.75，Pm1=0.125，Pm2=0.3，MAXGEN=2 000。

图4 遗传算子参数设计

3.2 算例分析

遗传算法相关参数见表2，其中小规模中可使用的车次设置为2次。

表2 遗传算法参数设置

采用改进遗传算法对小规模算例进行求解，并用gurobi求解相同问题，从而进行比较分析。具体求解结果见表3。由于在小规模案例中，遗传算法在同一实例中经过迭代所找出的近似最优解都相同，因此并不需计算其平均目标函数值。

表3 小规模算例求解结果分析（算例R1001-算例R1010）

从表3可以看出，在小规模问题中精确算法与改进遗传算法相比，其目标函数值在大部分算例中都相同，在小部分算例中有微小的差异，可验证所提出遗传算法的有效性。

为进一步验证本文提出遗传算法的优势，对中大规模算例进行实验对比。其中遗传算法对不同算例分别进行10 次求解。其中中规模算例可使用的车次设置为3 次，MAXGEN 设置为2 000 次；大规模算例可使用的车次设置为5 次，MAXGEN 设置为5 000次。

从表4 可知，在中规模算例中，改进遗传算法所得的目标函数值总成本比gurobi 求解结果高0.80%，但是算法计算速度在大多算例中远远快于gurobi 求解。从表5 可知，在大规模算例中，改进的遗传算法依旧能保持较好的鲁棒性，且依旧能快速得出近似最优值，但gurobi求解在规定的2小时内已经无法求出解。可见随着算例规模的进一步增大，遗传算法在速度方面的优势愈发体现出来，可用来求解大规模问题。

表4 中规模算例求解结果分析（算例R2001-R2020）

表5 大规模算例求解结果分析算例（R4001-R4010）

3.3 敏感度分析

在对算例进行求解时，调度车的车次限制（NV）、调度车的最大容量（Cap）以及第二次及之后从调度中心出发时允许初始的最大好车数（G_max）都会对结果有影响。为了探究以上三种因素的变化对总目标函数的影响，本节在中规模算例（R2001-R2010）下对其进行灵敏度分析。在敏感度分析时，初始NV=3，Cap=40，G_max=10。对不同因素进行分析时，十个算例分别进行五次求解且取其中的最小值记录，将每个算例中所记录的最小值取平均值，作为当前的目标函数平均值。

3.3.1 分析NV敏感度。从表6可知，随着NV从1到5逐渐变大，目标函数先降低后趋于平稳态势（如图5（b）所示）。

表6 调度车次限制（NV）敏感度分析

图5 目标函数和求解时间随着NV变化的敏感性分析

3.3.2 分析Cap敏感度。从表7可知，随着车辆容量Cap的增加，目标函数值下降，其下降斜率从大到小逐渐变小（如图6（b）所示）。

表7 车辆容量（Cap）敏感度分析

图6 目标函数和求解时间随着Cap变化的敏感性分析

分析原因为：当Cap小于40时，其完成任务所需要使用的调度车次大于初始的NV（值为3），因此其不仅需要更多的调度车次增加了惩罚成本，还需要多次来回调度中心增加了额外的路径成本。因此在Cap为20-40期间，目标函数值下降幅度较大，其下降幅度先大后小。当Cap大于40时，目标函数幅度下降变缓，其减少的成本在于减少来回调度中心的额外路径成本。随着车辆容量Cap的增加，求解时间总体呈下降趋势（如图6（a）所示）。原因在于随着Cap的增大，所需要使用的车次数减少，因此算法搜索时间变少。

3.3.3 分析G_max敏感度。从表8可知，随着车辆容量G_max的增加，目标函数先下降后趋于平稳，其下降幅度从大到小（如图7（a）所示）。

表8 允许所带的好车数（G_max）敏感度分析

图7 目标函数和求解时间随着G_max变化的敏感性分析

分析原因为：当调度车因容量限制返回调度中心，再次出发时调度车上的好车数会被初始化为G_max，若G_max过小，则会损失一些好车，从而造成好车不足惩罚成本的产生。随着G_max从0逐步增大到15左右时，目标函数都在下降，因为增大G_max可以减少对路线规划的限制从而搜索到目标函数值更小的满意解。随着G_max的进一步增加，由于其路径满意解中不存在需要G_max更大的路径，因此其目标函数值并没有下降。随着G_max的改变，求解时间总体呈上升趋势（如图7（b）所示），原因在于G_max的增大会在一定程度上增大搜索规模。

4 结语

本文考虑了共享单车的实际情况，包括好车的调度和坏车的回收，对于共享单车企业具有重要的现实意义。本文的主要工作如下：（1）在遗传算法的基础上，对其进行了改进，引入了爬山操作、自适应交叉、变异等。（2）本文通过gurobi对模型进行精确求解，并与启发式算法求解结果进行分析比较。通过小、中、大三个规模实验分析，证明本文所提出的改进遗传算法具有可行性和优势性。最后，本文对调度车的车次限制、最大容量以及第二次及之后从调度中心出发时允许初始的最大好车数进行了敏感性分析，其结果总体呈下降趋势，并得出了以下结论：（1）增加调度车的车次并不一定会降低成本，因为车次过多时一些调度车并不一定会以最优路线运行；（2）增加调度车的最大容量，调度车的运行成本降低，但降低幅度逐渐变小，因此需要结合调度车的固定成本来权衡合适的车辆容量；（3）增加第二次及之后从调度中心出发时允许初始的最大好车数，其运行成本先降低后略微上升，因此需要选择适当的初始最大好车数来减少成本。

本文提出的共享单车平衡和回收已经有了一定的成果，但还存在许多不足需要改善，在未来的研究中可以从以下几个方面进行改进：（1）可引入客户的满意度以及调度车作业时的碳排放量为目标函数，使其成为更复杂的多目标函数问题。（2）后续对模型假设复杂化，将其设置为每个站点可多次访问，共享单车所停位置为非固定式的散乱停放，以及好车坏车数量在调度工作途中会在较小幅度波动的情况。