0 引言

随着全球经济和贸易的不断融合，跨国运输联系日益频繁，多式联运作为一种现代化的运输组织方式，能够最大限度地发挥各种运输方式的优势，从而实现更高效的资源利用、更长的运输全程距离以及更好的综合效益。近年来，新冠疫情的爆发为当前国际集装箱运输带来了更大的机遇和挑战。一方面，订单和运量暴增，国际集装箱运输价格上升到之前的数倍甚至十倍；另一方面，由于疫情管控与工人停工等造成国际集装箱运输的时效延长，普遍存在延时问题。国务院也提出要大力发展多式联运，优化运输结构，提升运输效率，降低运输成本^[1]。因此，在运输路径选择中，如何同时实现成本和时效两个方面的最优化，是一个迫切需要解决的难题。

对于多式联运路径优化问题，国内外学者进行了很多富有成效的研究。Dib等^[1]在综合分析的基础上对路径选择结果的影响因素进行了总结分析，通过实证分析方法发现运输时间会影响路径选择并基于此而建立了路径选择模型。Idri等^[2]在调查研究的基础上构建了多式联运模型，并通过最短路算法完成最优路径求解。Boz · ejko等^[3]在考虑影响铁路运输因素的基础上，构建了货运路径选择模型。Gräbener等^[4]以多式联运为研究对象，全面且系统地剖析了其多目标优化问题，并引入了Martins算法。在多式联运路径选择方面，除了考虑运输时间，部分学者也选择将运输成本作为模型的目标函数^[5-6]。国内有关多式联运路径优化的研究具体可分为以下两个方面：(1)研究低碳多式联运路径优化问题, 如：刘松等^[7]在考虑碳排放限制、冷藏费用、货损费用等因素的基础上，通过遗传算法研究冷链集装箱多式联运的路径优化。袁旭梅等^[8]构建了不同低碳政策下的模糊多式联运鲁棒优化模型，研究发现不同的碳排放政策均可控制碳排放，但减排力度存在差异。刘学之等^[9]将碳税机制引入到交通运输行业，研究了该行业下最优的低碳多式联运组合方式和路线。(2)研究不确定性条件下的多式联运路径规划问题。李珺等^[10]在研究多式联运路径优化过程中，考虑了运输时间、中转时间、客户需求和中转集拼货运量4种混合不确定因素。陈汩梨等^[11]考虑了运输和转运环节中的不确定性以及客户个性的时间需求。张旭等^[12]研究了市场需求和运输时间双重不确定因素对多式联运路径优化的影响。刘松等^[13]以应急物资为研究对象，在市场需求和运输环境双重不确定情况下，构建了应急物资多式联运可靠路径模型。此外，也有部分学者将以上两个方面相结合，研究不确定性因素和低碳发展下多式联运路径优化问题^{[10, 12, 14]}。以上研究均是单目标规划问题，以运输时间或者运输成本作为目标函数。而本研究将建立多目标规划，在多式联运中同时实现运输成本和运输时效的最优化。

随着研究的不断深入，部分学者也探究了多目标规划问题。Topaloglu等^[15]针对运输过程中的车队管理问题，结合相关算法建立了综合模型。Ayed等^[16-17]综合各方面因素构建了多式联运路径选择模型，旨在有效解决城市道路拥堵问题。Ayar等^[18]针对海铁联运方面存在的问题，构建了多目标最优路径规划模型，以便控制运输成本和减少滞港时间。Cho等^[19]构建了WCSPP模型，该模型通过双目标动态规划算法的应用可以实现成本和时间的双重兼顾。Ben-Akiva等^[20]以客流预测为研究内容，构建了Logit模型，同时在货运量预测方面构建了ADA模型。上述模型在很多国家进行了应用并取得良好效果，其有效性得到证明。Barceló等^[21]以时间作为目标函数，通过构建实时决策模型来提升城市货流分配效率，旨在有效解决货流分配方面存在的问题。张敏等^[22]将运输成本、碳排放成本和客户满意度作为目标函数，通过多目标规划研究了低碳多式联运问题。上述多目标规划研究均未考虑货物时间价值，集装箱箱型等因素，而本研究构建的双目标优化模型考虑了上述因素的影响。并且，为了更好地解决多式联运问题，本研究也改进了传统Dijkstra算法。

