基于地铁—货车联运的物流配送路径优化

周晓晔，崔 瑶*，2，何 亮，马小云，王思聪

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

0 引 言

2019年我国快递年业务量突破630亿件.货运需求的大幅增长，引起道路资源与货物运输的不平衡，使交通问题日益严重，影响城市配送服务水平和效率.传统货车配送存在延误高、空驶率高、环境污染等问题，故学者提出一种新型配送模式——地铁配送[1].地铁具有快速，低污染，没有运输交叉矛盾等优势，通过地铁与货车联合运输，将地铁融入末端运输网络，不仅提高了货物配送效率，还解决了城市道路拥堵引起环境污染问题，符合绿色物流发展理念.

J.C.Rijssenbrij 等[2]提出利用城市轨道交通多余运能开展客货混运的观点.Masson 等[3-4]提出白天非客运高峰实施客货混运，夜晚开通货运专列的想法.谭寅亮等[5]分析了城市轨道交通客运的时空不均衡性，提出利用轨道交通客流低谷时段实施物流快运的构想.Yubo L.等[6]估算了北京地铁闲置时段的运力和车站改造成本.以上研究论证了非高峰时段利用地铁剩余运能开展货物运输的可行性，但仅从地铁角度分析，未考虑地铁与其他运输工具的联合运输问题.针对地铁与货车联运问题的研究较少：杨婷等[7]研究了带软时间窗的地铁网络路径优化问题，利用地铁客货共线形式实现地铁与货车的联合运输；周芳汀等[8]研究了地铁货运专列与配送车辆的联合运输，构建了带时间窗的配送网络路径优化模型；但均未考虑地铁实际开行方案及地铁服务能力的约束.

综上，利用地铁非高峰时段剩余运力开展货物运输，优化地铁与货车联运路径具有现实意义.本文在不改变地铁运行方案的前提下，考虑地铁时空约束对联运路径优化的影响，利用地铁列车时刻表信息界定配送时间窗限制；考虑地铁剩余运能、货车容量、最大行驶距离、客户服务时间窗等限制条件，以配送距离最短为优化目标，构建基于地铁—货车联运的物流配送路径优化模型.

1 模型构建

1.1 问题描述

分析历史客流数据，得到非高峰时段地铁各车次列车的剩余运能，根据每趟列车剩余运力和客户时间窗安排货物运输.紧邻地铁口的配送中心将货物运到地铁进站口，第三方物流公司按照地铁不同车次载货量调配货车提前到达各出货站点接运，并按照客户时间窗要求准时送达，使配送距离最短，完成配送后，货车直接返回车场.地铁线路和列车时刻表，地铁进出货站点和客户位置坐标，客户需求量和时间窗均已知.

1.2 假设条件

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

(2)非高峰时段所有车次均能载货，每趟车次货运量不能超过地铁剩余运能限制.

(3) 地铁各出货站点出货量不能超过接运货车最大载重量.

(4)货物中转作业时间固定.

(5)不考虑地铁的存储功能，货物到站后直接装车配送.

(6)货车完成配送后不返回地铁出货站点，且载货能力固定.

(7) 货物由地铁专用货箱统一运输，可快速装卸.

1.3 符号说明

(1)参数描述.

V为配送中心d的集合，d∈V；K为地铁站点c的集合，c∈K；L为地铁出货站点f的集合，f∈L，L⊂K；C为出货站点f所需配送客户if，jf的集合，if,jf∈C；R为在非高峰时段α地铁列车班次rα的集合，rα∈R；G为货车v的集合，v∈G；W为非高峰时段α的集合，α∈W；为第rα次列车由配送中心d到出货站点f的行驶时间为货车v到达出货站点f的时刻；Qv为货车v的容量；Qrα为非高峰时段α地铁列车班次rα的剩余运能；Sjf为服务客户jf的时间；tf,jf为地铁出货站点f到客户jf的行驶时间；tif,jf为末端配送路径客户if到客户jf的行驶时间；dif,jf为末端配送路径客户if到客户jf的行驶距离；qjf为客户jf的需求量；tjf为货车开始服务客户jf的时间；If为货物在出货站点f所需的转运时间；[Ejf,Fjf]为客户服务时间窗，Ejf为最早开始服务时间，Fjf为客户最晚开始服务时间；为第rα次列车从配送中心d到出货站点f的出发时刻；D为货车最大行驶距离；A为地铁平均行车速度；B为货车平均行驶速度；M为一个大的正整数.

