Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Hybrid Metaheuristics for Dynamic and Stochastic Vehicle Routing

  • Chapter
Hybrid Metaheuristics

Part of the book series: Studies in Computational Intelligence ((SCI,volume 434))

Abstract

Recent developments in telematics, such as the wide spread use of positioning services and mobile communication technologies, allow the exact monitoring of vehicles. These advances build the basis for automatic real-time fleet management systems. To be successful such systems have to rely on optimization algorithms for solving dynamic and stochastic vehicle routing problems based on ingredients such as historical data, stochastic modeling, machine learning, fast shortest-path calculation, fast construction heuristics, and exact and (meta)heuristic optimization methods. This book documents the growing interest in and success of hybrid metaheuristics. They are often used to solve complex and large real-world optimization problems, combining advantages from various fields of computer science and mathematical optimization. Within this chapter the application of such methods for the dynamic and stochastic vehicle routing problem is studied. After a general introduction in this field, the main commonalities of dynamic and stochastic vehicle routing problems are described and a short overview of classical algorithms for these problems is given. Then, in the third part hybrid metaheuristics for dynamic problems vehicle routing problems are be described. The third part focusses on stochastic problems. The fourth part examines the combination of dynamic and stochastic problems. The chapter is concluded with an outlook towards future developments in the field as well as promising open research areas.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alvarenga, G., de Abreu Silva, R., Mateus, G.: A hybrid approach for the dynamic vehicle routing problem with time windows. In: Fifth International Conference on Hybrid Intelligent Systems (HIS 2005), 7 pages (November 2005)

    Google Scholar 

  2. Alvarenga, G., Mateus, G., de Tomi, G.: A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research 34(6), 1561–1584 (2007); Part Special Issue: Odysseus 2003 Second International Workshop on Freight Transportation Logistics

    Google Scholar 

  3. Attanasio, A., Bregman, J., Ghiani, G., Manni, E.: Real-time fleet management at ecourier ltd. In: Sharda, R., Voss, S., Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., Minis, I. (eds.) Dynamic Fleet Management. Operations Research/Computer Science Interfaces Series, vol. 38, pp. 219–238. Springer, US (2007)

    Chapter  Google Scholar 

  4. Attanasio, A., Cordeau, J.-F., Ghiani, G., Laporte, G.: Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Comput. 30, 377–387 (2004)

    Article  Google Scholar 

  5. Beasley, J.: Route first–cluster second methods for vehicle routing. Omega 11(4), 403–408 (1983)

    Article  Google Scholar 

  6. Bent, R.W., Van Hentenryck, P.: Dynamic vehicle routing with stochastic requests. In: International Joint Conference On Artificial Intelligence, vol. 18, pp. 1362–1363 (2003)

    Google Scholar 

  7. Bent, R.W., Van Hentenryck, P.: Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper. Res. 52, 977–987 (2004)

    Article  MATH  Google Scholar 

  8. Berbeglia, G., Cordeau, J.-F., Laporte, G.: A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem. INFORMS Journal on Computing (2011)

    Google Scholar 

  9. Berbeglia, G., Pesant, G., Rousseau, L.-M.: Checking the feasibility of dial-a-ride instances using constraint programming. Transportation Science 45, 399–412 (2011)

    Article  Google Scholar 

  10. Bertsimas, D.J.: A vehicle routing problem with stochastic demand. Oper. Res. 40, 574–585 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bianchi, L., Birattari, M., Chiarandini, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T.: Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms 5, 91–110 (2006), doi:10.1007/s10852-005-9033-y

    Article  MathSciNet  MATH  Google Scholar 

  12. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer (1997)

    Google Scholar 

  13. Blum, C., Puchinger, J., Raidl, G.R., Roli, A.: Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing 11(6), 4135–4151 (2011)

    Article  Google Scholar 

  14. Bock, S.: Real-time control of freight forwarder transportation networks by integrating multimodal transport chains. European Journal of Operational Research 200(3), 733–746 (2010)

    Article  MATH  Google Scholar 

  15. Branchini, R.M., Armentano, V.A., Løkketangen, A.: Adaptive granular local search heuristic for a dynamic vehicle routing problem. Computers and Operations Research 36(11), 2955–2968 (2009)

    Article  MATH  Google Scholar 

  16. Caramia, M., Italiano, G., Oriolo, G., Pacifici, A., Perugia, A.: Routing a fleet of vehicles for dynamic, combined pickup and delivery services. In: Proceedings of the Symposium on Operation Research 2001, pp. 3–8. Springer (2001)

    Google Scholar 

  17. Chen, H.-K., Hsueh, C.-F., Chang, M.-S.: The real-time time-dependent vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review 42(5), 383–408 (2006)

    Article  Google Scholar 

  18. Chen, Z.-L., Xu, H.: Dynamic column generation for dynamic vehicle routing with time windows. Transportation Science 40, 74–88 (2006)

    Article  Google Scholar 

  19. Cordeau, J.-F., Laporte, G.: The dial-a-ride problem: models and algorithms. Annals of Operations Research 153, 29–46 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  20. Cordeau, J.-F., Laporte, G., Savelsbergh, M.W., Vigo, D.: Vehicle routing. In: Barnhart, C., Laporte, G. (eds.) Transportation. Handbooks in Operations Research and Management Science, vol. 14, ch. 6, pp. 367–428. Elsevier (2007)

    Google Scholar 

  21. Crainic, T.G.: Parallel solution methods for vehicle routing problems. In: Golden, et al. (eds.), [35], p. 589 (2008)

    Google Scholar 

  22. Créput, J.-C., Hajjam, A., Koukam, A., Kuhn, O.: Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem. Journal of Combinatorial Optimization, 1–22 (2011)

    Google Scholar 

  23. Dror, M., Laporte, G., Trudeau, P.: Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation Science 23(3), 166–176 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  24. Fabri, A., Recht, P.: On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transportation Research Part B: Methodological 40(4), 335–350 (2006)

    Article  Google Scholar 

  25. Fischetti, M., Lodi, A.: Local branching. Mathematical Programming 98, 23–47 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  26. Flatberg, T., Hasle, G., Kloster, O., Nilssen, E.J., Riise, A.: Dynamic and stochastic vehicle routing in practice. In: Sharda, R., Voss, S., Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., Minis, I. (eds.) Dynamic Fleet Management. Operations Research/Computer Science Interfaces Series, vol. 38, pp. 41–63. Springer, US (2007), doi:10.1007/978-0-387-71722-7_3

    Google Scholar 

  27. Fleischmann, B., Gnutzmann, S., Sandvoss, E.: Dynamic vehicle routing based on online traffic information. Transportation Science 38, 420–433 (2004)

    Article  Google Scholar 

  28. Fleischmann, B., Gnutzmann, S., Sandvoss, E.: Dynamic vehicle routing based on online traffic information. Transportation Science 38, 420–433 (2004)

    Article  Google Scholar 

  29. Fu, L., Rilett, L.R.: Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research Part B: Methodological 32(7), 499–516 (1998)

    Article  Google Scholar 

  30. Gendreau, M., Guertin, F., Potvin, J.-Y., Taillard, E.: Parallel tabu search for real-time vehicle routing and dispatching. Transportation Science 33, 381–390 (1999)

    Article  MATH  Google Scholar 

  31. Gendreau, M., Laporte, G., Séguin, R.: Stochastic vehicle routing. European Journal of Operational Research 88(1), 3–12 (1996)

    Article  MATH  Google Scholar 

  32. Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G., Løkketangen, A.: Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography. In: Golden, et al. (eds.) [35], pp. 143–169 (2008)

    Google Scholar 

  33. Goel, A.: Fleet Telematics. Operations Research/Computer Science Interfaces Series, vol. 40. Springer, US (2008)

    Google Scholar 

  34. Golden, B., Dearmon, J., Baker, E.: Computational experiments with algorithms for a class of routing problems. Computers & Operations Research 10(1), 47–59 (1983)

    Article  MathSciNet  Google Scholar 

  35. Golden, B., Raghavan, S., Wasil, E. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces Series, vol. 43. Springer (2008)

    Google Scholar 

  36. Gutjahr, W.J., Katzensteiner, S., Reiter, P.: A VNS Algorithm for Noisy Problems and its Application to Project Portfolio Analysis. In: Hromkovič, J., Královič, R., Nunkesser, M., Widmayer, P. (eds.) SAGA 2007. LNCS, vol. 4665, pp. 93–104. Springer, Heidelberg (2007), doi:10.1007/978-3-540-74871-7_9

    Chapter  Google Scholar 

  37. Haghani, A., Jung, S.: A dynamic vehicle routing problem with time-dependent travel times. Comput. Oper. Res. 32, 2959–2986 (2005)

    Article  MATH  Google Scholar 

  38. Hvattum, L., Løkketangen, A.: Using scenario trees and progressive hedging for stochastic inventory routing problems. Journal of Heuristics 15, 527–557 (2009)

    Article  MATH  Google Scholar 

  39. Hvattum, L.M., Løkketangen, A., Laporte, G.: Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science 40(4), 421–438 (2006)

    Article  Google Scholar 

  40. Hvattum, L.M., Løkketangen, A., Laporte, G.: A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems. Networks 49(4), 330–340 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  41. Hvattum, L.M., Løkketangen, A., Laporte, G.: Scenario tree-based heuristics for stochastic inventory-routing problems. INFORMS Journal on Computing 21(2), 268–285 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  42. Ichoua, S., Gendreau, M., Potvin, J.-Y.: Exploiting knowledge about future demands for real-time vehicle dispatching. Transportation Science 40(2), 211–225 (2006)

    Article  Google Scholar 

  43. Jaillet, P.: Probabilistic Traveling Salesman Problems. PhD thesis. Operations Research Center, MIT (February 1985)

    Google Scholar 

  44. Jih, W.-R., Yung-Jen Hsu, J.: Dynamic vehicle routing using hybrid genetic algorithms. In: Proceedings of 1999 IEEE International Conference on Robotics and Automation, vol. 1, pp. 453–458 (1999)

    Google Scholar 

  45. Johnson, D., McGeoch, L.: Experimental analysis of heuristics for the stsp. In: Gutin, G., Punnen, A., Du, D.-Z., Pardalos, P.M. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol. 12, pp. 369–443. Springer, US (2004), doi:10.1007/0-306-48213-4_9

    Google Scholar 

  46. Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (November 1995)

    Google Scholar 

  47. Kenyon, A.S., Morton, D.P.: Stochastic vehicle routing with random travel times. Transportation Science 37(1), 69–82 (2003)

    Article  Google Scholar 

  48. Khouadjia, M.R., Alba, E., Jourdan, L., Talbi, E.-G.: Multi-Swarm Optimization for Dynamic Combinatorial Problems: A Case Study on Dynamic Vehicle Routing Problem. In: Dorigo, M., Birattari, M., Di Caro, G.A., Doursat, R., Engelbrecht, A.P., Floreano, D., Gambardella, L.M., Groß, R., Şahin, E., Sayama, H., Stützle, T. (eds.) ANTS 2010. LNCS, vol. 6234, pp. 227–238. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  49. Laporte, G.: The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59(3), 345–358 (1992)

    Article  MATH  Google Scholar 

  50. Laporte, G.: Fifty years of vehicle routing. Transportation Science 43, 408–416 (2009)

    Article  MathSciNet  Google Scholar 

  51. Laporte, G., Musmanno, R., Vocaturo, F.: An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands. Transportation Science 44(1), 125–135 (2010)

    Article  Google Scholar 

  52. Larsen, A.: The Dynamic Vehicle Routing Problem. PhD thesis. Technical University of Denmark, Kongens, Lyngby, Denmark (2000)

    Google Scholar 

  53. Larsen, A., Madsen, O., Solomon, M.: Partially dynamic vehicle routing - models and algorithms. Journal of the Operational Research Society 53, 637–646 (2002)

    Article  MATH  Google Scholar 

  54. Larsen, A., Madsen, O.B., Solomon, M.M.: Classification of dynamic vehicle routing systems. In: Sharda, R., Voss, S., Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., Minis, I. (eds.) Dynamic Fleet Management. Operations Research/Computer Science Interfaces Series, vol. 38, pp. 19–40. Springer, US (2007)

    Google Scholar 

  55. Larsen, A., Madsen, O.B., Solomon, M.M.: Recent developments in dynamic vehicle routing systems. In: Sharda, R., Voss, S., Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces Series, vol. 43, pp. 199–218. Springer, US (2008) doi:10.1007/978-0-387-77778-8_9

    Google Scholar 

  56. Liao, T.-Y.: Tabu search algorithm for dynamic vehicle routing problems under real-time information. Transportation Research Record: Journal of the Transportation Research Board 1882(1), 140–149 (2004)

    Article  Google Scholar 

  57. Liao, T.-Y., Hu, T.-Y.: An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information. Expert Systems with Applications 38(10), 12548–12558 (2011)

    Article  Google Scholar 

  58. Marinakis, Y., Marinaki, M.: A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput. Oper. Res. 37, 432–442 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  59. Marinakis, Y., Migdalas, A., Pardalos, P.: Expanding neighborhood grasp for the traveling salesman problem. Computational Optimization and Applications 32, 231–257 (2005), doi:10.1007/s10589-005-4798-5

    Article  MathSciNet  MATH  Google Scholar 

  60. Mendoza, J.E., Castanier, B., Guéret, C., Medaglia, A.L., Velasco, N.: A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research 37(11), 1886–1898 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  61. Mladenovic, N., Hansen, P.: Variable neighborhood search. Computers & Operations Research 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  62. Montemanni, R., Gambardella, L., Rizzoli, A., Donati, A.: Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization 10, 327–343 (2005), doi:10.1007/s10878-005-4922-6

    Article  MathSciNet  MATH  Google Scholar 

  63. Parragh, S.N.: Ambulance Routing Problems with Rich Constraints and Multiple Objectives. PhD thesis. University of Vienna, Department of Business Administration (2009)

    Google Scholar 

  64. Parragh, S.N., Doerner, K.F., Hartl, R.F.: Variable neighborhood search for the dial-a-ride problem. Comput. Oper. Res. 37, 1129–1138 (2010)

    Article  MATH  Google Scholar 

  65. Pessoa, A., de Arago, M.P., Uchoa, E.: Robust branch-cut-and-price algorithms for vehicle routing problems. In: Golden, et al. (eds.) [35], pp. 297–325 (2008)

    Google Scholar 

  66. Pillac, V., Gendreau, M., Guéret, C., Medaglia, A.: A review of dynamic vehicle routing problems. Technical Report CIRRELT-2011-62. Centre interuniversitaire de recherche sur les reseaux denterprise, la logistique et le transport (CIRRELT), Montreal, Canada (2011)

    Google Scholar 

  67. Potvin, J.-Y., Xu, Y., Benyahia, I.: Vehicle routing and scheduling with dynamic travel times. Computers and Operations Research 33(4), 1129–1137 (2006), Part Special Issue: Optimization Days 2003

    Google Scholar 

  68. Powell, W.B.: Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley (2007)

    Google Scholar 

  69. Powell, W.B., Topaloglu, H.: Stochastic programming in transportation and logistics. In: Ruszczynski, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 555–635. Elsevier (2003)

    Google Scholar 

  70. Regan, A.C., Mahmassani, H.S., Jaillet, P.: Evaluation of dynamic fleet management systems: Simulation framework. Transportation Research Record: Journal of the Transportation Research Board 1645(1), 176–184 (1998)

    Article  Google Scholar 

  71. Rei, W., Gendreau, M., Soriano, P.: A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands. Transportation Science 44(1), 136–146 (2010)

    Article  Google Scholar 

  72. Resende, M., Ribeiro, C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 57, pp. 219–249. Springer, New York (2003), doi:10.1007/0-306-48056-5_8

    Google Scholar 

  73. Rockafellar, R.T., Wets, R.J.-B.: Scenarios and policy aggregation in optimization under uncertainty. Mathematics of Operations Research 16(1), 119–147 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  74. Schilde, M., Doerner, K., Hartl, R.: Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers & Operations Research 38(12), 1719–1730 (2011)

    Article  MATH  Google Scholar 

  75. Schorpp, S.: Dynamic Fleet Management for International Truck Transportation focusing on Occasional Transportation Tasks. PhD thesis. University of Augsburg, Faculty of Economics and Business Administration (2010)

    Google Scholar 

  76. Simão, H.P., Day, J., George, A.P., Gifford, T., Nienow, J., Powell, W.B.: An approximate dynamic programming algorithm for large-scale fleet management: A case application. Transportation Science 43(2), 178–197 (2009)

    Article  Google Scholar 

  77. Stützle, T., Hoos, H.H.: Analyzing the run-time behaviour of iterated local search for the tsp. In: III Metaheuristics International Conference. Kluwer Academic Publishers (1999)

    Google Scholar 

  78. Thomas, B.W., White, I.: Chelsea C. Anticipatory route selection. Transportation Science 38(4), 473–487 (2004)

    Article  Google Scholar 

  79. Toth, P., Vigo, D. (eds.): The vehicle routing problem. Society for Industrial and Applied Mathematics (2001)

    Google Scholar 

  80. Voss, S., Osman, I.H., Roucairol, C. (eds.): Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Norwell (1999)

    MATH  Google Scholar 

  81. Yang, W.-H., Mathur, K., Ballou, R.H.: Stochastic vehicle routing problem with restocking. Transportation Science 34, 99–112 (2000)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mobility Department, Austrian Institute of Technology, Klosterneuburg, Austria

    Ulrike Ritzinger & Jakob Puchinger

Authors
  1. Ulrike Ritzinger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jakob Puchinger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ulrike Ritzinger .

Editor information

Editors and Affiliations

  1. , Cite Scientifique, University of Lille 1, Bat.M3, Villeneuve d'Ascq, 59655, France

    El-Ghazali Talbi

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Ritzinger, U., Puchinger, J. (2013). Hybrid Metaheuristics for Dynamic and Stochastic Vehicle Routing. In: Talbi, EG. (eds) Hybrid Metaheuristics. Studies in Computational Intelligence, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30671-6_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-30671-6_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-30670-9

  • Online ISBN: 978-3-642-30671-6

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation