一种多式联运网络运输方式的组合优化模式

摘要

针对我国多式联运目前普遍存在的信息化水平不高，缺乏相应的决策支持系统的现状，首先对多种运输方式的运输特性进行了分析，通过对比，得出了运输方式的选择依据；然后建立了多式联运虚拟运输网络；最后在运输方式选择依据和运输网络的基础上得出了多种运输方式组合优化模型，并给出了求解算法。

正文

《1 引言》

1 引言

随着经济的全球化, 一些大型的物流企业不仅从事近距离的货物配送, 而且进行远距离的货物配送。当货物进行远距离配送时, 单一的运输方式未必是最优选择, 因为各种交通工具都有各自的技术优势。对于一个现代的物流企业, 如何充分利用自身的优势, 选择最佳的运输方式组合, 实行多式联运, 以最低的成本, 安全、如期地完成运输任务, 是一个值得探讨的问题。所谓多式联运是指有一个多式联运经营人 (运输企业或者运输代理企业) 负责承运, 一般以集装箱运输为媒介, 采用两种以上运输方式, 实行“一次托运、包干计费、一票到底、全程负责”的连贯运输。它具有显著的优越性, 特别是为货物的门到门运输提供了一条极为有效的途径^[1]。

我国多式联运目前普遍存在信息化水平不高, 缺乏相应的决策支持系统^[2,3]。为此, 笔者首先对多种运输方式的运输特性进行了分析, 通过对比, 得出了运输方式的选择依据;然后建立了多式联运虚拟运输网络;最后在运输方式选择依据和运输网络的基础上, 得出多种运输方式组合优化模型, 并给出了求解算法。

《2 多式联运运输方式选择依据》

2 多式联运运输方式选择依据

首先不妨对各种运输方式的优缺点加以比较。在企业发货给配送中心、分销商、批发商和最终消费者的运输实践操作中, 一般说来, 主要有4种运输方式可供选择:铁路运输、公路运输、水路运输和航空运输。表1对这些运输方式的优缺点进行了比较。

如果将固定成本和变动成本加以折衷, 运输成本最低的应该是水路运输 (见表2) 。因此, 远距离大宗产品的运输, 大多采用水路运输, 如国际运输中的远洋运输, 其次是铁路运输。但因包装便利、直达性能、运输网络等原因, 国内运输大多还是采用公路运输, 除非距离过长才采用铁路运输而放弃公路运输“门到门”的便利。

从运输方式的综合因素考虑, 公路运输是首选, 其次是铁路、航空和水路 (见表3) 。因此, 企业除了进出口大宗货物只能采用水路运输外, 一般都选择公路运输作为其货物运输的首选方式, 除非距离较远, 才采用铁路运输;或价值高、体积小、易腐烂、客户要求迅速交货的产品才通过航空运输。

表1 主要运输方式比较

Table 1 Comparison among main transportation modes

《表1》

运输方式	优点	缺点
铁路运输	大批量运输长距离运费便宜事故少, 安全性好	近距离运费高无法应急运输
公路运输	门到门的联合运输服务受外力冲击小、包装可简化	长距离运费高不适合大宗运输运输速度慢
水路运输	可大量运输散装货物装卸作业合理化适合大型货物运输	码头装卸费用高受天气影响大安全性准时性差
航空运输	运输速度非常快适合小批量中长距离运输包装比较简单	不适合廉价商品重量尺寸受到限制不适合远离机场托运

表2 主要运输方式成本比较

Table 2 Comparison of transport costs

《表2》

运输方式	固定成本	变动成本	综合成本
铁路运输	高	低	低
公路运输	高	适中	适中
水路运输	适中	低	最低
航空运输	低	高	高

表3 各种运输方式综合特征评分 (分值越小越好)

Table 3 Comprehensive characteristic mark of various transportation modes

《表3》

比较项目	铁路	公路	水运	航空
速度	3	2	4	1
可行性	2	1	4	3
可靠性	2	1	3	4
能力	2	3	1	4
频率	3	1	4	2
合计得分	12	8	16	14

通过上述对比分析, 得出多式联运运输方式的选择依据是, 不论选择何种运输方式, 企业都应遵循如下五大基本运输原则:a.安全——要求在运输过程中, 保证商品完好无损和运输工具的安全;b.迅速——保证把商品及时送到目的地;c.准确——保证把商品准确无误地运到交货地点, 包括正确办理各种有关运输单证, 使单货相符, 准确地计收、计付运杂费用, 避免错收、错付或漏收、漏付;d.节省——节约运杂费用和管理费用;e.方便——为货主着想, 简化手续, 减少工作层次, 不断提高服务质量。

《3 多式联运系统的网络描述》

3 多式联运系统的网络描述

