多时间窗车辆路径问题的智能水滴算法

《多时间窗车辆路径问题的智能水滴算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第24卷第6期2015年12月运筹与管理0PERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．24．No．6Dec．2015多时间窗车辆路径问题的智能水滴算法李珍萍，赵菲，刘洪伟(北京物资学院信息学院，北京101149)摘要：研究了多时间窗车辆路径问题，考虑了车容量、多个硬时间窗限制等约束条件，以动用车辆的固定成本和车辆运行成本之和最小为目标，建立了整数线性规划模型。根据智能水滴算法的基本原理，设计了求解多时间窗车辆路径问题的快速算法，利用具体实例进行了模拟计算，并与遗传算法的计算结果进行了对比分

2、析，结果显示，利用智能水滴算法求解多时间窗车辆路径问题，能够以很高的概率得到全局最优解，是求解多时间窗车辆路径问题的有效算法。关键词：车辆路径问题；多时间窗；数学模型；智能水滴算法中图分类号：0226文章标识码：A文章编号：1007—3221(2015)06—0001—10doi：10．12005／orms．2015．189⋯e川gentWaterDropSAlgor_thmfOrVehicIeROulingPrObIemwithMuIljpIeTimeVVindOwSLIZhen—ping，ZHAOFei，LIUHong—w

3、ei(5c^oofQ厂蜘r，nⅡ￡ion，Be玎ing形z￡ziUni秽e，苫i可，日e百玉zg10149，C^i见o)AbStraCt：’I’heVehiclemutingproblemwithmultipletimewindowsisinVestigatedinthispaper．TheconstraintsofVehicle’scapacityandthemultiplehardtimewindowsareconsidered．AnintegerlinearprogrammingmodelofVRPMTWispropos

4、ed，andtheobjectiVefunctionistominimizethetotalcostsincludingthefixedcostsofvehi．clesandthetransportationcostsofVehicles．Basedontheprinciplesoftheintelligentwaterdrops，anIntelligentWaterDmps(IDW)algorithmforsolvingtheVRPMTWisdesigned．Wefurtherdosimulationonanexample，

5、andcomparetheresultsobtainedbyIDwalgorilhmandGA(geneticalgorithm)algorithm．TheresultsshowthatwecanfindtheglobaloptimalsolutionofVRPMTWwithhigherprobabilityusingIntelligentWaterDropsalgorithmthanGeneticAlgorithm．IDWalgorithmisanefficientalgorithmforsolvingVRPMTW．Keyw

6、ords：Vehiclemutingproblem；multipletimewindows；mathematicalmodel；intelligentwaterdropsalgorithm0引言由Dantzig和Ramser于1959年提出的车辆路径问题(vehicleroutingproblem，简称VRP)⋯是组合优化中一类NP难问题。该问题自提出以来，引起了运筹学和管理科学工作者的广泛关注。车辆路径问题的扩展问题也不断得到广大学者的关注。车辆路径问题的扩展情况有：需求不确定的车辆路径问题、道路信息不确定的车辆路径问题。实

7、际物流配送中的很多问题，如连锁经营超市的商品配送问题、连锁经营餐饮门店的原料配送问题。2o、快递企业的快件收取及配送问题等，都可以归结为经典的车辆路径问题或车辆路径问题的扩展情况，因此，该问题有着广泛的应用背景。其中，带时间窗的车辆路径问题(VRPTw)是收稿日期：2014—05-10基金项目：国家自然科学资助项目(11131009，71540028)；北京市属高等学校长城学者培养计划项目(cIT＆TcD20130327)；北京市科委项目《用于电子商务物流的搬运机器人与多机器人现场控制系统研制及应用验证》；北京物资学院重大科研

8、项目《基于可移动货架的订单拣选优化问题研究》。作者简介：李珍萍(1966-)，女，博士，教授，研究方向：智能算法，复杂网络；赵菲(199l一)，女，硕士研究生，研究方向：物流工程；刘洪伟(1977-)，男，博士，讲师，研究方向：最优化理论。2运筹与管理2015年第24卷在经典