A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems

References

• Ahuja , R. 2002 . A survey of very large-scale neighborhood search techniques . Discrete Applied Mathematics , 123 ( 1–3 ) : 75 – 102 .
   Web of Science ®Google Scholar
• Aurenhammer , F. 1991 . Voronoi diagrams – a survey of a fundamental geometric data structure . ACM Computing Surveys , 23 ( 3 ) : 345 – 405 .
   Web of Science ®Google Scholar
• Baker , B.M. and Ayechew , M.A. 2003 . A genetic algorithm for the vehicle routing problem . Computers & Operations Research , 30 ( 5 ) : 787 – 800 .
   Web of Science ®Google Scholar
• Bakolas , E. and Tsiotras , P. 2010 . The Zermelo–Voronoi diagram: a dynamic partition problem . Automatica , 46 ( 12 ) : 2059 – 2067 .
   Web of Science ®Google Scholar
• Balseiro , S.R. , Loiseau , I. and Ramonet , J. 2011 . An Ant Colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows . Computers & Operations Research , 38 ( 6 ) : 954 – 966 .
   Web of Science ®Google Scholar
• Bentley , J.L. 1992 . Fast algorithms for geometric traveling salesman problems . ORSA Journal on Computing , 4 ( 4 ) : 387 – 411 .
   Google Scholar
• Blum , C. 2005 . Ant colony optimization: introduction and recent trends . Physics of Life Reviews , 2 ( 4 ) : 353 – 373 .
   Web of Science ®Google Scholar
• Bolduc , M.-C. 2010 . A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars . European Journal of Operational Research , 202 ( 1 ) : 122 – 130 .
   Web of Science ®Google Scholar
• Branchini , R.M. , Armentano , V.A. and Løkketangen , A. 2009 . Adaptive granular local search heuristic for a dynamic vehicle routing problem . Computers &Operations Research , 36 ( 11 ) : 2955 – 2968 .
   Web of Science ®Google Scholar
• Brandão , J. 2011 . A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem . Computers & Operations Research , 38 ( 1 ) : 140 – 151 .
   Web of Science ®Google Scholar
• Cao , E. and Lai , M. 2009 . A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands . Journal of Computational and Applied Mathematics , 231 ( 1 ) : 302 – 310 .
   Web of Science ®Google Scholar
• Chen , B. 2012a . Reliable shortest path finding in stochastic networks with spatial correlated link travel times . International Journal of Geographical Information Science , 26 ( 2 ) : 365 – 386 .
   Web of Science ®Google Scholar
• Chen , B. 2012b . Finding reliable shortest paths in road networks under uncertainty . Networks & Spatial Economics. , doi: 10.1007/s11067-012-9175-1
   Web of Science ®Google Scholar
• Choi , Y. 2009 . Multi-criteria evaluation and least‐cost path analysis for optimal haulage routing of dump trucks in large-scale open‐pit mines . International Journal of Geographical Information Science , 23 ( 12 ) : 1541 – 1567 .
   Web of Science ®Google Scholar
• Coy , S. 1998 . See the forest before the trees: fine-tuned learning and its application to the traveling salesman problem . IEEE Transactions on Systems, Man and Cybernetics , 28 ( 4 ) : 454 – 464 .
   Web of Science ®Google Scholar
• Devarenne , I. , Mabed , H. and Caminada , A. 2008 . “ Adaptive tabu tenure computation in local search ” . In EvoCOP 2008, LNCS 4972 , Edited by: van Hemert , J. and Cotta , C. 1 – 12 . Berlin : Springer-Verlag .
   Google Scholar
• Dongarra, J., 2011. Performance of various computers using standard linear equations software [online]. http://www.netlib.org/benchmark/performance.ps (http://www.netlib.org/benchmark/performance.ps) (Accessed: 31 December 2011 ).
   Google Scholar
