2016年以来，ofo、摩拜等共享单车企业异军突起，随之又涌现出7号电单车、蜜蜂等一大批共享电动车企业，颠覆了传统的出行方式，深刻地改变了人们的生活。众所周知，当共享电动车电池的电量耗尽或者低于某一阈值时，用户就难以继续使用。对此，目前共享电动车企业基本上都是采用人工换电池的方法，即运维人员实时监测电动车的电量，驾驶电池配送车辆前往各共享电动车节点取下电量不足的电池并换上已充满电的电池，然后将该电池带回仓库充电以便下次使用。

目前还没有任何有关更换共享电动车电池的过程中配送车辆路径问题的文献。实质上这是一个带软时间窗的车辆路径问题。自20世纪60年代车辆路径问题(vehicle routing problem,VRP)被提出以来，就引起了广泛的关注并被应用于多个领域^[1]。带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)是对有容量约束的车辆路径问题的延伸^[2]，在其基础上增加了时间窗约束^[3]。根据是否允许车辆抵达各节点的时间稍微偏离时间窗并对这种偏离施以惩罚^[4]，又可进一步将VRPTW分为带硬时间窗的车辆路径问题(vehicle routing problem with hard time windows,VRPHTW)和带软时间窗的车辆路径问题(vehicle routing problem with soft time windows,VRPSTW)^[5]。VRPSTW的求解方法有精确算法^[6-9]和启发式算法^[10]，由于精确算法的计算量随问题规模的扩大呈指数增长^[11]，所以现在多采用启发式算法来研究VRPSTW。Iqbal等^[12]运用改进的人工蜂群算法来解决多目标VRPSTW；Figliozzi等^[13]提出一种新的迭代路径建立与改善算法来解决VRPHTW和VRPSTW；Chiang和Russell^[14]利用混合邻域结构和先进的恢复程序改进禁忌搜索算法以解决VRPSTW；Xu等^[15]用粒子群算法求解模糊随机环境下的VRPSTW并取得了高质量的解决方案；Li等^[16]利用改进的遗传算法解决了果蔬配送中的VRPSTW，并以算例说明该方法优于传统方法。

本文提出并描述了共享电动车电池配送问题，然后考虑到企业对配送成本的要求和各节点用户对配送时间的要求，以总配送成本最小以及用户满意度最高为目标建立了一个带软时间窗的车辆路径问题模型，最后用改进遗传算法进行求解。

1 问题描述与模型构建 1.1 问题描述

共享电动车电池的配送问题实质上是带软时间窗的车辆路径问题，对该问题建立的模型描述如下：某共享电动车企业的一个电池仓库有其特定的责任区域，在某一时刻派出若干装有充满电的电池的配送车辆，沿着既定路线行驶，以更换其责任区域中电量低于某一阈值的共享电动车电池。该仓库拥有的配送车辆数量有限，且车辆的最大运载量为 $Q$ ，配送车辆均从时刻0出发依次前往各节点更换电池，节点的共享电动车数量与该节点用户需求一致，但可能其中部分共享电动车电池的电量耗尽或低于阈值从而导致车辆不可用，甚至全部都不可用。根据该时段该节点用车的历史记录，可以预测出该节点可用的共享电动车被骑完的时间，也就是配送车辆抵达该节点的最晚时间，配送车辆需要在预测的最晚时间之前抵达该节点，更换电量低于阈值的共享电动车电池，反之则会产生相应的惩罚成本，并且会导致用户满意度的降低。以总配送成本最小以及用户满意度最高为目标，为配送车辆规划恰当的路线。

为了便于分析问题，现对该模型做如下假设：

1) 除了用户将共享电动车骑走的行为，不考虑其他用户干扰；

2) 用户到达某一节点时，若有可用的共享电动车，则开始骑行，反之则直接离开，并且不会前往其他节点寻找共享电动车；

3) 各节点的共享电动车数量与该节点用户需求一致；

4) 各节点(包括仓库)之间的距离、各节点共享电动车的数量以及需更换的电池数量是已知的，并且可以预测出时间窗；

5) 每个节点都被一辆且仅一辆配送车辆访问一次。

1.2 模型构建 1.2.1 符号说明

$N$ 为责任区域内的共享电动车节点， $N = \{ {1, }$ ${2,\cdots,n} \}$ 。

${N_0}$ 为 ${N_0} = \left\{ 0 \right\} \cup N$ ，其中 $0$ 是仓库。

$I$ 为仓库拥有的配送车辆， $I = \{ 1,2,\cdots,{{i}}\} $ 。

$Q$ 为配送车辆最大运载电池数。

$c$ 为配送车辆行驶单位距离的成本。

${d_{mn}}$ 为节点 $m$ 与节点 $n$ 之间的距离。

${F_n}\left( t \right)$ 为根据历史记录建立的函数，表示从时刻 $0$ 到时间 $t$ 前往节点 $n$ 寻找共享电动车的用户数量。

${q_n}$ 为节点 $n$ 的共享电动车数量，由假设3)可知，也可用于表示节点 $n$ 的用户数。

