长江集装箱多式联运路径优化动态规划算法

李 俊，梁晓磊+，赵 胜，张 煜

(1.武汉科技大学 汽车与交通工程学院，湖北 武汉 430065；2.福建工程学院 交通运输学院，福建 福州 350108；3.武汉理工大学 港口物流技术与装备教育部研究中心，湖北 武汉 430063)

0 引 言

已有的集装箱多式联运路径优化研究大多将问题转化为最短路问题，以总成本最小为目标，基于模型构建、算法设计及仿真分析等方法实现问题求解[1,2]。Hao等[3]基于动态规划方法构建优化模型，利用动态规划算法求解。Tsao等[4]考虑碳排放影响，引入非线性优化方法实现问题优化。李敏[5]构建了长江经济带中段多式联运网络优化模型。陈伟[6]引入时间窗约束构建模型，采用遗传算法寻优。刘清等[7]构建多目标优化模型，并转化为单目标后基于遗传算法求解。汤银英等[8]构建双目标优化的0-1整数规划模型，采用非支配排序遗传算法(NSGA-II)求解。范方玲子等[9]构建多目标路径优化模型，设计遗传算法求解。任刚等[10]构建中欧集装箱多式联运路径选择优化模型，采用遗传算法寻优。Bok等[11]针对集装箱化货物运输需求，提出多式联运路径选择模型，并通过构建PC数据实现模型验证。Wang等[12]考虑降低碳排放，基于Witness仿真软件实现多式联运路径参数动态计算。陈钉均等[13]面向绿色多式联运，基于MATLAB仿真实现问题求解。

综上所述，已有研究大多基于已有算法改进实现问题求解，且对不同货流带来的路径通过能力、节点接收及中转能力之间的相互干涉影响也少有关注。因此，本文从长江集装箱多式联运实际需求出发，考虑不同货流运输需求及其时间窗约束，研究其模型构建与算法设计。

1 问题提出

集装箱多式联运是两种及以上交通运输方式相互衔接、转运来共同完成集装箱运输需求的一种复合运输方式。在集装箱多式联运网络中，往往包含多个不同的节点，且在每个节点存在多种运输方式可以选择，如何确定各节点的运输方式选取，为不同货流确定最佳路径方案，保证运输成本最低，是多式联运路径优化关键所在。

对于长江集装箱多式联运路径优化问题而言，需要综合考虑不同货流运输需求以及网络中路径与节点服务能力限制，制定出多式联运总费用最小的路径方案。具体来说，在满足不同货流运输需求前提下，需要考虑的约束包括货流时间窗限制、货流最大运输成本、路径最大通过能力、节点接收及中转能力等。多式联运总费用则包括不同节点间的运输成本、中途节点的转运成本和存储费用、错开时间窗带来的终点存储费用和逾期惩罚费用等。

2 模型构建

2.1 假设条件

从长江集装箱多式联运特点和现实约束出发，做出以下建模假设：

(1)考虑水路、公路和铁路3种运输方式；

(2)仅考虑20 ft标准普通集装箱，暂不考虑其它尺寸和类型的集装箱；

(3)运输途中任一节点至多可换装一次；

(4)各种运输方式及各货流基本信息已知。

2.2 数学模型

(1)集合

N表示多式联运路径中节点集合；

K表示多式联运路径中节点间运输方式集合；

O表示多式联运路径中所有起点集合，O⊂N；

D表示多式联运路径中所有终点集合，D⊂N；

M表示货流集合。

(2)参数

vk表示第k种运输方式的运输速度(km/h)， ∀k∈K；

Tkk′表示由第k种运输方式转换为第k′种运输方式的单位转运时间(h)， ∀k,k′∈K；

Um表示货流m包含的20 ft集装箱量(TEU)， ∀m∈M；

qm表示货流m的运输重量(t)， ∀m∈M；

Cmmax表示货流m最大可接受运输费用(元)， ∀m∈M；

ξi表示在节点i单位时间单位集装箱的存储费用(元/TEU·h)， ∀i∈N；

Bjk表示节点j对第k种运输方式的最大接收能力(t)， ∀i,j∈N，k∈K；

Qijk表示从节点i到节点j第k种运输方式的最大路径通过能力(t)， ∀i,j∈N，k∈K；

α为载运系数。

(3)决策变量

(4)模型

以运输总费用最小为目标，构建长江集装箱多货流多式联运路径优化的0-1整数规划模型

3 算法设计

深度优先遍历算法属于搜索树或图算法的一种，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。基于深度优先遍历的两阶段多式联运路径优化动态规划算法设计如图1所示。其中，第一阶段根据输入的货流、节点以及时间窗等数据，完成当前不同货流所有可行路径的遍历与计算；第二阶段以不同货流所有可行路径方案为初始输入条件，利用动态规划算法完成最优多式联运路径优化。

图1 算法总框架

3.1 第一阶段

第一阶段是在深度优先算法的基础上为每个节点赋予属性，以模拟货物中转、等待等情况。该阶段主要包含4个模块，其功能描述如下：

(1)模块1：货流离开当前节点时间计算。根据货流到达当前节点时间，确定货流在该节点处的发车班次，得到货流离开时间；

(2)模块2：中转费用计算。判断货流在当前节点处中转情况，若发生中转，则在总费用中加入中转费用；

(3)模块3：集截货时间计算。根据货流到达下一节点采用运输方式得到当前节点处的集截货时间等数据；

(4)模块4：存储费用计算。判断货流是否在当前节点时间窗内到达，若早于某一班次集货时间或晚于截货时间，则在总费用中加入存储费用。

