基于地铁-货车联运的动态配送选点-路径问题

崔 瑶，周晓晔，何 亮

(1.沈阳工业大学 管理学院，辽宁 沈阳 110000；2.辽宁科技学院 管理学院，辽宁 本溪 117000；3.辽宁省交通高等专科学校 机电工程系， 辽宁 沈阳 110000)

近年来，随着电子商务的快速发展，小批量、多频次、高时效货物的动态配送需求与日俱增，企业不断推出“极速达”、“闪送”等1 h高效配送服务，来快速响应客户的配送需求，使得求解动态车辆路径问题[1](Dynamic Vehicle Routing Problem，DVRP)变得越来越复杂。传统DVRP问题仅考虑单一货车配送的路径优化问题，采用增派车辆或调度现有车辆往返来实现动态配送，配送成本较高，而且易受交通限行影响，导致货物无法按时送达，所以传统DVRP已然不适于求解目前复杂多变的动态配送问题。地铁作为公共交通工具不仅具有高频、快速、准时的特点，而且存在闲置可共享的运输资源、站点遍布城市中心、与客户需求点距离较近、不受交通限行因素影响等优势。因此，在交通物流融合的背景下，通过共享地铁网络闲置运能将货物快速送达城市中心，再由货车灵活接运实现末端配送，将公共交通工具和传统配送工具联合，发挥其各自优势，为客户提供精准、快速的配送服务，是未来发展趋势[2]。

有关DVRP方面的研究，Abdallah等[3]构建带容量约束的动态车辆路径模型，按时间段将动态车辆路径问题转化成一系列静态车辆路径问题进行求解；Armas等[4]构建带软时间窗和客户优先权约束的多车型动态车辆路径模型，并采用了生成初始路径和实时动态调整的两阶段求解策略。Chen等[5]以总成本最小化为优化目标，建立带容量和时间窗约束的动态车辆路径模型，并采用生成初始路径和按时间段定期更新路径的两阶段求解策略。葛显龙等[6]研究不同动态等级场景下，考虑动态客户需求量的两级动态车辆路径问题，并设计禁忌搜索算法求解。张文博等[7]构建动态需求下带软时间窗的车辆路径模型，并设计启发式算法求解。张景玲等[8]提出一种动态需求下跨区域多配送中心沿途补货策略，构建两阶段车辆路径优化模型，并设计自适应免疫量子进化算法求解。上述文献为动态配送问题提供了多种解决方案，具有一定的借鉴意义，但都仅限于采用单一货车配送方式，对于多种运输工具联合运输的动态配送问题还缺少相应研究。

关于地铁和货车联合运输配送方面的研究，Trentini等[9]提出使用公共交通实现客货混运，共享公共资源，包括共享公共汽车、地铁、地铁站储物柜等。Masson等[10]提出共享公共交通资源实现货物配送，以提高公共交通利用率。Chen等[11]提出利用城市轨道交通多余运能开展客货混运的观点。Masson等[12]提出白天非客运高峰实施客货混运，夜晚开通货运专列的想法。Kikuta等[13]首次对城市地铁发展物流进行实证研究，提出札幌市利用地铁与卡车联合运输将货物从郊区配送到城市中心。周芳汀等[14]研究地铁和货车联合配送选点-路径问题，并设计改进递归粒度算法进行求解。周晓晔等[15]研究利用地铁非高峰时段剩余运能运输货物，构建带时间窗的地铁和货车联合运输配送路径优化模型，并设计改进的自适应遗传算法进行求解。上述文献仅从静态的角度研究地铁货运服务网络问题，缺少对动态服务网络的研究，忽略了地铁高频、快速的优势。

关于动态服务网络设计方面，本文研究的城市地铁-货车联运动态服务网络，解决地铁的动态选点以及地铁-货车协同配送路径的集成优化问题，此类问题研究较少。Andersen等[16]以货物运输时间最短为目标，考虑列车换线情况，构建多列车协同优化的动态服务网络设计模型。王保华等[17]研究了考虑列车开行时段、编组周转等约束的铁路动态货运服务网络设计优化模型，解决列车利用率问题。Ahmadi等[18]研究动态服务网络中车辆动态随机位置的定位路径集成问题。Marinakis等[19]构建以成本最小化为目标的随机需求选址-路径模型，并设计混合算法求解。蒋海青等[20]设计一种四阶段混合量子差分进化算法解决预优化和实时优化的两阶段选址-路径问题。上述文献虽然提出了诸多可借鉴的方法，但是未考虑地铁和货车联合运输的特征。与一般动态服务网络相比，本文研究设计基于地铁-货车的联运动态服务网络，将地铁选点与货车路径的优化进行集成，需要综合考虑地铁与货车的时空约束、相对位置和速度、客户时间窗等因素，优化过程更为复杂。