$q_n^*$ 为节点 $n$ 需要更换的电池数量，由假设3)可知，也可用于表示若配送车辆没有及时抵达，无法在节点 $n$ 满足需求的用户数量的最大值。

${t_n}$ 为配送车辆 $i$ 到达节点 $n$ 的时间，对于仓库 $0$ 而言， ${t_n} = 0$ 。

$\left[ {0,{E_n}} \right]$ 为节点 $n$ 的时间窗，其中 ${E_n}$ 表示根据历史记录计算的该节点可用的共享电动车被骑完的时间，即 $\int {{F_n}\left( t \right){\rm{ = }}{q_n} - q_n^*} $ 时t的解。

${S_n}$ 为若节点 $n$ 的共享电动车都可用，或配送车辆在可用的共享电动车被使用完之前已抵达该节点并及时更换电池，根据历史纪录计算的该节点的共享电动车被全部使用完的时间，即 ${F_n}\left( t \right) = {q_n}$ 时t的解(忽略发生在 ${S_n}$ 之后的用户行为)。

$U\left( {{t_n}} \right)$ 为节点 $n$ 的用户满意度函数，对于某一用户而言，若有可用的共享电动车，则其满意度为1，反之，其满意度为0。根据假设2)，可以得到节点 $n$ 的用户满意度函数 $U\left( {{t_n}} \right)$ 为

