网络条件下供需未匹配的公路港多车型甩挂调度优化

郭红霞，倪少权，贺裕雁

(1.西南交通大学，交通运输与物流学院，成都 610031；2.广西科技大学，经济与管理学院，广西柳州 545006)

0 引言

公路港甩挂运输网络规模的扩大和甩挂运输业务的不断拓展使得公路港甩挂调度难度增加，是我国公路港亟待解决的重要问题之一。目前我国现有政策对甩挂运输车辆类型进行了限制，卡车拖带挂车的甩挂运输车辆不允许在中国道路上运行，只允许牵引车加半挂车的形式(Tractor and Semitrailer)[1]，称 为TSRP(Tractor and Semitrailer Routing Problem)，这与欧美国家存在较大差异。目前，我国甩挂运输区域发展不平衡，发展较好的地区主要为华东、华南等经济发达区域，甩挂车辆主要从事以港口为核心的集装箱轴辐式甩挂集疏运。我国的公路港甩挂运输虽已得到足够的重视，但仍以“点对点”运输为主，两点辐射的范围也仅局限于某个区域内，甩挂运输效率不高。现阶段，我国开展公路港甩挂运输的车型特点决定了中长途干线运输是其主要应用领域，中长途干线运输以网络化、规模化特征成为体现甩挂运输高效性优势的依托条件，便于实现甩挂运输货源组织的规模化[2]。政府的大力支持，公路港甩挂运输网络的渐次铺开，货源的日益充足稳定以及企业信息化水平的提高，为公路港甩挂运输企业在全国范围内开展调度提供了保障。因此，研究网络条件下公路港甩挂调度优化问题对企业的车辆资源配置优化与运营具有重要的指导意义。

目前甩挂调度优化研究主要集中在“一线两点、两端甩挂”“轴辐式甩挂”“循环甩挂”等组织模式，针对网络条件的研究较少，且未考虑供需匹配问题。Li等[3]为解决“轴辐式甩挂”模式下的废气材料甩挂调度问题，以成本最小为优化目标，提出车辆流规划模型，设计了改进节约算法进行求解。Li等[4]针对“轴辐式甩挂”模式下的垃圾搜集甩挂调度问题，以总运行成本最小为目标函数，考虑时间窗、集装箱装卸时间等约束构建数学模型，通过设计两阶段启发式算法，实现装载和空箱的同步调度。杨珍花等[5]以综合成本最小化为目标，设计多阶段动态优化算法以解决“轴辐式甩挂”模式下甩挂车辆的动态调度优化问题。彭勇等[6]针对“循环甩挂”模式下的同城甩挂运输问题，为尽可能降低物流运输成本的同时提高客户满意度，构建了带时间窗的具有多行程的交换箱甩挂运输优化模型，提出装箱算法与遗传算法混合的启发式求解算法。Li等[7]基于“一线两点、两端甩挂”模式，为解决城际干线甩挂运输问题，以吨公里CO2排放量为优化目标，设计改进节约算法进行求解。李红启等[8]研究“一线两点、两端甩挂”模式下的城际干线甩挂运输问题，以CO2排放量为优化目标构建模型，并设计模拟退火算法进行求解。Regnier 等[9]研究“循环甩挂”模式下的企业甩挂运输调度问题，考虑时间窗等约束构建模型，并运用动态离线式建模求解器进行求解。靳志宏等[10]研究“循环甩挂”模式下的滚装甩挂码头牵引车调度问题，建立混合整数规划模型，并设计遗传算法求进行求解。杨珍花等[11]建立轴辐式与网络型混合模式下的多车型甩挂调度模型，以成本最小为优化目标构建模型，设计混合模拟退火算法进行求解。余莉等[12]结合网络条件下的甩挂运输及满载多车场车辆调度问题的特点，建立数学模型，并设计启发式算法进行求解。王清斌等[13]建立“循环甩挂”模式下考虑新增运输任务的干扰管理模型，设计遗传算法进行求解。在车辆路径优化方面，供需未匹配问题研究较多，但在甩挂调度优化方面较少。徐东洋等[14]以总成本最小为优化目标，建立同时考虑客户间供需未匹配和需求可拆分的取送货车辆路径问题模型，并设计基于大规模邻域搜索的迭代局部搜索求解算法。Chen 等[15]建立同时考虑客户间供需未匹配和分批交货的取送货车辆路径问题模型，提出基于变邻域搜索的局部搜索算法进行求解。Xu 等[16]建立同时考虑客户间供需未匹配和多需求的取送货车辆路径问题模型，设计禁忌搜索算法进行求解。Tadumadze等[17]建立同时考虑劳动力规划和卡车调度的混合整数模型，并设计启发式算法进行求解。

