多式联运路径优化模型与方法研究.pdf

《多式联运路径优化模型与方法研究.pdf》由会员分享，可在线阅读，更多相关《多式联运路径优化模型与方法研究.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、佟璐，等：多式联运路径优化模型与方法研究 技 术 与 方 法 d o i：1 0 3 9 6 9 4 i s s n 1 0 0 5=1 5 2 X 2 0 1 0 0 5 0 1 9 多式联运路径优化模型与方法研究 佟璐，聂磊，付慧伶(北京交通大学 交通运输学院，北京 1 0 0 0 4 4)摘要】考虑到多式联运路径的选择受到运输成本、运输时间、运输质量和服务水平等相关因素的影响，将多式联运的路径 优化问题转化成为一个广义最短路径问题，以成本和时间为优化目标建立了适应运量变化情况下的多式联运路径优化数学模 型，并选择蚁群算法对实际问题进行了求解验证。【关键词】多式联运；路径优化；最短路径；蚁

2、群算法【中图分类号】F 2 2 4 0 【文献标识码】A 【文章m 1 o o 5 1 5 2 X(2 0 1 0)0 5 0 0 5 7 0 4 Re s e a r c h o n Op t i mi z a t i o n M o d e l a n d M e t h o d o f M u l t i-mo d a l Tr a n s p o r t a t i o n Ro u ti n g TONG Lu，NI E L e i，F U Hu i l i n g (S c h o o l o f T r a ff i cT r a n s p o r t a t io n，B e

3、 i j i n g J i a o t o n g U n i v e r s i t y，B e ij i n g 1 0 0 0 4 4，C h i n a)Ab s t r a c t：Ta k i n g i n t o c o n s i d e r a ti o n t h e i mp a c t o n r o u t e s e l e c ti o n o f mu l t i-mo d a l t r an s por t a t i o n b y f a c t o rs s u c h a s t h e c o s t，t i me，q u ali t y an

4、d s e r v i c e l e v e l o f t r an s por t a t i o n，e t c ，t h e p a p e r c o n v e r t s the r o u ti n g pr o b l e m i n t o the g e n e r al p rob l e m of the s h o r t e s t p a th a n d e s t a b l i s he s t h e me t h a me t i c al mode l f o r t h e p rob l e m t h a t a i ms a t the o

5、 p t i mi z a t i o n of c o s t an d t i me wi t h v a r y i n g t r a n s p o r t v o l u me，wh o s e s o l u t i o n i s r e a l i z e d t h r o u g h a n t c o l o n y alg o r i t h m Ke y wo r d s：mu l t i mod al t r an s p o rt a t i o n；r o u t e o p t i mi z a ti o n；s h o r t e s t p mh；an

6、t c o l o n y alg o rit h m 1 引言 随着全球的经济发展，单一运输方式已不能满足运输市 场的需求，只有多式联运才能够很好的解决来自全球运输市 场的多方面的需求。多式联运是采用两种或者两种以上的运 输方式把货物从起始地运送到目的地。它是综合运输体系的 核心，在我国交通运输体系中发挥着重要的作用。多式联运的 路径优化有助于节省运输费用或节约运输时间，从而对提高 运输服务水平、竞争能力、社会综合效益具有重大意义。随着物流技术的发展，以及多式联运需求的增加，国内外 学者对多式联运的路径优化研究也逐步深入。其中，A n g e l i c a L o z a n o 等研究了

7、多式联运下的最短可行路径问题，并通过顺序 算法进行求解 ；张建勇等从实现总成本最小化的原则出发，建立了一种多式联运网络的最优分配模型，从定量角度分析了 多式联运系统的合理组织模式；王涛等对多种运输方式的运 输特性进行分析后，提出了运输方式组合优化模型，并给出求 解算法；王云鹏等对基于扩展 P e t r i 网的多式联运流程进行了 研究；Mi c h e l B e u t h e 研究了 l O种货物类别在公 一铁 一内陆 水运组成的多式联运网络中成本最小的运输优化问题；刘 诚等研究了带软时间窗物流配送车辆路径问题的并行遗传算 法嗣；魏众等提出最短时间路径 一运输费用模型r 0；H e r