综上，随着多式联运的快速发展，国内外学者都进行了一系列深入研究。现阶段的多式联运路径规划模型，包括单目标模型和多目标模型。单目标规划模型常见的目标函数包括路程最短化，成本最小化等等。多目标规划模型则包括两种常见模式: 第1种是目标权重约束设计; 第2种是目标权重求解。但是就现阶段而言，对国际集装箱多式联运的多目标规划模型的研究较少。随着全球经济化的发展，国际货物运输需求逐年递增，市场主体对货物运输方案的要求以及运输企业的服务水平也逐渐提高^[23]。而本研究以国际物流运输为研究对象，对国际集装箱多式联运最优路径规划进行研究。本研究的创新之处主要体现在以下两个方面：(1)在国际集装箱多式联运模型设计中考虑最小运输成本、最小运输时效两个目标规划模型，并采用权重分配将其转化为单目标规模型，更有现实价值。其中，最小运输成本模型在传统基础上考虑了相对微观的决策影响因素，如箱型、多式联运中转时间、多式联运等待时间等；(2)在模型求解算法上，为了让传统Dijkstra算法更好地解决多式联运问题，从3个方面对其进行改进：考虑有向带权的连通图，循环多顶点标号，增加交通工具类型元素。

1 模型描述 1.1 问题描述

探究国际集装箱运输最优路径规划问题，问题可用已知的源G=(V, E, W, T)来表示。其中，V为国际集装箱多式联运过程中的节点组合，包含运输起点、运输中点和运输终点。E为节点之间的运行方向。W为两两节点组成的权值，传统权值主要是线路长短，由于研究对象为多式联运的最优路径规划问题，因此权值为多目标规模模型的求解结果。T则为运输交通工具类型，即两两节点组成的线段所需的交通工具类型。

1.2 研究假设

具体假设如下所示：

(1) 各个节点换装最多只有一次。多式联运下的货物运输节点可以选择换装或者不换装两种决策，但换装之后会确定相应转运方式。

(2) 运量不可细分，具有整体性。多式联运下的货物是统一整体，不可将其划分成不同批次进行独立运输。

(3) 运输路线不能改变，具有固定性。另外，运输速度和单位成本也具有固定性。

(4) 运输过程集装箱的适配性。多式联运下的集装箱均采用国际标准，不存在所谓适配问题。

(5) 排除外部意外因素的影响。例如交通拥堵、天气恶化等因素。

(6) 节点之间运费的稳定性。多式联运下节点的运输费用，不考虑淡旺季浮动的影响。

1.3 符号说明

使用到的符号及其具体含义如下所示：

决策变量：

K为运输方式，k=1，2，3，4分别为公路、铁路、水路和航空运输；N_r为第r种类型的集装箱数量，单位为箱；x_{i1, i2}^k为节点i₁至节点i₂之间采用第k种运输方式；y_i1^kl为在节点i₁时是否将运输方式从k转换为l，若转换，则y_i1^kl=1，否则，y_i1^kl=0。

其他变量：

O为国际集装箱多式联运网络结构的起点；M为国际集装箱多式联运网络结构的终点；M_i为第i个城市节点，起点O到终点D的中间节点总数为M个；r为集装箱的类型，r=1为20′通用集装箱、r=2为40′通用集装箱；N为集装箱的总数量，单位为箱；q_r为第r种类型集装箱承载货物的重量上限，单位为kg；Q为运输货物的总重量，单位为kg；L_{i1, i2}为节点i₁至节点i₂的运输距离，单位为km；f_{i1, i2}^r为节点i₁至节点i₂的r类型集装箱的箱次费，该项费用按不同箱型分别确定；c_{i1, i2}^k为在节点i₁到i₂采取第k种运输方式的单位运输成本；c^kl_i2为在节点i₂实行运输方式k到l变动的固定换装费用；T_{i1, i2}^k为使用运输工具k，从节点i₁至节点i₂所需时间；V_k为第k种交通运输工具的平均运输速度，单位为km/h；s为第s类中转作业，即4种运输方式有6种运输中转情况，如公路(k=1)到铁路(k=2)之间的中转为一类，以此类推；T_{i1, i2}^s为第s类中转作业所需中转时间，单位为h；T_{i1, i2}^w为衔接等待时间，单位为h。

