不确定需求下考虑动态转运时间的多式联运路径选择

汤 瑞,胡军红,闻成维,张雯婕

(南京工业大学 交通运输工程学院,江苏 南京 211800)

国内外发展经验表明,多式联运能够提高运输效率30%左右,降低运输成本1/5左右,促进节能减排1/3以上[1]。为有效组合多式联运中的运输方式与路径,需要对运输路线进行合理的规划。在天气和交通等因素的影响下,路线规划具有不确定性,制订运输任务前考虑到不确定性,有助于有效避免不确定因素带来损失。近年来,国内外学者对不确定运输问题进行了深入研究,主要包括运输需求的不确定[2-4]、目的地时间窗的不确定[5-6]、运输时间及中转时间的不确定[7-9]、低碳因素相关的不确定[10]等。另外,在货物运输的过程中,存在季节性需求、突然补货等问题,安排运输计划时,运输量往往不能确定。本文探究运输需求不确定的多式联运路径选择。

在实际运输时,多式联运转运节点处由于列车与船舶班次固定,货物装卸、申请和调度流程复杂等原因,不同运输方式自身的转运时间不同,加之货运量的大小也会严重影响转运时间的长短,而转运时间的长短会对运输路径的选择产生一定的影响,因此,构建路径选择模型时必须全面考虑转运时间的影响。有学者考虑班期的限制,以运输时间最短为目标[11],或考虑时间惩罚成本以综合成本最低为目标[12-13],但这些学者都假设不同运输方式的转运时间相同,与实际运输状况不符。虽然部分研究在需求量不确定下考虑了不同运输方式的转运时间不同[14-15],但仍忽略了需求量与转运时间是正相关的。因此,有学者设置货运量与转运时间线性相关[16],但没有考虑货物完成中转后需要等待发车的时间。

综上分析,本文考虑运输需求与转运时间动态相关,探究不确定需求下考虑动态转运时间的多式联运运输方式及路径的选择,构建以运输费用、碳排放费用及运输总时间综合最低为目标的路径选择模型,以期能够有助于促进货物运输的经济性,提高运输服务的质量。

1 问题描述与建模

1.1 问题描述

一批需求量不确定的货物从出发地O至目的地D,运输过程中要经过多个中转节点进行换装或重新编组,中转节点可以选择公路、铁路、水路中的一种或多种运输方式。如图1所示,采用多重边法构建运输网络图,不同运输方式的中转时间、运输成本和碳排放量并不相同。本文以运输费用、碳排放费用及运输总时间综合最低为目标,研究需求不确定下的货物多式联运路径选择。三角模糊数是表达判断比较时给出的模糊量范围:最低可能值、最可能值和最高可能值。多式联运经营人可以通过以往数据分析货运量的变化范围,因此,使用三角模糊数[17]表示不确定货运量较为恰当。为便于建模,假设:① 同批货物在运输时不可以分割,相邻节点间一次只选择一种运输方式;② 同一节点货物只能转载一次或不转载;③ 每个节点同批货物最多只能经过一次;④ 在途运输成本与货运量及距离呈正相关,不受运输途中其他因素的影响;⑤ 每个节点之间各种运输方式的承载力以及节点的中转能力已知。

图1 多式联运网络模型Fig.1 Multimodal transport network model

1.2 模型构建

总运输费用(F)和总运输时间(T)对应的目标函数见式(1)和(2)。

(1)

(2)

式(1)表示总运输费用最低,总运输费用包括在途费用、中转费用及碳排放费用;式(2)表示总运输时间最短,总运输时间包括在途时间、转运时间及等待时间。

约束条件见式(3)—(9)。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(3)表示节点货运量不发生分割;式(4)表示运输货物时节点间只可选择一种运输方式;式(5)保证货物在同一个节点发生一次转载;式(6)保证运输过程的连续;式(7)为决策变量取值约束,被选择为1,否则为0;式(8)表示节点间运输方式的最大承载能力大于货运量;式(9)表示所选节点的不同运输方式的中转能力大于在节点中转的货运量。