综上所述，本文对基于地铁和货车联合运输的动态配送选点-路径优化问题开展研究，主要贡献及创新点是：①利用地铁共享的运输资源，从联合运输的角度研究动态配送问题，以联合运输配送成本最小为目标，构建地铁转运点选择、货车调度及接运配送路径的两阶段动态整体优化模型；②设计一种以改进遗传算法作为外层模块，以改进蚁群算法作为内层模块，通过内外层信息交互求解问题的集成算法；③针对模型特点，根据不同种类的节点特征，对外层遗传算法的编码结构进行重新设计，并改进交叉变异操作；根据货车先接后送原则，改进内层蚁群算法的编码方式和概率选择操作。最后设计仿真算例验证模型和算法的合理性和有效性。

1 问题描述

本文通过地铁和货车的联合运输，完成动态需求的配送任务，在满足地铁共享剩余运能和货车最大容量的前提下，按照客户时间窗需求将货物从一个临近地铁始发站的配送中心通过地铁网络运送到城市中心的转运点，再从转运点通过货车运送到客户手中。为充分利用现有货车，需要考虑地铁与接运货车的有效协同：一是如何利用地铁的剩余空间。通过分析历史客流数据可得线路l不同车次r途经站点的最大客流量，根据悲观主义决策准则计算lr的最小剩余运能Qlr作为容量上限。对当前所有客户需求，以不超过地铁容量上限为依据，按照所属区域邻近，时间窗有序原则依次上车，超出容量限制的需求按相同原则分配到下一车次，同时对接运货车的货物进行预优化，以实现地铁与货车的空间协同。二是如何实现与货车在时间上的衔接。由于地铁相对速度快，为保证货车在配送过程中的连续性，地铁运输的货物需先于货车到达转运点；同时货物在转运点的允许等待时间要满足客户的最晚送达时间。

初始阶段，货车在转运点等待接运货物，按最小成本规划初始地铁路径、转运点以及货车接运路径。动态阶段，时刻t更新需求，将动态问题转化为t时刻的静态问题，利用t时刻现有货车到转运点接运，对于新增和剩余需求规划地铁转运点、接运货车以及配送路径，对于货车未接运需求重新规划接运货车及配送路径，对于货车已接运未送达需求继续由原货车配送，仅重新规划配送路径。因此，如何选择转运点、调度货车协同接运，并优化货车接运配送路径，使联合运输配送成本最小是本文研究的关键问题。

初始阶段，货物从配送中心O出发经地铁，在转运点A、B、C中转，由货车v1、v2、v3接运配送，路径为O-A-1-2-3，O-B-4-5-6，O-C-7-8-9-10，见图1。假定t时刻，产生新增需求11、12，首先确定关键点位置，货车正在前往或正在服务(包括中转服务、配送服务)的节点为关键点(可以是地铁转运点或客户点)，并将其作为t时刻货车出发点，然后对未完成客户、新增客户以及开放转运点C、D、E统一重新规划路径：2-(O)D-11-3、5-6-C-7-8、C-9-(O)E-12-10，见图2。

图1 初始阶段地铁-货车联运配送网络选点-路径示意图

图2 动态阶段地铁-货车联运配送网络选点-路径示意图

2 模型构建

2.1 假设条件

(1) 地铁(开行方案、线路、转运点位置坐标)和客户需求(客户位置坐标、需求量、时间窗)的相关数据已知。

(2) 配送中心设在地铁始发站，且配送中心到地铁始发站的距离忽略不计。

(3) 转运点可被用于暂存和转运货物。

(4) 地铁线路站间行驶时间固定，且换线时间固定。

(5) 货物中转作业时间和客户服务时间固定。

(6)t时刻任意两个开放转运点之间无货车路径直接相连。

(7) 货车无需返回转运点，路径开放。

(8) 地铁线路运输货物不会影响客运服务质量。

2.2 模型中用到的参数和变量

2.3 模型建立

建立“初始阶段(t=0)+动态阶段(t≠0)”两阶段选点-路径整体优化模型

(1)

s.t.

(2)

(3)

