不确定需求下考虑混合时间窗的多式联运路径优化

邓学平，陈 露，田帅辉

(重庆邮电大学 经济管理学院，重庆 400065)

0 引 言

在经济全球化的背景下，国际物流成为国际贸易的重要实现方式之一。而多式联运在国际物流服务中有着至关重要的作用，推动国际物流的发展。与传统单一运输方式相比，多式联运充分利用了多种运输方式的优点，在运输成本，运输效率以及企业竞争力方面有了较大改进。目前，与多式联运相关的研究比较广泛，其中，多式联运的路径优化问题是研究的核心内容之一，具有重要的研究意义。

目前，国内外有关多式联运有较多研究。针对多式联运优化模型的研究如下：A.Lozano等[1]研究了在多式联运网络中搜索最短路径，运用顺序算法求解模型；Wang和Han[2]将运输成本、中转成本和中转延误成本之和作为总成本，以其最小为模型的优化目标,设计了基于多式联运网络变形以及最短路算法的求解方法,并用算例验证；Boussedjra等[3]通过双向研究策略来构建多式联运网络，同时将运输时间最小作为优化目标并设计遗传算法来求解；Resat等[4]考虑运输成本与运输时间，建立目标函数，并在马尔马拉地区的多式联运网络中应用该模型；Meng等[5]考虑了客户对运输时效性需求，以时间和成本最小为双目标建立优化模型，得到帕累托最优解，求解出满足客户需求下的最优路径；雷定猷等[6]针对长大货物，以最小的运输时间、运输距离以及费用建立目标函数,考虑线路界限、桥梁承重等约束, 建立了针对长大货物的多式联运路径优化模型，并设计了求解算法；李梦良等[7]将灾后应急物资作为多式联运优化的对象,将物资需求量、道路交通状况以及需求优先级作为影响因素,以应急救援的总成本最小、运输时间最短以及未能满足需求的惩罚费用最小为优化目标,运用鲁棒优化理论, 建立了多场景下应急物资的多模态运输优化模型；蒋洋等[8]建立了以运输成本、中转成本为目标函数的多式联运模型，并通过交叉熵算法来求解方法； Liao等[9]和Kim等[10]将碳排放量纳入优化目标，建立基于成本与碳排放量的优化模型，并求解得出最优路径与运输组合；Zhang等[11]考虑了环境成本，并据此建立模型，通过对荷兰集装箱运输网络优化的实例分析，发现价格制度不同，对应配置的运输网络也不相同；Sun等[12]考虑了基于列车计划和碳排放的路径优化问题，以成本最低为优化目标并建模，编程求解。针对求解模型算法的研究如下：熊桂武等[13]考虑了时间窗的约束，设计了正交试验的混合田口遗传算法求解问题；梁晓磊[14]以成本最小化建立目标函数，设计了变邻域粒子群算法来求解；刘杰等[15]基于运输过程总成本和碳排放总量建立多目标函数，同时建立了0-1规划模型,对带精英策略的非支配排序遗传算法进行改进并求解模型；刘丹等[16]基于可持续多式联运建立多目标优化模型,该模型将运输时间、成本和碳排放量最小作为目标函数，同时针对该模型设计了单目标遗传算法和多目标遗传算法联合的求解方式；陈雷等[17]引入碳税机制，将碳排放量转化为经济成本，建立了以货物运输及转运过程产生的运输中转成本和过程中产生的碳排放成本之和最小化为目标函数的优化模型；李珺等[18]考虑了速度服从随机分布的情境下，运用随机优化的方法,建立考虑运输成本和碳排放量的多式联运路径优化模型，将样本平均近似法和粒子群算法相结合来求解该模型。

