快捷货物公路干线运输组织优化研究

陈婉茹，张得志，梁一婧，曹健

(1.中南大学 交通运输工程学院，湖南 长沙 410075；2.南京大学 工程管理学院，江苏 南京 210046)

随着经济全球化和电商行业发展速度的加快，我国的快捷货运市场愈发活跃。降低快捷货运成本成为物流企业提高核心竞争力的重要途径之一。快捷货物运输涉及城市间干线运输及城市末端支线配送2个系统，“高成本、低效率”的问题在快捷货物公路干线运输中尤为突出。快捷货物干线运输系统依托跨越省、区(市)的骨干公路线，网络结构复杂；货物流量大，但在时空上的分布不均，对其进行协调调度具有很高的难度。目前快捷货物干线运输采用“点对点”直达运输模式，该模式下车辆往返服务于固定的始发终到枢纽，操作简单，适用于人工调度，但是灵活性较差。在实际运营过程中发现，由于周转需要，车辆在到达卸货地点后，往往没有足够的时间停留等待至下一批回程货物的到达，而只能即刻空载返回出发枢纽，由此，所产生的运输称之为单边运输。单边运输是导致我国快递企业运营车辆空驶率超40%的一大元凶[1]，它的存在大大增加了单位货物运输成本。如何在全国性路网的基础上，从运输组织优化的角度出发，减少快递干线单边运输，是一个亟待解决的现实难题。国内外学者对快捷货物干线运输优化展开了研究：赵晋等[2]从网络总成本最低的视角出发，构建了允许直达的混合轴幅式快货运输网络规划决策模型，提高了服务时效性和服务水平；YU等[3]建立了快递企业运输网络的双层优化模型，上层模型以总运输成本最小为目标设计运输网络和分配运输能力，下层模型以用户均衡为目标计算链路流量；李文莉等[4]构建了带分支流向约束的枢纽选址模型，通过改变现有网点的从属关系，构建了轴辐式快捷货运网络，并设计了相应的禁忌搜索算法；裴利奇等[5]在需求不确定的情境下，构建了双目标整数规划模型确定了快货运输枢纽的选址，运用NSGA-Ⅱ方法求解；ZHANG等[6]研究了多式联运下多主体的轴辐式快货运输网络，同时考虑了二氧化碳定价、网络末端配送和枢纽选址；张得志等[7]构建了基于低碳经济视角的多模式快捷货物物流网络优化决策模型，并设计了遗传算法进行求解；MARTIN等[8]研究了大规模快货运输网络结构与配送时间、相关的定价方案和负载计划的联合优化问题，以实现总利润的最大化；QU等[9]在货运需求不确定的背景下，构建了混合整数规划模型，解决内陆公路干线运输与水运的一体调度优化问题；DRAG‐OM IR等[10]研究了跨国跨区域的大规模包裹运输路线和多式联运方式的选择问题。目前快捷货物干线运输的研究主要围绕服务网络的设计展开，学者们通过确定物流节点的规模、数量、选址、内部布局，构建了具有点点式、轴辐式、混合式等不同特征的快货运输网络，实现各节点、路径的合理匹配，达到整个物流系统中物流成本最少的优化目标[11]。在运输组织方面的研究主要从公路干线与其他运输方式和运输工具协同配置优化的角度出发，围绕“公铁”联运、“公水”联运展开，鲜有学者研究单纯的公路干线运输车辆网络路径规划问题，而针对干线运输中的单边运输问题更是有待进一步研究[12]。基于上述分析，本文研究快捷货物公路干线运输组织优化，主要贡献如下：1)在分析快捷货物公路干线运输特征的基础上，提出提升干线运输效率的运输组织模式；2)将快捷货物干线运输组织优化问题抽象为考虑时间窗与路由限制的多车场车辆路径优化问题，构建决策分析模型并设计了基于时空的三维改进禁忌搜索算法；3)以顺丰速运的公路干线网络优化为例进行相应实证分析，结果表明，对干线运输路径的合理规划能够一定程度上帮助企业解决现有的单边空载浪费问题。

1 快捷货物公路干线运输组织优化对策分析

