基于地铁的地上地下闭环物流配送路径优化

2022-04-06郑长江陈宜恒沈金星

华东交通大学学报 2022年1期

郑长江，陈宜恒，沈金星

（河海大学土木与交通学院，江苏，南京， 210098）

随着社会经济的发展以及环境污染的加剧，政府和消费者对物流运输业提出了更高的要求。闭环物流正是顺应这一趋势而兴起的，它是科学高效规划物流网络的出发点，是正向物流网络与逆向物流网络的集成[1]。随着物流需求的增长，日益拥堵的城市路面交通难以保障闭环物流经济、绿色的发展，少占用地面空间的地上地下配送思路逐渐被发达国家重视[2-3]，其中基于地铁的物流配送模式，既充分利用低碳环保的地铁资源，又在成本上更具可行性，也受到学者们的关注。

日本札幌的地铁配送实验证明，小范围的地铁配送服务可以节约1/4 的货车运输[4]。Dampier等[5]研究了地铁货运的可行性和潜在问题，通过方案比选验证了该模式能有效缓解交通拥堵、减少车辆尾气排放。以上研究大都集中在配送模式的可行性分析和宏观影响评估，但基于地铁的地上地下配送模式研究需根据城市货运现状，以提高货运综合效能为目标，对配送路径和参数进行优化和分析。

Ghane 等[6]以建设费用和运输费用最小为目标对物流网络进行优化。 Eric 等[7]考虑了车辆容量、时间窗约束等，设计了一种配送路线的优化算法。汤雅连等[8]引入遗传算子和客户点分组策略，改进了蚁群算法以求解软时间窗约束下的多车型路径优化问题。Zhao 等[9]和周晓晔等[10]提出基于地铁系统在非高峰期进行物流运输，以最小运输距离为目标进行优化。周芳汀等[11-12]考虑了低碳、运输成本和客户点时间窗约束，提出以地铁网络为骨干的路径优化模型。杨婷等[13]研究了带软时间窗的地铁物流配送路径优化问题。易美等[14]利用分层分级配送思路，以建设成本、运输费用及中转服务费用最低为目标建立地下物流规划模型。以上研究都考虑了不同因素下的配送路径优化，但大多研究仅关注了传统的正向物流网络，忽略了物流链的重要环节——逆向回收，求解方案难满足时下城市闭环物流的需求。此外，大多文献针对基于单条地铁线路的配送问题进行研究，由于地铁配送货运需依靠列车运输货物，并利用地铁站完成货物转移，单线路地铁配送模式存在因上游货物转移延迟或阻塞导致货物堆积或货运中断[15]的问题。

面向区域闭环物流配送服务，设计地下地铁线网-地面货车的物流配送模式，提出考虑地铁客货共运方式的带时间窗闭环物流配送优化问题，并建立以运输成本、碳排放成本、时间窗惩罚成本、转运成本、固定成本和地铁货运运营成本为优化目标的地上地下闭环物流配送路径优化模型。还根据配送模式的地下地面分层特点，设计了基于半初始化子路径扰动策略的改进自适应遗传算法，并通过案例分析对所建立的模型和算法进行验证评估。

1 问题描述

1.1 地上地下闭环物流配送模式

针对一组分布在一定区域内需求已知，时间窗约束已知的客户点，地上地下闭环物流配送系统采用客货共运的地铁班列和轻型货车对其进行配送服务，其中客货共运的地铁班列是在不改变现行地铁发车时刻表的情况下，利用平峰时段在客运车厢后增设物流车厢的新型配送模式[15]。

但是由于客货共运地铁班列的运力限制和时段限制，所有货物由单一地铁线路运输、中转易影响到常规客运服务和物流配送效率。本文采取分层分级分区域的地上地下配送策略，以降低对常规客运的影响，提高地下配送转运效率。图1 所示为具体配送模式描述：①根据区位因素和周围交通环境，选择1，2 级地铁站承担货物中转功能，确定各2 级地铁站的配送区域；②正向物流中，利用地下网络货物从物流园依次运往1，2 级地铁站，并在2 级地铁站由货物电梯运往地面进行装卸，最终由货车运往各客户点；③逆向物流中，客户点的回收品用货车运往2 级地铁站，再由地铁运输至市郊回收。