在求解多车型调度优化问题时，相关学者采用精确求解算法和启发式算法。例如，Regnier等[9]针对实时动态优化问题，采用CPLEX 求解小规模问题。Subramanian 等[18]用CPLEX 求解小规模问题，同时针对大规模问题设计了自适应记忆规划算法进行求解。Villegas等[19]设计了一种基于贪婪随机自适应搜索程序的两阶段启发式算法。Tütüncü等[20]设计了贪婪的随机自适应记忆搜索算法。Oliviu等[21]设计了遗传算法和最邻近法相结合的方法进行求解。Li 等[22]设计了自适应大邻域启发式搜索算法求解两层级多车型车辆路径问题。Ghannadpour 等[23]提出了非支配排序遗传算法。Andre 等[24]针对两级固定车队异质车辆路径问题，提出一种基于局部搜索的Lin-Kernighan 启发式算法。Srivastava等[25]设计了非支配排序遗传算法、多邻域自适应禁忌搜索算法和精英蚁群算法求解。Soares等[26]基于可变邻域分解搜索下的固定与优化原则，提出一种新的元启发式算法求解大规模调度问题。

上述文献大多是在单车场、单一需求、供需已匹配、需求均衡视角下建立的模型假设，忽略了多车场、多需求、需求不均衡和供需未匹配的现实需求。在算法求解方面，已有文献证明甩挂运输调度优化问题属于NP-Hard 问题[1]，因此大部分文献采用元启发式算法和启发式算法进行求解，但在进行局部搜索时仅依靠理论而忽略了实际调研情况。因此，本文基于公路港作为甩挂作业场所和客户需求点的特性，考虑公路港间甩挂需求与车辆装载能力不匹配和多车型甩挂(即吨位大的牵引车可拖挂同车型或吨位小的半挂车)等现实需求，以网络运营成本最小为优化目标，建立网络条件下供需未匹配的公路港多车型甩挂调度优化模型，并根据实际调研设计基于节约里程法、动态规划法和改进模拟退火算法的两阶段启发式算法对模型进行求解。并与传统运输方式对比，证明多车型甩挂运输优势明显，为企业决策提供了支持。

1 问题描述

公路港甩挂运输的快速发展使得路网不断升级，公路港建设增多，线路间联系紧密，其中每两个公路港之间都有通道相连，多个公路港之间的甩挂运输业务形成网络，该甩挂运输网络向北辐射哈尔滨乃至整个东北地区，向南辐射广州、深圳等地，向西辐射成都、重庆等地，向东辐射宁波、上海等地，在全国范围内开展甩挂。公路港甩挂运输网络内，甩挂作业点提前将货物装上半挂车，装货完毕后由牵引车送至指定的公路港，牵引车无需等待卸货作业，卸下重挂，继续服务下一个客户点(公路港)，直到运行时间内完成最后一个甩挂任务后，停留于该公路港，即为网络条件下的公路港甩挂调度方式。实践调研发现，公路港甩挂运输网络中存在多个车场，公路港间甩挂需求不均衡，且存在多次甩挂和甩挂需求大于车辆装载能力的情况，其具体供需匹配关系及牵引车和挂车配置数量未知，属于多车场供需未匹配的调度问题。