2 模型构建 2.1 运输成本节约模型

从节点i₁到节点i₂的国际集装箱多式联运的运输成本如式(1)所示：

(1)

式(1)为从节点i₁到节点i₂的运输成本主要由集装箱使用费、运输费、中转费这3部分组成。

其中，集装箱使用费计算如式(2)所示：

(2)

集装箱运输费用计算如式(3)所示：

(3)

集装箱中转费用计算如式(4)所示：

(4)

因此，从起点O到终点D的国际集装箱多式联运运输的总成本Z如式(5)所示：

(5)

需要满足如下的约束条件：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

其中，式(6)为集装箱中转换装逻辑约束；式(7)为集装箱承载重量要满足运输的需求；式(8)为两个节点之间只能采用一种运输模式；式(9)为在运输节点的换装约束；式(10)为集装箱数量之间的关系。式(11)~(12)是变量本身应满足的条件，式(11)为交通运输方式的类型，式(12)为决策变量x_{i1, i2}^k和y_{i1, i2}^k必须是二进制约束。

2.2 最短运输时间模型

从节点i₁到节点i₂的运输时间如式(13)所示：

(13)

式中，主要包含3部分：第1部分为在途运输时间，具体计算式为：；第2部分为中转作业时间，T_{i1, i2}^N=y_i1^klT_{i1, i2}^SN；第3部分为衔接等待时间，即。

因此，从起点O到终点D的运输总时间T如式(14)所示：

(14)

式(14)需要满足如下的约束条件：

(15)

(16)

(17)

(18)

(19)

其中，式(15)~(18)与模型2.1中的约束条件有着相同的含义，在此不再赘述。式(19)为运输时间要小于客户所能承受的最大范围。

2.3 货物时间价值模型

周伟^[24]认为将成本模型与效率模型通过权重设计转化为单目标函数，需将效率模型与成本模型的单位统一。因此，将引入货物时间价值函数，实现集装箱多式联运运输时间模型向货物时间价值模型的转换，进而得出最优解，确定最优路径。

为降低研究难度，本研究选择线性函数展开研究。考虑到货物运输持续时间不会过长，且货物生命周期有限，因此本研究以月贬值率为指标。那么货物时间价值函数具体如式(20)所示：

(20)

式中，P_max为货物最开始运输时(T=0)，单位集装箱的运输价值；η和k分别为货物的入箱率和货物月贬值率。

2.4 双目标优化模型

由于运输成本与运输时间本身之间存在着矛盾。通常运输时间越短，运输成本则越高，如何平衡二者关系是本研究需要探究的主要问题。在此，通过线性加权法将双目标转化为单目标，以此确保规划模型的可解性。即根据不同类型客户需求偏好灵活设计子目标模型权重，继而求解模型最优解。

(21)

式中，α为成本偏好系数；β为时间偏好系数。

具体的双目标优化函数如式(22)~(23)所示：

(22)

(23)

双目标优化模型下的约束条件与模型2.1和2.2中的约束条件相同，即式(6)~(12)以及式(15)~(19)，在此不再赘述。

3 算法设计

求解“最短路径”的算法有很多，其中比较常见的算法包括Dijkstra算法，Bellman-Fold算法，SPFA算法，Johnson算法等等。本研究主要采用Dijkstra精确算法求解最优路径。

3.1 传统Dijkstra算法