上述有关多式联运的研究中有较多局限性。对多式联运模型的建立中，多数将货物运量作为确定值，虽便于研究，但是忽略了在货物实际运输的过程中存在季节性需求、突然补货等问题。因此，在安排运输计划时，运输量往往不能确定；对时间窗的考虑一般分为2种：①将目的地的硬时间窗作为约束条件来限制模型；②将其视为软时间窗，并将时间惩罚成本纳入总费用中，同时将碳排放量作为优化目标之一。单一地考虑软时间窗或硬时间窗虽简化模型研究，但忽略了对不同节点时间窗的考虑应该不同。针对模型求解算法，采用蚁群算法、遗传算法较多，虽有较强的鲁棒性，但这些算法仍存在搜索速度较慢，易陷入局部最优的缺点[19-20]。基于以上研究的局限性，本文主要从以下4个方面考虑：①将货物运量视为不确定的，用三角模糊数表示，研究不确定需求情形下的多式联运路径优化问题，可有效避免运力的浪费；②不同于单一时间窗，引入混合时间窗约束，对中间节点设置为软时间窗，允许货物提前或者延迟到达，但需支付一定的费用,对目的地的节点设置为硬时间窗，货物必须在该范围内到达，更符合实际运输情况；③将碳排放纳入考虑范围，同时根据国家碳减排政策，对碳排放总量进行限制；④对粒子群算法进行改进，融入模拟退火算法的思想，能够使粒子在寻优过程中快速跳出局部最优，提高算法收敛速度，求解本文模型。

1 问题描述与模型的建立

1.1 问题描述

假设两地之间需要运输一批货物，货物的需求量不确定，在运输过程中需通过若干节点，相邻2个节点之间可采用多种运输方式，如图1，采用多点间运输网络图的表示形式。O，D分别为起点和终点，中间有若干个节点，有公路、铁路、水路、航空4种运输方式，由于各节点之间可采用不同的运输方式，相对应的时间、成本、碳排放量各不相同。因此，本文旨在混合时间窗约束下，考虑不确定需求，找到一个既让企业对运输成本、时间较为满意，同时又达到碳排放要求的最优运输路线和运输方式。因此，考虑多式联运实际情况和便于建模求解，作出如下假设。

图1 多式联运网络图Fig.1 Multimodal network diagram

1)货物在运输途中只采用一种运输方式，不可进行分割运输；

2)只在节点城市处进行运输方式的转换；

3)在转运节点处，至多进行一次运输方式的转换；

4)在运输过程中，货物的属性状态不发生变化，没有货损情况。

1.2 模型建立

1.2.1 模糊需求分析

(1)

1.2.2 符号说明

1.2.3 模型建立

目标函数为

(2)

(3)

约束条件为

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(2)式表示运输总成本的最小值，包括运输成本、中转成本、时间惩罚成本；(3)式表示整个运输过程碳排放量的最小值；(4)式表示货物在2个节点间运输时间的计算方法，与速度相关；(5)式表示货物从起点运输到目的地节点的整个运输总时间要在规定货物到达的硬时间窗内；(6)式表示整个运输过程产生的总成本应低于托运人的成本限制；(7)式表示整个运输过程中产生的总碳排放量不能超过碳排放限制；(8)式表示货物在2个节点间运输，其货运量须在所选运输方式的运输能力范围内；(9)式表示货物在某个节点中转时，货运量须在所选运输方式的中转能力范围内；(10)式表示每个节点处，货运量的流量平衡；(11)式表示货物运输时，转换运输方式的连续性；(12)式表示货物在运输过程中只能采用一种运输方式，不可拆分；(13)式表示每个节点最多中转一次；(14)式表示决策，被选择该值取1，否则为0。

2 模型求解

2.1 模糊机会约束规划

为将上述模型中的模糊变量明确表达，需将模型转化为确定性形式。最初，由Charnes和Cooper[21]提出机会约束规划的概念，利用置信水平来解决不确定性。在此基础上，1996年Liu和Iwamura[22]首次提出含有模糊参数的机会约束规划相关理论。该理论的核心思想是所做决策需满足模糊约束条件的可能性大于等于某一置信水平，可将模糊机会约束条件转化为确定性的形式，即可得到清晰化的模型表达式。本文主要采用Liu和Iwamura提出的模糊机会约束规划模型，表示为

(15)

Pos{gi(x,ξ)≤0,i=1,2,…p}≥βi

(15)—(17)式中：x是模糊决策向量；ξ是模糊向量；Pos{·}表示{·}里事件发生的可能性；f(x,ξ)为目标函数；gi(x,ξ)为该模糊规划的约束条件；α表示目标函数的置信水平；βi表示约束条件的置信水平，是事先确定的值。

