论文研究-遗传算法求解多式联运最小费用问题 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.21M 资料格式：pdf 举报版权申诉

weixin_39840914-11546823-4744302543375730569.pdf-第1页.png

第1页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第2页.png

第2页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第3页.png

第3页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第4页.png

第4页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第5页.png

第5页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第6页.png

第6页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第7页.png

第7页 / 共8页

weixin_39840914-11546823-4744302543375730569.pdf-第8页.png

第8页 / 共8页

文本预览

遗传算法求解多式联运最小费用问题 http://www.paper.edu.cn 王欣欣北京邮电大学自动化学院北京（100876） E-mail:mushroomxinxin@gmail.com 摘要：多式联运是现代物流网络运作的主体和纽带。在多品种、小批量的市场环境下，多式联运的物流系统规划工作变得更加重要也更加复杂。本文以运筹学为基础，研究多式联运最小费用问题，将该问题划分为两个步骤求解。第一步根据运输路段信息枚举可行的路线；第二步运用遗传算法，将第一步生成的路线作为基因，所有订单的路线构成染色体，考虑运输的重量、数量、体积等能力限制约束，建立数学模型。提出一个基于对应位杂交、自适应相关变异的混合遗传算法，改善求解速度。最后对一个小规模算例(7 点* 15 订单*12 路段) 进行求解，并对得到的结果进行了验证。关键词：物流，多式联运，遗传算法 1 引言多式联运是现代物流网络运作的主体和纽带，是贯穿整个现代物流活动的主线[1]。在越来越个性化的市场环境下，多式联运系统规划工作变得更加重要也更加复杂。建立准确、合理的多式联运模型，可提高企业的运送速度和服务质量，实现高效、低耗的物流运输目标，从而获得巨大的经济效益。针对多式联运的模型和算法，很多学者从不同的角度分别对最短路、最短时间以及基于时间因素的最短路问题进行了研究[2~6]。Angelica Lozano 等在每条有向边对应一种运输方式的情况下，研究了多式联运的最短路问题 [2]。张运河等将多式联运广义最短路问题纳入到多重图最佳路线的求解上，通过在图中增加虚拟的发、到站，使得该问题完全转化为一个最短路问题，应用静态最短路算法对其求解[3]。魏众、申金升等提出了一个适用于多节点、长距离的多式联运运输网络问题，并运用系统的理论和方法，建立多式联运下的路径最短时间模型，并求得与之对应的路径的运输费用[4]。魏航等针对时变条件下多式联运的最短路问题，考虑了各个节点的不同运输方式之间有出发时间限制的约束条件[5,6]。这些研究对提高企业物流运输效率有一定的意义。然而决定企业运输成本的因素有很多，不是简单的最短路径或者最短时间。在运达时间允许的情况下，换另外一种运输方式多走一些路程也可能节约运输成本。遗传算法[7]是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法具有大范围全局搜索的能力和刻扩展性，对优化对象既不要求连续，又不要求可微，并具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多级值优化和组合优化问题。作为一种新的全局优化搜索算法，遗传算法在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。因此，本文采用遗传算法对多式联运最小费用问题进行了研究。 2 建立多式联运问题模型 2.1 问题提出与假设某第四方物流企业与多个承运商合作，将业务发展到了多个城市。为满足客户对运输的要求并降低运输成本，获得最大的利润，该公司需要结合订单和各承运商能够提供的运输路 - 1 -