快捷货物公路干线运输中单边运输产生的根本原因在于：各城市OD对之间发送与到达的货流量不是一对一平衡匹配的，从而导致了点对运输模式下的回程空载浪费。可以通过以下4种改进的干线运输组织模式来降低空载浪费。模式1：全循环运输——由不同单程运输接续衔接出发地和目的地，在构成的环形路径中只包含载货弧段，不含空载弧段。模式2：半循环运输——区别于全循环运输，半循环运输模式下的车辆环路中允许包含一段空载弧段。模式3：对开运输——合并始发地和目的地相反的两段单程运输。模式4：摆渡运输——将两段相向行驶且始发地与目的地距离较近的单程运输进行短途接驳。上述运输组织模式示意图如图1所示。但值得注意的是，在实际生产过程中，整合弧段的边际管理成本将随着车辆路由弧数量的增加而不断提高，因此在进行优化的过程中需要根据生产经验对最大路由弧段数进行限制。

图1 4种改进的干线运输组织模式示意图Fig.1 Diagram of four improved transportation organizationmodes

2 问题描述

快捷货物干线运输优化问题实际上是一个定义在一个有向图上的考虑时间窗和路由限制的多车场弧路由问题(Multi-depot Arc Route Problem w ith Time Windows and Routing Constrains,MDARP-TW-RC)，即在满足车辆路由弧段数量限制及服务时间窗的约束下，找到车辆路由单程的最佳组合，以达到最小化运输成本的目的。图2为一个拥有10个中转枢纽点，8个单边运输任务的网络实例，为了便于区分，用矩形代表车辆始发和终到的中转枢纽。优化后，该网络包含由10-7-6构成全循环运输、由2-1-5构成半循环运输、由3-4构成对开运输以及未被整合的单边运输8-9。

图2 单边运输优化网络示意图Fig.2 Unilateral transportation optim ization network

一般地，长途干线运输车辆所走行的公路径路是固定的，可以认为单程运输中与里程相关的变动成本是一定的，即图3中r1与r2的运输成本是已知的。从而，快捷货物干线运输优化问题需要考虑的变动成本为单程运输衔接时车辆走行r3，r4及在枢纽点换装所产生的成本。经过这样的抽象，可以将一次单程运输看作一个“点”，将单程运输起始点的时间窗视作该“点”的时间窗，将车辆完成单程运输的时间视为车辆离开该“点”的时间，将车辆在枢纽处的装卸成本与运输成本看作车辆途经该“点”的成本，从而将MDARP-TWRC转化为考虑时间窗和路由限制的多车场车辆路径问题(Multi-depot Vehicle Route Problem w ith Time Windows and Routing Constrains,MDVRPTW-RC)。

图3 MDARP-TW-RC转化为MDVRP-TW-RCFig.3 MDARP-TW-RC to MDVRP-TW-RC

3 优化模型

将问题定义在有向图G=(V,A)上，其中V是单程运输点集，A是由两两单程运输点连接构成的弧集。特别地对于∀i∊V有A的子集Ai满足Ai={(j,k)|(j,k)∊A,k≠i}。R为单程运输需求集合，，，ar，br分别表示运输需求r的起止点和起止时间。TT1，TT2，TT3分别表示车辆卸装、卸空、装载所需要的时间。dij表示点i和点j之间的距离，S表示车辆的平均行驶速度，TC表示单位距离的运输成本，WC表示等待成本。Q表示一次运输所包含的弧的最大数量。表示在线路中(除最末外)增加一个单程运输点而带来的路由弧段数的增加，当为1，否则为2。表示在线路最末端增加一个单程运输点而带来的路由弧段数的增加，当为0，否则为1。本文从宏观角度出发，对有利于运营的单程线路组合进行发掘，做出如下假设：

1)干线运输车辆从某枢纽出发，完成运输任务后需返回所属枢纽；

2)车辆空载运输成本为载货运输成本的一半；

3)每个单程运输仅由一辆车服务，且默认车辆能够满足装载需求；

4)不考虑不同车型车辆在载重和体积上的差异；

5)不考虑路况变化对车速的影响，即车辆在运输过程中的行驶速度是恒定的；

6)车辆到达时间满足软时间窗，当车辆在某分拨中心的等待时间大于12 h时需加以惩罚。

表示单程i到达单程j起点并完成换装的时间，表示单程j返回单程i起点并完成换装的时间。表示从至开始单程j的等待时长，表示从至开始单程i时间的等待时长。表示从前单程起点i到后单程起点j的运输成本，表示从末单程终点j返回首单程起点i的运输成本。在运输成本的计算中直接考虑了软时间窗的惩罚，建模如式(1)～(6)：

