计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 76-82.doi: 10.11896/j.issn.1002-137X.2018.04.011
• 2017年全国理论计算机科学学术年会 • 上一篇 下一篇
孙启,金燕,何琨,徐凌轩
SUN Qi, JIN Yan, HE Kun and XU Ling-xuan
摘要: 文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。
[1] GOLDEN B,RAGHAVAN S,WASIL E.The Vehicle Routing Problem:Latest Advances and New Challenges [M].Springer US,2008. [2] CORBERN A,PRINS C.Recent results on arc routing problems:An annotated bibliography[J].Networks,2010,56(1):50-69. [3] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005,166:65-85. [4] PANDI R,MURALIDHARAN B.A capacitated general routing problem on mixed networks [J].Computers & Operations Research,1995,22:465-478. [5] DELL’AMICO M,HASLE G,CARLOS J,et al.An AdaptiveIterated Local Search for the Mixed Capacitated General Routing Problem [J].Transportation Science,2014,50(4):1223-1238. [6] KOKUBUGATA H,MORIYAMA A,KAWASHIMA H.Apractical solution using simulated annealing for general routing problems with nodes,edges,and arcs[M]∥Engineering Stochastic Local Search Algorithms :Designing,Implementing and Analyzing Effective Heuristics.Springer Berlin Heidelberg,2007. [7] BRANDIO J,EGLESE R.A deterministic tabu search algorithm for the capacitated arc routing problem [J].Computers & Ope-rations Research,2008,35(4):1112-1126. [8] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005. [9] BOSCO A,LAGANA D,MUSMANNO R,et al.Modeling andsolving the mixed capacitated general routing problem [J].Optimization Letters,2013,7(7):1451-1469. [10] POTVIN J Y,BENGIO S.The vehicle routing problem withtime windows part II:genetic search [J].INFORMS Journal on Computing,1996,8(2):165-172. [11] CHEN Y,HAO J K,GLOVER F.A hybrid metaheuristic approach for the capacitated arc routing problem[J].European Journal of Operational Research,2016,253(1):25-39. [12] BACH L,HASLE G,WHLK S.A lower bound for the node,edge,and arc routing problem [J].Computers & Operations Research,2013,40(4):943-952. |
No related articles found! |
|