http://www.paper.edu.cn 段，规划确定各订单的运送路线。运用遗传算法求解该问题，需要进行如下的假设：需求假设 1：每个订单都有固定的重量、体积和数量，而且订单不能被拆分。需求假设 2：不存在单张订单超过路段运送能力的现象。假设数据中已将运货量过大的订单拆分为若干个运货量适中的小型订单。成本假设 1：运输成本就等于配送的单位成本同所配送的重量的乘积，不考虑数量和体积的因素。成本假设 2：数据中采用平均的运输成本，不考虑因由淡季、旺季的影响而造成的运输报价不同的因素。成本假设 3：货物中途的转运成本和因转运产生的存储成本为零。为公司业务覆盖的 d 个城市的集合。为 m 个运货订单的集合。其中订单 i 的起始城市 1 = = = d 1,2,... ) m ) 1,2,... { s s S 2, 1 { O o o , 2 2.2 定义符号和变量 } k s s ， ( ,... ,... k d } i o o ，( ,... ,... = i m site S∈ ， 2i site S∈ 。和到达城市分别为 1i } n r 1,2,... ) ， ( ,... = n j S∈ ， 2 j site site S∈ 。的起点终点分别为 1j 量的运输费用。路段 j 上每班次的运输能力为 r r 2, 1 r ,... { R = j 为各承运商可提供的 n 条路段的集合。其中路段 j tUnit 为单位重 carrier 为承运商名称， cos quantity ， volume 和 j weight 。 j j j j 定义 m*n 的二维矩阵变量： ijX 1, ( ) ⎧ 当订单i经过路段j = ⎨ 0, ⎩ j (当订单i不经过路段 ) 。 tUnit 。已知赋权有向图 D=（S，R），对每个弧 Rj=（ 1j 定义变量 Path 为得到的路线集合，其中共有 h 个元素，其序号用 p 表示，（p=1,2,…h）。 site 称为 Path ={R ,R ,...,R }。我们称 Pathp 为从点 site 的一条路线，点 site 为终点 Site2p。Costp 表示第 p 个路线的单位运输费用。则起始点 Site1p，点 2 jx site ），有相应的权 cos site 到 1jx site ， 2 j 11j 11j j2 j1 jx p j 2.3 问题的分解由于多式联运问题条件和约束都很复杂，对其进行明确的数学建模就显得十分困难。为清晰的表达建模思想，将该问题的求解划分为两个步骤。第一步，由 S 和 R 构成的有向图 D=（S，R），利用求指定点对间的路线，得到订单可以运输的所有可供选择的路线。以图 2-1 为例。实线代表公路运输，三条代表不同的承运商；虚线同理代表铁路运输。若存在从 1 点到 2 点的订单，则六条路段便构成了六条路线。即为了第二步找到的解更全面，要对所有可能的路线进行枚举。 - 2 -

http://www.paper.edu.cn 1 2 图 2-1 城市 1 到城市 2 的连通图本步骤主要考虑的是空间约束：同一订单所经过的路段的起点和终点首尾相接并且整条路线的起点终点与订单的起点终点相同。根据订单的起点、终点数据，得到需要枚举路线的起点终点，再逐一进行枚举。至此，可将 ijX 的取值范围缩小，从而压缩解空间。第二步，利用遗传算法对订单和路线进行编码和运算，进行最小费用求解，同时判断时间窗口的约束。获得问题的可行解乃至最优解。这样做的好处有二：一是将复杂的问题简单化，使求解过程清晰易懂；二是能够充分考虑可行解的不同情况，避免过早陷入局部最优的局面。缺点是当问题规模扩大时，第一步的求解变得繁琐复杂，严重影响内存的分配和求解速度的提高。针对这一问题，结合第二章的费用假设，可以将求解所有路线转变为求解运输订单的最短路和次短路，调整后求解速度和内存占用问题都可得到较好的解决。 2.4 问题的基本模型根据问题的业务逻辑，基本数学模型可以表示为： Cost Min m n = ∑∑ i 1 = j 1 = weight i *cos tUnit X * j ij 。 k m ∑∑ l 1 = i 1 = quantity X T * * ij i ≤ quantity j jl ； Subject to k ∑∑ m l 1 = i 1 = volume X T * * ij i ≤ volume j jl ； k m ∑∑ weight X T * * ij i jl ≤ weight j i l 1 = 1 = 。 3 多式联运问题的遗传算法设计设计遗传算法的一个重要步骤是，对所解问题的变量进行编码表示，编码表示方案的选取在很大程度上依赖于问题的性质及遗传算子的设计。通常，在设计遗传算法时，只有两个方面与所求问题有关，即问题的编码表示与适应函数的确定。 3.1 染色体结构的确定将问题的潜在解从解空间转换到遗传算法编码空间的过程称为编码。在标准遗传算法中，染色体是用二进制码 0 和 1 进行编码的，但是这种编码机制在解决旅行商问题等与顺序有关的带有约束的优化问题时就受到了限制。为此人们开发出了新的编码机制，自然数编码就是其中之一[8]。自然数编码的定义为：如果染色体的基因为自然数 1 到 m 的全排列，则称此染色体为长度为 n 的自然数编码染色体。自然数编码的优势是顺序自然确定，并且满足 - 3 -