8、m i n i a I C a l v e t e 研究了带软时间窗车辆路径问题，提出了求解该问题 的目标规划法嗍；孙华灿等提出合理路径概念，建立了一个含 路径合理性约束的联合运输路径优化模型，指出除了运输效 益最大化外，合理的换装序列和换装次数限制是联合运输路 径选择和优化必须要考虑的因素19 1。上述研究构建的多式联运 网络模型是从不同的层面考虑的，存在着一定的局限性，有些 模型中仅以运输时间、运输成本或服务水平为单 目标的情况 下，寻求满足条件的最优多式联运路径。没有考虑不同时间段 会引起运输时间和运输费用的改变，也没有考虑到交通流量 对运输的影响。有些研究忽略了货物换装的成本计算和货物

9、 运到期限的约束，并假定运量在运输节点处不可分割，但在实 际中，如果某运输节点对某种货物有运输需求，则运量会在节 点处发生变化。为此，本文研究运量在某运输节点发生变化情 况下，如何进行多式联运路径的优化，运用双目标整数规划理【收稿日期 2 0 0 9 1 2 3 0 基金项目】国家自 然科学基金项目(6 0 8 7 0 0 1 2)；铁道部科技研究开发计划项目(2 0 0 8 X 0 2 7 一 A)【作者简介】佟璐(1 9 8 3 一)，女，内蒙古乌兰浩特人，北京交通大学交通运输学院博士，主要研究方向为交通运输规划与管理；聂磊(1 9 7 0 一)女，湖南长沙人，北京交通大学交通运输学院教授

10、，博士。一5 7 技 术 与方 法 物流技术2 0 1 0 年3 月刊(总第2 1 2 期)论和方法构建多式联运路径优化模型，最后通过运用启发式 算法对模型进行求解分析为今后的相关研究工作提供理论 依据和工作基础。2 多式联运路径决策模型 在多式联运网络中，运输费用、运输时间、运输质量、运输 服务水平是影响多式联运路径选择的几个重要因素。其中，运 输费用包括各区段的运费、中转费等，运输时间包括各区段的 运输时间、中转站的中转时间等。服务水平主要包括设施条 件、手续便捷度、运输信息畅通度和港口、场站的服务质量等。为了描述多式联运路径选择过程，构建如图 1 所示的多式联 运网络图，构建方式采用文献

11、【1 0】的方法。构建如图 1 所示的多式联运网络图。无向图 G=(N，E)，N 表示网络中的所有节点(仓库、中转站或城市等)，N：其中 i=l，2，n时表示节点站，k=l 2-，m时表示各种运输方式，一 般情况下取 m-4，即k表示铁路、公路、水运、航空；E表示所 有连接边，包括运输弧和方式之间的换装弧；运输弧是相同运 输方式不同节点间的连线，连线的权值为货物在两节点间耗 费的运输费用；换装弧是相同节点不同运输方式问连线，连线 的权值为货物在节点处的换装费用。货物在多式联运网络运 输过程中，在换装节点处的费用包括不同方式间的换装费用 和货物等待引起的额外费用。如果两节点间不提供某种运输 方式

12、或不发生换装，则该边的权值取无穷大。图 1 多式联运网络图 2 1 网络最短路数学模型 建立多式联运网络的数学模型如下：11 n 2=川 +。+d k ly +(1)t n R m i G,7 E m l em l n m in t=+件 +w，(2)吼 件 +V f ”，V k E m (3)1=Q一 ，v i n,kE m f 4)1 V i n，k m =l V j k E m 6 一5 8一 或+l+j+l 2 y V f n，k e m，l e (7)i，0，1)V i e n，k E m，l e m (8)t“k 0 Vi En,k m，z m (9)上述模型中，目标函数(1)为多