在建模过程中，本文以一天为一周期，并用1 440m in表示。式(1)和式(4)将单程i与单程j间的接续时间依据和的位置关系划分为2种情况，若则无需空载，车辆直接在进行卸装作业；若则车辆需要增加一段长度为dn+i,ni的空载路由，并在和分别完成卸空，装载作业。式(2)和式(5)计算了车辆到达单程运输点至开始服务需要等待的时间。式(3)和式(6)依据等待时间是否超过阈值，计算了由单程运输点衔接所带来的成本，其中包括与走行距离相关的行驶成本及等待成本。

结合所讨论的干线单边运输实际问题，本文建立了干线运输优化决策模型，该模型的实质是多车场带时间窗的车辆路径优化模型的扩展。不同于一般的多车场问题，出发枢纽也在决策的范围内，因此本文设计有二元决策变量xi,j,k，当以i为起始点的运输包含弧(j,k)时取1，否则取0。此外，还设计有整数决策变量oi，用以表示车辆途经i点时已路由的弧段数。具体模型如式(7)～(13)：

模型的目标函数(7)为最小化运输成本，采用逐弧段叠加的方法进行计算；约束条件(8)表示每个单程运输点被且仅被访问一次；约束条件(9)为流平衡约束，表示对于每个分拨中心而言到达车辆数等于出发车辆数；约束条件(10)和(11)对车辆路由弧段的数量加以限制；约束条件(12)和(13)对决策变量的取值进行了规定。本文所建立的非线性模型可以通过大M法转化为混合整数线性规划模型，但本研究的目的在于解决实际背景下的大规模优化问题，无法用求解器在可接受的时间内求得全局最优解，因此不对其做过多赘述。

4 求解算法

本文研究的干线运输优化问题是多车场带时间窗的VRP的延伸，属于NP-hard问题。根据GENDREAU等[13-14]对求解VRP的一些现代启发式算法的综述，禁忌搜索是目前求解VRP的较为有效的方法。另外，禁忌搜索算法在求解多车场车辆路径问题中也不断得到成功的应用[15-16]。因此，本文研究选择设计禁忌搜索算法进行求解，并通过设计有效的初始解生成算法、邻域结构和禁忌规则，增强了搜索的多样性，从而克服了启发式算法容易过早收敛的缺点[17]。

4.1 初始解构造

使用Clarke andW right节约算法[18]可以快速获得一个初始解。首先，将单程点按照发车时间先后排列，并为每个单程点分派一辆车。然后，按照顺序不断尝试合并2条路线，在尊重路由弧段数约束的情况下获得最大的节约。当没有可行的合并时结束迭代，即得到初始解。

4.2 邻域移动

为了尽可能扩大解的搜索范围，在本文中，同时采用2个路径间算子：点插入和点交换，对当前解进行邻域搜索。点插入算子将将某路径的一个单程点插入另一路径中，如图4(a)所示，该操作可能产生或删除路径。点交换算子交换某路径中的一个单程点与另一路径中的一个单程点。如图4(b)所示。

图4 算子示意图Fig.4 Diagram of operators

4.3 基于时空的禁忌规则

初始解的优劣会直接影响算法的效率，但通过有效的禁忌规则可以降低搜索过程对初始解的依赖性[19]。本文设计了基于时空的禁忌规则，不同于传统的禁忌规则，采用三维禁忌表，记录改进发生时所作操作的客户点及路径。如图5所示，每个点对应一张n×n的禁忌表，一旦有改进操作发生在某点的某路径组合间，则置相应表中相应组合的禁忌周期为禁忌期限TT。在下次迭代中，禁止点的操作发生在禁忌周期不为0的路径组合间，除非改进后的解优于历史最优解。每次迭代后，更新禁忌周期，释放周期为0的路径组合。

图5 三维禁忌表示意图Fig.5 Three-dimensional tabu list

4.4 解的评价函数及接受准则

每次迭代后，需要对所得到的邻域解进行评估，以决定是否接受它，而只接受改进解的一般做法容易导致过早的收敛。本文采用Dueck提出的Record-to-Record Travel，RRT算法[20]定义一个邻域解的阈值接受准则。设s*是历史最优解，s'是邻域解。F(Δ)是解的评价函数，本文中直接采用优化模型的目标函数对解进行评价。若F(s')

4.5 算法流程

为了描述方便，定义以下变量：当前的迭代步数iter；最大的迭代步数max-iter；候选解集cand-list；当前解S；最佳候选解S'；历史最优解S*。

算法流程如下。

步骤1：用节约算法得到初始可行解，并将其作为s和s*。