图1 基于地铁的地上地下配送模式Fig.1 A ground-underground model based on metro network

综上，基于地铁的地上地下闭环物流配送模式假设条件如下。

1） 1 级地铁站至同一2 级地铁站的运输任务由同一线路的地铁分班次运输；

2） 1 级地铁站一次只开行一列至2 级地铁站的客货共运模式地铁，直到2 级地铁站的配送量均完成才开行下一列至另一2 级地铁站的地铁；

3）一个客户点仅允许同一辆货车服务；

4）当2 级地铁站的配送量超过单次列车容量时，需等待下一班次列车；

5）当客户点的配送量超过货车容量时，同一辆货车需返回至对应2 级地铁站以完成剩余运输任务；

6）货物由地铁专用物流车厢运输，可快速装卸；

7）地面路网各路段的行车速度是恒定的，不考虑路段内的车辆变速情况；

8）地铁的客运发车时刻表已知，且假设地铁线网的发车间隔是恒定的。

1.2 符号说明

为便于理解，现将本文用到的参数汇总如表1所示。决策变量定义如表2 所示。

表1 参数符号描述Tab.1 Notation and description for the parameters

表2 决策变量符号描述Tab.2 Notation and description for the decisive variables

1.3 数学模型

地下配送时间和地铁发车间隔f、2 级地铁站间的运输时间tij相关。由于地面配送时间易受路面交通状况影响，根据百度地图实时交通拥堵指数和祝付玲[17]的研究成果，设路面交通状况为拥挤、缓行、畅通不稳定和畅通时，货车路段平均速度V 分别为20，25，30 km/h 和40 km/h。货物配送总时长T 如式（1）所示。

为保证地铁货运不影响常规地铁客运，基于地铁的地上地下闭环物流配送模式引入地铁站配送时间窗。如果货物提前到达2 级地铁站，货物堆积在地铁站内，产生货物堆积风险成本，这与堆积的货物量和堆积时间有关；如果货物在指定时间窗内到达2 级地铁站，则不产生额外费用；当货物延迟抵达2 级地铁站时，提前到达的货车需要停靠等待，产生停靠等待的成本。

式中：M 是一个趋近于无穷大的数；Tt是可容忍的超出时长。

碳排放成本是对货车的每单位CO2排放量按照税率0.75[18]征收碳排放税。参考英国交通研究所的实载车辆碳排放计算公式[19]和任腾等[20]对车辆碳排放量的修正，设货车在路段（i，j）上运载的货物量为kij，碳排放成本Cctax如式（4）所示。

式中：α0，α1，α2，α3分别为0.98，-0.011，7.3×10-7，22.36；β 取7.5×10-5。

基于上述假设分析和实际闭环物流的配送过程，以运输成本，时间窗惩罚成本，碳排放成本，转运成本，固定成本和地铁货运运营成本的总成本W 最小化为目标，建立了基于地铁的地上地下配送路径优化目标函数如式（5），约束条件如式（6）～式（16）所示。

约束条件（6）～（10）与地下运输有关，其中：约束条件（6）保证一个2 级地铁站仅由同一地铁线路服务，约束条件（7）保证2 级地铁站间路径不连通，约束条件（8）表示一个2 级地铁站至多允许同一地铁线路额外发车一次，约束条件（9）确保同一线路地铁至多发车两次就完成运输任务，约束条件（10）保证2 级地铁站的配送量等于客户点的配货量之和。约束条件（11）～（13）与地面运输有关，其中：约束条件（11）保证一个客户点仅由一辆货车服务，约束条件（12）表示一个客户点至多允许货车返程一次，约束条件（13）确保货车至多往返一次就完成运输任务。约束条件（14）确保同一节点内无路径。约束条件（15）确保配送路径的单向性。约束条件（16）表示决策变量的属性。

2 算法设计

地上地下物流配送线路联合优化问题实质上是2E-VRP 问题，属于NP 难题，许多学者都采用遗传算法（genetic algorithm，GA）求解目标模型。但遗传算法在寻优过程中存在收敛速度慢、易早熟等问题。首先，基于配送模式分层分级分区域特点，对2级地铁站和客户点进行聚类；其次，采用改进的自适应遗传算法（adaptive genetic algorithm，AGA）提高收敛速度，并引入半初始化策略和子路径扰动策略增加算法迭代后期的种群多样性。