本文构建的多式联运成本-碳排放量模型属于多目标数学模型，目标函数中只有需求量含有模糊参数，因此，通过线性加权法将多目标问题转化成单目标问题，应用上文中提出的理论，可以将模型转化为

(16)

α,β1,β2∈(0,1)

λ∈[0,1]

(17)

以及 (4) 式，(5) 式，(10)—(14) 式。

2.2 算法设计

针对组合优化问题的求解方法，目前的研究主要分为精确算法和启发式算法。本文研究的多式联运路径优化问题包含了模糊需求、运输路径和运输方式的选择、时间窗的约束以及总成本、碳排放量的目标，求解过程中计算量较大，因此，本文涉及的模型不适合用精确算法求解。而启发式算法被更多地应用在求解组合优化问题中，包括遗传算法、粒子群算法等。其中，粒子群算法具有实现容易、寻求最优解等优点，因而在解决实际问题中得到广泛的应用。它广泛用于解决实际问题。粒子从一组随机解开始，迭代来寻求最优解，并通过自适应值评估当前解的质量。粒子通过跟踪个体极值和群体极值的2个最佳值来更新速度和位置。然而，与其他启发式算法一样，在搜索过程中，容易陷入局部最优的情况。而在模拟退火算法中，先设定一个初始温度，温度逐渐下降，在退火过程中，接受比当前解更差的解的概率将以一定的概率给出，并且利用接受的特征跳出局部最优解以达到全局最优解。新的解决方案，接受劣质解决方案的概率将受温度参数控制，并随着温度的降低而降低。因此，利用模拟退火算法的特性可以提高粒子群算法的局部寻优能力，改善其早熟性。

编码与解码设计：采用n×4n×4的矩阵编码，前3列分别表示每条路径由公路、铁路、水路3种运输方式运输的优先级，根据优先级选择当前路径采取哪一种运输方式。第4列表示路径的优先级。根据优先级选择路径。解码时从排列的第1个节点开始，直到到达目的地，根据优先级，选择最优路径以及相对应的运输方式。

具体操作步骤如下。

步骤1初始化各粒子参数，各粒子的初始速度和位置信息；

步骤2对各粒子的适应度进行分析，将各粒子的个体适应值和当前位置储存在个体极值pbest中，选取其中最优适应值并将其个体位置和适应值储存在全局极值gbest中；

步骤3将温度初始化，一般采用设定

t0=f(pg)/ln5

(18)

步骤4在当前温度下，确定每个粒子pi的适应值

(19)

xi,j(t+1)=xi,j(t)+vi,j(t+1)

(20)

vi,j(t+1)=φ{vi,j(t)+c1r1[pi,j-xi,j(t)]+

c2r2[pg,j-xi,j(t)]}

(21)

(22)

步骤6计算粒子新的目标值，并更新各粒子的pbest和gbest，然后进行退温操作，表示为

tk+1=λtk

(23)

步骤7设置最大迭代次数为200，根据是否符合其判定条件，判断是否停止搜索，若满足，则停止搜索过程并输出最优结果，否则返回步骤4。

3 实例验证

3.1 实例数据

图2 多式联运算例网络图Fig.2 Network diagram of multi-join operation

表1 节点间的距离Tab.1 Distance between nodes km

表2 运输方式转换的碳排放量Tab.2 Carbon emissions from transportation mode conversion

表3 运输方式转换的单位成本(单位：元/t)和中转时间(单位：h)Tab.3 Unit cost of transportation mode conversion (unit: yuan / t) and transit time (unit: h)

表4 节点间的最大运输能力Tab.4 Maximum transport capacity between nodes t

续表

表5 节点处的最大中转运输能力Tab.5 Maximum transfer capacity at the node t

表6 节点的时间窗Tab.6 Time window of the node

3.2 案例分析

为了验证本文设计应用的基于模拟退火的粒子群算法的性能，运用MATLAB编程，分别采用粒子群算法和基于模拟退火的粒子群算法对多式联运多目标优化模型进行求解。参数设置为N=10，G=200，c1=1，c2=1，ωmax=1.2，ωmin=0.5，λ=0.5,并将2种算法的求解结果进行对比。多次实验取最优解，得到如图3—图5的收敛曲线。表7为具体求解结果。