http://www.paper.edu.cn 某些约束条件。针对多式联运问题的遗传算法采用自然数编码有多种不同的编码方案，好的遗传算法编码方案应该能够从候选解中减少或消除冗余的解。冗余是指一个解通过一个染色体经过一系列方法后再现并且还能够出现多次的情况。冗余解的出现扩大了查找空间，降低了算法的查找效率。本文采用自然数编码的变形——整数编码，染色体的每个基因位的值是 1~h(路线序号) 和其他用于划分染色体为不同部分的标志位(订单序号的相反数)。 -1 2 -2 14 -3 7 -4 9 Order1 Order2 Order3 Order4 图 3-1 染色体设计方案 1 运输订单的路线序号订单的序号的相反数注：以四个订单为例，染色体标为淡蓝色图 3-1 为根据单染色体设计方案设计出的染色体，这种设计使用了一个长度为 2m 的染色体，因此称之为“单染色体”设计方案。该方案中，m 个订单依次编号为-1 到-m 并按顺序排列，其后分别紧随着运输路线编号。因此这个长度为 2m 的整数列的任何一种排列组合都可能是问题的解。这样编码还可以继续压缩。将订单的序号位去掉，运输路线序号出现的顺序即为其代表的订单。具体设计方案见图 3-2。这样，染色体长度从 2m 变为 m，即节约了内存空间，又为后续算子操作提供方便。 1 2 5 16 8 21 11 19 13 23 路线序号 1 2 3 4 5 6 7 8 9 10 订单序号 3.2 初始群体的确定图 3-2 染色体设计方案 2 为了能使算法收敛到全局最优，遗传群体应具有一定规模；但为了保证计算效率，群体规模也不能太大。一般说来，群体规模取值在 10 到 100 之间比较合理。在初始化染色体时，先将 m 个订单的所有运输路线中任选其一，这样 m 条路线按顺序排列就构成一条满足问题需要的染色体。重复这一过程，直至生成满足群体规模数的染色体。 - 4 -

http://www.paper.edu.cn 在确定初始群体时，要充分考虑订单与路线的起点终点的匹配和不同路线的覆盖，既能保证初始群体不包含不可行解，又能保持群体特征的多样性。 3.3 适应函数的确定目前，我们在设计遗传算法时，群体规模一般在几十到几百之间，与实际物种的规模相差甚远。因此，个体繁殖数量的调节在遗传算法中比较重要。如果群体中出现了超级个体，即该个体的适应值大大超过群体的平均适应值，则按适应值比例进行选择时，该个体很快会在群体中占有绝对的比例，从而导致算法较早地收敛到一个局部最优点，这种现象称为“过早收敛”。又如在搜索过程的后期，虽然群体中存在足够的多样性，但群体的平均适应值可能会接近群体的最优适应值。在这种情况下，群体中实际上己不存在竞争，因而搜索目标难以得到改善，这种现象称为“停滞现象”。基于上述原因，改变算法性能的方法之一，就是对适应值进行调节，即通过变换来改变原适应值间的比例关系。常用的比例变换有线性变换及指数函数变换等。本文根据问题的特点将目标函数运输费用最小作为主要评价标准。由于目标函数不存在为负的可能性，因此确定适应度函数为： Fit ( ( ) f x ) = 1 ( ) f x ，其中 ( f x ) 为目标函数。另外，需要在适应函数的基础上加入惩罚函数 ( )P x 。易知， 0 < Fit ( ( ) f x ) < 1 。要使不可行解获得惩罚，只要令 P x = 。 ( ) 1 综上，本文中适应函数确定为： Fit ( ( ) f x ) = 1 ( ) f x 1 ( ) f x ⎧ ⎪⎪ ⎨ ⎪ ⎪⎩ ,( x ) 为可行解。 − 1 ( ) ，为不可行解 x 3.4 遗传算子的确定 (1) 选择算子选择算子的好坏直接影响了遗传算法的收敛性，选择压力过大容易导致未成熟收敛，选择压力过小又容易导致收敛速度过慢[8,9]。选择算子的选择压力按适应值比例选择、线性排名选择、锦标赛选择、(L,K)选择、(L+K)选择的顺序从弱到强[9]。由于多人旅行商问题的搜索空间较大，所以本文采用线性排名选择以便达到成熟收敛。运用 Michalewcz 提出的非线性排序的选择概率计算公式： P i ⎧ ⎪= ⎨ ⎪⎩ q (1 − q (1 − i q ) ) N 1 − i ,( = i N ,( = 1 − 1,2,... N − 1) ) 。理论上 q 为排序第一的选择概率，但是本文算法采用精英保留策略，即当前代的最优个体不参加遗传操作直接进入下一代，因为在选择操作中保留当前最好解的遗传算法能以概率收敛到最优解。也就是说这里的 q 为排序第二的选择概率。 (2) 交叉算子 - 5 -

