基于节点拆分指派问题的多式联运路径优化问题研究

王丹++张磊++许艳丽++于新升

摘 要：在多式联运路径优化问题中，城市节点、运输方式、转运方式的选择尤为重要。把不同运输方式、转运方式通过节点的拆分融入到网络图中，以运输总成本最低、运输总时间最短作为路径优化的整体目标，建立了多式联运路径优化问题模型。通过权重系数的引入，将多目标规划问题转换为单目标规划问题，并将优化模型转化为指派问题模型。最后，以算例证明了路径优化模型的可行性和有效性。

关键词：多式联运；节点拆分；指派问题

中图分类号：U116.2 文献标识码：A

Abstract： In the problem of path optimization about the multimodal transportation， the choice of city node， mode of transportation and mode of transit is very important. To put the different modes of transport， transit mode integrate into the network map through the node split， the final objective is the total transportation cost and the total time to the minimum. Transform the multi-objective planning problem into a single-objective planning problem by introducing the weighting factor， and transform the optimization model into an assignment problem model. Finally， the feasibility and effectiveness of the model is proved by examples.

Key words： multimodal transportation； node splitting； assignment problem

0 引 言

随着现代物流业与交通运输业的飞速发展，多式联运打破运输方式间的界限，在现代经济的发展中起到尤为重要的作用，已经成为降低物流成本的有效措施，成为提高市场竞争力的有效手段。国民经济和社会发展“十三五”规划的发布，表明国家对物流、对多式联运的重视程度也已经有了显著提高。

国内外众多学者在多式联运方面做出了广泛而深刻的研究。王清斌研究了带有时间约束的、以总运输成本最小为目标的混合整数规划模型[1]；Hu Z H设计了免疫近似算法来解决应急调度的路径优化[2]；JANSEN研究了模拟基于港口的集装箱运营规划[3]；Grabener T研究了基于时间窗的城市交通多目标路径优化模型，并利用改进的Martins算法求解[4]；佟璐认为多式联运路径的选择受到多方面相关因素的影响，并将问题转化成为广义最短路径优化问题[5]；雷定猷等将长大货物作为研究目标，将多目标多式联运问题简化，并采用遗传算法求解[6]；周骞等用遗传算法求解了以配送成本最低和时间成本最小为目标的配送网络优化模型[7]。

1 问题描述

在多式联运网络中，存在一个起始节点和一个终止节点以及若干中间节点，任意两个节点之间可能存在若干种运输方式，由一种运输方式转变为另一种运输方式需要一定的转运时间和转运成本。总成本包含运输成本和转运成本，总时间包含运输时间和转运时间。要解决的问题是：从起始节点到终止节点之间寻找一条运输路径使得总成本最低，同时总时间最短。

2 模型假设和符号说明

2.1 模型假设

（1）运输过程中的运量不可分割，在某一节点处发生运输方式的变化时，该节点和下一可达节点之间只能选择一种运输方式。

（2）在节点处发生运输方式的变化时，只考虑转运时间和转运成本；在两节点之間只考虑运输时间和运输成本。

（3）运输方式的改变只能发生在节点处。

（4）每个运输节点都具备运输方式转变的所有条件，即在任一节点处发生运输方式的转变都是可行的。

2.2 符号说明

A表示所有节点集合，i∈A；A表示初始节点；A表示终止节点；B表示节点i可到达的节点集合，j∈B；D表示运输方式的集合，k，l∈D；c表示节点i，j之间选择第k种运输方式的运输成本；t表示节点i，j之间选择第k种运输方式的运输时间；c表示在节点i，运输方式由k转换到l所需费用；t表示在节点i，运输方式由k转换到l所需时间；x

式（1）、式（2）为目标函数，其中式（1）使总成本最低，式（2）使总时间最短；式（3）至式（9）为约束条件，其中式（3）至式（5）保证模型的解能获得一条从起始节点到终止节点的路径，式（6）使若路径经过节点i，则i，j两个节点之间只能选择一种运输方式，式（7）保证运输的连续性，式（8）、式（9）使决策变量只能取0或1。

4 模型求解

4.1 模型简化

由于多目标模型的多个目标函数之间往往互不相容，因此导致求解复杂，为简化求解，加入成本和时间的权重系数，将多目标函数转化为单目标函数，用其反映在路径选择中分别对成本和时间的重视程度。

4.2 网络变形

图1中，包含3个网络节点，其中a为初始节点，a为中间节点，a为终止节点。因为每个路径存在几种运输方式，所以将节点进行拆分，若经由a节点进出有两种运输方式，经由a节点进出有两种运输方式，则将节点拆分后的网络图如图2所示。