步骤2：初始化禁忌表，置iter为0。

步骤3：对s进行点插入邻域搜索，并将产生的可行解放入cand-list中。

步骤4：对s进行点交换邻域搜索，并将产生的可行解放入cand-list中。

步骤5：若cand-list为空则终止算法，否则转步骤6。

步骤6：若cand-list存在优于s*的禁忌解，则解禁该解作为s'；若整个cand-list都被禁忌，则解禁其中评价函数值最小的解作为s'；否则，从cand-list中选择评价函数值最小的非禁忌解作为s'；根据RRT准则判断是否接受s'作为当前解s，更新禁忌表，iter的值加1。

步骤7：若F(s')

步骤8：若iter<=max-iter，则转步骤3；否则，终止算法。

5 数值实验

为了验证本文提出的优化方法的合理性和实用性，选取顺丰速运部分干线单程运输数据进行优化决策，部分算例数据如表1所示。

表1 顺丰干线网基础数据Table 1 Basic data of SF trunk line network

结合实际生产运作过程对模型涉及参数进行标定：卸车作业的中转时长为120m in，装车作业及卸装作业的中转时长为240m in；车辆的平均行驶速度为1.167 km/m in，单位运输成本为1元/km；每次运输所包含的弧段(包括空驶)应小于4段；等待成本为130元。置最大迭代次数设置为500，禁忌期限为10。

5.1 求解结果

输入228条顺丰速运干线运输中的单程运输数据，若未经优化，这些单程运输均以“点对点”直达运输的模式进行，其总运输成本达388 637.92元。依据本文所提出的模型算法对上述算例进行优化，算法运行10次后，得到最优解的路径数目为201条，总运输成本降低至373 751.56元，节省了14 886.36元，节省率达3.83%，且得到最优解的最优计算时间为5.87 s。

最终输出的线路中，包含18条半循环模式线路，4条摆渡模式线路，将部分优化后的线路罗列如表2。若将上述结果应用到快递企业自有车辆的常态化运行中，将带来非常可观的运输成本节省。此外，随着包裹量的不断增加，快递企业自有车辆承担着巨大的运输压力。作为应对策略，公司可以使用第三方物流(3PL)供应商使用外包车辆。在一定的车辆租借成本下，快递企业需要从战略层出发，确定外包路线的外包策略，而上述结果可以很好地辅助相关物流企业进行干线外包路线规划的决策。

表2 部分优化结果Table 2 Partialoptim ization results

5.2 敏感性分析

干线运输主要依托于高速公路，其路况有所波动，例如，在节假日的时候整体路况都较为拥堵，车辆的到车时间会相较于平均时间有所延误，而在平日，路况更为通畅时，车辆的到车时间会相较于平均时间有所提前。基于此，本文对所有车辆的到车时间均提早1 h和2 h，及所有车辆到车时间延迟1 h和2 h的4种不同情况进行了分析。如图6所示，整合线路数量和总成本随着到车时间的变化在一定水平上波动。但运输成本和优化线路在不同到车时间下无明显变化规律。究其原因，到车时间的提早和推迟都会改变单程接续的等待时间，从而影响整合优化的最终方案。到车时间对优化的影响体现在最终线路的优化方案上，将提前2 h的整合结果与推迟2 h的结果进行可视化，如图7所示。上述结果共同表明快捷货物干线运输的动态优化值得进一步探讨。

图6 线路数和成本的变化趋势Fig.6 Changing trendsof the total costand the number of routes

图7 不同到车时间下优化方案的示意图Fig.7 Diagram of the optim ization scheme fordifferentvehicle arrival time

6 结论

1)在全国性路网的基础上，将单程运输整合成全循环、半循环、对开、摆渡等不同模式，可以有效降低车辆的空载率，从而降低运输成本。

2)快捷货物干线运输优化问题经过合理的简化和抽象，可以转化为一个多车场车辆路径扩展问题，并借助弧流模型进行表述。

3)快捷货物干线运输优化问题是NP难问题，需要借助启发式算法进行求解。在顺丰大规模干线运输网络的实例测试中，本文所设计的基于时空的三维改进禁忌搜索算法可以在5.87 s左右就求得该算例的满意解，且结果显示优化方案的运营成本比实际运营方案节约3.83%。

4)路况会对车辆的到车时间产生直接的影响，从而影响整合优化的最终方案。动态环境下的快捷货物公路干线运输组织优化值得进行更加深入的研究。