动态自适应混合智能算法在VRP问题中的应用

《动态自适应混合智能算法在VRP问题中的应用》由会员分享，可在线阅读，更多相关《动态自适应混合智能算法在VRP问题中的应用（5页珍藏版）》请在装配图网上搜索。

1、物流技术2010年 第3期物流工程与管理第 32 卷 总第 189 期LOGISTICS ENGINEERING AND MANAGEMENT doi:10.3969/j.issn.1674-4993.2010.03.024动态自适应混合智能算法在VRP问题中的应用张磊，鲍福光，彭 扬(浙江工商大学，浙江杭州310018 )【摘 要】货物配置和车辆路径安排是个典型的NP难题。文中在建立 VRP问题数学模型的基础上，构造了求解该问题的混合智能算法。在如何确定车辆数的问题上提岀一种新的算法思路一一动态自适应确定车辆数；同时文 中提岀了一种新的编码思维，将车辆信息引入染色体中；在遗传算法终止后，利用

2、模拟退火对每一辆车的路线分别 进行优化。最后，对具体案例进行仿真实验，证明了文中算法是有效的。【关键词】VRP问题；新式编码；动态自适应；混合智能算法【中图分类号】TP35【文献标识码】A【文章编号】 1674-4993 (2010) 03-0058-03Application of Dynamic Self-Adaptive mixed intellige ZHANG Lei, BAO Fu-guang, PENG Yang(Zhejiang Gongshang University, Hangzhou 310018, China )【Abstract 】Cargo configuratio

3、n and vehicle routing arrangement is a NP. This issue of theestablishment of VRP based on the mathematical model is constructed for solving the problem of hybridintelligent algorithm. In the issue of how to determine the number of vehicles, we put forward a newalgorithm - Dynamic Adaptive determine

4、the number of vehicles; simultaneously, this paper presents a newcoding ideas, the vehicle information pull into the chromosome; in the end of genetic algorithm, usingsimulated annealing line for each car separately optimized. Finally, the simulation of specific cases proves that this algorithm is e

5、ffective.【Key words】 VRP; New coding; Dynamic Adaptive; Hybrid intelligent algorithm 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/ki.iidt 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/ki.iidt1引言随着物流技术和应用的发展，物流

6、配送过程中的车辆路径优化问题（Vehicle Routing Problem VRP）成为一个研究的热点。它是一个 NP难题，不能得到解析解，通常只能通 过各种启发式算法得到近似解。启发式算法求解该问题就成为人们研究的一个重要方向，并出现了多种启发式算法，如Clarke和Wright提出的节约法1，Gillett和Miller提出的扫描法等，虽然这些算法 为求解配送路径优化问题提供了有效的方法，但也存在一定 的问题，如节约法虽然具有运算速度快的优点，但也有组合 点零乱、边缘点难以组合的问题，扫描法为非渐进优化等。遗传算法是J.Holland 教授模拟达尔文生物进化论的自然选 择和遗传学机理的生

7、物进化过程的计算模型2，是一种通过模拟自然进化过程搜索最优解的方法，目前已广泛应用于各 种优化或控制领域。本文将采用混合智能算法去解决VRP问题：遗传算法先从整体方面出发，安排总体路径；最后经过模拟退火进 一步优化每一辆车的路径。在引入遗传算法时的难点有：问题是一个动态的问题，当各个需求点变化时，需要的车辆数就在时时变动， 如何确定车辆数。如何将车辆数加入到编码之中，从而在 编码中体现更多的实际有效信息。如何进行有效的交叉， 适合新式编码。2假设与数学模型假定配送中心最多可以用 m辆车对n个商店进行运输配 送，每个车辆载重为 6 （i =1，2，3， m），每个商店的 需求量为di （i =1

8、，2，n），商店商店j的运输成本 为cj，商店i至应送中心的成本为 c0或c0i （ i, j = 1， 2，n），车辆的载重能力可以满足任意一个商店的要求。 忽略体积因素，在满足各商店配送需求且不超载的情况下， 如何安排每辆车的行驶路径，使总的运输成本最低。弓I入如 下变量：Vik为0-1变量，值为1时，表示第k辆车访问需求点i， 值为 0 时，表示其他情况（i = 1,2,., n; k =1,2,., m）；Rk为0-1变量，值为1时，表示第k辆车经过点i直接 1 94-201 I China Academic Journal Electronic Publijihing House.

9、All rights reserved, http:/ki.iidt 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/ki.iidt【收稿日期】2010-02-20【作者简介】 张磊（1988-），男，宁波人，浙江工商大学信息学院物流管理专业，本科生，研究方向：供应链物流系统工程。彭 扬（1972-，男，六安人，浙江工商大学信息学院，博士，副教授，研究方向：供应链物流系统工程商务智能。 1 94-201 I China Academic Journal Elec

