0 概述

城市共享单车在方便居民短距离出行、缓解城市交通拥堵等方面发挥着重要作用。由于单车用户用车具有随机性、单向性等特点, 导致各停放点单车数量分布不均, 需定期组织货车回收、再投放单车, 平衡各停放点单车数量。随着我国各城市共享单车系统规模的扩大, 单车再平衡工作量与日俱增, 设计开发共享单车再平衡智能调度软件以实现高效的共享单车再平衡, 已成为共享单车运营主体降本增效、提升服务质量的关键。

共享单车再平衡过程可描述为:利用具有相同载重的车辆从单车维护与补给中心出发, 完成一定区域内各停放点单车的再分配, 使各停放点达到预先设置的容量后回到中心。在此过程中, 运输车辆可以在各停放点调配运送单车, 也可以在出发前从维护与补给中心载入一部分单车调配到各停放点, 或将各停放点多余的单车运回维护与补给中心。而共享单车再平衡问题(Bike-sharing Rebalancing Problem, BRP)即为在共享单车再平衡过程中, 对所有的车辆求解最短的行驶距离或最少的行驶时间。

共享单车在世界各地的普及, 使BRP问题受到广泛关注。在国外的研究主要将BRP模型分为静态和动态2类进行求解。

静态BRP模型基于假设:在车辆开始服务各停放点后, 各停放点单车的平衡数量不发生变化。文献[1]提出该类模型并对其求解; 文献[2]设计分枝定界法求解该模型; 文献[3]研究目标函数为用户不满意度、车辆行驶时间最少的BRP模型, 并利用分阶段启发式算法及CPLEX求解包含200个停靠点的BRP; 文献[4-5]对BRP进行深入研究, 不仅构建了4种BRP数学模型、标准测试算例, 还运用破坏修复启发式算法求解包含500个停靠点的BRP; 文献[6]研究只有一辆运输车辆且允许对停靠点进行多次访问的BRP, 利用可变邻域搜索技术设计启发式算法, 并对包含500个停靠点的BRP求解。

由于在共享单车再平衡过程中, 用户仍然在使用单车, 各停靠点单车平衡数量具有动态性, 因此需要建立动态BRP模型。文献[7]运用时间序列化方法, 以时长T为周期将动态BRP模型划分为若干个静态BRP模型来求解, 根据用户服务的分布函数确定每一个周期各停靠点的单车平衡数量, 并将优化目标设置为最小化各点单车平衡数量的不匹配度; 文献[8-9]应用在线处理方法求解动态BRP模型, 在运输车辆服务完某一停靠点后, 实时更新其他停靠点的取送量信息进行下一步决策。

目前, 国内对BRP尚缺少系统研究, 已报道的多为案例研究, 如文献[10]构建基于用户满意度的多目标共享单车调度模型并采用遗传算法对其求解, 同时以南京市江宁区的实际算例进行验证; 文献[11]通过预测各停靠点的取送车需求量, 运用动态调度优化策略建立系统的动态调度模型, 设计模拟退火遗传算法对其求解, 并以西安市雁塔区的数据进行验证; 文献[12]引入停靠点取送车的时间窗约束、多调度中心约束条件, 建立BRP模型并运用混合粒子群算法对其求解。此外, 文献[13-15]也对BRP问题进行了研究。

国外学者较系统地研究了BRP问题的特点及经典启发式算法, 但求解速度与质量有待进一步提升, 而国内研究多为案例研究, 研究成果难以推广应用。考虑到遗传算法对车辆路径问题(Vehicle Route Problem, VRP)具有较好的求解效果, 例如:文献[16-18]分别使用遗传算法求解了周期性、开放式和多目标VRP, 取得了较好的效果, 本文采用遗传算法并结合破坏修复启发式算法的启发规则来求解BRP。

1 BRP数学模型

根据图论的定义, 将BRP表示为一个完备图G=(V, E), 其中, V={1, 2, …, n}表示顶点集, 且1表示单车维护与补给中心, V′＝{2, 3, …, n}表示单车停放点集, E={(i, j)|i, j∈V, i≠j}表示弧集或边集。本文符号定义如下:M表示实施再平衡运输的车辆数, Q表示运输车辆的最大载重量, d_i表示车辆在第i个单车停放点取送量(取值范围为[-Q, Q], d_i < 0表示该停放点需补充单车, d_i>0表示该停放点要回收单车), c_ij表示车辆访问弧(i, j)产生的运输成本或时间, θ_j表示车辆访问第j个停放点后的载重量(即车辆线路载重量)。定义决策变量x_ij=1表示车辆访问了弧(i, j), 否则, x_ij=0。BRP的数学模型如下:

$ \begin{array}{l} \min F(x) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{c_{ij}}} } {x_{ij}}\\ {\rm{s}}{\rm{.t}}{\rm{.}} \end{array} $

(1)

$ \sum\limits_{i = 1}^n {{x_{ij}}} = 1, j \in {V^\prime } $

(2)

$ \sum\limits_{i = 1}^n {{x_{ji}}} = 1, j \in {V^\prime } $

(3)

$ \sum\limits_{j = 1}^n {{x_{1j}}} \le M $