本文在上述网络条件下提出公路港多车型甩挂调度优化，具体如图1 所示。图中，圆圈内数字表示公路港编号，线上数字表示公路港之间的甩挂运输量与所需车型。以甩挂运输线路①→⑤→③→②→①为例，如果不同的车型之间不可以进行交叉甩挂，该条线路至少需要3辆35 t牵引车、2辆37 t 牵引车和5 辆40 t 牵引车，而且回程时均为空驶。但如果不同车型之间允许进行交叉甩挂，在连续工作时间内，5辆40 t的牵引车从公路港1出发到达公路港5，其中2辆牵引车可以继续完成公路港3到公路港2 和公路港2 到公路港1 的甩挂任务，将会减少2辆35 t和2辆37 t牵引车的使用，同时降低了回程空驶率，提高运输效率，很明显此种方案更优。

图1 网络条件下供需未匹配的公路港多车型甩挂调度优化示意图Fig.1 Schematic diagram of multiple tractor-and-semitrailer scheduling with unmatched supply and demand under network condition

该公路港甩挂运输网络除了具有多车场、多需求、需求不均衡以及多车型甩挂的复杂性外，还具有如下特性：公路港之间的甩挂需求往往大于车辆最大装载能力，需对公路港之间的甩挂需求进行拆分，并通过多辆不同类型牵引车共同完成甩挂任务，要求进行供需匹配，但匹配关系未知，研究如何以较低的运营成本进行公路港间的供需匹配决策和牵引车与挂车数量配置，属于更难求解的NPHard问题。

2 模型建立

2.1 模型假设

根据公路港甩挂运输特点，做出如下假设：

(1)网络中所有牵引车、半挂车都属于公路甩挂运输推荐车型，但型号存在不一致情况，且牵引车只能牵引不大于自身准拖最大质量的半挂车，牵引车类型和半挂车类型对应。

(2)不考虑空半挂车的调度。由于公路港同时又是挂车池，因此，网络中各公路港有足够多的半挂车，无需从其他公路港调度空半挂车。

(3) 两个公路港间往返行驶的距离及时间相同。这一点主要与甩挂运输车辆的运作相关，实践中司机采用高德地图推荐的路线开展甩挂运输。

(4) 牵引车甩挂半挂车作业时间计入行驶时间。此假设与公路港甩挂的实际操作是一致的，故该假设合理。

(5)牵引车执行“一车一挂”的满载运输，即牵引车一次只能拖带一辆半挂车。这与我国公路港甩挂运输运营实践相符合。

(6)牵引车的起终点均为公路港，起始公路港和终止公路港可不一致。公路港内可以停放牵引车和半挂车，因此不必考虑牵引车完成运输任务后返回车场，这一点与我国公路港甩挂运输实际调研相符合。

(7)公路港间的甩挂需求独立，无时间和运输先后顺序限制。

(8)网络中每天都产生甩挂需求，且每天的需求存在波动，企业可以根据每天实际需求安排调度，所有的需求都必须满足。由于某些节点之间距离较远，甩挂运输不一定能够在一天内完成，因此假设前一天未完成的甩挂任务不影响后续调度。

2.2 符号说明

N——所有公路港的集合，共有n个公路港，N={1,2,…,n} ；

i,j,l——公路港的编号，i,j,l∈N；

K——牵引车的集合，K={1,2,…,k} ；

k——牵引车的编号，k∈K；

m——牵引车的类型，m∈{1,2,3} ；

mk——第m种类型牵引车k，k∈K；

dij——公路港i,j之间的距离(km)；

qij——公路港i,j之间的甩挂需求，用货物吨位表示，由于需求不一定平衡，qij不一定等于qji；

T——牵引车连续工作的时间，规定所有牵引车每天连续工作的时间都相等；

Vm1,Vm2——m类型牵引车牵引重挂、空驶的速度(km·h-1)；

S——牵引车甩挂任务的集合，S={1,2,…,S,…} ；

a,b,s——牵引车甩挂任务的编号，a,b,s∈S；

P——较大值；

KZ——路网需要的牵引车总数。

2.3 数学模型

(1)目标函数

(2)约束条件