图2中，a为虚拟初始节点，a、a为a节点拆分后的中间节点，a、a为a节点拆分后的中间节点，a为终止节点。每个路径代表一种运输方式或转运方式。

4.3 变化后的模型符号说明

A表示变化后所有节点集合，i∈A；A表示变化后的初始节点；A表示变化后的终止节点；c表示节点i，j之间产生的成本；t表示节点i，j之间产生的时间；x=

；α表示运输过程中成本的权重系数；β表示运输过程中时间的权重系数；μ表示货物的单位时间价值，即集装箱迟到目的地1h所产生的成本或费用，由货物的种类及数量决定。

4.4 变化后的模型

式（10）为目标函数，目标是总成本最小；式（11）至式（16）为约束条件，其中式（12）至式（14）保证模型的解能获得一条从起始节点到终止节点的路径，式（7）保证路径方向由起始节点指向终止节点，式（16）使决策变量只能取0或1。

5 算例分析

一个20英尺集装箱从郑州运往韩国首尔，途中有济南、济宁两个中转站以及青岛、连云港两个港口。各城市之间的运输网络如图3所示。其中，郑州到济南、郑州到济宁、济宁到济南间的运输方式包含公路运输和铁路运输，济南到青岛有公路运输和铁路运输，济宁到连云港之间有公路运输和铁路运输，济南到连云港只存在公路运输，青岛、连云港和韩国首尔间只存在水路运输。各节点之间的运输网络如图4所示。各节点之间的运输成本如表1所示；其中，不存在运输路径的两节点运输成本取一个足够大的数，本例中取1 000 000元。

图4中，0代表虚拟初始节点，1代表在郑州选择公路运输，2代表在郑州选择铁路运输，3代表在济宁选择公路运输，4代表在济宁选择铁路运输，5代表在济南选择公路运输，6代表在济南选择铁路运输，7代表在青岛选择公路运输，8代表在青岛选择铁路运输，9代表在青岛选择水路运输，10代表在连云港选择公路运输，11代表在连云港选择铁路运输，12代表在连云港选择水路运输，13代表终点首尔。

各节点之间的运输时间如表2所示。其中，不存在运输路径的两节点运输时间取一个足够大的数，本例中取1 000 000小时。

利用Excel进行规划求解。μ表示货物的单位时间价值，即集装箱迟到目的地1h所产生的成本或费用，由货物的种类及数量决定；本例中取200元/小时。现实环境中，不同公司或产品对时间和成本的要求存在差异，于是α值的变化会导致最优解的变化。

当α=0.1时，计算结果如表3所示，即运输路径为：郑州-（公路）-济南-（公路）-青岛-（水路）-首尔。运输总时间为28.5小时，运输总成本为9 845.6元。

当α=0.4时，计算结果如表4所示，即运输路径为：郑州-（公路）-济南-（铁路）-青岛-（水路）-首尔。运输总时间为30.5小时，运输总成本为9 043元。

当α=0.6时，计算结果如表5所示，即运输路径为：郑州-（铁路）-济南-（铁路）-青岛-（水路）-首尔。运输总时间为34小时，运输总成本为8 134.3元。

6 结 论

在各参数确定的情况下，模型存在一个最优解。时间较短的运输路线，自然成本相对较高，反之亦然，公司往往需要依据实际情况，调整相关参数，得出综合考虑时间和成本意义上的最优运输路径。

参考文献：

[1] 王清斌，韩增霞，计明军，等. 基于节点作业随机特征的集装箱多式联运路径优化[J]. 交通运输系统工程与信息，2011，11（6）：137-144.

[2] Hu Z H. A container multimodal transportation scheduling approach based on immune affinity model for emergency relief[J]. Expert Systems with Applications， 2011，38（3）：2632-2639.

[3] Jansen B， Swinkels P C J， Teeuwen G J A， et al. Operational planning of a large-scale multi-modal transportation system[J]. European Journal of Operational Research， 2004，156（1）：41-53.

[4] Grabener T， Berro A， Duthen Y. Time dependent multi objective best path for multimodal urban routing[J]. Electronic Notes in Discrete Mathematics， 2010，36：487-494.

[5] 佟璐，聶磊，付慧伶. 多式联运路径优化模型与方法研究[J]. 物流技术，2010，29（3）：57-60.

[6] 雷定猷，游伟，张英贵，等. 长大货物多式联运路径优化模型与算法[J]. 交通运输工程学报，2014（1）：75-83.

[7] 周骞，白云卯，徐春龙. 基于遗传算法的多式联运物流运输配送路径优化研究[J]. 物流工程与管理，2015，37（1）：89-91.