(4)

$ \sum\limits_{j = 2}^n {{x_{1j}}} = \sum\limits_{j = 2}^n {{x_{j1}}} $

(5)

$ \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } \le |S| - 1, S \subseteq {V^\prime }, S \ne \emptyset $

(6)

$ {\theta _j} \ge \left( {{\theta _i} + {d_j}} \right){x_{ij}}, i \in V, j \in {V^\prime } $

(7)

$ {\theta _i} \ge ({\theta _j} - {d_j}){x_{ij}}, i \in {V^\prime }, j \in V $

(8)

$ {\text{max}} (0, {d_j}) \le {\theta _j} \le {\text{min}} (Q, Q + {d_j}), j \in V $

(9)

式(1)为目标函数, 最小化运输总成本或时间; 式(2)和式(3)确保除维护与补给中心点外其余单车停放点均被访问且只访问一次; 式(4)和式(5)确保所有的运输车辆在完成任务后均回到维护与补给中心; 式(6)为消除子回路约束; 式(7)~式(9)为BRP车辆载重约束, 确保各运输车辆在实施单车回收与投放过程中, 车辆线路载重量不超过额定载重量, 其假设在某一停放点回收的单车可被投放到任意其他需要的停放点, 且在车辆出发或者回到补给中心时, 载重可不为0(因为可以事先装入部分单车, 或者带回部分单车)。

2 求解BRP的遗传算法 2.1 算法基本框架

基本的遗传算法是基于种群的并行搜索机制, 本文采用基于个体搜索机制的非代际遗传算法^[19], 该机制能在进化的过程中更好保留优异个体的同时兼顾种群的多样性, 算法描述如下:

1) 初始化种群Pop。

2) 若终止条件不符合:

3) 按染色体的适应度选择2个染色体x、y。

4) 依交叉概率P_cross对x、y实施交叉算子, 生成2个新个体x′、y′。

5) 依变异概率P_mut对x′、y′实施变异算子, 生成2个新个体x″、y″。

6) 更新种群, 将x″、y″替换Pop中2个适当度最差的染色体。

7) 算法结束, 返回种群中适应度值最大的染色体。

2.2 算法的编码与初始解生成

本文算法采用多维整数编码方法, 1, 2, …, n代表单车停放点位置编号, 其中编号1代表单车维护与补给中心。每一基因位除包含单车停放点位置编号外, 还包含以下信息:对应的线路编号信息, 该基因位在线路中的排列顺序, 当前线路中该停放点之后位置再插入点时对应单车容量的上限(U_i)与下限(D_i)。染色体编码示意图如图 1所示。

BRP模型具有以下性质^[20]:

性质1  设Route为一条可行线路, Position(P₁, P₂, …, P_i-1, P_i, P_i+1, …P_n)为在构造线路时可插入待访问取送点的位置(如图 2所示), 设P_i位置可插入车数范围为[D_i, U_i], 若要保持插入后Route仍可行, 则有:

$ \begin{array}{*{20}{l}} {{U_i} = Q + min \{ {\theta _1}, {\theta _2}, \cdots , {\theta _i}\} - max \{ {\theta _i}, {\theta _{i + 1}}, \cdots , {\theta _n}\} }\\ {{D_i} = - Q - min \{ {\theta _i}, {\theta _{i + 1}}, \cdots , {\theta _n}\} + max \left\{ {{\theta _1}, {\theta _2}, \cdots , {\theta _i}} \right\}} \end{array} $

根据性质1, 本文算法可实时计算对应插入位置单车容量的上限与下限, 该容量区间表示确保插入停靠点后的新路径仍然可行的回收与投放单车数量区间。

本文算法初始解生成采用随机选择停靠点作为插入位置, 通过容量区间实时检测并判断每次插入操作是否可行。如果插入操作可行, 则允许实施, 否则, 选择其他停靠点检测并判断。如果对所有停靠点插入操作均不可行, 则重新生成一条新路径, 直到所有的停靠点均插入到当前解。

2.3 交叉算子

为了不在交叉过程中过度破坏染色体片断, 交叉算子采用线路交叉方法, 即在参与交叉的2个染色体中随机各选取一条线路作为交换片段进行交换。在交叉过程中涉及大量的停靠点插入操作, 可通过采用容量区间实时检测, 确保当前插入操作可行, 具体过程如下:

1) 对参与交叉的2个父染色体x与y随机各选取一条参与交叉的线路, 将从x(y)染色体上选取的线路中的点形成待插入y(x)染色体的位置集合Insert_to_y(Insert_to_x)。

2)在染色体x(y)中将与集合Insert_to_x(Insert_to_y)重复的点删除。在此过程中可能会造成被删除点的线路变为不可行, 本文采用2种策略进行处理。

策略1  一旦线路变为不可行, 则将该线路所有的点放入Insert_to_x集或Insert_to_y集。

策略2  采用分裂策略, 即删除重合点, 将重合点前后两部分点按原有排列顺序各形成一条子线路放在原染色体中。

策略1有助于提升解的多样性, 而策略2有助于保留原染色体的优质基因片段。本文在运用交叉算子时混合使用二种策略。