最优路径规划模型涵盖两个基本要素：运输成本与运输效率。王涛等^[25]借助时间价值函数与权重系数实现了多目标向单目标的转换。本节算法设计立足国际集装箱，多式联运实际。在Dijkstra算法实际应用中，需要输入的参数涵盖了基本查询条件，比如：始发站、终点站以及出发时间。因此，研究可选择精确串行算法中的Dijkstra算法作为本研究模型求解算法。

Dijkstra在最短路径确认方面提出了标号法，该方法也是现阶段被学者广泛认可的一种算法。该算法主要是针对权图中最短路径问题而采取的算法，可以确定某一顶点到其他各与顶点之间的最短路径。标号法目前在很多领域都得到非常广泛的应用，无论是在物流运输，还是在科学测绘等方面都取得良好成果。例如在高速公路收费、智能运输系统应用等方面利用标号法实现了有效突破，在确定最短路径方面发挥了重要作用。因此，很多学者开始探究基于Dijkstra的标号法，通过对这一算法进行优化和改进来更高效的探究最优路径。

相较于其他类型算法，Dijkstra算法的最大优势是应用了标号法。设G= (V, E, W)，该式中V为所有顶点的集合，E为两两顶点之间形成的路径，W为路径对应的权重系数集合。W_ij是大于等于0的数值，当i与j出现不相邻的情况，那么可出现W_ij=∞。而Dijkstra算法的主要使用范围是对图G中任意两两节点之间的最短距离进行求解。

Dijkstra算法具体操作方法是：对起始点进行永久性标号操作，并将其记作v₁；求解下一个能够满足永久性要求的顶点v_i，在G中的顶点v_i处标记永久性p标号l_i^(r)*，并将该点归入通过集，即P_r=P_r-1∪ {v_i}，T_r=T_r-1-{v_i}，从头到尾对T_r进行执行操作，直到T_r是空集(ϕ)的时候，退出迭代；不然就继续开展下一步的计算步骤，即对T_r中的临时性t标号进行迭代计算，可以获取第2步下的永久性标号顶点l_i^(r)*以及新的临时性标号l_j^(r)=min {l_j^(r-1), l_i^(r)*+w_ij}。接下来，令r←r+1，转到第2步进行计算并构成循环，只有当G中所有顶点都变成p标号时，退出循环，Dijkstra算法计算结束。

3.2 Dijkstra改进算法 3.2.1 Dijkstra算法的局限性

(1) 尚未建立完善的算法退出机制。在一些有向带权联通图中，原有的Dijkstra算法并不具备可行性。

(2) 无法满足多式联运过程中多个顶点可同时获得p标号的需求。

(3) 无法满足多式联运交通工具多样性需求。本研究将多式联运作为研究对象，有向带权交通图涵盖了节点、方向、权以及交通工具类型k，所以该算法难以针对交通工具组合，选择提供有效的解决之道。

3.2.2 Dijkstra改进算法的符号设置

(1) 假定G中顶点v₁与v_i的最短路径的权重大小为l_i^{(r, k)*}，其中，r是大于等于0的数值，那么这一数值也标志着G中某个顶点v_i在第r步获取了永久性p标号，标号记录为l_i^{(r, k)*}；

(2) 假定G中顶点v₁与v_j的最短路径的权重大小上限时l_j^{(r, k)}，那么这一数值也标志着G中有一个顶点v_j在第r步获取了临时性t标号，标号记录为l_j^{(r, k)}；

(3) 假定P_r={v|v为已获得永久性p标号的顶点}，那么标志着第r步通过集，r是大于等于0的数值；

(4) 假定T_r=V-P_r，T_r标志着第r步的未通过集。

(5) 假定N_r为第r步获取永久性p标号的点集合。

3.2.3 Dijkstra算法的改进原理

针对传统Dijkstra算法无法满足多式联运路径规划的局限性，提出以下改进思路：