$\qquad U({t_n}) = \left\{ {\begin{array}{*{20}{l}} {{q_n}},&{{t_n} \in [0,{E_n}]};\\ {2{q_n} - q_n^ * {\rm{ - }}{F_n}({t_n})},&{{t_n} \in ({E_n},{S_n})};\\ {{q_n} - q_n^ * },&{{t_n} \in [{S_n},\infty ]}{\text{。}} \end{array}} \right.$

$\alpha $ 为在 ${E_n}$ 之后到达节点 $n$ 的单位时间惩罚成本。

$\qquad {x_{mni}} = \left\{ {\begin{array}{*{20}{l}} 1,&{{\text{配送车辆}}i{\text{从节点}}m{\text{行驶到节点}}n};\\ 0,&{{\text{否则}}}{\text{。}} \end{array}} \right.$

$\qquad {y_{ni}} = \left\{ {\begin{array}{*{20}{l}} 1,&{{\text{节点}}n{\text{由车辆}}i{\text{配送}}};\\ 0,&{{\text{否则}}}{\text{。}} \end{array}} \right.$

1.2.2 建立模型

根据问题描述及符号说明，可以建立如下模型。

$\qquad \min {Z_1} = \sum\limits_{i = 1}^I {\sum\limits_{\mathop {m,n \in {N_0}}\limits_{m \ne n} } {c{d_{mn}}{x_{mni}}} } + \alpha \sum\limits_{n \in N} {\max \{ {t_n} - {E_n},0\} },\!\!\!\! $

(1)

$\qquad \max {Z_{\rm{2}}} = \frac{{\displaystyle\sum\limits_{{\rm{n}} \in N} {U({t_n})} }}{{\displaystyle\sum\limits_{{\rm{n}} \in N} {{q_n}} }}{\text{。}}$

(2)

s.t.

$\qquad \sum\limits_{n \in N} {{x_{0ni}}} {\rm{ = 1 }},\;\;\;\forall i \in I;$

(3)

$\qquad \sum\limits_{m \in N} {{x_{m0i}}} {\rm{ = 1 }},\;\;\;\forall i \in I;$

(4)

$\qquad\sum\limits_{i \in I} {{y_{ni}}} = 1{\rm{ }},\;\;\;\forall n \in N;$

(5)

$\qquad \sum\limits_{n \in N} {q_n^ * {{\rm{y}}_{ni}}} {\text{≤}} Q,\;\;\;\;\; \forall i \in I;$

(6)

$\qquad {x_{mni}},{y_{ni}} \in \{ 0,1\} ,{\rm{ }}\;\;\forall m,n \in {N_{\rm{0}}},\;\forall i \in I{\text{。}}$

(7)

目标函数(1)表示最小化总成本，具体包括运输成本和惩罚成本；目标函数(2)表示最大化用户的平均满意度；式(3)和式(4)表示配送车辆均从仓库出发，访问除仓库外的其他节点后，最终返回仓库；式(5)表示除仓库外的每个节点都有且仅有一个配送车辆为其服务；式(6)表示车辆装载容量限制；式(7)是0-1约束。

2 改进的遗传算法

遗传算法是借鉴生物学“适者生存”的思想发展起来的一种智能算法^[15]，常用于解决NP难问题^[17]。通过搜索每一代中的优秀个体，不断迭代进而逼近全局最优解，但它容易过早收敛^[18]。为了解决这一个缺点，本文采用扫描法生成初始种群并且运用基于最佳路径成本改进的交叉算子对其进行改进。

2.1 编码方式和初始种群的生成

本文采用符号编码的方式将问题的解空间转换成遗传算法的编码空间。符号编码法是指个体染色体编码串中的基因值取自一个无值含义、只有代码含义的符号集^[14]，如 $\left\{ {\left. {A,B,C\cdots} \right\}} \right.$ ，利用整数表示节点序号、顺序表示访问的顺序，例如 $\{1,2,3,4,5, 6,7,8,$ $9,10\}$ 代表依次访问节点1~10。由于不同的车辆对应不同的路径，本文不再采用传统的用“0”表示车辆的方法，而是直接利用扫描法找出整数序列和路径对应关系，并分别存储整数序列和路径，极大地提高了编程效率。

本文利用随机扫描法生成初始种群，改善了传统方法生成初始种群(随机生成)的过程中会产生大量不可行解的缺点。具体的实现方法是，随机生成一个所有用户的排列序列，然后从第一个节点进行扫描，累加扫描到的节点的需求，若该累加值不大于车辆容量，则将该节点添加到路径1中并继续扫描，否则将该节点作为路径2的第一个节点，重复上述步骤，依次可得路径2、路径3 ……直到不存在没有被分配路径的节点。

2.2 适应度函数、选择、交叉、变异操作

在本文中，适应度由每个染色体的成本函数的倒数决定，如式(8)所示。

$\qquad{f_i} = 1/\left(\sum\limits_{\scriptstyle\mathop {m,n \in {N_0}}\limits_{m \ne n} \atop } {c{d_{mn}}{x_{mni}} + \alpha \sum\limits_{n \in N} {\max \{ t - {E_n},0\} } } \right){\text{。}}$

(8)

式(8)可以计算每一个染色体的适应度函数值，这意味着成本越大，相应染色体的适应度函数值就越小。

本文采用轮盘赌选择算子，又称比例选择算子。根据它的操作过程可知，染色体的适应度越大，则其被选中的概率就越大。由此可知，染色体的成本越大，其被选中的概率就越小。

一般来说有单点交叉、双点交叉和部分匹配交叉等交叉算子，本文改进了传统的交叉算子，得到了一种新的交叉算子，称之为基于最佳成本路径的交叉算子。具体的做法是，从两个父代中分别随机选取两个路径，之后交叉地在父代中移除相关节点，得到新的“亚父代”，再之后将所移除的路径中的节点随机地插入到“亚父代”中，在满足车辆容量限制的条件下找到最佳路径成本子代。它不仅可以避免产生不可行解、提高“子代”优秀率，并且可以加快收敛速度，同时在两个父代相同的情况下仍能迭代，继续寻找最优解，一定程度上避免了“早熟”现象。

本文采用的变异算子是约束路径反转突变，首先随机选择两个突变点，然后将突变点之间的节点顺序反向排列得到新的染色体，如下所示：

$\qquad {{P1:}}1,2,\left| {3,4,5,6} \right|,7,9 \to {{P2: }}1,2,6,5,4,3,7,9{\text{。}}$

3 实验结果与分析

为了验证本文提出的算法，采用Solomon VRP问题标准测试数据集R101进行仿真测试。由于R101原始数据集是双边的时间窗问题，而本文模型中的时间窗是单边时间窗，为此需要将原始数据集中的时间窗修改成单边时间窗。修改后的数据格式见表1。

将交叉概率设置为0.85，变异概率为0.01。通过Matlab编写传统算法和本文改进的算法并分别对修改后的R101数据集进行计算，结果如图1所示。

图1中的计算结果有效地验证了本文改进的遗传算法的有效性：在达到相同的适应值时，本文改进的遗传算法所需要的迭代次数较少；在相同迭代次数下，本文改进的遗产算法可以得到更好的适应度值。因此可知本文所提出的改进遗传算法是有效的，同时本文所提出的改进遗传算法的收敛速度比传统算法快，且较容易地跳过平台阶段。

为了得到种群大小和迭代次数对改进遗传算法的影响，本文改变种群规模和迭代次数得到四组参数。之后在每组参数下，利用修改后的R101数据集进行5次仿真模拟，得到的最佳适应度值计算结果如表2所示。

从表2可以看出，当种群和迭代次数都比较小的时候，本文改进的遗传算法往往得不到最佳适应度值，随着迭代次数或者种群大小的提高，得到的最佳适应度值将提高。但当种群大小和迭代次数提高到一定的水平之后，继续增大种群大小和迭代次数对于提高最佳适应度值的帮助不大。因此在实际的应用中可以据此选择合适的种群大小和迭代次数来减少计算代价。

4 结论

针对共享电动车电池配送问题中各节点用户对时效性的要求，本文用软时间窗反映用户满意度，并考虑到企业对配送成本的要求，在此基础上建立了一个以总配送成本最小以及用户满意度最高为目标的VRPSTW模型；为应对传统遗传算法易过早收敛的缺点，本文采用扫描法和基于最佳路径成本改进的交叉算子对其进行改进，然后用算例证明本文的改进是有效的，同时有效提高了传统遗传算法的收敛速度，最后通过数值实验找出了种群大小、迭代次数与最优解之间的相关关系，在实际应用中可以据此选择合适的种群大小和迭代次数。结果表明本文共享电动车电池配送路径多目标优化模型及其求解算法是有效的，可以为共享电动车电池配送路径优化提供理论依据与实践指导。