10、tronic Publijihing House. All rights reserved, http:/ki.iidt59张 磊等：动态自适应混合智能算法在VRP问题中的应用19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net到点j , 值为 0 时，表示其他情况(i, j =1,2,.,n;k =

11、1,2,.,m)；建立数学模型:m n nm i n刀刀刀C ij R j kk = 1 j = 0 i = 0J = 1, V i = 1,2. .ff(2)尺啪= I朮=12 “(3)JUw送儿* =工 =r；1Vu=l,2h.,ff,Vk* = L.2.(4)Yjji J,=1,2,.(5)t/J,j = 0,L2-.JF(0)陷丘12./讹=12”.阿(了)P *= ,2,.jj;Jt= 1,2,.,ffl(g)G,(9) Dj = I.2k0.k =1 J,(10)m 0.n0(11)其中，式 （1）表示目标函数整个配送过程中运输成本的最 小化；式 （2）表示某个需求点有且仅有一辆车

12、访问；式 各运输车辆均从配送中心岀发，经过需求点后，最后要回到 配送中心；式 （4）表示每个需求点都有一辆车经过；式 车辆的装载量大于其所访问的需求点的需求量，即不岀现超 载情况发生；式（6）表示点到j点的运输费用与j点到i点的 运输费用相等；式（7）（8）（9）（1和）（11）均为变量的取值范围。3 VRP问题的混合智能算法的构造Step1 :动态自适应确定车辆数假设有n个配送点，各个配送点i （ i =1， 2，n） 的配送量为di （ i =1，2,，n），车限重为b。n常规车辆数的算法为：车辆数=Hdi/b。这是非科学的计算方法，也是不符合实际的，因为货物不可分割，得出的 车辆数可能因

13、为过小而无法得到可行解。本文米用一种新思维 动态自适应车辆数确定法。具 体实现是将所有的客户点随机排序，从头依次将各客户点的 货物量逐步累加，在超过车辆满载量之前为一车，直至所有 的货物装完为止，累加并记录该条染色体的车辆数。通过一 个大种群的染色体算岀其中记录的最少车辆数作为本模型所 要的车辆数。此方法避免了货物被迫分割现象的发生，同时 也避免了同批货物分次到达同一个目的地的情形。Step2 :新的编码方式本文采用自然数编码方法，构造配送路线优化问题的解 向量的染色体结构。但如何将车辆数体现在编码中并且能发 挥应有的效果则是当前最大的难题。本文将采取一种新的编码思维方式，假设问题是1个配送中

14、心、n个配送点的分配选择与路径优化问题，本文自然 数编码的染色体长度将不再是常规思维下的1+n，而是n+m-1（车辆数由step1中算出），多出白m-2个点，称之为“虚拟配送中心” ，m-1个配送中心分散在染色体中间将染色 体分割成m段，每一段则为每辆车的路径。本文称这种新型 的编码思维方式为：“分割染色体法”。这种编码的创新为我 们整个算法的实现奠定了基础，同时可以与下面的交叉建立 一个良好的衔接。Step3 :初始化群体随机产生N条染色体组成初始群体，并淘汰不符合约束的 染色体，对每一条染色体，分别计算它们的函数适应度值，并 按适应度值排序。由于约束条件的限制，随机产生的染色体将 会有很大

15、一部分不符合条件，所以一般将初始群体取为3N。Step4 :适应度的计算对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函 数值（即各条配送路径的长度之和）。本文根据配送路径优化 问题的特点所确定的编码方法，能够知道每辆车所行走的路 线，对各条路径逐一进行判断，看其是否满足约束条件（是 否超载），若不满足，则将该条路径定为不可行路径，目标函 数值加一个绝对大的惩罚数。（3）St表示：选择选择采用轮盘赌3的方法进行，选择得到的个体进入下一步交表示变异。在每代种群中，以一定的交叉概率对个体 进行交叉重组，在此交叉概率中采用自适应概率。这样，可 以有

16、效加强优秀个体的遗传能力，保护其进入下一代；对于 适应度低于平均值的个体，采用较大的交叉概率，增大弱势 个体的淘汰率。但是同时，又保证了在进化初期优秀个体不 会占有完全的主导地位，降低了局部最优解的岀现概率。Step6 :有效交叉标准遗传算法的交叉只是简单的随机交换。结合VRP问题的实际情况以及新式编码，本文采用能与新式编码良好结 合的刘海交叉，交叉的过程也是一种择优的过程，即交叉 的同时，也在择优。应用这种交叉法的优点在于：能跳出局部最优解，继续寻找问题的全局最优解；收敛速度非常快，具有较强的全局搜索能力。能够保证得到的子代染色体一定是可行的且比 其父代染色体更加优异，交叉本身就是一次择优。

