Adaptive search techniques for problems in vehicle routing, part I: A survey
DOI:
https://doi.org/10.2298/YJOR140217009KKeywords:
Adaptive strategies, local search, metaheuristics, vehicle routingAbstract
Research in the field of vehicle routing often focused on finding new ideas and concepts in the development of fast and efficient algorithms for an improved solution process. Early studies introduce static tailor-made strategies, but trends show that algorithms with generic adaptive policies - which emerged in the past years - are more efficient to solve complex vehicle routing problems. In this first part of the survey, we present an overview of recent literature dealing with adaptive or guided search techniques for problems in vehicle routing.References
Anagnostopoulos, A., Michel, L., Van Hentenryck, P., Vergados, Y., “A simulated annealing approach to the traveling tournament problem”, Journal of Scheduling, 9 (2006) 177-193.
Azi, N., Gendrau, M., Potvin, J.-Y., “An Adaptive Large Neighborhood Search for Vehicle Routing Problem with Multiple Trips”, Tech. Rep. CIRRELT-20012-08, Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Canada, (2010).
Azi, N., Gendrau, M., Potvin, J.-Y., “A dynamic vehicle routing problem with multiple delivery routes”, Annals of Operations Research, 199(1) (2012) 103-112.
Azi, N., Gendrau, M., Potvin, J.-Y., “An adaptive large neighborhood search for a vehicle routing problem with multiple routes”, Computers & Operations Research, 41 (2014) 167-173.
Baldacci, R., Mingozzi, A., “A unified exact method for solving different classes of vehicle routing problems”, Mathematical Programming, 120(2) (2009) 347-380.
Balseiro, S. R., Loiseau, I., Ramonet, J., “An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows”, Computers & Operations Research, 38(6) (2011) 954-966.
Battiti, R., “Reactivesearch: Toward Shelf-Tuning Heuristics”, in: V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, G. D. Smith (eds.) Modern Heuristic Search Methods, John Wiley and Sons Ltd (1996) 61-83.
Battiti, R., Brunato, M., “Reactive Search Optimization: Learning While Optimizing”, in: M. Gendreau, J.-Y. Potvin (eds.) Handbook of Metaheuristics, Second Edition, International Series in Operations Research & Management Science, Springer Science+Business Media LLC, vol. 146 (2010) 543-571.
Battiti, R., Tecchiolli, G., “The Reactive Tabu Search”, ORSA Journal on Computing, 6(2) (1994) 126-140.
Berger, J., Barkaoui, M., “A new hybrid genetic algorithm for the capacitated vehicle routing problem”, Journal of the Operational Research Society, 54 (2003) 1254-1262.
Bräysy, O., “A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows”, INFORMS Journal on Computing, 15(4) (2003) 347-368.
Bullnheimer, B., Hartl, R. F., Strauss, C., “An improved ant system algorithm for the vehicle routing problem”, Annals of Operations Research, 89 (1997) 319-328.
Cattaruzza, D., Absi, N., Feillet, D., Vidal, T., “A memetic algorithm for the Multi Trip Vehicle Routing Problem”, European Journal of Operational Research, 236(3) (2014) 833-848.
Clarke, G., Wright, J. W., “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12(4) (1964) 568-581.
Cordeau, J. F., Maischberger, M., “A parallel iterated tabu search heuristic for vehicle routing problems”, Computers & Operations Research, 39(9) (2012) 2033-2050.
Crevier, B., Cordeau, J. F., Laporte, G., “The multi-depot vehicle routing problem with inter-depot routes”, European Journal of Operational Research, 176(2) (2007) 756-773.
Croes, G. A., “A Method for Solving Traveling-Salesman Problems”, Operations Research, 6(6) (1958) 791-812.
Dantzig, G. B., Ramser, J. H., “The truck dispatching problem”, Management Science, 6 (1959) 80-91.
Demir, E., Bektas, T., Laporte, G., “An adaptive large neighborhood search heuristic for the Pollution-Routing Problem”, European Journal of Operational Research, 223(2) (2012) 346-359.
Di Gaspero, L., Schaerf, A., “A composite-neighborhood tabu search approach to the traveling tournament problem”, Journal of Heuristics, 13(2) (2007) 189-207.
Dorigo, M., Stützle, T., “Ant Colony Optimization: Overview and Recent Advances”, in: M. Gendreau, J.-Y. Potvin (eds.) Handbook of Metaheuristics, Second Edition, International Series in Operations Research & Management Science, Springer Science+Business Media LLC, vol. 146 (2010) 227-263.
Duhamel, C., Lacomme, P., Prins, C., Prodhon, C., “A GRASP ELS approach for the capacitated location-routing problem”, Computers & Operations Research, 37(11) (2010) 1912-1923.
Garey, M. R., Johnson, D. S., “Computers and Intractability; A Guide to the Theory of NP Completeness”, W. H. Freeman & Co., New York, NY, USA, (1990).
Gendreau, M., Hertz, A., Laporte, G., “A Tabu Search Heuristic for the Vehicle Routing Problem”, Management Science, 40(10) (1994) 1276-1290.
Gendreau, M., Iori, M., Laporte, G., Martello, S., “A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints”, Networks, 51(1) (2007) 4-18.
Ghaziri, H., “Solving routing problems by a self-organizing map”, in: T. Kohonen, K. Makisara, O. Simula, J. Kangas (eds.) Artificial Neural Networks, North-Holland Amsterdam, (1991) 829-834.
Gillett, B. E., Miller, L. R., “A Heuristic Algorithm for the Vehicle-Dispatch Problem”, Operational Research, 22(2) (1974) 340-349.
Glover, F., “Future paths for integer programming and links to artificial intelligence”, Computers & Operations Research, 13(5) (1986) 533-549.
Glover, F., “Tabu Search– Part I”, ORSA Journal on Computing, 1(3) (1989) 190-206.
Glover, F., “Tabu Search– Part II”, ORSA Journal on Computing, 2(1) (1990) 4-32.
Hansen, P., Mladenović, N., “Variable Neighborhood Search”, in: P. M. Pardalos, M. G. C. Resende (eds.) Handbook of Applied Optimization, Oxford University Press New York, (2000) 221-234.
Hansen, P., Mladenović, N., “Variable Neighborhood Search: Principles and applications”, European Journal of Operational Research, 130(3) (2001) 449-467.
Hansen, P., Mladenović, N., Moreno Pérez, J. A., “Variable neighborhood search: methods and applications”, Annals of Operations Research, 175(3) (2010) 367-407.
Hemmelmayr, V. C., Cordeau, J. F., Crainic, T. G., “An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics”, Computers & Operations Research, 195(3) (2009) 803-809.
Hemmelmayr, V. C., Doerner, K. F., Hartl, R. F., “A variable neighborhood search heuristic for periodic routing problems”, Computers & Operations Research, 39(16) (2012) 3215-3228.
Hernández-Pérez, H., Salazar-González, J. J., “Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem”, Transportation Science, 38(2) (2004) 245-255.
Hosny, M. I., Mumford, C. L., “Solving the One-Commodity Pickup and Delivery Problem Using an Adaptive Hybrid VNS/SA Approach”, in: R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (eds.) Parallel Problem Solving from Nature, PPSN XI, Lecture Notes in Computer Science, Springer Berlin Heidelberg, vol. 6239 (2010) 189-198.
Hsiao, P. C., Chiang, T. C., Fu, L. C., “A VNS-based Hyper-heuristic with Adaptive Computational Budget of Local Search”, IEEE Congress on Evolutionary Computation, (2012) 1-8.
Irnich, S., Funke, B., Grünert, T., “Sequential search and its application to vehicle-routing problems”, Computers & Operations Research, 33(8) (2006) 2405-2429.
Khebbache-Hadji, S., Prins, C., Yalaoui, A., Reghioui, M., “Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows”, Central European Journal of Operations Research, 21(2) (2013) 307-336.
Khouadjia, M., Jourdan, L., Talbi, E., “Adaptive particle swarm for solving the dynamic vehicle routing problem”, IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), (2010) 1-8.
Kovacs, A. A., Parragh, S. N., Doerner, K. F., Hartl, R. F., “Adaptive large neighborhood search for service technician routing and scheduling problems”, Journal of Scheduling, 15(5) (2012) 579-600.
Kritzinger, S., Tricoire, F., Doerner, K. F., Hartl, R. F., “Adaptive search techniques for problems in vehicle routing, Part II: A numerical comparison”, to appear in Yugoslav Journal of Operations Research (2014).
Lau, H. C. W., Chan, T. M., Tsui, W. T., Pang, W. K., “Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem”, IEEE Transactions on Automation Science and Engineering, 60(2) (2010) 383-392.
Lei, H., Laporte, G., Guo, B., “The capacitated vehicle routing problem with stochastic demands and time windows”, Computers & Operations Research, 38(12) (2011) 1775-1783.
Leung, S. C. H., Zhou, X., Zheng, J., “Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem”, Computers & Operations Research, 38(1) (2011) 205-215.
Lin, S., “Computer Solutions of the Traveling Salesman Problem”, Bell System Technical Journal, 44 (1965) 2245-2269.
Lourenço, H. R., Martin, O. C., Stützle, T., “Iterated Local Search: Framework and Applications”, in: M. Gendreau, J.-Y. Potvin (eds.) Handbook of Metaheuristics, Second Edition, International Series in Operations Research & Management Science, Springer Science+Business Media LLC, vol. 146 (2010) 363-397.
Martin, O., Otto, S. W., Felten, F. W., “Large-step Markov chains for the traveling salesman problem”, Complex Systems, 5(3) (1991) 299-326.
Mester, D., Bräysy, O., “Active-guided evolution strategies for large-scale capacitated vehicle routing problems”, Computers & Operations Research, 34(10) (2007) 2964-2975.
Michallet, J., Prins, C., Amodeo, L., Yalaoui, F., Vitry, G., “Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services”, Computers & Operations Research, 41 (2014) 196-207.
Mills, P., Tsang, E., Ford, J., “Applying an Extended Guided Local Search to the Quadratic Assignment Problem”, Annals of Operations Research, 118(1-4) (2003) 121-135.
Mladenović, N., Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, 24(11) (1997) 1097-1100.
Ngueveu, S. U., Prins, C., Wolfler Calvo, R., “An effective memetic algorithm for the cumulative capacitated vehicle routing problem”, Computers & Operations Research, 37(11) (2010) 1877-1885.
Novoa, C., Storer, R., “An approximate dynamic programming approach for the vehicle routing problem with stochastic demands”, European Journal of Operational Research, 196(2) (2009) 509-515.
Or, I., “Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking”, Ph.D. thesis, North Western University, Chicago, USA (1976).
Osman, I. H., “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operations Research, 41(4) (1993) 421-451.
Parragh, S. N., Doerner, K. F., Hartl, R. F., “Variable neighborhood search for the dial-a-ride problem”, Computers & Operations Research, 37(6) (2010) 1129-1138.
Penna, P. H. V., Subramanian, A., Ochi, L. S., “An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem”, Journal of Heuristics, 19(2) (2013) 201-232.
Pillac, V., Guéret, C., Medaglia, A. L., “An event-driven optimization framework for dynamic vehicle routing”, Decision Support Systems, 54(1) (2012) 414-423.
Pirkwieser, S., Raidl, G. R., “Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem”, in: M. Blesa, C. Blum, G. R. Raidl, A. Roli, M. Sampels (eds.) Hybrid metaheuristics, Lecture Notes in Computer Science, Springer Berlin Heidelberg, vol. 6373 (2010) 174-189.
Pisinger, D., Ropke, S., “A general heuristic for vehicle routing problems”, Computers & Operations Research, 34(8) (2007) 2403-2435.
Polacek, M., Benkner, S., Doerner, K. F., Hartl, R. F., “A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows”, Business Research Journal, 1(2) (2008) 207-218.
Polacek, M., Hartl, R. F., Doerner, K. F., Reimann, M., “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows”, Journal of Heuristics, 10(6) (2004) 613-627.
Potvin, J.-Y., Naud, M. A., “Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier”, Journal of the Operational Research Society, 62 (2011) 326-336.
Prins, C., “A simple and effective evolutionary algorithm for the vehicle routing problem”, Computers & Operations Research, 31(12) (2004) 1984-2002.
Reimann, M., Doerner, K. F., Hartl, R. F., “D-Ants: Savings Based Ants divide and conquer the vehicle routing problem”, Computers & Operations Research, 31(4) (2004) 563-591.
Reimann, M., Stummer, M., Doerner, K. F., “A savings based ant system for the vehicle routing problem”, in: W. B. Langdon, et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002). San Francisco: Morgan Kaufmann (2002).
Ribeiro, G. M., Laporte, G., “An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem”, Computers & Operations Research, 39(3) (2012) 728-735.
Ropke, S., Pisinger, D., “A unified heuristic for a large class of Vehicle Routing Problems with Backhauls”, European Journal of Operational Research, 171(3) (2006) 750-775.
Ropke, S., Pisinger, D., “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows”, Transportation Science, 40(4) (2006) 455-472.
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., Dueck, G., “Record breaking optimization results using the ruin and recreate principle”, Journal of Computational Physics, 159 (2000) 139-171.
Shaw, P., “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems”, in: M. Maher, J. F. Puget (eds.) Principles and Practice of Constraint Programming CP98, Lecture Notes in Computer Science, Springer Berlin Heidelberg, vol. 1520 (1998) 417-431.
Stenger, A., Vigo, D., Enz, S., Schwind, M., “An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping”, Transportation Science, 47(1) (2013) 64-80.
Stützle, T., Hoos, H., “Stochastic Local Search”, in: SLS Methods, Morgan Kaufmann, (2005) 61-112.
Subramanian, A., Battarra, M., “An iterated local search algorithm for the Travelling Salesman Problem with Pickups and Deliveries”, Journal of the Operational Research Society, 64(3) (2013) 402-409.
Subramanian, A., Uchoa, E., Ochi, L. S., “A hybrid algorithm for a class of vehicle routing problems”, Computers & Operations Research, 40(10) (2013) 2519-2531.
Taillard, É. D., “Parallel Iterative Search Methods for Vehicle Routing Problems”, Networks, 23(8) (1993) 661-673.
Taillard, É. D., Badeau, P., Gendreau, M., Potvin, J.-Y., “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation Science, 31(2) (1997) 170-186.
Taillard, É. D., Gambardella, L. M., Gendreau, M., Potvin, J.-Y., “Adaptive memory programming: A unified view of metaheuristics”, European Journal of Operational Research, 135(1) (2001) 1-16.
Tang Montané, F. A., Galvão, R. D., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers & Operations Research, 33(3) (2006) 595-619.
Tarantilis, C. D., Kiranoudis, C. T., “Bone-Route: An Adaptive Memory-Based Method for Effective Fleet Management”, Annals of Operations Research, 115 (2002) 227-241.
Tarantilis, C. D., Zachariadis, E. E., Kiranoudis, C. T., “A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities”, INFORMS Journal on Computing, 20(1) (2008) 154-168.
Thompson, P. M., Psaraftis, H. N., “Cyclic transfer algorithms for multivehicle routing and scheduling problems”, Operations Research, 41(5) (1993) 935-946.
Toth, P., Vigo, D., “The Granular Tabu Search and Its Application to the Vehicle-Routing Problem”, INFORMS Journal on Computing, 15(4) (2003) 333-346.
Vidal, T., Crainic, T. G., Gendreau, M., Prins, C., “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows”, Computers & Operations Research, 40(1) (2013) 475-489.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., Rei, W., “A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problems”, Operations Research, 60(3) (2012) 611-624.
Vidal, T., Crainic, T. G., Gendreau, M., Prins, C., “A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems”, European Journal of Operational Research, 234(3) (2014) 658-673.
Voudouris, C., Tsang, E. P. K., Alsheddy, A., “Guided Local Search”, in: M. Gendreau, J.-Y. Potvin (eds.) Handbook of Metaheuristics, Second Edition, International Series in Operations Research & Management Science, Springer Science+Business Media LLC, vol. 146 (2010) 321-361.
Waters, C. D. J., “A solution procedure for the vehicle-scheduling problem based on iterative route improvement”, Journal of the Operational Research Society, 38(9) (1987) 833-839.
Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., “A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints”, European Journal of Operations Research, 195(3) (2009) 729-743.
Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., “A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service”, Expert Systems with Applications, 36(2) (2009) 1070-1081.
Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., “An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries”, European Journal of Operational Research, 202 (2010) 401-411.
Zhao, F., Li, S., Sun, J., Mei, D., “Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem”, Computers & Industrial Engineering, 56(4) (2008) 1642-1648.
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