(1) 算法退出机制上的改进方案：一般来讲，传统Dijkstra算法在求解最优路径的应用中，主要针对没有方向指标的联通图，不适应存在不连通环节的有向带权联通图，但实际上集装箱多式联运路径规划必然是有向带权联通图，同时还有两个顶点间不连通的概率存在。因此，研究将Dijkstra算法的退出机制改为：T_r=Ø, r≥0或l_i^(r)*=∞(l_i^(r)*=min{l_j^(r-1)}, r≥1)。

(2) 多个顶点可同时获得p标号的改进方案。传统Dijkstra算法每一步标记一个永久性p标号顶点，实际上集装箱多式联运路径规划过程中，多个顶点可能在某次循环下都满足永久性p标号的条件。设, r≥1，当多个顶点同时获取永久性p标号时，通过集就可以调整成：P_r=P_r-1U {v_i}；那么没有通过的集合就可以调整成：T_r=T_r-1-{v_i}。

(3) 多式联运交通工具多样性需求的改进方案：传统Dijkstra算法涉及的元素为顶点、方向、权，但多式联运需增加运输类型元素，即改进后Dijkstra算法需包含顶点、方向、权、运输类型这4个元素。本研究涉及的运输方式主要用k表示，Dijkstra算法要针对永久性p标号以及临时性t标号来做调整与改进优化，把原有的l_i^(r)*改为l_i^{(r, k)*}，把原有的l_j^(r)改为l_j^{(r, k)}。

3.2.4 Dijkstra改进算法的求解步骤

本研究对传统Dijkstra算法进行改进之后，其计算过程主要包括3个步骤：

(1) 首先：起始点v₁获取永久性标号；l₁^(0)*=0，P₀= {v₁}，T₀=V-{v₁}，除起始点v₁外的其它顶点v_j获得临时性t标号，且l_j⁽⁰⁾=w_ij。

(2) 第2步：求解下一个永久性p标号顶点v_i；设, r≥1，N_r=Ø，如果满足minl^(r-1)=∞，结束计算。设v_i∈T_r-1，当l_i^{(r-1, k)}=minl^(r-1)时，在G中的顶点v_i处标记永久性p标号l_i^{(r, k)*}，即，并将v_i纳入通过集，即P_r=P_r-1∪{v_i}，T_r=T_r-1-{v_i}，遍历T_r，直至T_r为空集(Ø)，结束Dijkstra算法；否则进入下一步计算。

(3) 第3步：基于N_r，重新计算未通过集T_r中的临时性t标号；若第2步中的永久性p标号顶点为l_i^{(r, k)*}，则表示新的临时性t标号。对于v_i∈N_r，只有当l_i^{(r, k)*}+w_ij^k < l_i^{(r, k)}，才需要进行修改，此时l_j^{(r, k)}=l_i^{(r, k)*}+w_ij^k。接下来，按照传统Dijkstra算法操作步骤进行计算求解即可。

4 算例分析 4.1 算例数据

本研究选取了某公司由湖南C运往德国H的集装箱货物需求为案例场景，探究某公司多式联运通道的最优选择问题。具体描述如下：目前，某客户的货物需求为电子类产品，共计20个40尺普高箱和30个20尺开顶箱，共50箱货物，由C运往H，可供选择的多式联运通道为华南至西北大通道、华南至中部各省份城市，与国际大通道海运或中欧班列等的结合。具体的运输路径如表 1所述。

除此之外，还需搜集不同交通工具的运输速度、节点之间不同交通方式的运输距离以及运输费用等。相关数据见表 2。

4.2 模型求解及结果分析

基于搜集的模型指标数据，赋予成本模型与效率模型不同权重，求解单目标综合模型的求解结果。从极端值与均值两个角度，分别进行权重设计试验，求解不同权重需求下，国际集装箱运输的最优路径，具体求解结果可见表 3。

当成本偏好系数为α=0.2，时间偏好系数为β=0.8，该类型客户为运输时间偏好型客户，即客户希望运输时间最短。最优路径为“C—Z—H”，该路径下的运输长度P=909 152.2，运输成本为C=1 303 437.2。