根据运输方式选择依据中更节省和迅速的原则, 为了使决策者得到更直观的信息, 需要建立一个描述多式联运系统特征的运输网络。

多式联运系统基本网络^[4,5,6], 由节点以及每两个节点之间的一条或相互平行的多条连线所组成, 笔者定义一个连线为i, j, m (i, j∈N, m∈M) 。其中, i代表起始节点, j代表终止节点, m代表i, j之间可用的某种运输方式, N代表网络上所有节点的集合, M代表网络上所有运输方式的集合。基本网络如图1所示。

《图1》

图1 路网图

Fig.1 Road network

假设一个运输网络由A, B, C三个节点组成, 可用的运输方式有公路、铁路、航空。对该路网的描述采用图2的形式。即用具有方向性的多条相互平行的直线直接连接相邻的两节点, 每条连线代表一种可能的运输方式。

以上基本网络对于每种运输方式单独完成运输任务、没有不同运输方式之间联合运输发生的情形可以很好地进行描述。如果为了完成某项运输任务, 或为了节省时间费用, 而要求在多种运输方式之间进行联合运输, 即要实现多种运输方式之间的换装 (乘) , 该网络该如何描述?假定各种运输方式之间的衔接只能在节点发生, 则可以通过节点的扩展来解决这个问题, 如图3所示。其基本做法是:将发生换装 (乘) 的节点a, 根据其流入流量1, 2和流出流量3, 4, 分裂成两个流入节点a₁, a₂和两个流出节点a₃, a₄, 并在其间用换装 (乘) 线相连, 从而形成一个由流入节点和流出节点两部分组成的换装 (乘) 扩展节点。

《图2》

图2 路网描述图

Fig.2 Description of road network

《图3》

图3 节点扩展图

Fig.3 Expansion of nodes

接下来, 构造节点扩展后的多式联运运输网络图G (V, A) , 见图4, 具体方法是:

《图4》

图4 虚拟运输网络图

Fig.4 Virtual transportation network

1) 除始发点O外, 其他各城市分别扩展为g个城市, 其中每个代表一种运输方式;

2) 同一个城市扩展而来的点与点之间不存在连接弧;

3) 各条弧上的权重分为三类:费用权重、时间权重和能力权重。

其中, 费用权重=两城市之间的运费 + 中转费用;时间权重=两城市之间的运输时间 + 中转时间;能力权重=两城市之间某种运输工具的运输能力。

为计算方便, 虚拟一个最终节点D′, 因此D_i到D′之间的时间和费用均为0, 而运能为无穷大。

《4 多式联运运输方式的组合优化模型与求解算法》

4 多式联运运输方式的组合优化模型与求解算法

建立多式联运虚拟运输网络后, 笔者提出了一个适用于远距离、多城市之间的多种交通方式的组合优化模型, 并且给出了相应的求解算法。

《4.1问题的提出》

4.1问题的提出

假设一个物流企业将一批货物从货物的中心地点O运送到目的地D, 中途经过n个城市, 任意相邻的两个城市之间都有g种运输方式可供选择, 相邻的两个城市之间各种运输方式的运输时间、运费、运输能力不同。当从一种运输方式转换到另一种运输方式时, 需要一定的中转时间和中转费用, 而且在整个运输过程中的总时间不能超过运输期限T。对于特殊的货物 (例如危险品、易腐货品、牲畜、鲜活货物等) , 还要考虑其换装的可能性, 在综合上述各种因素之后, 确定最佳的多式联运运输组合方式, 使得总运费最低。

《4.2模型的假设及符号说明》

4.2模型的假设及符号说明

《4.2.1 模型假设》

4.2.1 模型假设

运量在某一城市对之间不能分割, 即在某一特定的城市对之间, 只能选择一种运输方式。

《4.2.2 符号说明》

4.2.2 符号说明

$x_{i, i + 1}^{k} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 与城市 i + 1 之间 \\ 选择第 k 种运输方式 \\ 选择其他的运输方式 \end{array}$ $x_{i, i + 1}^{k} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 与城市 i + 1 之间 \\ 选择第 k 种运输方式 \\ 选择其他的运输方式 \end{array}$

$γ_{i}^{k l} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 由第 k 种运输方式 \\ 转换到第 l 种运输方式 \\ 不发生转换 \end{array}$ $γ_{i}^{k l} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 由第 k 种运输方式 \\ 转换到第 l 种运输方式 \\ 不发生转换 \end{array}$

$μ_{i}^{k l} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 由第 k 种运输方式转换 \\ 到第 l 种运输方式 ‚ 场地、设施、 \\ 特殊 ⌶ 具均满足变更要求 \\ 不满足变更要求 \end{array}$ $μ_{i}^{k l} = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 在城市 i 由第 k 种运输方式转换 \\ 到第 l 种运输方式 ‚ 场地、设施、 \\ 特殊 ⌶ 具均满足变更要求 \\ 不满足变更要求 \end{array}$

