郭军华，宋星雨

(华东交通大学 交通运输工程学院，江西 南昌 330013)

0 引言

由于高速铁路的特性，高铁快运的开通满足了客户对高时效、高附加值的快运运输需求。但高铁快运的末端配送还存在运输成本高、配送效率低等问题[1]，“最后一公里”瓶颈依然存在。为打破瓶颈，提升高铁快运在物流市场的竞争力，提出了适用于城市内存在多个高铁站的高铁货运专列“去配送中心”配送模式[2]，但此模式还需要根据高铁快运现阶段的发展研究，对其进一步优化完善，从而提高普适性。

在对高铁快运现阶段研究中发现，高铁快运的发展给传统的铁路运输带来了转机，加速了铁路货运物流的现代化进程[3]。为研究货运对客运系统的影响，学者们在旅客列车系统中添加了货物列车的数学模型[4]，并发现在现有的客运系统中进行客货混运能提高列车利用率且仅小幅提高边际运行成本[5]。目前，随着高铁快运量的增加与服务效率标准的提升，现有的网点中转再配送方式，增加了货物的运输成本，延长了快递周转时间，无法满足灵活化的市场需求；国内外学者先后提出提高高铁快运核心竞争力，关键是完善高铁快运“最后一公里”的配送服务[6-7]。车辆路径规划作为“最后一公里”问题的研究热点，主要以配送总成本和总时间最小为目标[8-10]，考虑货物时间窗、车辆因素构建车辆路径规划模型[11-12]。

因此，将高铁快运客货协同运输和城市末端配送相结合，并提出了一种“去配送中心”的高铁快运城市末端配送方式，即配送货车(以下简称“货车”)将高铁站的货物不经过货物配送中心直接配送到城市末端物流收发点。基于高铁运行时刻，以配送时间和成本为目标，综合考虑货物分配、车辆配送路径和货物运输时间等约束，构建高铁快运末端配送模型；设计改进遗传算法对模型进行求解，从而获得最优的高铁快运末端配送方案。

1 问题描述与建模

1.1 问题描述

针对高铁快运末端配送展开研究，货物装载于高铁始发站，利用现有高铁快运客货协同的运输方式，至目标高铁站进行卸货；根据高铁到站时间和到站货物量，定时派出货车在高铁站装载货物，不经货物配送中心中转，直接配送至城市末端各物流收发点以满足货物配送时效要求，高铁快运的城市配送流程如图1 所示。货车须在物流收发点的收货时间窗内进行服务，否则会产生惩罚成本，完成所有物流收发点服务的货车必须返回高铁站。

图1 高铁快运的城市配送流程Fig.1 Distribution process of high speed rail express in city

1.2 模型假设

为简化模型，特做出以下假设。

（1）高铁站没有储存功能，货物到站后需要立即分拣并装入货车[2]；

（2）所有货车均采用同一种车型，其荷载能力固定[2]；

（3）不考虑高铁列车晚点，即高铁到站时间是固定的，且不考虑货车在行驶过程中道路环境的突发状况[13]；

（4）高铁站和各物流收发点的位置坐标已知，物流收发点的货物需求和收货时间窗已知。

模型中的具体符号表示如表1所示。

表1 符号表示Tab.1 Symbolic representation

1.3 模型建立

在车辆路径规划中，在保证配送成本最小的同时也要缩短配送时间，因此模型目标函数在总成本中主要考虑货车的行驶距离、使用成本和惩罚成本，在总配送时间中考虑货车在途时间和服务时间，其计算公式如下。

模型需要满足货车载重约束、货车到达目的地的时间约束，货车路线的唯一性等约束条件，具体约束条件如下。

（1）配送第n批货物时使用货车的总数量|K|，可表示为

（2）货车k装载货物的容量限制，可表示为

（3）货车k超载的惩罚成本，可表示为

（4）货车k对第n批货物的各物流收发点i有且仅能到达一次，可表示为

（5）配送第n批货物时，物流收发点i完成配送的时间等于货车k离开的时间，可表示为

（6）为消除货车路线中出现子回路的情况，将其约束为

（7）配送第n批货物的货车k到达物流收发点i的配送时间约束，可表示为

（8）货车k在配送第n批货物时，不在时间窗内配送将产生的惩罚成本，可表示为

模型为总运输成本和时间最小的双目标模型，为了方便求解需将双目标转化为单目标问题。通过把运输总时间进行阈值划分并给定相应的时间成本系数，将运输时间转化为运输成本，利用线性求和的方式完成多目标模型转化为单目标模型。因此，按照时间等级的成本函数转化到模型的目标函数，表达式为

