一种基于Voronoi图求解车辆路径问题的混合启发式算法.pdf

《一种基于Voronoi图求解车辆路径问题的混合启发式算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第2期2010年2月。计算机应用研究ApplicationResearchofComputersV01．27No．2Feb．2010一种基于Voronoi图求0日Zk白，}匕12：1／日解车辆路径问题的发式算法张志军1，李峰1，曹布阳2(1．江苏大学计算机科学与通信工程学院，江苏镇江212013；2．同济大学软件学院，上海201804)摘要：针对由多个配送中心和多个客户点组成的物流网络中的车辆路径问题，提出了一种基于“集群第一，路线第二”的路径优化策略，即首先使用Voronoi分割对配送区域进行划分，然后引入综合插入算法和变邻域搜索算法的混合启发式算法求解配送

2、区域内车辆路径问题。通过算例和应用系统的分析与验证表明，该混合算法既能获取质量较优解，同时也具有较好的实时性，能较好地满足实际应用需求。关键词：Voronoi分割；混合启发式算法；插入式算法；变邻域搜索；邻接信息中图分类号：TP301．6文献标志码：A文章编号：1001—3695(2010)02-0515—04doi：10．3969／j．issn．100l-3695．2010．02．031HybridheuristicalgorithmusingVoronoidiagramforvehicleroutingproblemZHANGZhi-junl，LI—Fen91，C

3、AOBu-yan92(1．&hodofComputerScience&TelecommunicationEngineering，五angsuUniversity，Zhe,Cid,,gliangsu212013，Ch／na；2．School矿Soft蝴Egg／咖，蛳Vn／versity，Shangha／201804，Ch／na)Abstract：Thispaperproposedtheoptimizationstrategyofvehicleroutebasedonthestrategyof“clusterfirst。routesecond”whichaimedatth

4、evehiclerouteproblemsmadeupofmultipledispatchingcentersandsale·pointsinthelogisticsnetwork．Firstly。usedVoronoitessellationtodividethedispatchingregions，andthenintroduced’ahybridheuristicalgorithmwhi_chcombinedtheplug-inalgorithmandthevariableneighborsearch(VNS)algorithminordertosolvethe

5、optimizationproblemsofvehiclerouteindispatchingregions．ThishybridalgorithmCanachieveabettersolutiontovehiclemuteoptimizationproblemsthroughtheexperimentresultsandtheanalysisandverificationoftheapplicationsystem．Atthesametime，italsohasgoodreal—timewhichcanbettermeettheneedsofpracticalapp

6、lication．Keywords：Voronoites础afion；hybridheuristicalgorithm；CI；VNS；adjacencyinformation0引言车辆路径问题(vehicleroutingproblem，VfuP)一直是运筹学、管理学、计算机科学等领域的研究热点问题，在现实生活中有着广泛的应用，是一个具有重要理论意义和实际应用价值的研究课题。车辆路径问题一般定义为：对一系列客户，组织适当的行车路线，使车辆有序地通过，在满足一定的约束条件(如货物需求量、发货量、交货时间、车辆容量限制、行驶里程限制、时间限制等)下，在客户可以接受的演算时

7、间内，给出尽可能优化的路线规划方案，最大限度地降低客户的运营成本(运营时间、距离或其他费用)。该问题1959年由Dantzig等人⋯提出后，几十年来已取得大量研究成果。由于VRP是NP—hard问题，难以用精确算法求解，对此类问题求解方法的研究主要集中于能在较短时间内给出较优解的启发式算法。1960年，Clarke等人肛。首先提出一种启发式节省法来建立车队配送路线。启发式节省法简单易懂、求解速度快，但只适合求解小型、简单的VRP。1960--1970年，提出简单启发式算法，包括各种局部改善启发式算法和贪婪法(greedy)等。1970---1980年