式(1)表示网络运营成本由重挂行驶成本、空驶成本、固定成本和惩罚成本组成，且运营成本最小；式(2)表示每一个甩挂任务均被满足，且只能由一辆牵引车服务；式(3)表示甩挂需求得到满足；式(4)表示牵引车被使用后才可服务甩挂任务；式(5)表示当前牵引车不服务某个任务时顺序为0；式(6)表示每辆牵引车服务任务顺序的编号不同；式(7)表示每辆牵引车服务任务编号的取值范围；式(8)表示每辆牵引车重载趟数；式(9)表示每辆牵引车空载趟数；式(10)表示每辆牵引车重挂是否经过公路港行驶路线；式(11)表示每辆牵引车空挂是否经过公路港行驶路线；式(12)和式(13)表示每个甩挂任务的始发公路港和终到公路港不相同；式(14)表示牵引车连续工作时间限制；式(15)表示惩罚成本，γ为使用高质量牵引车牵引低质量挂车的惩罚系数，也为不同牵引质量牵引车成本极差系数；式(16)表示牵引车使用数量。

3 两阶段启发式算法设计

网络条件下供需未匹配的公路港多车型甩挂调度优化属于NP-Hard 问题[2]，在较短的时间内很难获取较为满意的解。为此，本文设计两阶段启发式算法进行求解，第1阶段通过动态规划法将甩挂需求分割成单个半挂车可以承载的重量，将其转变为一个或多个甩挂任务，将连续型问题转变为离散型问题，以降低问题复杂度；第2 阶段考虑到动态规划拆分的甩挂任务数量较多，因此运用节约里程法对甩挂任务进行合并以减少解空间的数量，以得到较好的初始解，并设计改进的模拟退火算法进行求解。

3.1 动态规划法设计

动态规划法主要思想是将问题分解成若干个子问题，先求解子问题的最佳解，然后从这些子问题的解中得到原问题的最佳解。本文通过该算法解决不考虑任务合并的前提下甩挂需求的分割问题，属于整数规划问题。

3.2 改进模拟退火算法设计

(1)初始解的生成

本文运用节约里程法对甩挂任务进行合并以形成初始解，首先令一辆牵引车只服务一个甩挂任务，然后通过计算任意两个任务在满足约束下合并后节省的成本得到费用表，依据费用表更新节约成本最大的合并线路，并更新费用表，直到任意两个任务无法合并或无法节约成本。

(2)解空间结构设计

将合并后的甩挂任务分别编号以形成解空间。若H为甩挂任务数量，则编码长度为H，设H=8，具体解空间结构如图2所示。

图2 网络条件下供需未匹配的公路港多车型甩挂调度解空间结构图Fig.2 Solution space structure diagram for multiple tractorand-semitrailer scheduling with unmatched supply and demand under network condition

(3)邻域解构造方法

基于“一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解”“全局最优解是所有可能邻域的局部最优解”两个实际理论，本文通过3 种邻域结构进行搜索以提高求解最优解的可能性，分别是插入、交换和逆反。

(4)算法终止准则

改进模拟退火算法包括内外两个终止准则。

①内循环终止准则，采用与问题规模相关联的步数抽样，即当内循环次数达到与网络规模乘某个系数值所对应的步数时，则该温度下的内循环终止。

②外循环终止准则，采用设置终止温度阈值的方法，即当温度下降到某一设定阈值时，算法终止并输出结果。

4 算例分析

依托公路港甩挂运输网络，甩挂运输企业在30个城市都具有公路港，如何在公路港网络中安排车辆调度，使得整个网络运营成本最低是企业管理者希望解决的技术问题。根据交通运输部公布的3批公路甩挂运输推荐车型，该企业使用的牵引车车辆及重挂空挂行驶成本、固定成本如表1 所示。假设同一类型不同型号牵引车行驶速度相同，重挂和空驶的速度分别为Vm1=50 km·h-1，Vm2=70 km·h-1，每天连续工作时间T=16 h，dij值根据高德地图点击导航，选择高德地图推荐的路线得出。γ可以直接由表1 计算得到。qij值使用Matlab 2010a软件中的randint函数，在[0,100]内生成30 个客户点之间的甩挂任务，所有甩挂任务均为整数。改进的模拟退火算法(ISA)中，初始温度设置为1000°C，算法结束温度设置为0.1°C，温度衰减参数ε为0.95，马尔科夫链长度uk为50。算法运行30次，取其中的最优值作为最终结果。