2 模糊模型清晰化处理

2.1 模糊机会约束模型的转化

为了清晰地表达所构建模型中的模糊变量,需要将模型转换为确定的形式。当模糊变量出现在约束中时,通常可以使用期望值模型或模糊机会约束规划方法来解决。如果决策者期望平均意义上的解决方案,则可以选择期望值模型。如果客户的交货要求只有一个大概的时间范围,即只要在一定程度上满足,就可以选择模糊机会约束规划。本文主要借鉴1996年Iwamura等[18]首次提出的不确定理论规划方法:含有模糊参数的模型只要满足做出模糊机会约束决策的概率在一定的置信度之上,就可以得到清晰的模型方程。具体可表示为式(10)—(13)。

目标函数:

(10)

约束条件:

(11)

(12)

(13)

2.2 模糊机会约束模型清晰化

(14)

(15)

(16)

(17)

对于多目标问题采用线性加权法[19]处理,即分别对式(1)和(2)赋予权值ω1和ω2,且ω1+ω2=1,0≤ω1,ω2≤1,然后进行加权处理。由于成本和时间的量纲不同,不能直接进行数学运算,因此对目标函数进行量纲为一化处理,具体步骤如下。

步骤1:分别求出置信水平α下运输成本的最大值F*、最小值F-,运输时间的最大值T*、最小值T-。

步骤3:设定成本权重参数ω1和时间权重参数ω2的值,Z=ω1F′+ω2T′,表示量纲为一化后的目标值。

综上,目标函数为minZ=ω1F′+ω2T′,约束条件为式(3)—(7)及式(14)—(17)。

3 算法设计

需求不确定下的多式联运路径选择问题属于组合优化问题,模型中涉及较多中间变量,结构相对复杂,是典型的NP-hard问题,采用启发式算法进行求解。遗传算法(GA)是启发式算法种类之一,在自然种群遗传学启发的原理下解决问题,提供强大的全局优化,适用全局优化问题的求解,但收敛问题太快,容易导致局部最优。模拟退火算法(SA)源于实体退火原理,是一种基于蒙特卡罗迭代解的启发式随机搜索过程,这样可以避免搜索陷入局部极值。本文综合考虑模拟退火算法与遗传算法的优劣,设计基于模拟退火的遗传算法,具体流程如图2所示。

图2 算法流程Fig.2 Algorithm flow

为了提高计算效率,选取部分优秀个体进行模拟退火。根据适应度函数计算方法,按适应值从优到劣得到染色体排序,具体步骤如下。

步骤1:初始化数据,确定种群大小(Gs)、最大迭代次数(Gt)、交叉概率(Gc)、变异概率(Gm)、初始温度(U0)、终止温度(Ud)、降温速率(q)及惩罚系数(Pe)。

步骤2:对个体进行编码,根据目标函数计算个体的适应值,找到最优的适应值(Xbest)并储存下来。

步骤3:利用轮盘赌机制对染色体进行选择,然后进行单点交叉及单点变异。

步骤4:将个体适应度数值从大到小排列,选择部分优秀个体进行降温操作,并利用单点交叉产生新解N。利用Metropolis法则判断是否接受新解;并判断是否满足终止温度,即Temp=T0q。

步骤5:将模拟退火得到的新种群放入原种群后进行排序,判断能否达到终止要求,如果可以满足则输出最终结果,否则转到步骤3,继续操作直到满足终止条件。

4 算例分析

4.1 算例设计

表1 不同运输方式的相关参数

表2 转运相关数据

表3 各运输方式参数

图3 多式联运算例网络图Fig.3 Network diagram of multimodal operation example

4.2 结果分析

通过MATLAB编程对多式联运路径选择模型进行求解,其中:Gs=100,Gt=300,Gc=0.7,Gm=0.3;U0=3 000,下降速率Ud=0.001。参数设置为α=0.9,β1=β2=1,ω1=ω2=0.5,多次运算取最优解。图4为遗传算法与基于模拟退火的遗传算法(SAGA)收敛曲线对比图,表4为具体求解结果。

