资源描述：
《MK_带软时间窗的集货与送货多车辆路径问题节约算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第10卷第2期交通运输工程学报Vol10No22010年4月JournalofTrafficandTransportationEngineeringApr.2010文章编号:16711637(2010)02009905带软时间窗的集货与送货多车辆路径问题节约算法祁文祥,陆志强,孙小明(上海交通大学机械与动力工程学院,上海200240)摘要:研究了物流配送中多车运输的集货与送货车辆路径规划问题,以增加时间惩罚费用的方式插入软时间窗约束,将租车费用、货车运输费用和时间惩罚费用三者之和
2、最小作为优化目标,建立数学模型。采用启发式节约算法求解该模型,考虑时间惩罚费用和运输费用,比较每一配送节点上直接送货和间接送货的节约费用关系,求出最优配送路径。试验结果表明:当配送次数达到50次时,货车平均装载率仍能达到80%以上,该节约算法能减少货车空程行驶和租车次数,优化了全局费用。关键词:多车辆路径问题;集货与送货;启发式节约算法;软时间窗中图分类号:U492.3文献标志码:ASavingalgorithmofmultivehicleroutingproblemwithpickup
3、deliveryandsofttimewindowQIWenxiang,LUZhiqiang,SUNXiaoming(SchoolofMechanicalEngineering,ShanghaiJiaotongUniversity,Shanghai200240,China)Abstract:Multivehicleroutingproblemwithpickupsanddeliverieswasstudied,andsofttimewindowconstraintwasconsidered
4、byaddingtimepunishmentcost.Themathematicalmodelwasbuilt,anditsoptimizedobjectwastheminimumofcombinationwithvehiclerentcost,transportationcostandtimepunishmentcost,andthemodelwassolvedbyusingheuristicsavingalgorithm.Timepunishmentcostandtranspirationco
5、stwerecalculatedrespectively,andtherelationbetweendirectandindirectdeliverieswascomparedtoobtainbestroutes.Testresultindicatesthatwhenthetimesofpickupsanddeliveriesreach50,theaverageloadingrateoffreightcarstillachievesabove80%,sotheheuristicsavingalgo
6、rithmcanreducethedistancewithoutloadageandrenttimes,andoptimizetotalcost.2tabs,4figs,11refs.Keywords:multivehicleroutingproblem;pickupanddelivery;heuristicsavingalgorithm;softtimewindowAuthorresumes:QIWenxiang(1984),male,graduatestudent,+86213420
7、6782,sjtuqwx@gmail.com;LUZhiqiang(1968),male,associateprofessor,+862134206782,zhiqianglu@sjtu.edu.cn.外包给第三方物流企业,而多批次、小批量的送货模0引言式也成为各企业降低库存风险的重要手段。另一方随着第三方物流的兴起,很多企业为降低物流面,第三方物流企业出于自身运营成本考虑,在满足成本,越来越倾向于把原来由自己承担的运输任务客户运输要求的前提下需要采取有效的路径优化方收稿日期:2009
8、1218基金项目:国家自然科学基金项目(70771065);上海市浦江人才计划项目(07PJ14052)作者简介:祁文祥(1984),男,湖北武汉人,上海交通大学工学硕士研究生,从事第三方物流协同服务优化研究。导师简介:陆志强(1968),男,江苏太仓人,上海交通大学副教授。100交通运输工程学报2010年案,才能实现自身利益的最大化。制。货车一次只进行一个任务,不考虑货物拼车情车辆路径规划是降低运营成本的重要手段之况;如果某个任务的送货