(4)

(5)

∀j∈Va(t)∪Vb(t)

(6)

(7)

(8)

(9)

v∈Vv(t)j∈Vu(t)t≠0

(10)

v∈Vv(t)o∈Voi∈Vg(t)

k∈Vk(t)∪Vabg(t)j∈Vu(t)t≠0

(11)

(12)

i∈Vg(t)j∈Vb(t)

(13)

v∈Vv(t)o∈Voi∈Vg(t)j∈Va(t)∪Vb(t)

(14)

∀v∈Vv(t)j∈Va(t)∪Vb(t)i∈Vabg(t)

(15)

(16)

Tij=dij/v∀i,j∈Vabg(t)i≠j

(17)

(18)

i∈Vg(t)j∈Vb(t)

(19)

(20)

ni∈{0,1} ∀i∈Vg(t)

在参加这次哈佛管理课程之后，我认识到了这种现象的出现固然与公司的体系与氛围有关，但如果双方都有着足够的沟通意识和技巧，对此类问题会有极大的促进作用。

(21)

3 算法设计

本文研究的是动态问题，因此采用“初始优化阶段+动态优化阶段”的两阶段动态调度策略求解[17]，同时依据地铁发车间隔设置新增客户的监测系统，以判断m=m+1时刻是否进行动态优化，见图3。

图3 两阶段动态调度策略流程

初始优化阶段，首先，将具有相近空间和时间分布的客户进行聚类，实现不同配送区域的时空划分，并将各配送区域所覆盖的地铁出口作为备选转运点。其次，在生成初始配送方案阶段，采用Mark-Sweep算法确定开放转运点：①根据距离最短原则，将客户分配给各备选转运点，获得初始转运点和客户分配结果；②确定配送中心到初始转运点的地铁最短线路；③依据地铁最短线路的共享剩余运能和客户时间窗优先原则，确定转运点和客户点，同时进行标记；④整理不满足地铁共享剩余运能的客户，清除标记点并返回步骤①重新分配，直到找到符合要求的转运点；对确定的转运点进行开放操作。最后，对分配到开放转运点的客户采用带时间窗和车容量约束的蚁群算法获得初始配送路径，并计算目标函数值。

动态优化阶段，结合问题研究特征，设计双层启发式集成算法进行求解，遗传算法具有良好的收敛性和全局搜索能力，蚁群算法具有良好的鲁棒性和局部寻优能力，将两种算法的优点相结合[21]，使其适应于求解基于地铁-货车联运的选点-路径的整体优化问题，本文算法流程见图4。首先，将改进的遗传算法作为外层模块，根据t时刻确定新增客户的时空分布、所属配送区域，以及所属区域范围内执行任务的货车的关键位置和未送完客户点等信息；为客户随机分配执行货车和备选转运点，生成动态阶段选点-分配染色体和初始种群。然后，将外层染色体信息传递给内层模块，依据染色体的客户-转运点-货车分配信息，设计改进的蚁群算法对接运货车进行多转运点接送路径优化，计算配送成本，再反馈给外层模块，并与地铁运输成本相加，即为染色体的适应度值。最后，进行遗传操作，直到达到终止条件。

图4 本文算法流程

3.1 外层遗传算法的选点-分配编码

由于涉及转运点和接运货车的分配，采用二维矩阵编码方式。其中，列为客户点，行为转运点分配、接运货车选择。例如，新增客户①～⑤，开放转运点为A、B、C，t时刻执行任务车辆为v1和v2，新增车辆v3和v4，编码见图5。车辆v1已接运客户1、3，到转运点A接客户4、6、①和②；车辆v2已接运客户2，到转运点B接客户5和④；车辆v3到转运点B接客户③；车辆v4到转运点C接客户⑤；为保证初始种群中染色体的可行性，需要判断是否满足约束条件，如果不满足则重新生成，直到满足约束条件为止。

图5 选点-分配矩阵编码结构

3.2 适应度计算

针对联合运输多转运点接送特征，改进传统蚁群算法的编码方式和概率选择操作，求解货车最优配送路径，并获得货车配送成本，再与地铁运输成本相加，最终获得染色体的适应度值，适应度值越小被选择的概率越大。

3.3 内层蚁群算法的改进