• Dorigo , M. and Stützle , T. 2010 . “ Ant colony optimization: overview and recent advances ” . In Handbook of metaheurisitcs , 2nd , Edited by: Gendreau , M. and Potvin , J.-V. 227 – 263 . New York : Springer .
   Google Scholar
• Duczmal , L.H. 2011 . Voronoi distance based prospective space-time scans for point data sets: a dengue fever cluster analysis in a southeast Brazilian town . International Journal of Health Geographics , 10 : 29 doi: 10.1186/1476-072X-10-29
   PubMed Web of Science ®Google Scholar
• Dueck , G. and Scheuer , T. 1990 . Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing . Journal of Computational Physics , 90 ( 1 ) : 161 – 175 .
   Web of Science ®Google Scholar
• Ergun , O. , Orlin , J.B. and Steele-Feldman , A. 2006 . Creating very large scale neighbourhoods out of smaller ones by compounding moves . Journal of Heuristics , 12 ( 1–2 ) : 115 – 140 .
   Web of Science ®Google Scholar
• Fleszar , K. , Osman , I.H. and Hindi , K.S. 2009 . A variable neighbourhood search algorithm for the open vehicle routing problem . European Journal of Operational Research , 195 ( 3 ) : 803 – 809 .
   Web of Science ®Google Scholar
• Fortune , S. 1987 . A sweepline algorithm for Voronoi diagrams . Algorithmica , 2 ( 1–4 ) : 153 – 174 .
   Google Scholar
• Gendreau , M. , Hertz , A. and Laporte , G. 1992 . New insertion and postoptimization procedures for the traveling salesman problem . Operations Research , 40 : 1086 – 1094 .
   Web of Science ®Google Scholar
• Glover , F. 1977 . Heuristics for integer programming using surrogate constraints . Decision Sciences , 8 ( 1 ) : 156 – 166 .
   Google Scholar
• Glover , F. and Laguna , M. 1997 . Tabu search , Boston , MA : Kluwer Academic Publishers .
   Google Scholar
• Golden , B. 1998 . “ The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results ” . In Fleet management and logistics , Edited by: Crainic , T. and Laporte , G. 33 – 56 . Boston , MA : Kluwer .
   Google Scholar
• Groër , C.S. 2008 . Parallel and serial algorithms for vehicle routing problems , University of Maryland . Doctoral dissertation
   Google Scholar
• Groër , C. , Golden , B. and Wasil , E. 2010 . A library of local search heuristics for the vehicle routing problem . Mathematical Programming Computation , 2 ( 2 ) : 79 – 101 .
   Google Scholar
• Hansen , P. and Mladenović , N. 2001 . Variable neighborhood search: principles and applications . European Journal of Operational Research , 130 ( 3 ) : 449 – 467 .
   Web of Science ®Google Scholar
• Hemmelmayr , V.C. , Doerner , K.F. and Hartl , R.F. 2009 . A variable neighborhood search heuristic for periodic routing problems . European Journal of Operational Research , 195 ( 3 ) : 791 – 802 .
   Web of Science ®Google Scholar
• Hiquebran , D.T. 1993 . A revised simulated annealing and cluster-first route-second algorithm applied to the vehicle routing problem . Engineering Optimization , 22 ( 2 ) : 77 – 107 .
   Web of Science ®Google Scholar
• Hjertenes , Ø.M. 2002 . A multilevel scheme for the travelling salesman problem , Norway : Department of Informatics, University of Bergen . Master thesis
   Google Scholar
• Holland , J.H. 1975 . Adaptation in natural and artificial systems , Ann Arbor , MI : The University of Michigan Press .
   Google Scholar
• Hu , F. , Xu , W. and Li , X. 2012 . A modified particle swarm optimization algorithm for optimal allocation of earthquake emergency shelters . International Journal of Geographical Information Science. , doi: 10.1080/13658816.2011.643802
   Google Scholar