其约束公式⑵至公式⑿不变，运输总时间的等级划分为60 min 内送达、120 min 内送达和超过120 min 送达3 种情形，根据运输总时间产生的时间成本，可表示为

式中：ε3，ε4，ε5为时间成本系数，满足ε3＜ε4＜ε5。

2 算法设计

高铁快运末端配送路径规划属于非确定性多项式困难问题，基于软时间窗下的多目标路径规划问题求解更为复杂。因此利用改进的遗传算法进行求解，以提高解的质量避免算法陷入局部最优，从而得到高铁快运末端配送路径优化模型的求解算法。

2.1 改进的遗传算法

首先，通过编码方案进行编码生成初始种群，设路径规划方案为G=(g1，g2，…，gk)，其中gk表示车辆路径，而在车辆路径gk=(0，1，2，…，n，0)中，0 表示高铁站，物流收发点为1，2，…，n，车辆数的编码为n+1，n+2，…，n+k(k为货车的最大车辆数)，本文将物流收发点和车辆作为基因片段。例如有5 个配送点，由2 辆货车进行配送，因此车辆1 的编码为6，车辆2 的编码为7。其中车辆1 的路径规划为g1=(0，5，3，1，0)，车辆2 的路径规划为g2=(0，2，4，0)，其染色体编码为5316247，最终调度方案为G=((0，5，3，1，0)，(0，2，4，0))。使用目标函数的倒数作为个体适应度，然后采用轮盘赌算法进行选择操作，依概率选择个体使算法保持随机性。选择后的个体采用OX 交叉和变异操作产生新的个体，从而在保证优良基因保留下来的同时还能保证种群的多样性。然后调用大规模邻域搜索算法完成“破坏”和“修复”两个过程在种群中寻找最优个体。循环上述过程，直至迭代结束或者找到最优解，算法流程如图2所示。

图2 改进的遗传算法基本流程Fig.2 Basic process of improved genetic algorithm

2.2 “破坏”和“修复”

由于遗传算法容易陷入局部最优解，因此选取大规模邻域搜索算法中影响搜索性能的“破坏”和“修复”2个过程，对当前解进行优化避免过早收敛。

“破坏”过程，以减少运输总路程为目标，总路程的增加是由于少数物流收发点的存在导致车辆路径的运输路程增大，所以移动这类物流收发点到其他位置能够有效减少运输总路程。首先从当前解的物流收发点集合中随机选出一个物流收发点，然后根据相关性再依次移出几个物流收发点达到需要的数量，用I表示所有被移出物流收发点的集合，用P表示剩下的物流收发点。

其中相关性计算公式中，R(i，j)表示相关性，R(i，j)越大，表示i，j之间的相关性越大。di，j表示i与j之间的距离，li，j表示i与j是否由同一辆货车服务。如果在同一条路径上时为0，否则为1。R(i，j)计算公式为

式中：d′i，j表示标准化后的值，其值在[0，1]之间。

“修复”过程，根据最远插入启发式，依次从I中选择一个物流收发点重新插回P中。首先算出I中所有的物流收发点的最小插入距离，从中选出最大的元素，插入相应的车辆路径达到目标值减小的目的。

3 算例求解与结果分析

3.1 算例设计

以上海站非高峰时段(10：00—11：00)高铁运营为例，选择该时间段内时间邻近的高铁列车，上海站高铁列车时刻表如表2 所示，图定列车时刻表来源于2021年9月1日上海站的车站大屏数据。

表2 上海站高铁列车时刻表Tab.2 Shanghai station high speed railway timetable

案例研究的上海各区域15 个物流收发点，如图3 所示。根据高德地图实时避免拥堵路线记录了物流收发点及高铁站的旅行时间。以上海市城市总体规划中市区和郊区为依据，基于高铁时刻表和每批货物的配送时间窗，对各物流收发点的各批次货运时间窗进行划分，共有15 个物流收发点，其中1—9 位于郊区，10—15 位于市区。货车提前到达物流收发点的时间惩罚单位成本为20元/min，延后到达的单位成本为30 元/min，时间窗的超限值为20 min。根据高铁装载的货物量[14]设置货车载重量为 1500 件，允许装载货物超出载重量的30%，超载的惩罚成本为 1000 元/件。各物流收发点的所有批次货物需求量如表3 所示，货车单位距离的运输费用为0.5 元[15]。改进遗传算法的相关参数设计如下，算法种群规模为100，最大迭代次数为200，交叉概率为0.9，变异概率为0.05。