图3 粒子群算法收敛曲线Fig.3 Particle swarm algorithm convergence curve

表7 2种算法求解结果Tab.7 Results of two algorithms

图5 粒子群算法与基于模拟退火粒子群算法收敛曲线对比Fig.5 Convergence curve comparison between particle swarm optimization and particle swarm optimization based on simulated annealing

根据图3、图4这 2种算法的收敛图以及图5直观的对比图，从迭代次数方面看，粒子群算法在接近120代开始收敛，而基于模拟退火的粒子群算法在40代以内开始收敛。基于模拟退火的粒子群算法在求解收敛速度上较粒子群算法更快，具有求解多式联运问题的优越性。同时也可看出，基于模拟退火粒子群算法求解最小值的解明显优于基本粒子群算法。根据表7的2种算法的具体求解结果看，2种算法在总成本、碳排放总量和总时间有明显差距。粒子群算法求解的结果为总成本119 925.69万元，碳排放总量12 587.9 kg，总时间60.32 h。而改进粒子群算法求解的结果为总成本109 275.54万元，碳排放总量9 715.97 kg，总时间41.08 h。总成本减少了8.88%，碳排放量减少了22.82%，运输总时间减少了31.9%。两者结果相比，基于模拟退火的粒子群算法的寻优结果明显比粒子群算法更好。从程序运算时间上看，粒子群算法运行时间为21.04 s，基于模拟退火的粒子群算法运行时间为18.92 s。由以上分析可知，基于模拟退火的粒子群算法具有很强的寻优能力，在收敛速度以及运行时间较粒子群算法都有明显优势，也能满足多式联运路径多目标优化问题对求解算法的要求。

图4 基于模拟退火的粒子群算法收敛曲线Fig.4 Convergence curve of particle swarm optimization algorithm based on simulated annealing

为了进一步分析模糊运量对路径优化的影响，分别改变置信水平α，β的值并求解，进行灵敏度分析，如图6。

图6 α的灵敏度分析Fig.6 Sensitivity analysis of α

由图6可知，保持β1，β2的值不变，随着α的增大，目标函数值也不断增大。这表明在现实生活中，随着客户对需求量的满意度增加，总运输成本和碳排放量也会增加。为了提高客户对需求量的满意度，多式联运承运人需对运输路径、运输方式进行改进，在综合考虑总费用、碳排放量的情况下，选择最合适的置信水平，在满足客户对需求量的要求的同时也减少运力的浪费，为承运人决策提供依据。

保持α的值不变，分别改变β1，β2的值，目标函数值不发生变化，如图7。由于本实例的多式联运运输规模较小，公、铁、水3种运输方式的运输能力以及节点的中转能力都大于等于需要运输的货物量，因此，本案例中，改变节点和运输路径的运输中转能力不影响路径优化选择。但在一些实际情况中，会出现某段路径运输能力不足或中转节点中转能力不足，只能更改运输路径。因此，增强各种运输方式的运输能力和节点中转能力可以有效地降低运输成本，优化运输路径。

4 结束语

本文首先考虑了客户需求的不确定性，运用模糊机会约束规划理论与三角模糊函数对模型进行转化，大大降低了由于需求量不确定导致的运力浪费，也使物流企业能够及时对多变的市场需求进行处理，同时引入了混合时间窗约束，对中间节点设置软时间窗，目的地节点设置硬时间窗，在考虑碳排放量的基础上按照国家碳减排政策对碳排放总量进行限制，以此构建了基于总运输成本和碳排放量的多目标多式联运优化模型。同时，对基本粒子群算法进行改进，设计了基于模拟退火的粒子群算法对该模型进行求解。结合案例分析，该模型能够平衡总运输成本与碳排放量的关系，优化运输路径，基于模拟退火的粒子群算法从多方面优于基本粒子群算法。同时通过对置信水平α，βi进行灵敏度分析，可知不确定的货物运量以及节点运输能力与中转能力会影响路径优化的结果，从而为多式联运承运人提供合理的决策依据，对多式联运的发展有一定的意义。

由于多式联运问题的复杂性，本文仍存在需要进一步研究的问题。后续工作将考虑运输过程中时间的不确定性、在货物运输过程中，货物发生损耗的情况以及天气等自然条件的影响。