• Imran , A. , Salhi , S. and Wassan , N.A. 2009 . A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem . European Journal of Operational Research , 197 ( 2 ) : 509 – 518 .
   Web of Science ®Google Scholar
• Jozefowiez , N. , Semet , F. and Talbi , E. 2008 . Multi-objective vehicle routing problems . European Journal of Operational Research , 189 ( 2 ) : 293 – 309 .
   Web of Science ®Google Scholar
• Kaku , I. , Xiao , Y. and Xia , G. 2003 . The deterministic annealing algorithms for vehicle routing problems . International Journal of Smart Engineering System Design , 5 ( 4 ) : 327 – 339 .
   Google Scholar
• Keenan , P. 2008 . Modelling vehicle routing in GIS . Operational Research , 8 ( 3 ) : 201 – 218 .
   Google Scholar
• Kirkpatrick , S. , Gelatt , C.D. Jr and Vecchi , M.P. 1983 . Optimization by simulated annealing . Science , 220 ( 4598 ) : 671 – 680 .
   PubMed Web of Science ®Google Scholar
• Kytöjoki , J. 2007 . An efficient variable neighborhood search heuristic for very large scale vehicle routing problems . Computers & Operations Research , 34 ( 9 ) : 2743 – 2757 .
   Web of Science ®Google Scholar
• Laporte , G. 2007 . What you should know about the vehicle routing problem . Naval Research Logistics , 54 ( 8 ) : 811 – 819 .
   Web of Science ®Google Scholar
• Laporte , G. 2009 . Fifty years of vehicle routing . Transportation Science , 43 ( 4 ) : 408 – 416 .
   Web of Science ®Google Scholar
• Lee , Y.H. 2008 . A heuristic for vehicle fleet mix problem using tabu search and set partitioning . Journal of the Operational Research Society , 59 ( 6 ) : 833 – 841 .
   Web of Science ®Google Scholar
• Lei , T. and Church , R. 2010 . Mapping transit‐based access: integrating GIS, routes and schedules . International Journal of Geographical Information Science , 24 ( 2 ) : 283 – 304 .
   Web of Science ®Google Scholar
• Li , F. , Golden , B. and Wasil , E. 2005 . Very large-scale vehicle routing: new test problems, algorithms, and results . Computers & Operations Research , 32 ( 5 ) : 1165 – 1179 .
   Web of Science ®Google Scholar
• Li , X. , He , J. and Liu , X. 2009 . Ant intelligence for solving optimal path‐covering problems with multi-objectives . International Journal of Geographical Information Science , 23 ( 7 ) : 839 – 857 .
   Web of Science ®Google Scholar
• Li , X. and Yeh , A. 2005 . Integration of genetic algorithms and GIS for optimal location search . International Journal of Geographical Information Science , 19 ( 5 ) : 581 – 601 .
   Web of Science ®Google Scholar
• Liu , X. 2008 . A bottom-up approach to discover transition rules of cellular automata using ant intelligence . International Journal of Geographical Information Science , 22 ( 11–12 ) : 1247 – 1269 .
   Web of Science ®Google Scholar
• Liu , X. 2012a . A multi-type ant colony optimization (MACO) method for optimal land use allocation in large areas . International Journal of Geographical Information Science. , doi: 10.1080/13658816.2011.635594
   Google Scholar
• Liu , X. , Lao , C. and Li , X. 2012b . An integrated approach of remote sensing, GIS and swarm intelligence for zoning protected ecological areas . Landscape Ecology , 27 ( 3 ) : 447 – 463 .
   Web of Science ®Google Scholar
• LourenÇo , H.R. , Martin , O.C. and Stützle , T. 2010 . “ Iterated local search: framework and applications ” . In Handbook of metaheurisitcs , 2nd , Edited by: Gendreau , M. and Potvin , J.-V. 363 – 397 . New York : Springer .
   Google Scholar