17、Step7 :引入模拟退火实现每一辆车的自优化U 別一!整味 両工昭”L ：处送供图1算法整体流程图在遗传算法结束时，利用模拟退火实现解的更优，因为60物流工程与管理32卷染色体被分割后的每一段并不可能在遗传算法下都实现最优，而通过模拟退火可以实现局部（也就是每一小段染色体） 都能得到最优路径（每一辆车各自走的都是最优），从而在不 改变每辆车的货物分配选择条件下，只改变了路径顺序，从 而实现整体解的进一步优化。4实例验证本文根据上述混合智能算法编制了 MATLAB程序，并 对文献5列岀的一个某配送中心对 13个需求点进行送货的物流配送路径优化问题实例进行了实验计算，文献中采用节 约矩阵法得到解

18、决方案5，得到的总行程是 176。汽车的载重量为200t。可以根据载重量和各点需求量，采用本文中的动态自适应车辆数确定法算岀，车辆数等于4辆图2十次运行结果比较图算法，提出一种新的算法思路 动态自适应车辆数确定法， 使本文的模型更符合实际情况；同时本文提岀了一种新的编 码思维方式，将车辆信息引入染色体中，进行分割染色体处 理，同时应用与此编码结合度较好的择优交叉方式，对解决 类似的组合优化问题具有一定的参考价值。 本文在建立VRP问题的数学模型的基础上，构造了求 解该问题的遗传算法与模拟退火结合的混合智能算法。实验 计算结果表明，此混合智能算法是一种性能优良的启发式搜 索方法，利用该方法可以方

19、便有效地求得物流配送路径优化 问题的最优解或满意解。 文本的模型与算法能很好的应用于有多家代理店的同 城速递业务和具有多家连锁店的大型企业的配送业务的货物 配置与路径优化安排。参考文献1陈晓伟，张悟移，耿继武.节约法在配送路线选择中的应用J.昆明理工大学学报（理工版）,2003,（04）:140-1432陈国良，王煦法，庄镇泉，王东生.遗传算法及其应用M.19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal E

20、kctronic Publishing Huuse. Al rights reserved, ki net表1十次运行结果比较表次数12345678910平均遗传算法160178170165168164168167166161166.7混合智能算法159163160159162161161161160159160.119Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net在表1中可以发现，运用单独遗传算法10次运行的平均值为166.7 ，而运用混合智能算法10次运行的平均值为

21、160.1 ，而且，几乎每一次都有所改进。其中1、4、，第6、10次不大于170属于最优值符合条件自动停止。其中第1、4、10次的结果得到了最优值 159，对比采用节约矩阵 法5得到的总行程176，有了较大的改进。5结论VRP问题中，在如何确定车辆数的问题上，摒弃传统北京：人民邮电出版社， 1996.3王小明.遗传算法一一理论、应用与软件实现M西安： 西安交通大学出版社， 2002:25-26.4刘海，郝志峰，林智勇.改进遗传交叉算子求解TSP问题J.华南理工大学学报（自然科学版）,2002,（12）:71-73.5美森尼尔，乔普瑞彼杯,梅因德尔著，李丽萍译供应连 管理-战略、规划与运营M.北

22、京:社会科学文献岀版社 2003,11.19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net（上接第31页）就必须周期性地检查满足顾客要求的能力， 以及初次接触后顾客要求的变化；持续性接触。持续的、专 门的顾客交流对主要客户很重要，关于满意程度、顾客拜访 及其他交流方式的讨论为评估顾客满意提供了迅速的反

23、馈信 息，使供应商在变化及发生问题前预先觉察，顾客和供应商 通过设计执行的改进计划都能受益。现代物流要求第三方物流企业已不仅仅是客户物流业务 的承包人，而是要求其服务延伸到客户的经营活动中，与客 户形成利益同享，风险共担的伙伴关系，第三方物流必须改 变传统的经营理念、管理方法，扩展服务范围，提高服务质 量，才能提高市场竞争力，实现企业的发展壮大。所以，第 三方物流企业要注意练内功，强化管理，完善功能，提高服 务质量。物流企业之间要加强合作，避免互相倾轧，只有形 成健康有序的市场环境，才能保证现代物流业最终走上正轨,并茁壮发展起来。参考文献1（美）唐纳德 J 鲍尔索克斯，戴维J 克劳斯.林国龙，

24、 宋柏，沙梅译.物流管理M.北京：机械工业岀版社， 2000.2国际物流师培训教程编委会.国际物流师培训教程M0 .北京：中国经济出版社，2006.3曾剑，王景锋，邹敏.物流管理基础M.北京：机械工 业出版社，2006.4田源，周建勤.物流运作实务M.北京：清华大学出版社，北京交通大学出版社,2004.5江苏省职业技能鉴定中心组织.物流师基础知识M.呼和浩特：内蒙古人民出版社，2005. 王自勤.物流管理概论M.杭州：浙江大学出版社，2004.19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net