13、式联运总成本，由货物流动 总成本、中转总成本和卸货总成本组成；目标函数(2)为最小化 多式联运时间，其中货物实际到达时间由线路运输时间和换 装时间组成；约束(3)表示运输能力约束；约束(4)表示运输弧段 的货物量为总运输量与所经节点总需求量的差值；约束(5)表 示两个节点之间只能选择一种运输方式；约束(6)表示在某个 节点处只能发生转换；约束(7)表示如果在节点 i 运输方式由k 转换为 l，则从节点 i-1 到节点 i，运输方式为 k，从节点 i 到节 点 i+l ，运输方式采用 l；约束(8)为决策变量为 0或 1 变量；约 束(9)为变量为非负性约束。2 2 网络最短路模型参数说明 c

14、川：节点 i，i+1 之间第 k种运输方式单位运输成本；d ：在节点 i，货物从第 k种运输方式转换到第 1 种运输 方式的中转成本；S：在节点 i 由于需求卸货产生的单位成本；f ：从节点 i，i+1 之间第 k 种运输方式货物运输时问；z ：在节点 i 处，运输方式由k转换到l 时的转运时间；w i：在节点 i 处由于需求卸货产生的单位卸货时间；t：节点i，i+l 之间第 k种运输方式的运输能力；l 1 节点 到件1 采用k 种运输方式进行运输 _f十 1 0 甭 则 k l 1 节点f 如果采用辟专 1 运输方式进行运输，k 1 y，1 o 否 则 Q：货物总需求量；q。：为节点 i 的

15、货物需求量；q ，：为节点 i，i+l 之间货物运输量。3 求解多式联运路径优化的蚁群算法 蚁群算法(A n t c o l o n y A l g o ri t h m，A C A)是一种新型的模拟进 化算法，由意大利学者 M D o r i g o、V M a n i e z z o和 A C o l o r i n i 等人 在 2 0 世纪 9 O年代首先提出，称之为蚁群系统(A n t c o l o n y s y s t e m)。它是受到人们对 自然界中真实的蚁群集体行为研究成果 的启发而提出的一种基于种群的模拟进化算法。生物学研究 表明一群互相协作的蚂蚁能够找到食物源和巢之间

16、的最短路 径，而单只蚂蚁则不能。蚂蚁间相互协作的方法是它们在运动 过程 中，能够在所经过的路径上 留下一种称之为外激素(P h e r o m o n e)的物质进行信息传递，而且蚂蚁在运动过程中能够 感知这种物质，并以此指导 自己的运动方向，因此由大量蚂蚁 组成的蚁群集体行为便表现出一种信息正反馈现象：某一路 径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，该 算法已成功的解决了多种组合优化问题。3 1 解的构造 在求解多式联运路径优化问题的蚁群算法中，本文采用 佟璐，等：多式联运路径优化模型与方法研究 技 术 与 方 法 k 只蚂蚁共同构造一个可行解，蚂蚁之间通过信息素值来交换 信息，

17、合作求解并不断优化，同时为该蚂蚁分配一个子周游列 表 H I(i 为蚂蚁编号)，该表记录了这只蚂蚁访问过的点；之后 弓 I 入另一只蚂蚁遵循第一只蚂蚁的行为在剩下的点中继续搜。索。每只蚂蚁是一个独立的用于构造解的过程，蚂蚁的任务是 在有着多方面约束下，依次寻找连通节点，并在连通节点弧上 留下信息素。使用弧的信息素以及启发式信息来决定指派的 次序，应用局部优化进行信息素更新，在所有的 k个蚂蚁都构 造完解后，再应用全局信息素更新。3 2 蚂蚁的路径选择 一r；(【)表示 t 时刻在点 i,j 连线上残留的信息素。初始时刻，各条边上的信息素相等，设 T i(t=o)=c(C为一常数)，蚂蚁 k在