当成本偏好系数为α=0.5，时间偏好系数为β=0.5。该类型顾客会综合考虑运输时间和运输成本，此时，最优路径为“C—L—H”，该路径的长度为P=1 025 310.7，运输成本为C=11 957 690.6。

当成本偏好系数为：α=0.8，时间偏好系数为：β=0.2，该类型客户为运输成本偏好型客户，即希望运输成本最小。在此需求下，最优路径为“C—Z—H”，该路径的长度和成本分别为P=982 510.0和C=786 963.3。

综上，本研究构建的国际集装箱多式联运最优路径规划模型与算法，可为不同运输目标型客户，提供不同的最优运输方案，能够满足不同类型客户差异化需求，提升运输效率，建立与客户的良好关系。

4.3 最优路径对年度运输总量的影响

对客户而言，除了关注当次的运输成本、运输时间外，也关注路径规划对年度运输总量的影响，接下来，主要讨论这3种路径规划对年度运输总量的影响。

由表 4可以得出，“C—L—H”，“C—Z—H”这两个路径下，年度运输总量相差不大，但“C—L—H”路径的成本较低；而“C—Z—H”这个路径虽然成本较低，但年度运输总量下降明显，因此，在综合考虑成本、时间以及年度运输总量的情况下，“C—L—H”是最优路径。

4.4 改进Dijkstra算法的检验

为了验证本研究构建的Dijkstra改进算法模型在解决多式联运问题中的有效性，本节将引入启发式算法对上述案例进行求解。然后，将这3种不同需求下Dijkstra改进算法模型与混合算法模型的结果进行对比分析。

4.4.1 启发式算法及求解

考虑前文构建的Dijkstra改进算法模型在时间、成本方面进行了权重分配对比，因此，在混合算法的迭代中，也加入了这一因素，分别进行了3次迭代：对成本重视程度较高、对时间重视程度较高、时间成本均衡，关键参数设置为：种群数量为100，选择概率为0.01，变异概率为0.15，信息素初始值为10。表 5给出了3种不同需求偏好下的求解结果，从仿真结果可以看出，3种不同需求偏好求解问题的最终结果差异较大，但时间成本均衡下具有更快的收敛能力。

4.4.2 算法对比

将Dijkstra改进算法模型与混合算法模型结果进行对比见表 6。可以发现，相对于混合算法而言，改进Dijkstra算法求解效果要略微优秀，在这3种需求下，总时间均比较小。成本方面，只有对成本偏好较高(α=0.8，β=0.2) 时，混合算法成本略低于Dijkstra改进算法，其他两种情况，混合算法都是高于Dijkstra算法的，特别是时间成本均衡的情况下，差值相对较大，而这种情况是客户需求做多的情况，充分验证了本研究构建的Dijkstra改进算法模型在解决多式联运问题中的有效性。

5 结论

本研究在考虑货物时间价值，集装箱箱型等因素的条件下，研究集装箱多式联运问题，依次建立运输节约成本、最短运输时间模型，以及整合运输成本和时间加权的双目标优化模型，并对传统的Dijkstra算法进行改进。利用ZH公司的实际案例数据进行算例分析，验证构建的双目标优化模型和求解算法的可行性和有效性，并进一步地探究最优路径对年度运输总量的影响。研究结果表明：(1) 不同运输目标客户的需求偏好会影响多式联运最优路径的选择，进而影响运输成本、运输时效及年度运输总量。(2) 与混合算法相比，Dijkstra改进算法求解效果更优。只有对成本更加偏好时，混合算法在解决多式联运问题时的成本略低于Dijkstra改进算法，而在其他情况下，Dijkstra改进算法求解出的运输成本和时间则更加经济高效，其最大时间节约率和成本节约率分别为30.86%，20.31%。

不足与展望：受限于各方面因素，本研究依然存在不足之处。例如，多式联运过程中不同交通工具的发车时间、作业时间带有一定的预估性，与实际存在一定偏差，实际上不同交通运输方式会有专门的列车时刻表，因此，未来可将列车时刻表与模型算法共同导入智慧系统，实现对国际集装箱多式联运的智能选择。