4.1 固定工作时长下的结果分析

通过计算，需要1447辆牵引车完成既定任务，每辆牵引车的编号如表2 所示。从表3 中可以看出，与传统运输方式相比，牵引车数量减少了7.30%，节约成本2.32%，甩挂比为1.00∶1.08，体现了多车型甩挂的优越性。

表2 网络条件下供需未匹配的公路港多车型甩挂调度运行结果Table 2 Results of multiple tractor-and-semitrailer scheduling optimization in highway port with unmatched supply and demand under network condition

表3 传统运输方式与多车型甩挂计算结果对比Table 3 Comparison of calculation results between traditional and common tractor and semi-semitrailer transportation

4.2 不同工作时长下的结果对比

随着牵引车工作时长的增加，甩挂运输会尽可能发挥长交路的优势，所服务的公路港数量随之增加，进而形成不同的牵引车调度方案。为此，将延长算例中牵引车的工作时长，分别为16，32，48，72 h，具体计算结果如表4所示。

表4 不同牵引车工作时长下的结果对比Table 4 Comparison of results under different working hours

结果表明，牵引车使用数量、总成本、甩挂比与牵引车工作时长之间存在密切关系，具体如下：(1) 相较于我国2022 年的甩挂比1.00∶1.04，算例中的甩挂比均高于该数值，且与牵引车工作时长成正比。甩挂比越高，表示每辆牵引车路线能拖挂的半挂车数量越多，运输网络上牵引车的使用效果越好，车辆配置效率越高，网络运营成本越低，证明了多车型甩挂的优势。(2) 牵引车工作时长越长，牵引车使用数量和总成本越小，甩挂比越大。(3)牵引车工作时长越长，牵引车数量减少比例和总成本节约率均呈现出梯度增加的趋势，尤其当牵引车工作时长为72 h 时，多车型甩挂的优势凸显。(4)不同工作时长下甩挂比合理值的确定，也为公路港甩挂运输企业购置牵引车和半挂车方案提供了决策支持。

4.3 不同算法下的结果对比

为进一步验证算法的性能，本文将改进蚁群算法(IACS)、改进粒子群算法(IPSO)和改进模拟退火算法(ISA)进行对比，3种算法采用相同的局部搜索策略。IACS算法中Nc_max为最大迭代次数，设置为600；α为信息素重要程度的参数，设置为1；β为启发式因子重要程度的参数，设置为4。IPSO算法中的学习因子c1，c2均取1.5，粒子速度vmax=5，vmin=-5。目标函数最值对比如图3所示。

图3 多车型甩挂目标函数最值对比Fig.3 Comparison results of maximum objective function for common tractor and semitrailer transportation

由图3 可知，IACS 算法的平均目标值均小于IPSO 和ISA，较IPSO 和ISA 分别降低了28.75%、1.5%，运行时间较IPSO 减少5.28%、较ISA 增加51.8%。通过对比可以看出，IACS算法的平均总运营成本略优于ISA 算法，差距不大，但运行时间远远大于ISA算法。因此，综合考虑认为采用ISA两阶段启发式算法较优，并证明了ISA算法在处理大规模问题时寻找最优解的优越性。

5 结论

多车型甩挂相比于单一车型运输运营成本要低，说明多车型甩挂可以更恰当地安排运力，物尽其用；随着牵引车工作时长的增加，多车型甩挂能够在更大优化空间内提高甩挂比、降低牵引车空驶率和空载距离、提高牵引车的使用效率和优化车辆配置，进而降低网络运营成本。在未来的研究工作中将增加针对不同区域甩挂运输的算例，为公路港甩挂运输企业提供更为精细的指导。