1）基于K-means 的聚类。地上地下物流配送路径优化问题包含多车辆分区域配送。根据2 级地铁站数Nd、客户点的配送量qi和可派遣货车数等约束条件，基于地理位置信息，利用K-means 法对配送区域进行聚类划分，并确定各2 级地铁站配送区域内的客户点。

2）编码与初始化。采取排列编码：①随机选取2 级地铁站生成Nt个序列； ②将2 级地铁站服务范围内的客户点随机排列成子路径，并插入到对应的2 级地铁站序列中；③插入1 级地铁站，生成一条染色体编码；④评估该染色体的目标值，并标注需要货车返程的节点。例如Nt=2 的配送路径为

其中1 为1 级地铁站，2-3 为2 级地铁站。地下运输顺序为先配送2 号站点，再配送3 号站点；2 级地铁站节点2 服务节点4，5，6 和8，配送完节点8后货车需返回节点2 再前往节点5，2 级地铁站节点3 服务节点7，9。

3）子路径交叉和变异。为加快种群进化速度，引进反映种群集中分散程度的参数γ=arcsin（fmin/favg），favg和fmin为当前种群的平均适应度和最优适应度；改进的交叉概率Pc和变异概率Pm如式（17）和（18）所示。当γ＜π/6 时，种群适应度较分散，应增加Pc值以快速生成新的优质解，同时降低Pm值，减小破坏优质解的概率；当γ＜π/6 时，适应度较集中、个体过于相似，需降低Pc值、提高Pm值。

式中：Pc1和Pc2为预设的交叉概率最大值和最小值，可取0.8，0.6；Pm1和Pm2为预设的变异概率最大值和最小值，可取0.1，0.01。

如图2 以概率Pc，Pm随机选择客户点子路径执行交叉和变异。执行交叉操作时，选择2 个父代染色体1 和2，随机选择一组节点序号，交换2 个染色体的对应节点，生成2 个子代染色体1 和2；执行变异操作时，针对同一编码中的客户点子路径，随机产生2 组同数目不同数的索引，找到对应节点进行翻转。

4）半初始化策略和子路径扰动策略。采取精英保留和半初始化策略以改进后期个体过于相似的问题。若新一代种群最优适应度高于历史最优值，则未更新次数的计数φ 增1；当φ 大于阈值μ，则认为迭代已陷入局部最优，此时随机选择除最优个体外的一半个体进行初始化，另一半个体进行子路径交叉变异。

为增加后期种群多样性，借鉴粒子群算法的扰动方式[21]，引入式（19）的扰动概率Pr和图2 的子路径扰动操作：①随机选择客户点i；②以所属的子路径总距离最小为目标，重排客户点i 所属的子路径；③以概率exp（－（fi-fmin）/Riter）接受新编码。

图2 子路径交叉变异扰动Fig.2 The crossover, mutation and disturbance of sub path

Pr＝pr×exp（（Ri-1）/Riter）（19）

式中：fi为扰动后的适应度；pr为预设扰动概率最小值，可取0.15；Riter为最大迭代次数；Ri为当前迭代次数。

5）改进AGA 算法流程简述。 ①生成初始种群，种群规模为S；②存储历史最优个体，收敛次数加1；③轮盘赌法选择个体，计算Pc，Pm，Pr；④若φ≤μ，以概率Pc，Pm执行子路径交叉变异；若φ＞μ，执行半初始化策略的交叉变异； ⑤若0-1 随机数r

3 实例分析

3.1 背景

根据周芳汀等[11]的地铁服务范围敏感度分析，地铁配送模式对服务范围大小不敏感，参考该文设定的100 km2服务范围，如图3 选取南京市地铁站作为1 级地铁站（节点1）和附近6 km 内为研究区域；考虑区位因素和人流量，选取5 个现有站点（节点2-3，5-7）、2 个候选的改建站点（节点4，8）作为2 级地铁站，选取20 个客户点，表3 展示了各节点经纬度转换为XY 坐标的相关信息，表4 展示了各客户点配送量、取货量和时间窗需求。