(2)决策变量.

表示从客户if到客户jf由货车v提供服务时，取值为1，否则为0；表示货物由配送中心d到出货站点f通过第rα次列车运送给客户jf时，取值为1，否则为0.

1.4 模型建立

式(1)为目标函数，表示地铁配送和货车配送总距离最短；式(2)表示每辆车对每个客户只能访问一次，且客户需求不可拆分；式(3)表示货车负载限制；式(4)表示货车最大行驶距离约束；式(5)表示非高峰时段地铁存在剩余运能，则用地铁进行运货；式(6)表示地铁第rα次列车的剩余运能满足客户需求；式(7)表示货车在第rα次列车到站前到达出货站点；式(8)表示货物从配送中心到客户jf的最早到达时间限制；式(9)表示客户if，jf在时间窗内接受服务；式(10)和式(11)表示二进制决策变量.

2 算法设计

地铁—货车联运物流配送路径优化问题属于NP难题，传统精确算法难以快速求解，故结合地铁配送路径特点采用改进的自适应遗传算法求解.

(1)编 码.

采用多维不等长数组编码方式，由字母与自然数组成.假设A、B、C为出货站点，1～11为客户，利用元胞数组元素多样性、多维度特征，随机生成一条染色体编码，如图1 所示.配送路径分别是A→9→3，B→10→4→6→7→11，C→8→2→5→1.

图1 染色体编码Fig.1 Chromosomal coding

(2)解 码.

为保证多维不等长数组编码索引的一致性，进行解码操作，如图2 所示.①将染色体按支路拆分，转换成多个基因段；②将字母编码对应放入各行基因段最后，并在客户总数基础上递增.

图2 染色体解码规则Fig.2 Chromosome decoding rules

(3)初始化种群.

地铁配送路径优化问题可看作分区域开放式路径优化问题[9]，按客户到各出货站点距离远近划分配送区域，各区域内的客户按时间窗和地理位置进行配送.初始化种群流程如图3 所示.第1 阶段依据第rα次列车能够提供服务的时间范围，对不同时间窗客户进行聚类；第2阶段依据地铁剩余运能确定第rα次列车的客户需求；第3阶段通过扫描算法产生初始种群.

(4)适应度函数.

本文目标函数为配送距离最短，故适应度函数为目标函数值的倒数，适应度函数值越大，染色体越优.

图3 初始化种群流程图Fig.3 Initial population flowchart

(5)遗传算子.

①选择算子.计算种群个体适应值，适应值越大被选中的概率越大，采用轮盘赌选择和精英保留相结合策略.首先，保留适应值最大的个体，替换子代适应值最差个体.其次，采用轮盘赌选择父代个体，交叉与变异的概率通过自适应调整策略[10]计算获取.

②交叉算子.依据自适应交叉概率，选择两个父代染色体I和II进行解码操作，对拆分出的基因段[a1(n-1),a1n]和[b1(n-1),b1n]，[a22]和[b22]，[a31,a32]和[b31,b32]按照映射法交叉，重组形成子代染色体I*和II*.检验子代染色体是否满足约束条件，若不满足则删除.采用改进部分匹配交叉法避免破坏优秀基因串，如图4所示.

图4 交叉示意图Fig.4 Crossover diagram

③变异算子.依据自适应变异概率，选择一条染色体；随机产生两个不相等的自然数索引k1和k2，找到对应基因.若基因为各基因段最后一个基因，则重新生成；否则，交换位置，形成新的子代变异染色体.对变异后的染色体进行约束条件检验，如不符合则删除.