http://www.paper.edu.cn 对不同的编码方式，遗传算子的具体操作形式有所不同。要求解的问题是物流配送车辆调度优化问题，需要较好的保留起点终点一致和路段的顺序关系，所以在这里采用对位交叉，即两父代染色体对应基因位进行交叉，避免非对应位的交叉。具体步骤解释如下： 1、在两父代染色体中任意插入两个交叉点。如： P1={2,3,5, ||7,5,9,13,17,15,||21}； P2={4,6,5,||11,4,8,14,19,16,||23}。 2、将两个切割点之间的基因进行交叉得到两个子代染色体，完成变异过程。 w1={2,3,5, ||11,4,8,14,19,16, ||21}； w2={4,6,5, || 7,5,9,13,17,15, ||23}。 (3) 变异算子对于 MMTTW 问题，随机的变异容易造成较优的解变成不可行解。为了避免这一情况，由于第一步已经枚举了运输路线，因此针对订单的运输路线，设定变异只能发生在相同起点和终点的路线之间。 3.5 终止条件遗传算法是一种反复迭代的搜索方法，它通过多次进化逐渐逼近最优解而不是恰好等于最优解，因此需要确定终止条件。常有的方法有三种[10]。 1、规定遗传迭代的代次。刚开始时，迭代次数小一些，如规定 10 次。然后视情况逐渐增加次数，可达上千次。 2、当目标函数是方差这一类有最优目标值的问题时，可采用控制偏差的方法实现终止。一旦遗传算法得出的目标函数值(适应值)与实际目标值之差小于允许值后，算法终止。即： f x ( ) f δ∗− ≤ 。 f x 为遗传算法得出的目标函数值； f ∗ 式中 ( ) 3、检查适应度的变化。在遗传算法后期，一旦最优个体的适应度没有变化或变化很小为实际目标值；δ为足够小的数。时，即令计算中止。本文采用比较简单易实现，同时也是最常用的方法 1。确定最大遗传代数为 S 与 R 个数的乘积，即（d*n）。 4 算例下面以某一个城市到另外多个城市的运输订单为例，给出一个简单的算例。设有城市 S =7 个，需要运输的订单共有 O =15 个。共有两种运输方式，分别为航空和公路。已知可供选择的路段有限，所有可以利用的路段承运商的数据如表 4-1；各订单的相关数据如表 4-2 所示。利用本文的遗传算法求解，得到了这些订单的运输计划如表 4-2。表 4-1 路段数据表序起终费数量体积重量号点点用能力能力能力 5000000 5000000 A1 001 002 1 5000 5000000 5000000 A2 001 002 1.1 5000 5000000 5000000 A3 001 005 1.2 5000 5000000 5000000 A4 001 005 1.3 5000 20000 C1 001 002 .4 5000000 5000000 20000 5000000 5000000 C2 001 002 .4 C3 001 005 .5 20000 5000000 5000000 - 6 -