综上，算法第一阶段设计如图2所示，图中“变异”表示把集合中遍历过的元素数据替换为一个极大数，避免重复遍历。

图2 算法第一阶段设计

3.2 第二阶段

集装箱多式联运中不同货流之间会相互叠加影响。节点中转能力和路径通过能力约束下，不同货流的运输路径选择产生干涉影响，需要进行整体优化和动态规划寻找全局最优。以第一阶段得到的不同货流所有可行路径方案为输入，进行算法第二阶段优化设计，求解多式联运最优路径方案。算法第二阶段设计如图3所示。

图3 算法第二阶段设计

4 算例研究

4.1 算例设计

从长江集装箱多式联运现状出发，选取长江沿线5个关键节点(重庆、宜昌、武汉、南京、上海)，各节点间均有公路、铁路和水路3种运输方式供选择。设计3条货流展开算例研究，具体信息如下：①货流1从重庆至南京，途径宜昌和武汉，包含20TEU集装箱；②货流2从武汉至上海，途径南京，包含15TEU集装箱；③货流3从宜昌至南京，途径武汉，包含10TEU集装箱。

4.2 算例参数

各种运输方式的相关参数设置为：铁路运输速度为80 km/h，成本为0.135元/(t·km)；水路运输速度为24 km/h，成本为0.03元/(t·km)；公路运输速度为100 km/h，成本为0.35元/(t·km)[5]。3条货流的最大运输成本限制依次为16万元、7万元和7万元。其它数据设计参见表1至表6。

表1 不同节点间不同运输方式距离

4.3 算例求解

4.3.1 不同货流可行路径方案

所有集装箱按20 t/TEU计算箱重。算法采用Python 3.7编程实现，所有算例均采用笔记本电脑(Intel Core I5-6200U, 2.30 GHz,8 GB RAM)运行求解。

对于货流1，全部理论路径共27条，见表7。其中，满足时间窗、最大成本、路径通行能力在内约束的多式联运可行路径为方案11，采用斜体标注(以下表格相同处理)。

对于货流2，全部理论路径共9条，见表8。其中，满足时间窗、最大成本、路径通行能力在内约束的多式联运可行路径位方案5和6。

表2 不同运输方式班次信息/h

表3 节点加收费用信息

表4 货流时间窗约束及惩罚费用

表5 道路能力约束/t

表6 节点中转能力约束/TEU

表7 货流1多式联运可行路径方案(部分)

表8 货流2多式联运可行路径方案

对于货流3，全部理论路径共9条，见表9。其中，满足时间窗、最大成本、路径通行能力在内约束的多式联运可行路径为方案4至方案8。

表9 货流3多式联运可行路径方案

4.3.2 集装箱多式联运最优路径方案

同时集装箱多式联运不同货流运输任务时，与不同货流单一考虑相比，需考虑所有货流带来的节点接收能力、中

转能力、班次运行能力以及路径通过能力之间的相互影响，较单一货流的路径优化问题更为复杂。综合考虑不同货流间相互干涉影响，得到集装箱多式联运总成本最低的路径方案见表10。由于受武汉至南京间铁路运输方式道路通过能力约束，在货流1和货流2均选择费用最低路径时，货流3仅能选择费用第二低的方案6。

表10 集装箱多式联运最优路径选择

4.3.3 时间窗约束松弛分析

以货流2为例，多式联运路径到达时间与总成本之间的关系趋势如图4所示。从图4可以看出，路径的到达时间与总费用之间大体呈现负相关，因此如果调整到达时间，即将货流的时间窗约束后移，可得到总费用更低的路径方案。

图4 货流2路径到达时间与总费用关系趋势

例如将货流2的时间窗约束由[222,246]调整为[222,251]，则此时货流2的全部可行路径方案见表11。从表11中可看出，通过适当松弛时间窗约束可有效降低集装箱多式联运总成本。原最优路径6的总费用为33 980.75元，调整后最优路径9的总费用为12 938.75元，下降比例明显。

表11 时间窗调整后货流2可行路径方案

4.3.4 班次信息调整分析

如表2所示，在集装箱多式联运中各种不同运输方式均按固定的时间控制班次到发，因此不同货流抵达最终目的节点的到达时间与运输方式的班次信息密切相关，同时班次信息的调整也可能会对不同货流在中途节点的存储费用、最终节点的存储费用或逾期费用等产生影响。

现以货流2为例，尝试将表2不同运输方式班次信息中的首次截货时间提前5小时展开分析。调整后，货流2所有路径方案的变化情况见表12。从表12中可以看出，由于提前首次截货时间带来了班次提前发出，使得货流2的所有路径方案到达时间均提前5 h。

表12 调整班次信息后货流2路径方案变化情况

此时，货流2的可行路径方案见表13。从表13中可看出，通过适当调整运输方式的班次信息可有效降低集装箱多式联运总成本。原最优路径6的总费用为33 980.75元，调整后最优路径9的总费用为13 688.75元，下降比例明显。

表13 调整班次信息后货流2可行路径方案

5 结束语

本文从长江集装箱多式联运运输需求及其时间窗限制出发，以运输总费用最小为目标构建了集装箱多式联运路径优化模型，并设计基于深度优先遍历的多式联运路径优化动态规划算法实现求解。算法包含两阶段：第一阶段通过网络遍历求解得到不通货流可行路径方案集；第二阶段以其作为输入，实现多式联运最优路径方案选取。算例研究表明：适当调整货流时间窗约束或运输方式班次信息可得到总费用更低的路径方案；算法可实现长江集装箱多式联运路径优化，可为实际制定路径方案提供参考。后续将针对算例数据的准确性以及节点更多的大规模问题展开研究。