Adaptive search techniques for problems in vehicle routing, part II: A numerical comparison

Authors

  • Stefanie Kritzinger Johannes Kepler University Linz, Department of Production and Logistics, Linz, Austria
  • Karl F. Doerner Johannes Kepler University Linz, Department of Production and Logistics, Linz, Austria
  • Fabien Tricoire University of Vienna, Department of Business Administration, Vienna, Austria
  • Richard F. Hartl University of Vienna, Department of Business Administration, Vienna, Austria

DOI:

https://doi.org/10.2298/YJOR140217011K

Keywords:

Adaptive strategies, local search, variable neighborhood search, vehicle routing

Abstract

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

Bodin, L., Golden, B., Assad, A., Ball, M., “Routing and scheduling of vehicles and crews: the state of the art”, Computers & Operations Research, 10(2) (1983) 195-211.

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.

Bräysy, O., Gendreau, M., “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms”, Transportation Science, 39(1) (2005) 104-118.

Christofides, N., Mingozzi, A., Toth, P., “The vehicle routing problem”, in: N. Christofides, A. Mingozzi, P. Toth, C. Sandi (eds.) Combinatorial Optimization, Wiley Chichester New York, (1979) 313-338.

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., Doerner, K. F., Hartl, R. F., “A variable neighborhood search heuristic for periodic routing problems”, Computers & Operations Research, 39(16) (2012) 3215-3228.

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.

Kritzinger, S., Tricoire, F., Doerner, K. F., Hartl, R. F., “Adaptive search techniques for problems in vehicle routing, Part I: A survey”, to appear in Yugoslav Journal of Operations Research 25(1) (2015) 3-31.

Kritzinger, S., Tricoire, F., Doerner, K. F., Hartl, R. F., Stützle, T., “A Unified Framework for Routing Problems with a Fixed Fleet Size”, Tech. Rep. JKU-PLM-2012-006, Johannes Kepler University Linz, Austria, (2012).

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.

Mladenović, N., Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, 24(11) (1997) 1097-1100.

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.

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.

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.

Repoussis, P. P., Tarantilis, C. D., Ioannou, G., “The open vehicle routing problem with time windows”, Journal of the Operational Research Society, 58(3) (2007) 355-367.

Schrage, L., “Formulation and structure of more complex/realistic routing and scheduling problems”, Networks, 11(2) (1981) 229-232.

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.

Solomon, M., “Algorithms for the vehicle routing and scheduling problems with time constraints”, Operations Research, 45(2) (1987) 254-265.

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.

Tricoire, F., Romauch, M., Doerner, K. F., Hartl, R. F., “Heuristics for the multi-period orienteering problem with multiple time windows”, Computers & Operations Research, 37(2) (2009) 351-367.

Downloads

Published

2015-06-01

Issue

Vol. 25 No. 2 (2015)

Section

Research Articles

License

Copyright (c) 2015 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.