表3 各物流收发点的所有批次货物需求量件Tab.3 Demand for all batches of goods at each logistics delivery point

图3 物流收发点的位置Fig.3 Location of logistics delivery points

3.2 算法有效性分析

基于案例中高铁货物的第一批数据，分别使用蚁群算法、遗传算法和改进的遗传算法求解，其中遗传算法与改进遗传算法参数相同，蚁群算法的参数如下：蚁群数量为10，信息素因子为1，启发函数因子为3，信息素挥发因子为0.5，信息素常量为10，迭代次数为200 代。汇总3 种算法运行10 次的最优值如表4 所示。虽然蚁群算法最优运输时间稍短，但其成本最优解远大于改进遗传算法和遗传算法得出的最优解，而改进遗传算法的最优值整体稍优于遗传算法。根据3 种算法成本和时间的平均值可得，蚁群算法成本最优解在[-14%，11%]内浮动，时间最优解在[-6%，6%]内浮动，改进遗传算法成本最优解在[-5%，5%]内浮动，时间最优解在[-1%，1%]内浮动，遗传算法成本最优解在[-50%，46%]内浮动，时间最优解在[-6%，6%]内浮动。综上所述，改进遗传算法的迭代过程和稳定性综合来看更好，而且能够得出高质量的最优解，适合求解本次模型。

表4 3种算法运行10次的最优值Tab.4 Optimal value of three algorithms running 10 times

3.3 算例结果

根据算法有效性比较，利用改进遗传算法对算例进行求解，得到最优运输总成本为 4723.4 元，运输时间为 2086 min。最优配送方案如表5 所示，配送1 h 内到达的所有高铁快运货物共使用15 辆货车，每辆货车平均在90 min内将货物配送完毕。此外，共有5 个物流收发点未在时间窗内完成配送，分别是第一批的6，7 号收发点，第二批的4 号、8号收发点，第三批的6号收发点。由于4个收发点都位于郊区，根据配送路径和配送时间可知，距离较远的物流收发点多与其距离最近的市区物流收发点共同进行配送，当货车将多个郊区收发点共同进行配送时，更容易违反时间窗。但货车每次违反时间窗的时长均不超过10 min，即高铁快运的末端配送能够保证每一批货物在60 min内完成市内各物流收发点配送，在110 min 内将郊区物流收发点配送完毕。

表5 最优配送方案Tab.5 Optimal distribution scheme

3.4 货车载重量影响分析

为探究货车的载重量对配送方案的影响，对比了3 种载重量的货车，得到3 种货车载重量的配送方案和货车满载率如图4 所示，由于货车的载重量不同，所以3 批货物的货车满载率会发生改变。对比图4a、图4b和图4c可知，载重量为 1000件货车的平均满载率最高，达到了74.27%。载重量 1500件的货车平均满载率为49.51%，高于载重量 1800 件的货车平均满载率41.26%，在相同配送方案下，载重量 1800 件的货车空间没有得到较好的利用，所以使用载重量 1500 件的货车优于 1800 件的货车。

图4 3种货车载重量的配送方案和货车满载率Fig.4 Distribution scheme and full load rate of three kinds of wagon load capacity

此外，3种货车载重量的运行结果如表6所示，载重量为 1500 件的货车运输时间和总成本最低。 1800 件的货车只在总成本上高于 1500 件的货车， 1000件的货车与 1500件的货车运行结果相比，多花费1.2%的运输时间和38.4%运输成本，由于载重量为 1000 件的货车选择增加违反时间窗个数，使最大行驶距离增加了5.4%，从而避免违反货车载重，保证车辆安全。基于上述分析，载重量为 1500 件的货车无论是在时间上还是成本上都优于其他2 种载重量的货车，并且满载率相对较高，所以使用载重量为 1500 件的货车在本算例中是最佳方案。

表6 3种货车载重量的运行结果Tab.6 Running results of three kinds of wagon load capacity

4 结论

针对高铁快运“最后一公里”配送问题，考虑即时配送、货车载重和货物时间窗，建立了最优运输成本和运输时间的多目标模型，设计了改进的遗传算法，以上海站及上海各区域的物流收发点为例，将改进的遗传算法与蚁群算法、遗传算法进行对比分析，验证了设计的算法对本案例的有效性。得出的案例结果表明，高铁快运末端“去配送中心”的直接配送模式能够保证在成本维持不变的情况下，提高配送服务的质量和效率。此外，对不同的货车载重量进行了分析，得出最佳高铁快运末端配送方案，为高铁快运末端配送路径规划提供一定指导和决策支持。