④种群扩充机制.为保证子代种群与原种群具有相同数量个体，实现对优秀个体的保护，同时保持种群的多样性，从外部种群挑选适应值大的个体补充到子代中.

(6)终止条件.

最大适应度值和平均适应度值趋于稳定或达到最大迭代次数时，运算终止，输出最优解.

3 算例分析

3.1 算例数据

以某市地铁2号线下行方向作为研究对象，行车间隔10 min，某工作日非高峰时段为：05:30-06:30，09:00-17:00，20:00-23:00.分析历史客流数据，得到当天非高峰时段各车次剩余运能，最多可服务3 000～3 500 个客户，如图5 所示.客户时间窗在[06:00，24:00]范围内服从均匀分布，时间窗周期为60 min.配送中心、出货站点及客户点的位置坐标通过百度地图获得，客户地理位置服从均匀分布.出货站点为工业展览馆、岐山路、医学院.配送中心到各出货站点的距离和运行时间分别为：工业展览馆9.2 km，16 min；岐山路15.3 km，30 min；医学院22.9 km，44 min.货车平均行驶速度为15 km/h，地铁平均行车速度为60 km/h，货车最大行驶距离为65 km，转运时间为5 min，客户服务时间为1 min.

3.2 结果分析

计算获得每趟列车的服务客户，各车次计算模型相同，故以09:30 发车的第25 次列车为例，服务客户信息如表1所示.

图5 某工作日非高峰时段地铁各车次剩余运能Fig.5 Remaining capacity of each train in non-traffic peak time of a workday

表1 配送客户信息Table 1 Distribution customer information

根据模型和算法，优化20位客户配送路径，对比分析地铁—货车联合配送与货车单独配送两种模式，如表2和表3所示.

表2 地铁—货车联合配送方案Table 2 Subway-freight truck intermodal distribution plan

表3 货车配送方案Table 3 Freight truck distribution plan

由表2 和表3 可知：地铁—货车联合配送，配送总距离126 km，在用户时间窗内全部送达；货车配送，3辆货车同时从○出发，总距离为160 km，未按时送达客户数9个；地铁—货车联合配送距离节省34 km，利用地铁高准时性配送大幅度提高客户满意度；实现客户需求与各出货站点最优匹配，确定了各出货站点的出货量.两种不同方式的配送路径如图6和图7所示.

图6 地铁—货车联合配送路径Fig.6 Subway-freight truck intermodal distribution route

图7 货车配送路径Fig.7 Freight truck distribution route

3.3 算法性能分析

与迭代局部搜索算法进行对比，验证本文算法对地铁—货车联合配送路径问题的求解效果，如图8和图9所示，计算结果如表4所示.

图8 迭代局部搜索算法Fig.8 Iterative local search algorithm

图9 改进的遗传算法Fig.9 Improved genetic algorithm

通过比较分析，迭代局部搜索算法收敛速度较快，但配送总距离相对较长.本文通过编码方式的创新，初始化种群的设置和交叉操作的改进，使改进的自适应遗传算法不仅运行时间短，计算效率高，而且能够获得较好的最优解，验证了算法的有效性.

表4 计算结果对比分析Table 4 Comparison and analysis of calculation results

4 结 论

地铁—货车联合配送是一种新型城市配送模式，利用地铁非高峰时段剩余运能开展货物运输更符合实际.为适应地铁和货车联合配送特征，本文考虑地铁时空因素，建立联合配送优化模型，改进自适应遗传算法求解.结果表明，地铁—货车联合配送能够为客户提供更精准的配送服务，比货车单独配送效率更高，对指导实际应用具有一定的理论意义.

本文仅研究了单条地铁线路货物运输，没有考虑整个地铁配送网络，以及与干线运输的衔接配合，这些问题对地铁配送系统整体性研究是必不可少的，为下一步研究方向.