表3 节点位置Tab.3 Node location information

表4 节点基本信息Tab.4 Node specific information

图3 案例背景Fig.3 Case background

参考英国地下物流系统单位里程的总投资额为1.32 亿元[22]和地铁使用年限为30 年，设改建地铁站点的固定成本和运营成本每工作小时折旧额为500 元。根据周晓晔等[10]对地铁转运点转运时间的设置，设地上地下单位货物中转时间为0.003 min/件。结合邓红星等[23]对地面货物装卸时长的设置，设地面单位货物装卸时间为0.02 min/件。

3.2 地铁客货共线时段确定

选取1 级地铁站2016 年10 月24 日（周一）至28 日（周五）的AFC 刷卡数据，绘制如图4 的1 级地铁站到站人数时间曲线图。根据到站人数的非高峰段确定地铁客货共线运营时段为10：00～15：00，即1 级地铁站时间窗限制为[10，15]，同理各2 级地铁站的时间窗限制为[10，20]。

图4 工作日期间1 级地铁站到站人数曲线图Fig.4 The number of people arriving at Metro 1 station within a workday

3.3 讨论与分析

1）算法性能分析。取不同种群规模和最大迭代次数，分别用AGA 算法[25]（k1=k3=1，k3=k4=0.5）和本文改进AGA 算法（μ=Riter/3）求解表5 的案例1，结果如图5 所示，并与在Cplex12.8 求解器得出的精确解进行对比。

表5 案例1～6 的50 次求解结果平均值Tab.5 The average value of 50 algorithm results of Case 1 to 6

图5 迭代结果对比图Fig.5 The comparison of iteration results

可以看出改进的AGA 算法，能在有限的迭代次数内更快求得优质解，其运算时间比AGA 算法平均缩短了49.14%；此外基于半初始化和子路径扰动策略的改进AGA 算法求解的偏差小，更稳定，易求得优质解。由改进AGA 算法求得的最优配送路径如图6 所示，目标值23 174.54，具体路径如下，其中，10，13，25 为货车返程点。

图6 改进算法求解的路径优化结果Fig.6 The result of routing optimization

在同案例背景下，基于CPLEX 12.8 运算精确求得的目标值为22 978.20，即在有限的迭代次数内，改进算法求得平均最小目标值的相对误差为0.894%，平均值的误差为1.415%，该误差在可接受范围内。

2）地下网络运输因素分析。选择7 个2 级地铁站、7 辆货车，设计如表5 的案例1～6。分析可知总成本与地下运输时间、节点平均服务时间成正相关关系；从案例1～3 可知，案例1 单次列车运量小、发车频次高导致地下运输时间长，进而平均服务时间较长和总成本较高，而对比案例1，可灵活调整物流车厢数的案例3 有效减少了15.4%的地下运输时间，平均送达时间和总成本也相应减少了4.6%和3.8%；对比案例3～6 可知，增大发车间隔、减少物流车厢容量均会增加地下运输时间、平均服务时间和总成本，此时求得的配送路径具有较次的送达时效性和经济性。

3）不同资源配置策略分析。基于表5 中总成本小、送达时效性好的案例3 参数设置，设计了如表6的案例。分析可知：对比仅依靠地面运输的案例0和案例3 可知，地上地下闭环物流配送路径的碳排放量和平均服务时间分别降低了57.5%，8.1%，可见地上地下的配送模式在保证经济性的同时可提供送达时效性好，低碳环保的配送路径；由案例7～8可知，合理的货车数可以优化地面运输路径、减少碳排放量，但货车数的增加会导致服务时间和总成本的上升，总成本的平均增长率为4.1%；从案例9～10 可知，合理利用现有地铁线网完成地下地上配送可以在保证货物送达时效性的同时降低49.4%的总成本，但地铁站服务区域的缩小会导致配送方案的碳排放量上升3.5%；此外由案例11 可知，较少的客货共运地铁站点会导致货运中转时间超出站点时间窗，进而使总成本上升了66.0%，即此时货物中转影响到了地铁客运，同样也使得配送方案的碳排放量和平均服务时间增加了54.2%和7.5%，货运送达稳定性和低碳无法满足。