http://www.paper.edu.cn C4 001 005 .5 C5 002 006 .2 C6 002 003 .2 C7 005 004 .3 C8 005 007 .3 20000 5000000 5000000 5000000 5000000 20000 5000000 5000000 20000 5000000 5000000 20000 20000 5000000 5000000 表 4-2 订单数据及结果表最小运输成本：52850 序号数量体积 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2799 5406 4779 17 3331 4187 2973 6971 2841 3237 2445 49 3597 5547 9321 21 50 40 1.9673229 0 20 32 25 50 25 28 14 5.6482105 0 25 50 80 585 8470 6140 10000 6140 8670 4210 5080 9000 12000 重量起点终点结果 2500 7560 7120 001 001 001 001 001 001 001 001 001 001 001 001 001 001 001 005 C3 001 005 005 C3 001 005 007 C3 001 005 C8 005 007 006 C1 001 002 C5 002 006 003 C1 001 002 C6 002 003 007 C3 001 005 C8 005 007 004 C3 001 005 C7 005 004 002 C1 001 002 006 C1 001 002 C5 002 006 002 C1 001 002 003 C1 001 002 C6 002 003 006 C1 001 002 C5 002 006 003 C1 001 002 C6 002 003 006 C1 001 002 C5 002 006 002 C1 001 002 根据运筹学图论的理论进行验证，得到的结果是最优的，同时满足运输能力的限制。 5 结论利用给出的模型，可以求解得到从起点到终点之间，满足订单要求的运输计划，并且满足总的费用最小化。运输决策者可以根据自身的条件，添加一些约束条件求解运输计划。当然，在给出的模型中，没有考虑转运成本、转运能力以及运输时间等限制，考虑这些问题也将会是一个很有意义的问题。 - 7 -

http://www.paper.edu.cn 参考文献 [1]. 曾露玲. 现代物流和国际多式联运的关系［J］. 物流科技,2005,28(113): 18～19. [2]. Lozano A, Storchi G. Shortest viable path algorithm in multimodal networks ［J］. Transportation Research Part A ,2001,35 : 225～241. [3]. 张运河. 优化多式联运问题的一种广义最短路方法研究［J］. 铁道学报,2006(8), 28,(4):22～26. [4]. 魏众,申金升. 多式联运的最短时间路径-运输费用模型研究［J］. 中国工程科学,2006(8), 18(18): 61～ [5]. 魏航,李军,蒲云. 时变网络下多式联运的最短路径问题研究［J］. 系统工程学报,2007(4), 22(2) :205～ [6]. 魏航,李军,刘凝子. 一种求解时变网络下多式联运最短路的算法［J］. 中国管理学,2006(8), 14(4): 56～ 64. 209. 63. [7]. 周明，孙树栋，遗传算法原理及应用［M］.北京:国防工业出版社，1999:1~32 [8]. Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning ［ J ］ . Addison-Wesley-Publishing, 1989. [9]. Back T. Selective pressure in evolutionary algorithms: a characterization of selection mechanisms ［A］. Orlando, Proceedings of the first international conference on evolutionary computation ［C］. USA, 1994. [10]. 禹建丽，李晓燕，王跃明，韩平著.一种基于神经网络的机器人路径规划算法［J］. 洛阳工学院学报.2001，22(1):31~34 Study on the Min-Cost Problem of Multi-Modal Transport With Genetic Algorithm No.10 XiTuCheng Road Haidian District,Beijing （100876） Wang Xinxin Abstract Multimodal transport is a link and the main operation of modern logistics network. In multi-species, small quantities of the market environment, the logistics system planning of multimodal transport has become more important and more complex. This paper is based on operational research to study the minimum cost problem of multimodal transport. The issue is divided into two steps to solve. The first step enumeration practicable path according to the route information; the second step using genetic algorithm, paths in the first step are generated as gene, all the paths of orders constitute chromosome. Mathematical model was established considering the weight, quantity and size restrictions. Based on the corresponding position crossing and adaptive mutations, a hybrid genetic algorithm was proposed to improve the speed of solving. Finally, The solution to a small-scale problem (7points* 15orders* 12routes) was presented to illustrate the model and the algorithm. Keywords: logistics: multi-modal transport; genetic algorithm. - 8 -

分享到：

赞收藏

资料库

论文研究-遗传算法求解多式联运最小费用问题 .pdf

相关推荐

开发技术

热门标签

最新资料