采用键值对编码形式，v为节点，ω为来源点。接收外层传输信息并构造货车路径的解，路径节点由新增客户点、开放转运点、关键节点和未送完客户点4部分构成，其中转运点由字母表示，其他节点由自然数表示。针对多转运点接送特征，需为客户节点定义来源点，在访问客户节点时必须先访问其来源点，这样才能表达出货物先接后送的情况；客户节点的来源点定义为对应转运点，如果编码结构中不存在客户节点来源点，则将其来源点替换成关键节点，转运点的来源点定义为关键节点，货车只能从关键节点出发。如车辆v1：<3,3*>→<1,3*>→→<4,3*>→<6,3*>→<②,B>→<①,B>，其中关键节点3*，未送完客户点1、4、6的来源点是A，由于编码中不存在A，所以转换为3*，开放转运点B的来源点是O，同理转换为3*；新增客户点①、②的来源点是B，见图6。

图6 键值对编码结构和多点接送概率选择操作示意

传统蚁群算法采用Tabu表节点的顺序记录路径，Tabu表中的节点是按照选择概率对待访问节点集合Unvisited(k)中元素随机获取，由于本文考虑先接后送的情况，在节点选择时受Tabu表中来源点的影响，可能存在不可行路径，因此本文对蚁群算法的概率选择操作进行如下改进：

(22)

δ(i,j)=dik+dkj-dij-P

(23)

P=ψmax(Ei-hi,0)+ζmax(hi-Fi,0)

(24)

改进编码结构与概率选择操作后的算法过程伪代码如下：

M=50； ∥初始化种群规模

form=1:M∥种群循环

Tabu(m)←keynode; ∥初始化禁忌表，从关键节点出发

whileUnvisited(m)≠∅; do

fori=1:size(Unvisited(m)) ∥遍历待访问节点集合

ifUnvisited(i)(ω) inTabu(m) then ∥判断节点来源点已存在

J(m)←Unvisited(i); ∥生成可访问节点集合

End

End

fori=1:size(J(m)) ∥遍历可访问节点集合

p(J(m),i)=式(22); ∥节点选择概率

Tabu(m)←j=find(p(J(m),i)>rand);∥选定下一节，并将其加入禁忌表

End

Unvisited(j)=∅; ∥待访问表中删除选定节点

End

End

returnTabu(best); ∥输出最优解

3.4 遗传操作

(1)选择算子。采用轮盘赌选择和精英保留相结合的选择策略。

(2)截取掩码交叉算子。采用掩码形式的交叉操作算子，首先依据选择概率在初始种群中选取两条父代染色体，然后截取参与遗传操作基因段，按截取部分生成随机二维结构的0-1掩码矩阵，其他位置用-1替代，不进行交叉操作。在交叉过程中，如果掩码对应位置为1，则从对应父代染色体中取得该位置基因；若掩码对应位置为0，则从另一父代染色体取得该位置基因[22]。检验子代染色体是否满足约束条件，若不满足则删除，见图7。

图7 截取掩码交叉操作示意图

(3)截取掩码变异算子。依据变异概率选择一条染色体；然后截取参与遗传操作基因段，按截取部分随机产生两个自然数索引k1和k2，从染色体中找到对应k1位置基因，从备选转运点中找到对应k2位置元素，如果相等，则重新生成索引，否则进行替换，形成新的子代变异染色体。对变异后的染色体进行约束条件检验，如不符合则删除。

(4)种群扩充机制。为保证子代种群与原种群具有相同数量个体，实现对优秀个体的保护，同时保持种群的多样性，从外部种群随机挑选可行个体补充到子代中。

(5)终止条件。最小适应度值和平均适应度值趋于稳定或达到最大迭代次数时，运算终止，输出最优解。

4 算例分析

4.1 算例数据及结果分析

以某市地铁网络货物运输为例，分析某日历史客流数据，得到地铁线路各车次最小剩余空间，见图8，取第25次列车为开始时刻，地铁车次行车间隔7 min。根据客户时空聚类划分配送区域，当前配送子区域服务范围在(36.98,77.68)，(46.18,85.19)经纬度之间，该区域经过4条地铁线路，分别是1号线、2号线、9号线、10号线，备选转运点(地铁站点)有12个，配送中心位置为O(48.89,71.39)。

图8 某日地铁线路各车次最小剩余空间

表1 初始客户信息

表2 地铁运行时间和距离

利用Mark-Sweep算法和蚁群算法对初始阶段的地铁-货车联运动态配送选点-路径模型进行优化求解，产生初始配送方案，见图9、表3。

表3 初始配送方案

图9 初始选点-路径