• Marinakis , Y. and Marinaki , M. 2010 . A hybrid genetic – particle swarm optimization algorithm for the vehicle routing problem . Expert Systems with Applications , 37 ( 2 ) : 1446 – 1455 .
   Web of Science ®Google Scholar
• Martin , O. and Otto , S.W. 1996 . Combining simulated annealing with local search heuristics . Annals of Operations Research , 63 ( 1 ) : 57 – 75 .
   Web of Science ®Google Scholar
• Mendoza , J. , Medaglia , A. and Velasco , N. 2009 . An evolutionary-based decision support system for vehicle routing: the case of a public utility . Decision Support Systems , 46 ( 3 ) : 730 – 742 .
   Web of Science ®Google Scholar
• Mester , D. and Bräysy , O. 2007 . Active-guided evolution strategies for large-scale capacitated vehicle routing problems . Computers & Operations Research , 34 ( 10 ) : 2964 – 2975 .
   Web of Science ®Google Scholar
• Milthers , N.P.M. 2009 . Solving VRP using Voronoi diagrams and adaptive large neighborhood search , Department of Computer Science, University of Copenhagen . Master thesis
   Google Scholar
• Mladenović , N. and Hansen , P. 1997 . Variable neighborhood search . Computers and Operations Research , 24 ( 11 ) : 1097 – 1100 .
   Web of Science ®Google Scholar
• Mole , R.H. , Johnson , D.G. and Wells , K. 1983 . Combinatorial analysis for route first-cluster second vehicle routing . Omega , 11 ( 5 ) : 507 – 512 .
   Web of Science ®Google Scholar
• Mooney , P. and Winstanley , A. 2006 . An evolutionary algorithm for multicriteria path optimization problems . International Journal of Geographical Information Science , 20 ( 4 ) : 401 – 423 .
   Web of Science ®Google Scholar
• Morin, R.C.,2002. Managed C# versus Unmanaged C++ [online]. http://www.kbcafe.com/articles/CSharp.Performance.pdf (http://www.kbcafe.com/articles/CSharp.Performance.pdf) (Accessed: 22 June 2012 ).
   Google Scholar
• Nagata , Y. and Bräysy , O. 2008 . “ Efficient local search limitation strategies for vehicle routing problems. In: C. Cotta and J. van Hemert ” . In EvoCOP2008, Lecture Notes in Computer Science, vol. 4972 , 48 – 60 . Berlin : Springer-Verlag .
   Google Scholar
• Nagata , Y. and Bräysy , O. 2009 . Edge assembly-based memetic algorithm for the capacitated vehicle routing problem . Network , 54 ( 4 ) : 205 – 215 .
   Google Scholar
• Okabe , A. 2000 . Spatial tessellationsconcepts and applications of Voronoi diagrams , 2nd , Chichester , , UK : John Wiley and Sons .
   Google Scholar