3) 利用节约算法将Insert_to_x(Insert_to_y)插入x(y)。

2.4 变异算子

本文算法共使用了3种变异算子:

1) Swap变异算子, 随机从参与变异的染色体x′或y′中选取2个点进行交换, 形成新的染色体x″、y″。

2) Merge变异算子, 在参与变异的染色体x′或y′中随机选择2条线路, 将第1条线路的尾点与第2条线路的首点相连。

3) Destroy & Repair变异算子, 从参与变异的染色体x′或y′中随机选取3个点, 将其从当前解中移出, 并保证移出3个点后x′或y′仍可行, 再插入到x′或y′中形成新的染色体x″或y″。

在运算过程中等概率随机采用上述3种变异算子, 而再插入过程均采取最优插入方法, 即选择最优节约值最大的插入位置插入, 且采用保优策略, 保证变异后的新染色体x″、y″的适应度优于原染色体x′、y′。

2.5 算法的终止条件与多样性保持策略

当算法运行到指定搜索的最大循环次数Search_Max时, 算法停止搜索, 输出结果。当算法运行Not_Improve次循环, 种群中的当前最优解未出现改进时, 引入破坏修复机制来扰动原有种群, 增强种群多样性, 提升算法寻优能力。具体方法为从种群中选出30%的染色体, 对每染色体采用类似于Destroy & Repair变异算子的方法进行破坏修复, 按10%~30%比例随机选择染色体中的点进行删除, 并保持原染色体可行, 再根据最优插入方法进行插入, 形成新的染色体。为了保证算法收敛, 在种群引入破坏修复机制时, 采取种群保优策略, 即原种群中的最优染色体始终被保留。

3 算法测试 3.1 测试环境与测试方法

本文运用BRP问题标准测试算例进行算法测试, 该算例可在网站http://www.or.unimore.it/resources/BRP/home.html下载。将测试算例按单车停靠点数量分为小规模算例(n≤50)、中等规模算例(50 < n≤100)以及大规模算例(n>100), 采用Matlab2014编程实现算法, 硬件条件为CPU(core i3, 3.1 GHz)、Rom(4 GB)。参数设置为:变异概率取0.6, 交叉概率取0.3, 种群规模为100, 最大循环次数Search_Max分别为5 000(小规模)、10 000(中规模)和20 000(大规模), Not_Improve分别为500(小规模)、1 000(中规模)和2 000(大规模), 每个算例运行10次, 取最好的解进行比较。

3.2 测试结果

在已有的BRP求解算法中, 文献[2]运用了分支定界法(B & C)、文献[4]运用了线路破坏与修复启发式算法(D & R)分别求解了该问题的标准算例, 且其测试硬件环境与本文基本相同。因此, 本文选择上述2种算法作为对比算法。表 1~表 3为3种算法计算结果与计算时间比较。其中, N/C分别代表算例的停靠点数量与运送单车的卡车额定载重量, S_i代表各算法的求解结果, CPU_i表示各算法的求解CPU消耗时间, g_B & C=(S₂-S₁)/S₂、g_D & R=(S₃-S₁)/S₃, 分别表示本文算法相较于B & C、D & R在求解质量上的提升比例, g_t_B & C=(CPU₂-CPU₁)/CPU₂、g_t_D & R=(CPU₂-CPU₁)/CPU₂, 分别为本文算法相较于B & C、D & R算法在求解时间上的节约比例。在表 1中, 对于B & C、D & R 2种算法计算时间小于2 s的情况未进行比较。

由小规模算例测试结果可以看出, 本文算法与B & C、D & R一样, 均能找到算例的最优解。本文算法的求解的平均CPU消耗为3.8 s, 比B & C的17.3 s快, 但仍慢于D & R的0.7 s。

由中等规模算例测试结果可以看出, 本文算法找到9个算例的最优解, 并且其平均求解质量虽然比B & C、D & R低8.5%与6.4%, 但求解的平均CPU消耗为36.5 s, 相较于B & C的2 309.5 s、D & R的222.4 s分别提升98.4%与83.6%。

由大规模算例测试结果可以看出, 本文算法的求解速度优势更明显, 虽然求解质量分别比B & C、D & R低69.7%与25.9%, 但求解的平均CPU消耗为217.1 s, 分别比B & C、D & R提升94.0%与77.8%。

4 结束语

BRP是共享设施再平衡调度中重要的实际应用问题, 在共享经济快速发展的背景下具有较高的研究价值。本文提出一种求解BRP的遗传算法。通过应用非代际遗传算法框架, 采用多维整数编码方法, 设计路线交叉算子和k点破坏修复变异算子, 并引入破坏修复机制来保持种群多样性。实验结果表明, 该算法对小规模算例具有良好的求解质量, 所有算例均能在4 s内找到最优解, 对于中等规模和大规模算例, 本文算法求解质量有待进一步提升, 但其运算速度相较于B & C和D & R算法具有显著优势。下一步将考虑停靠点规划布置、用户取用车习惯以及管理机构再平衡管理目标(成本或用户满意度最优)等实际需求, 设计相应的高效算法求解BRP问题。