动态优化阶段，取t=35时刻作为动态需求更新时刻，此时有10个新增客户产生，客户信息见表4，配送网络关键节点集合为{17,13,7,16,10}，配送网络中货车在关键点出发时的剩余容量为{3,4,2,10,8}，货车未完成客户的集合为{{6,20};{1,9,15};{5,11,14,19};∅;{2}}；未出地铁客户集合{4,3,18}，根据当前已知信息对动态配送网络进行优化，利用集成算法对t时刻的联合运输配送选点-路径模型进行求解，并产生t时刻的配送方案，见表5、图10。

表4 新增客户信息

表5 t时刻的配送方案

图10 动态阶段选点-路径

从动态配送方案中可以看出，采用地铁-货车联运的动态配送成本和传统货车动态配送成本相比，减少了18.44%，原因在于：①本文利用共享的城市地铁网络运输货物，减少了货车的数量；②动态客户需求通过地铁到达开放转运点，利用现有执行车辆到相应转运点实现短距离接运，无需返回配送中心取货或重新派车配送，节省了车辆运输距离和车辆数量。联合运输成本中地铁的运输成本略高，这是由于地铁线路固定导致运输距离稍大于传统货车，但是通过地铁可将货物快速送达指定转运点，实现地铁与货车的精准衔接，提高配送时效，在t=98时刻所有客户全部完成配送，符合动态客户的高时效需求，进一步说明采用基于地铁和货车联运配送模式更适于动态配送情景。

4.2 不同规模算例结果分析

为了讨论本文算法对地铁和货车联运的动态配送选点-路径问题的适用性，对不同问题规模的算例采用该算法进行求解分析，仿真计算结果对比见表6。

表6 仿真计算结果对比分析

在相同时刻对不同规模的动态客户进行分析可以看出，动态客户数量小于50时，算法的稳定性较高，可得出较好的优化结果；当问题规模增大时，最优解的搜索成功率下降，并且计算时间和迭代次数较长，主要是因为该集成算法的时间复杂度为O(n5)，随着动态客户节点数的增加，计算规模成5次方增长。因此，本文所提出的集成算法适用于求解中小规模动态问题，并且全局搜索能力强。

4.3 算法性能分析

与禁忌搜索(TS)和遗传算法(GA)进行对比，验证本文算法对地铁和货车联运的动态配送选点-路径问题的求解效果见图11，算法性能对比见表7。

图11 算法收敛图比较

表7 本文算法与TS和GA的算法性能对比

通过比较分析，本文算法的搜索成功率较高，能够获得较好满意解。对于TS算法求解，虽然在收敛速度和计算时间方面占有优势，但容易陷入局部最优，解的质量不高，而且该算法的搜索成功概率较低。对于GA算法求解，虽然同样可以搜索到较好满意解，但在搜索成功率、计算时间等方面与本文算法相比结果较差。这是因为本文算法对内层蚁群算法的概率选择操作进行了改进，保证了解的可行性，最大程度地缩小了搜索空间，提高算法运行效率和精确度，但本文算法为获取全局解以及外层遗传算法的多样性，在收敛速度和计算时间方面还需进一步提高。

5 结论

本文对共享公共交通工具和传统配送工具联合运输的动态配送问题进行了研究，在考虑地铁共享剩余运能、货车容量、客户服务时间窗、多转运点接送等因素基础上，建立了两阶段动态整体优化模型；为了提高求解效率，提出了双层启发式集成算法，外层遗传算法改进了截取掩码交叉变异算子，解决了转运点、货车选择问题，同时保证了解的多样性；内层蚁群算法改进了键值对编码结构和多点接送概率选择操作，优化了接运配送路径。设计仿真算例验证了模型和算法的有效性，与目前传统货车动态配送模式进行了比较，研究表明在实际中当高时效动态客户需求产生时，应用本文所提出的数学模型进行处理比传统动态配送模式能够更快速、精准的响应动态需求，同时可以有效降低整体配送成本，是DVRP理论的扩展，也是一种共享型经济模式的体现，对指导实际应用具有一定的理论意义。同时地铁作为客运交通工具，运送货物可通过专用带轮货箱、专用安检通道、设置隔仓、隔离卡扣等技术手段减少对乘客的影响。本文仅考虑新增需求的地铁和货车联运动态配送问题，没有考虑需求变更、取消需求等情况。此类问题对基于地铁-货车联运的动态配送问题的研究必不可少，是下一步需要研究的内容。