表4 两种算法求解结果

图4 算法收敛曲线对比Fig.4 Comparison of algorithm convergence curves

由图4可以看出:基于模拟退火的遗传算法在15次左右收敛,而遗传算法从66次开始收敛。由表4可以看出:相较于遗传算法,基于模拟退火的遗传算法求解的路径总运输成本降低了1.7%、运输时间降低了1.1%,目标函数值降低了2.0%,可以说明在本文中基于模拟退火的遗传算法优于遗传算法。

由表4还可知:最优运输方案为1—铁—3—铁—8—铁—9—水—13—公—15,此方案最低运能限制是从节点13运输至节点15时采用公路运输,最低运能限制为207 t。为进一步分析不确定货运量是否会对多式联运最优路径方案的选择造成影响,置信水平α取0.9,调整不确定需求量的分布区间并进行对比,最终得到了8组最优的方案,如表5所示。

表5 货运量参数对路径选择的影响

由表5可以看出:满足节点运输方式能力以及中转能力时,随着不确定需求量分布区间的变化,最优的运输方案不变,运输成本随着需求量的上升而增加,转运时间的占比逐渐提高;当超过最优运输方案中最低运能限制时,运输方案发生改变。转运时间占比逐渐降低直至为0,铁路在路径中占比有所提升。这是由于转运时间与货运量动态相关,随着货运量的增加,转运时间也会随之增加,经营人为降低运输时间,会选择单位转运时间较快的方式或选择不发生转运。

由于不同决策者对时间和成本的要求不同,为便于对成本与时间敏感性不同的决策者挑选方案,通过改变成本函数的权值ω1与时间函数的权值ω2,得出以下5种情况下多式联运运输方案,见表6。

表6 不同权重系数下最优方案

由表6可以发现:当时间函数与成本函数的权重相差不大时,运输方案中会选择转运以平衡时间和成本。当时间函数的权重最大时,其运输时间相较于平均权重的运输时间降低了51.1%,全程采用公路运输方式;当成本函数的权重最大时,运输成本相较于平均权重的运输成本降低了83.9%,全程采用水路运输方式。随着时间函数的权重逐渐提高,公路在运输方案中的占比逐渐降低,水路占比逐渐上升。

5 结论

以运输成本及运输时间综合最低为目标,构建不确定需求下的多式联运路径选择模型。运用模糊机会约束规划理论对模型进行清晰化处理,设计基于模拟退火的遗传算法求解模型,可得到以下结论:

1)基于模拟退火的遗传算法从运输成本、迭代次数等方面都优于基本的遗传算法,表明本文算法在不确定需求下多式联运路径选择问题上的有效性。

2)在满足最优运输方案的最低运能限制时,不确定需求量分布区间的变化不影响多式联运的运输方案,转运时间的占比随着不确定需求量分布区间的上升逐步增加。多式联运经营人可根据以往经验选择最优运输方案;若超过最优运输方案的最低运能限制,运输方案会发生改变,转运时间占比逐渐降低直至为0,且铁路占比大大增加。此时多式联运经营人制订运输方案时可以通过提高铁路占比减少转运次数得到最优运输方案。

3)当多式联运经营人注重货物运到时间短时,倾向选择速度较快的公路运输方式,转运时间占比也较低;当多式联运经营人注重运输成本时,倾向选用运价较低的铁路与水路运输方式,运输时间和转运时间占比也会相应增加。

符号说明：

d表示多式联运运输网络的终点

I城市节点集合,I={i,j|i,j=1,2,3…n}

K运输方式集合,K={k,l|k,l=1,2,3},1—公路,2—铁路,3—水路

o表示多式联运运输网络的起点

Q1货物最小运量,t

Q2货物最大运量,t

Q3最可能货物需求量,t

r碳税率,元/kg

Vk第k种运输方式的运输速度,km/h

α表示已知的置信度,α∈[0,1]

β1表示已知的置信度,β1∈[0,1]

β2表示已知的置信度,β2∈[0,1]