• Oppen, J. and Løkketangen, A., 2004. Node aggregation in vehicle routing [online]. Norwegian Informatics Conference, Stavanger, Norway, 2004. www.nik.no/2004/bidrag/Oppen.pdf (http://www.nik.no/2004/bidrag/Oppen.pdf) (Accessed: 19 December 2011 ).
   Google Scholar
• Oppen , J. and Løkketangen , A. 2006 . Arc routing in a node routing environment . Computers & Operations Research , 33 ( 4 ) : 1033 – 1055 .
   Web of Science ®Google Scholar
• Osman , I.H. 1993 . Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem . Annals of Operations Research , 41 ( 4 ) : 421 – 451 .
   Google Scholar
• Paulik , A. 1990 . Worst-case analysis of a generalized heapsort algorithm . Information Processing Letters , 36 ( 3 ) : 159 – 165 .
   Web of Science ®Google Scholar
• Pisinger , D. and Ropke , S. 2010 . “ Large neighborhood search ” . In Handbook of metaheuristics , 2nd , Edited by: Gendreau , M. and Potvin , J.-Y. 399 – 420 . New York : Springer .
   Google Scholar
• Prins , C. 2004 . A simple and effective evolutionary algorithm for the vehicle routing problem . Computers & Operations Research , 31 ( 12 ) : 1985 – 2002 .
   Web of Science ®Google Scholar
• Prins , C. 2007 . Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic . Transportation science , 41 ( 4 ) : 470 – 483 .
   Web of Science ®Google Scholar
• Prins , C. 2009 . “ A GRASP × Evolutionary local search hybrid for the vehicle routing problem ” . In Bio-inspired algorithms for the vehicle routing problem , Edited by: Pereira , F. and Tavares , J. Vol. 161 , 35 – 53 . Berlin : Springer .
   Google Scholar
• Prutsakul , A. 1998 . Integrated inventory problem and vehicle routing problem in one warehouse and multi-retailer distribution system. Master of science. Texas Tech University
   Google Scholar
• Resende , M.G.C. and Ribeiro , C.C. 2010 . “ Greedy randomized adaptive search procedures: advances, hybridizations, and applications ” . In Handbook of metaheurisitcs , 2nd , Edited by: Gendreau , M. and Potvin , J.-V. 283 – 320 . New York : Springer .
   Google Scholar
• Ropke , S. and Pisinger , D. 2006a . A unified heuristic for a large class of vehicle routing problems with backhauls . European Journal of Operational Research , 171 ( 3 ) : 750 – 775 .
   Web of Science ®Google Scholar
• Ropke , S. and Pisinger , D. 2006b . An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows . Transportation Science , 40 ( 4 ) : 455 – 472 .
   Web of Science ®Google Scholar
• Santos , L. , Coutinho-Rodrigues , J. and Antunes , C. 2011 . A web spatial decision support system for vehicle routing using Google Maps . Decision Support Systems , 51 ( 1 ) : 1 – 9 .
   Web of Science ®Google Scholar
• Santos , L. , Coutinho-Rodrigues , J. and Current , J.R. 2010 . An improved ant colony optimization based algorithm for the capacitated arc routing problem . Transportation Research Part B: Methodological , 44 ( 2 ) : 246 – 266 .
   Web of Science ®Google Scholar
• Tarantilis , C. , Diakoulaki , D. and Kiranoudis , C. 2004 . Combination of geographical information system and efficient routing algorithms for real life distribution operations . European Journal of Operational Research , 152 ( 2 ) : 437 – 453 .
   Web of Science ®Google Scholar
• Toth , P. and Vigo , D. 2003 . The granular tabu search and its application to the vehicle-routing problem . INFORMS Journal on Computing , 15 ( 4 ) : 333 – 346 .
   Web of Science ®Google Scholar
• Ursani , Z. 2011 . Localized genetic algorithm for vehicle routing problem with time windows . Applied Soft Computing , 11 ( 8 ) : 5375 – 5390 .
   Web of Science ®Google Scholar
• Van Breedam , A. 1994 . An Analysis of the behaviour of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related and time-related constraints , Dissertation (PhD). University of Antwerp .
   Google Scholar
• Wassan , N. , Wassan , A. and Nagy , G. 2008 . A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries . Journal of Combinatorial Optimization , 15 ( 4 ) : 368 – 386 .
   Web of Science ®Google Scholar
• Yu , B. and Yang , Z.Z. 2011 . An ant colony optimization model: the period vehicle routing problem with time windows . Transportation Research Part E: Logistics and Transportation Review , 47 ( 2 ) : 166 – 181 .
   Web of Science ®Google Scholar
• Yücenur , G.N. and Demirel , N.Ç. 2011 . A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem . Expert Systems with Applications , 38 ( 9 ) : 11859 – 11865 .
   Web of Science ®Google Scholar
• Zachariadis , E.E. and Kiranoudis , C.T. 2010 . A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem . Computers & Operations Research , 37 ( 12 ) : 2089 – 2105 .
   Web of Science ®Google Scholar