18、运动过程中根据各条边上的信息素大小决定转移方向。P 表 示在 t 时刻蚂蚁 k由点 i 转移到点 i 的概率：施 k p ta b (10)I (r)【仉 【k q t a b 其中，T l i，为启发式信息，表示蚂蚁从点 i 转移到点 j 的期 望程度，本文中取 ii=l d i(d 表示点 i 到点 j 的距离)，0【为 在路径 i i 上残留信息的重要程度，B为启发式信息的重要程 度，集 合t a b u 为 禁 忌 表，ta b u k=，日 。3 3 信息素更新 每一组的所有蚂蚁周游完成后，该组中的蚂蚁所经过的 路径上的信息素要根据下式进行调整：，(f+1)=(1 一，)f，(f)+

19、Av v-(1 1)其中，表示信息素的蒸发系数，一 r ，为本次周游中边 i j 上的信息素增加量，如果边 i j 没有被任何一只蚂蚁走过则 T。取零；否则令 T。，：，L为该组所有蚂蚁所经过的边长 之和 4 求解多式联运路径问题的蚁群算法步骤 S t e p 1：读人各节点之间可以选择运输方式的信息数据，包 括：各种方式的运输时间、运输距离、运输量、各种方式间的中 转时问、中转运费、卸货费用。定义各参数值：O t；B；Q；最 大迭代次数 N C m a x。蚂蚁结构定义：节点间运输成本信息、运 输成本、中转成本、运输时间、中转换装时间、货物到达终点站 总时间、中转记录、线路选择信息。S t

20、e p 2：初始化蚂蚁，蚂蚁结构中所有信息为零。初始化信 息素矩阵，认为满足约束条件的两个结点单向连通，不连通的 结点间的信息素为零。对于连通的结点间的信息素初始值相 同，令 T ii=c(C为常数)。S t e p 3：设置第 k只蚂蚁的禁忌表，将 m只蚂蚁随机分配到 r 1 个节点，使得蚂蚁从任意结点开始搜寻满足约束条件的最大 连通 图。S t e p 4：寻找连通图，设蚂蚁 k此时到达 点，然后搜寻满 I 足跟N 接续的 后序节点N=N ，N：并记录N 到N中 所有 元素的信息素，将其归一化 P _ f p】，P 2,P 3，p ，J 后作为选择下 一节点 N 的概率，按公式(1 O)。

21、为了防止达到局部最优解，设 定一个阈值 P，随机生成一个数，如果 t oP 则选择概率最 大的节点，否则将概率累计求和，大于随机数 的节点作为 选择的下一个节点。蚂蚁 k 移动到 N 点时，N。和 N k 从蚂蚁 k 的周游列表中删除，并对弧上信息素按公式】行更新。S t e p 5：当蚂蚁完成一次循环后，记录蚂蚁的结构中所有信 息，每条弧上的总费用和即为第一个 目标函数的评价值。S t e p 6：全局信息素更新，选择到 目前为止连通图总费用最 少的蚂蚁作为信息素更新的依据。S t e p 7：计算评价值，如果第一个 目标的评价值有所改进，则保留当前解为最好解，在此基础上计算第二个 目标的评

22、价 值。否则，信息素采用上次最好解的信息素。S t e p 8：迭代次数 N C=N C+I，如果 N c小于设定的迭代次数 NC_ma x，则转至 S t e p 2，否则转入 S t e p 9。S t e p 9：输出最优解及 目标函数值。5 算例分析 某运输企业想运一批货物从城市 0到城市 E，途经 A、B、C、D四个城市，而且相邻两个城市之间可选择的运输方式在表 1中给出，其有关参数见表 1 和表 2，各城市货物需求量见表 3，单位搬卸费为 1 元，单位搬卸时间为6 ra i n。在运量变化下，如 何选择多式联运路径，使运输企业既可以节省运输总费用，又 可以缩短运输总时间?表 1 各个城市之间的单位运费和运输时间表 o A A B B c c D D E 注：分母为运输时间(h)，分子为单位运费(元)，M为不存在某种运输方式。表 2 不同运输方式之间的单位中转费用和中转时间表 铁路公路 航空水运 注：分母为单位中转运费(元)，分子为中转时间(h)。表 3 各个城市货物需求量表 旦 0 5 7 0 0 8 用 MA T L A B开发的蚁群算法程序对问题进行求解，蚁群 一5 9