An Improved Agent-Based Approach to the Dynamic Vehicle Routing Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

An Improved Agent-Based Approach to the Dynamic Vehicle Routing Problem

  • Conference paper
  • First Online:
Intelligent Decision Technologies 2016 (IDT 2016)

Part of the book series: Smart Innovation, Systems and Technologies ((SIST,volume 56))

Included in the following conference series:

  • 725 Accesses

Abstract

The paper proposes a multi-agent approach to the Dynamic Vehicle Routing Problem, where the process of solving instances of the problem is performed by a set of software agents with different abilities. The agents are responsible for generating new requests, managing a set of requests, allocating them to the available vehicles, and monitoring the behavior of the system. The main steps of the algorithm implemented in the system include dispatching the static and dynamic requests to the available vehicles. In order to increase the efficiency of these processes, a request buffering strategy has been implemented. Computational experiment confirmed its positive impact on the results obtained by the proposed approach.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 22879
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 28599
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 28599
Price includes VAT (Japan)
  • 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

Similar content being viewed by others

References

  1. Barbucha, D., Jȩdrzejowicz, P.: Multi-agent platform for solving the dynamic vehicle routing problem. In: Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems (ITSC 2008), pp. 517–522. IEEE Press, New York (2008)

    Google Scholar 

  2. Barbucha, D.: A multi-agent approach to the dynamic vehicle routing problem with time windows. In: Badica, C., Nguyen, N.T., Brezovan, M. (eds.) Computational Collective Intelligence. Technologies and Applications—5th International Conference, ICCCI 2013. LNCS, vol. 8083, pp. 467–476. Springer. Berlin (2013)

    Google Scholar 

  3. Branchini, R.M., Armentano, A.V., Lokketangen, A.: Adaptive granular local search heuristic for a dynamic vehicle routing problem. Comput. Oper. Res. 36(11), 2955–2968 (2009)

    Article  MATH  Google Scholar 

  4. Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.): Combinatorial Optimization. John Wiley, Chichester (1979)

    MATH  Google Scholar 

  5. Gendreau, M., Guertin, F., Potvin, J.-Y., Taillard, E.: Parallel Tabu search for real-time vehicle routing and dispatching. Transp. Sci. 33(4), 381–390 (1999)

    Article  MATH  Google Scholar 

  6. Hanshar, F.T., Ombuki-Berman, B.M.: Dynamic vehicle routing using genetic algorithms. Appl. Intell. 27, 89–99 (2007)

    Article  MATH  Google Scholar 

  7. Larsen, A.: The on-line vehicle routing problem. Ph.D. Thesis, Institute of Mathematical Modelling, Technical University of Denmark (2001)

    Google Scholar 

  8. Lund, K., Madsen, O.B.G., Rygaard, J.M.: Vehicle routing problems with varying degrees of dynamism. Technical report, Institute of Mathematical Modelling, Technical University of Denmark (1996)

    Google Scholar 

  9. Mitrovic-Minic, S., Laporte, G.: Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp. Res. Part B 38, 635–655 (2004)

    Google Scholar 

  10. Mitrovic-Minic, S., Krishnamurti, R., Laporte, G.: Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transp. Res. Part B 38, 669-685 (2004)

    Google Scholar 

  11. Montemanni, R., Gambardella, L.M., Rizzoli, A.E., Donati, A.V.: A new algorithm for a dynamic vehicle routing problem based on ant colony system. J. Comb. Optim. 10, 327–343 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Pillac, V., Gendreau, M.: Guret, C., Medaglia, A.L.: A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225, 1–11 (2013)

    Google Scholar 

  13. Psaraftis, H.: A dynamic-programming solution to the single vehicle many-tomany immediate request dial-a-ride problem. Transp. Sci. 14(2), 130–154 (1980)

    Google Scholar 

  14. Pureza, V., Laporte, G.: Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. INFOR 46(3), 165–175 (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Systems, Gdynia Maritime University, Morska 83, 81-225, Gdynia, Poland

    Dariusz Barbucha

Authors
  1. Dariusz Barbucha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dariusz Barbucha .

Editor information

Editors and Affiliations

  1. Maritime University, Gdynia, Poland

    Ireneusz Czarnowski

  2. Artificial Intelligence Department, Universidad Politécnica de Madrid, Boadilla del Monte, Madrid, Spain

    Alfonso Mateos Caballero

  3. KES International, Shoreham-by-sea, United Kingdom

    Robert J. Howlett

  4. University of Canberra, Canberra, South Australia, Australia

    Lakhmi C. Jain

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Barbucha, D. (2016). An Improved Agent-Based Approach to the Dynamic Vehicle Routing Problem. In: Czarnowski, I., Caballero, A., Howlett, R., Jain, L. (eds) Intelligent Decision Technologies 2016. IDT 2016. Smart Innovation, Systems and Technologies, vol 56. Springer, Cham. https://doi.org/10.1007/978-3-319-39630-9_30

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-39630-9_30

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-39629-3

  • Online ISBN: 978-3-319-39630-9

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation