有时间限制的多式联运路径优化模型研究

卢 欣，雷 强，王其才

（西南交通大学 交通运输与物流学院，四川 成都 610031）

1 研究背景

随着生产专业化程度日益提高，生产地点不断分散，高附加值产品比重也不断增加，社会经济活动日趋高效化，使得时间价值变得越来越重要。对轻工、电子产品、纺织品及服装、医药制品、食品、仪器仪表、鲜活易腐品等高附加值、时效性强的货物而言，货主希望以尽可能少的时间耗费和适宜的价格交付完好。限时性的快捷货物运输已成为货运发展的趋势之一。多式联运是该类货物较佳的运输组织形式，灵活的运输方案是从事快捷货物运输企业取得竞争优势的关键。在有时间限制条件下，对多式联运路径进行优化对满足客户需求和节约运输成本具有重要意义。

随着多式联运需求量的增加，关于多式联运路径优化的研究也逐步深入。有学者研究了多式联运下的最短可行路径问题[1]；付晓凤等从运输时间与成本的相关性出发，建立了基于时间/成本一体化的多式联运路径优化模型[2]；佟璐等以成本和时间为优化目标，建立了适应运量变化情况下的多式联运路径优化模型，将问题转化为广义的最短路径，并选择蚁群算法对实际问题进行了求解验证[3]；杨文东等提出了有时间窗的多式联运问题的双层优化模型，并设计了求解路径优化模型的蚁环算法[4]。以上研究主要是将时间转化为费用，或者将时间设为多目标规划的一个子目标函数。而对于有严格送达时间限制的快捷货物运输，求得的最优解不一定能完全满足时间要求。在此，主要研究用 K 最短路的方法来求解带时限的多式联运路线优化问题[5]。

2 问题描述与符号定义

假设有一批货物要从点 O 途经n个城市运送到点 D，将每个城市视为一个节点。每个节点有 4 个货运站，分别对应公路、水路、铁路和航空 4 种运输方式，从上一节点的某个站出发只能采取对应的运输方式，并且必须首先到达下个节点的对应货运站，各运输方式的转换只能在各节点内进行，并且最多进行一次转换。因此，将节点n拆开成点2n－1和点2n。点2n－1可以表示为节点n的入口，点 2n表示为节点n的出口。例如，将节点1拆成点1和点2，节点2拆成点3和点4，依次类推，这样点D就变成点2n＋1，构建的多式联运网络如图1所示。

图1中的符号定义为：Noden为节点城市n；Point 2n－1为节点n拆分而成的入口；Point 2n为节点n拆分而成的出口；①、②、③和④分别代表每个点的4个货运站；表示以k运输方式从点2n到点2n＋1；表示以k运输方式从点2n到点2n＋1的费用；表示以k运输方式从点2n到点2n＋1的时间；表示在节点n内，运输方式由i转换为j；表示在节点n内，运输方式由i转换为j的费用；表示在节点n内，运输方式由i转换为j的时间。

3 建立模型

建立多式联运网络的数学模型为：

图1 多式联运网络示意图

式中：当节点n到节点n+1 选择运输方式k时，，否则；当在节点n运输方式由i转 换为j时，否则；当在节点n运输方式由i转换为j时，否则当在节点n运输方式由i转换为j时，否则T0为货物运输的时间限制。

4 求解步骤

通过对上述问题的描述和多式联运网络图的分析可以看出，该问题可以看做带约束条件的最短路径问题。这也是一个 NP(Non-Deterministic Polynomial) 问题，很难直接得到一个满足时间限制条件的解，但是能迅速对一个解是否满足要求进行验证。

对于最短路问题的求解，Dijkstra 已经给出比较好的算法[6]，对于有约束条件的最短路求解，可以用 K 最短路法来逐次试探。先求得k最短路，然后检验此路径是否满足时间限制要求。模型的具体算法步骤如下。

步骤 1：用最短路法求运输费用的最短路，然后计算出此路径所消耗的时间，如满足约束条件，则该解为问题最优解，如不满足则转步骤 2。

步骤 2：用最短路法求运输时间的最短路，如不满足时间约束，则此问题无解；如满足，令k＝1，转步骤 3。

步骤 3：用 K 最短路法计算运输费用最小的第k＋1 条最短路，并计算出此路径所消耗的时间，如满足约束条件，则该解为问题最优解；如不满足则重复步骤 3，直至满足约束要求为止。

5 实例计算

现有一批货物从城市 0 经过 2 个城市运送到城市 3，要求货物运输时间不超过 12 d，并通过合理选择运输方式的组合，使运输成本最低。城市间各种运输方式的运输费用和时间如表 1 所示，各城市内部各种运输方式的中转费用和时间如表 2 所示。

表1 城市间各种运输方式的运输费用和时间

表2 各城市内不同运输方式转换的费用和时间

用最短路法求出运输费用最小的方案为：0→1选择水路，在 1 不转运；1→2 选择水路，在 2 不转运；2→3 选择水路。该路径的运输费用为 1 万元，时间消耗为 17 d，不满足时间约束条件。

用最短路法求出运输时间最少的方案为：0→1选择航空，在 1 不转运；1→2 选择航空，在 2 不转运；2→3 选择航空。该路径的时间消耗为 5 d，说明此问题有解。

用K最短路法求出运输费用最小的第二短路，运输方案为：0→1 选择水路，在 1 由水路换为铁路；1→2 选择铁路，在 2 由铁路换为水路；2→3 选择水路。该路径的运输费用为 1.4 万元，时间消耗为 18 d，不满足时间约束条件。

用 K 最短路法求出运输费用最小的第三短路，结果有 2 条。①运输方案一。0→1 选择水路，在 1不转运；1→2 选择水路，在 2 由水路换为铁路；2→3 选择铁路。该路径的运输费用为 1.5 万元，时间消耗为 15 d，不满足时间约束条件。②运输方案二。0→1 选择水路，在 1 不转运；1→2 选择水路，在 2 由水路换为航空；2→3 选择航空。该路径的运输费用为 1.5 万元，时间消耗为 12 d，满足时间约束条件。因此，运输方案二为满足 12 d 内将货物送到的运输费用最小的方案。

6 结束语

多式联运路径优化问题是多因素的综合规划问题，文中仅对有时限的多式联运货物运输的路径优化问题进行了研究，模型的算法思路简单，但实际计算量较大。当节点较少或可供选择的运输方式较单一时，可用此模型及算法求解。但是，随着运输节点的增多和运输方式的多样化，会使问题解的数目成几何倍数增长，使求解变得异常困难，因此需要考虑引入遗传算法来改进算法，提高求解效率。

[1] Lozano A，Storchi G. Shortest Viable Path Algorithm in Multimodal Networks[J]. Transportation Research Part A，2001(35)：225-241.

[2] 付晓凤，马 彬，张 娟，等. 多目标一体化的联运路径优化方法研究[J]. 铁道运输与经济，2009，31(9)：83-85.

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

[4] 杨文东，王文芳. 有时间窗的多式联运问题分析与建模[J]. 南京航空航天大学学报，2009，41(1)：111-115.

[5] Eppstein D. Finding the K Shortest Paths[J]. SIAM Journal on Computing，1999，28(2)：652-673.

[6] Dijkstra EW. A Note on Two Problems in Connection with Graphs[J]. Numer. Math，1959(2)：269-271.