C^k_{i, i+1}—从城市i到城市i+1选择第k种运输方式的运输成本;

f^k_{i, i+1}—从城市i到城市i+1选择第k种运输方式的运输能力;

d^kl_i—在城市i, 由第k种运输方式转换到第l种运输方式的中转费用;

a^kl_i—在城市i, 由第k种运输方式转换到第l种运输方式的中转时间;

t^k_{i, i+1}—从城市i到城市i+1选择第k种运输方式的运输时间;

T—从中心点到目的地容许的时间期限;

J—可供选择的交通工具集合;

I—所有要经过城市的集合;

q—货物的运量;

M—一个充分大的惩罚因子。

《4.3模型的建立》

4.3模型的建立

目标函数为

$\begin{array}{l} Ζ = \min \sum_{i \in Ι} \sum_{k \in J} x_{i, i + 1}^{k} C_{i, i + 1}^{k} + \\ \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} γ_{i}^{k l} d_{i}^{k l} + \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} (μ_{i}^{k l} - 1) Μ \end{array}$ $\begin{array}{l} Ζ = \min \sum_{i \in Ι} \sum_{k \in J} x_{i, i + 1}^{k} C_{i, i + 1}^{k} + \\ \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} γ_{i}^{k l} d_{i}^{k l} + \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} (μ_{i}^{k l} - 1) Μ \end{array}$

约束条件为

