带软时间窗的开放式满载车辆路径问题研究.pdf

《带软时间窗的开放式满载车辆路径问题研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、c0，印”据r励∥一P盯f愕口材铆ffc口flD船计算机工程与应用带软时间窗的开放式满载车辆路径问题研究孙国华SUNGuohua山东经济学院信息管理学院，济南250014SchoolofInfornlationM强agement，sh柚dongEcononlicu11ivcrs时，砌a11250014，ChillaSUNGuohua．ResearchonopenvehicIeroutingprobIemwithfhUloadandsomtimewindows．ComputerEnglneenngandAppⅡcations。20ll，47(17)：13-17．Abstract：ThefIln1

2、0ad廿雏sponationproblemisresearchedtosatis母medem孤dofproductlonent唧nses．Basedon廿leex。clllsivecharact甜sticofmisproblem，it’sconcludedthatt11etotal仃ansponationcostisdetenniIledbymeemp够-load觚ns-portati∞cost．n∞the叩cnVehicleroutiIlgproblemw油如1lloadandsoft·tirllewindowsis仃蛆sfbrredtoamIll廿-d印otopenvehiclerouti

3、ngproblemwi也son—timewiIldows柚dam坟ed·mtegermathematicalmodelispresemedbasedonme廿ansfen．ed鹬ymmetricgraph．PSOalgorimm们thnearneighborinteractionsis画VentosolVetheproblemandisVeri6ed幽ughanex锄ple．111eexpe血entresultspfovemehjglle伍ciencyofthealg嘶血mtosolVetheopenVehicleromillgprob-1emwi_ch伍UloadandsofI．timewi

4、ndows．1【eywords：vehicleroutingpmblemwithmllload；timewindows；panicleswann叩dmization摘要：为满足某些生产制造企业的满载运输需求，针对运输任务对车辆具有独占性的特点，分析得到总运输费用的大小取决于车辆的空车行驶费用，在此基础上，将带软时间窗的开放式满载车辆路径问题转化为带软时间窗的多车场开放式车辆路径问题，在非对称图上建立了相应的数学模型，并设计了近邻粒子群算法对模型进行求解。设计算例对算法进行了验证，实验结果表明：该算法可以快速求得软时间窗的开放式满载车辆路径问题的满意解。关键词：满载车辆路径问题；时间窗；粒子群算

5、法DOI：10．3778／j．is蚰．1002．8331．2011．17．005文章编号：1002．8331(2011)17．0013．05文献标识码：A中图分类号：TP291前言随着世界经济的快速发展和现代科学技术的进步，物流业作为国民经济中的一个重要服务行业，正在全世界范围内迅速发展，并逐渐成为国民经济发展的动脉和基础产业。运输是物流系统最重要的功能要素之～，运输费用占物流系统燕体费用的50％左右，因此，研究车辆路径问题，对降低物流系统的成本具有非常重要的现实意义。对于某些大型的生产制造企业，如水泥行业原材料石灰石与煤炭的运输、钢铁行业铁矿石的运输、木材厂木材的运输，由于运输量非常大，进行

6、的常常是从供应地到需求地的整车运输，车辆在供应地装载了货物后，必须将货物直接送至需求地，在完成此次运输任务之前，不允许穿插服务其他顾客，也就是说，运输任务对为其服务的车辆资源具有独占性，这与一般车辆路径问题中每条线路同时配载多个顾客的货物有一定的差别。同时，由于供应地与需求地通常距离较远，车辆在完成远距离运输任务后，通常直接停靠在需求地或者赶往下一个供应地，一般无需返回配送中心，因此，车辆的行驶线路多是开放式的。文献[1．6】研究了开放式车辆路径问题，但由于车辆同时配载多个顾客的货物，因此，不完全适用于解决满载车辆路径问题；文献[7．9】研究了带时间窗的独占性集送货(PDPTw)车辆路径问题，

7、虽然可以看作满载车辆问题，但由于车辆从配送中心出发最终要返回配送中心，属于单车场闭环路径优化问题，因此，也不完全适用于生产制造企业的开放式车辆路径问题。粒子群算法(PanicleswamlAlgorimm，PS0)是通过对鸟群(或鱼群)的研究而得出的一种群体随机优化算法。它具有概念清晰、实现容易、便于应用等优点，在各类多维连续空间优化问题上均取得了较好的效果u””。但是由于粒子群算法的寻优能力主要