集装箱多式联运中多运输网络最短路径问题研究

集装箱多式联运中多运输网络最短路径问题研究

随着世界经济的快速发展和市场竞争的加剧，箱式多式联运已成为物流企业发展的热点。在多式联运的过程中，合理选择运输方式，组织运输方式，充分利用多式联运箱式运输的优势，提高我国物流业服务体系水平、能力和各种运输方式的综合效率，取得更好的经济效益。本文将运输路线优选和运输方式优选综合起来加以考虑,建立了带时间约束和能力约束的,以总运输成本最少为目标的组合优化模型,并给出了相应的求解方法。1城市之间各种运输方式、运输路线转换的影响假设一个物流中心A0要将一批货物从物流中心运送到货物目的地(A),中途经由若干随机分布的城市构成的运输网络,网络中任意相邻的城市之间都有若干种(g种)运输方式可供选择,且各种运输方式的运输时间、运费、运输能力不同,在每个城市可以进行运输方式的转换,当从一种运输方式转换到另一种运输方式时,需要一定的中转时间和中转费用,而且在整个运输过程中,总的运输时间不能超过运输期限(T),如何在不超过运输期限和各种运输方式运输能力的前提下安排运输路线和选择最佳的运输组合方式,使得总运费最低是要解决的问题。2模型描述2.1城市之间的运输方式。城市(1)运量在某一对城市之间不能分割,即在某一对特定的城市之间,若存在路径,则在这对城市之间只能选择一种运输方式;(2)运输成本是距离的线性函数;(3)运输网络中,同一阶段和非相邻阶段城市之间可存在路径。2.2第2阶段的运输时间。在c阶段的j城市到i+1阶段的k城市选择第v种运输方式的运输成本;阶段的j城市到i+1阶段的k城市选择第v种运输方式的运输能力;阶段的j城市到i+1阶段的k城市选择第v种运输方式的运输时间;:在i阶段的j城市由第v种运输方式转换到第w种运输方式的中转费用;在i阶段的j城市由第v种运输方式转换到第w种运输方式的中转时间;Ai:第i阶段所有城市的集合;T:从始发点到目的地容许的时间期限;J:可供选择的交通工具集合;M:一个充分大的惩罚因子;3城市某一城市的运输方式目标函数以整个运输过程中的运输成本最少为目标,而总费用由三部分组成,即运输费用、中转费用、惩罚费用。公式(2)表示在相邻阶段的某一城市对之间,如果存在路径,只能选择一种运输方式,即运量不能分割;式(3)表明,在i阶段的j城市,最多有一次运输方式的改变;式(4)确保运输的连续性;式(5)表明货物必须在规定的期限内运到;式(6)表明货物的运量不能超过某种运输工具的能力;式(7)表明决策变量取整数0或1。4城市虚拟运输路径的构建通过虚拟一个运输网络,将原问题转化为一个带时间约束和能力约束的最短路径问题,然后采用数学规划软件Lingo8.0求解带有时间约束和能力约束的最短路径。从配送中心A0将一批货物中途经若干城市运往目的城市A9,如图1所示,存在路径的城市之间有三种运输方式:铁路、公路、水路可供选择。详细解法阐述如下:(1)划分运输阶段为了方便模型的求解,首先将运输网络划分为若干阶段,A0位于第一阶段,A1、A2、A3位于第二阶段,A4、A5位于第三阶段,A6、A7、A8位于第四阶段,目的地A9位于第五阶段。如图2所示。(2)向运输网络中增加虚拟节点对于不相邻阶段的城市之间存在路径的,应在路径上中间阶段增加虚拟节点,如图2所示,二阶段城市1与四阶段城市6之间存在一条路径,在三阶段增加虚拟节点M;二阶段城市3与四阶段城市8之间存在一条路径,在三阶段增加虚拟节点N。如图3所示。(3)构建扩展的虚拟运输网络图方法如下:①为简化模型的计算,在有路径相连的城市之间默认三种运输方式均可到达。②除始发点A0外,将其他每个城市分别扩展成g个城市(每个城市代表一种运输方式),扩展后的g个城市仍处于原来的网络阶段,最后,虚拟一个目的地。如图4所示,其中,0代表始发点A0,1、2、3为A1扩展的3个虚拟城市,1代表铁路运输,2代表公路运输,3代表水路运输,依此类推,31、32、33为目的地A9扩展的3个虚拟城市,分别代表铁路、公路、水路运输。34为虚拟的目的地。③同一个城市扩展来的节点与节点之间不存在连接弧,原来有弧连接的两个城市,各自扩展来的g个城市之间两两有弧连接,原来没有弧连接的两个城市,各自扩展来的g个城市间都没有弧连接。④各条弧上的权重分为三类:费用权重、时间权重、能力权重。费用权重=两城市间的运输费用+中转费用;时间权重=两城市间的运输时间+中转时间;能力权重=两城市间某种运输工具的运输能力。⑤对于两个网络阶段之间建立的虚拟城市,假设i阶段的第m个城市到j阶段的第n个城市之间的各阶段内都有一个虚拟城市,设i阶段的第m个城市到i+1阶段的任一虚拟城市之间的运费、运输时间、运输能力都为i阶段的第m个城市到j阶段的第n个城市的运费、运输时间、运输能力,相邻阶段的虚拟城市与虚拟城市之间的运费、运输时间均为零,运输能力设为一个充分大的数,依此类推,j-1阶段的虚拟城市到j阶段的第n个城市的运费、运输时间均为零,运输能力设为一个充分大的数。将没有弧连接的城市之间的运输费用、运输时间设为一个充分大的整数,运输能力设为零。虚拟一个最终点34,因此31→34,32→34,33→34的运输时间和运输费用均为零,而运输能力为无穷大。则原问题的求解转化为:在不超过运输期限和运输能力约束的前提下,求从节点0→34的最短路径。如图4所示。(4)用Lingo8.0求解最短路径。5计算与分析5.1已知条件以如图1所示运输网络为例。各城市之间的运费、运输时间、运输能力如表1所示,不同运输方式的中转费用和中转时间如表2所示。5.2运营结果按上述算法思想,采用数学规划软件Lingo8.0求解,得到不同运量和运输期限要求下运输路线和运输方式的组合优选结果,如表3所示。6“多城市间多种运输方式的组合优化模型”建立了在运输路线不确定的情况下选择最佳的运输组合方式,使得总运费最低的多式联运模型,