${\begin{cases} \sum_{k \in J} x_{i, i + 1}^{k} = 1 \forall i \in Ι \\ \sum_{k \in J} \sum_{l \in J} γ_{i}^{k l} = 1 \forall i \in Ι \\ x_{i - 1, i}^{k} + x_{i, i + 1}^{l} \geq 2 γ_{i}^{k l} \forall i \in Ι, k \in J, l \in J \\ \sum_{i \in Ι} \sum_{k \in J} t_{i, i + 1}^{k} x_{i, i + 1}^{k} + \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} a_{i}^{k l} γ_{i}^{k l} \leq Τ \\ q \leq f_{i, i + 1}^{k} \forall i \in Ι, k \in J \\ x_{i, i + 1}^{k}, γ_{i}^{k l} \in {0, 1} \forall i \in Ι, k \in J, l \in J \end{cases}$ ${\begin{cases} \sum_{k \in J} x_{i, i + 1}^{k} = 1 \forall i \in Ι \\ \sum_{k \in J} \sum_{l \in J} γ_{i}^{k l} = 1 \forall i \in Ι \\ x_{i - 1, i}^{k} + x_{i, i + 1}^{l} \geq 2 γ_{i}^{k l} \forall i \in Ι, k \in J, l \in J \\ \sum_{i \in Ι} \sum_{k \in J} t_{i, i + 1}^{k} x_{i, i + 1}^{k} + \sum_{i \in Ι} \sum_{k \in J} \sum_{l \in J} a_{i}^{k l} γ_{i}^{k l} \leq Τ \\ q \leq f_{i, i + 1}^{k} \forall i \in Ι, k \in J \\ x_{i, i + 1}^{k}, γ_{i}^{k l} \in {0, 1} \forall i \in Ι, k \in J, l \in J \end{cases}$

其中, 目标函数以整个运输过程中的运输成本最少为目标, 而运输成本由运费、中转费用和惩罚费用三部分组成。第1个约束条件对应假设, 在某一特定的城市对之间只能选择一种运输方式, 即运量不能分割;第2个约束条件表明, 在城市i, 只有一次运输换装;第3个约束条件确保运输的连续性;第4个约束条件表明货物必须在规定期限内运到;第5个约束条件表明货物的运量不能超过某种运输工具的能力;第6个约束条件表明决策变量是取整数0或1。

《4.4模型求解算法》

4.4模型求解算法

通过前面构建的多式联运虚拟运输网络, 将原问题转化为一个带时间约束和能力约束的最短路径问题。考虑到多式联运过程中, 发生换装 (乘) 的次数不会太多, 这决定了此类问题规模不会太大, 可以利用基于Dijkstra算法的启发式算法, 来求解此类带有时间约束和能力约束的最短路径问题, 其时间复杂度是O (m2) 。算法的基本思想是:首先在不考虑时间约束的前提下, 用求出从O→D′带有能力约束的最短路, 然后在已求得最短路径的基础上, 用启发式算法来调整, 使之满足时间约束。

有关符号的说明:

dist[i]表示节点O→i的费用最少的最短距离;time[i]表示节点O→i的最短距离上的总时间, T为时间约束;cost[i][j]表示节点i→j的费用 (如果i→j不满足运输换装的条件, 则cost[i][j]=∞) ;V为节点总集;S已标记的节点集合; $\bar{S}$ $\bar{S}$ 为未标记的节点集合;

V={O, P₁₁, P₁₂, P₁₃, …, P_1k, …, D₁, …, D_k, D′};S, $\bar{S}$ $\bar{S}$ ⊂V且有 $S \cup \bar{S} = V$ $S \cup \bar{S} = V$ ;

$p a t h [i] = {\begin{cases} k \\ \infty \end{cases} \begin{array}{l} 表示 Ο \to i 的最短路径上 ‚ \\ 节点 i 的前一个节点为 k ； \\ 表示 Ο \to i 不存在最短路； \end{array}$ $p a t h [i] = {\begin{cases} k \\ \infty \end{cases} \begin{array}{l} 表示 Ο \to i 的最短路径上 ‚ \\ 节点 i 的前一个节点为 k ； \\ 表示 Ο \to i 不存在最短路； \end{array}$

$l a b e l [i] = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 表示 Ο \to i 的最短路径已找到 ‚ \\ 表示 Ο \to i 的最短路径未找到； \end{array}$ $l a b e l [i] = {\begin{cases} 1 \\ 0 \end{cases} \begin{array}{l} 表示 Ο \to i 的最短路径已找到 ‚ \\ 表示 Ο \to i 的最短路径未找到； \end{array}$

ΔT^kj_i表示在城市i, 由第k种运输方式变换到第l种运输方式所节省的时间;

ΔF^kj_i表示在城市i, 由第k种运输方式变换到第l种运输方式所增加的费用;

max (i, k, l) 表示在城市i, 由第k种运输方式变换到第l种运输方式, 第l种是最优的。

算法步骤:

Step 1 初始化

S←{O}, path[0]←O, label $[0] = 1 ‚ \bar{S} \leftarrow V - S 。$ $[0] = 1 ‚ \bar{S} \leftarrow V - S 。$ 对∀i∈S, 有dist[i]←cost[0][i], label[i]=0, path[i]=∞;

Step 2 若label[D′]=1, 转Step 6, 否则转Step 3;

Step 3 在所有的i∈S, j∈S满足q≤f_ij的点中选择, 令dist[k]←min{dist[j]}, 置 $\bar{S} \leftarrow \bar{S} - {k} ‚ S \leftarrow S \cup {k} ‚$ $\bar{S} \leftarrow \bar{S} - {k} ‚ S \leftarrow S \cup {k} ‚$ 置label[k]=1;

Step 4 对所有的i∈S, j∈ $\bar{S}$ $\bar{S}$ 置dist[j]=min{dist[j], dist[k]+cost[k][j]}, path[j]←k, 转Step 2;

Step 5 输出dist[D′]的最短路径, 根据最短路径求出该路径上的总时间time[D′];

Step 6 根据已求出的最短路径确定各区间的运输方式, 并存放于mode[i] (i=1, 2, …, n+1) 中, 确定最短路的总时间 (total-time) 和总费用 (total-fair) ;

Step 7 判断total-time≤T是否成立, 是, 转到Step 9, 否, 转到Step 8;

Step 8 i←n+1, k←mode [i], 对于所有的l∈J计算 $\max (i, k, l^{*}) = \max_{l \in J} {\frac{Δ Τ_{i}^{k l}}{Δ F_{i}^{k l}}},$ $\max (i, k, l^{*}) = \max_{l \in J} {\frac{Δ Τ_{i}^{k l}}{Δ F_{i}^{k l}}},$

total-time←total-time-ΔΤ^kl_i, total-fair←total-fair-ΔF^kl_i, 令i←i-1, 转Step 2;

Step 9 输出最终各区间的选择运输方式, 总时间, 总费用, 结束。

说明:在上述公式中, 符号←表示赋值给。

《5 结语》

5 结语

多式联运运输方式组合优化模型在总成本最小的原则下, 定量地分析了多式联运系统中各种运输方式的最优组织模式, 通过各种费用的合理标定以及现代计算机技术的应用, 可以方便地为经营决策者提供精确的数据结果, 为我国多式联运系统的合理组织提供科学依据。

运输方式	优点	缺点
铁路运输	大批量运输长距离运费便宜事故少, 安全性好	近距离运费高无法应急运输
公路运输	门到门的联合运输服务受外力冲击小、包装可简化	长距离运费高不适合大宗运输运输速度慢
水路运输	可大量运输散装货物装卸作业合理化适合大型货物运输	码头装卸费用高受天气影响大安全性准时性差
航空运输	运输速度非常快适合小批量中长距离运输包装比较简单	不适合廉价商品重量尺寸受到限制不适合远离机场托运

展示更多