Serving Multiple Urban Areas with Stochastic Customer Requests | SpringerLink
Skip to main content
Springer Nature Link
Log in

Serving Multiple Urban Areas with Stochastic Customer Requests

  • Conference paper
  • First Online:
Dynamics in Logistics

  • 1232 Accesses

Abstract

We consider the problem of routing one vehicle for serving customer requests. Customer requests appear randomly over time and must be either confirmed or rejected after becoming known. Our goal is maximization of the number of customer requests served within a given period of time. Customers have different request probabilities and are geographically clustered. The problem reflects a typical situation of logistics service providers covering a number of urban areas with one vehicle. We solve the problem by approximate dynamic programming. Our results are compared to solutions gained from state-of-the-art waiting heuristics.

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

  • Bellman R (1957) Dynamic Programming. Princeton University Press

    Google Scholar 

  • Bertsimas DJ, van Ryzin G (1991) A stochastic and dynamic vehicle routing problem in the Euclidean plane Operations Research 39:601–615

    Article  MATH  Google Scholar 

  • Bertsimas DJ, van Ryzin G (1993) Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles. Operations Research 41:60–76

    Article  MATH  MathSciNet  Google Scholar 

  • Bianchi L (2000) Notes on dynamic vehicle routing – The state of the art. Technical Report IDSIA-05-01, Idsia, Manno-Lugano (CH)

    Google Scholar 

  • Branke J, Middendorf M, Nöth G, Dessouky M (2005) Waiting strategies for dynamic vehicle routing. Transportation Science 39:298–312

    Article  Google Scholar 

  • Gendreau M, Potvin JY (1998) Dynamic vehicle routing and dispatching. In: Crainic T, Laporte G (eds) Fleet Management and Logistics, Kluwer, London

    Google Scholar 

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

    Article  MATH  Google Scholar 

  • Larsen A, Madsen OBG, Solomon MM (2007) Classification of dynamic vehicle routing systems. In Zeimpekis V et al. (eds) Dynamic Fleet Management, Springer, New York

    Google Scholar 

  • Larsen A, Madsen OBG, Solomon MM (2008) Recent developments in dynamic vehicle routing systems. In Golden B et al. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, New York

    Google Scholar 

  • Mitrovic-Minic S, Laporte G. (2004) Waiting Strategies for the dynamic pickup and delivery problem with time windows. Transportation Research B 38:635–655

    Article  Google Scholar 

  • Novoa C, Storer R (2009) An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research 196:509–515

    Article  MATH  Google Scholar 

  • Papastavrou JD (1996) A stochastic and dynamic routing policy using branching processes with state dependent immigration. European Journal of Operational Research 95:167–177

    Article  MATH  Google Scholar 

  • Powell W (1986) A stochastic model of the dynamic vehicle allocation problem. Transportation Science 20:117–129

    Article  Google Scholar 

  • Powell W (1996) A stochastic formulation of the dynamic assignment problem with an application to truckload motor carriers. Transportation Science 30:195–219

    Article  MATH  Google Scholar 

  • Powell W (2007) approximate dynamic programming. Wiley, Hoboken (NJ)

    Book  MATH  Google Scholar 

  • Psaraftis H (1988) Dynamic vehicle routing problems. In: Goldan B, Assad A (eds.) Vehicle Routing: Methods and Studies. North-Holland, Amsterdam

    Google Scholar 

  • Psaraftis H (1995) Dynamic vehicle routing: Status and prospects. Annals of Operations Research 61:143–164

    Article  MATH  Google Scholar 

  • Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Computers & OR 27:1201–1225

    Article  MATH  Google Scholar 

  • Solomon MM (1987) Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows. Operations Research 35:254–265

    Article  MATH  MathSciNet  Google Scholar 

  • Thomas B (2007) Waiting Strategies for Anticipating Service Requests at Known Customer Locations. Transportation Science 43:319–331

    Article  Google Scholar 

  • Thomas B, White C (2004) Anticipatory route selection. Transportation Science 38:473–484

    Article  Google Scholar 

  • Topaloglu H (2007) A parallelizable and approximate dynamic programming-based dynamic fleet management model with random travel times and multiple vehicle types. In Zeimpekis V et al. (eds) Dynamic Fleet Management, Springer, New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Decision Support Group, Carl-Friedrich Gauss-Department, University of Braunschweig, 38106, Braunschweig, Germany

    Stephan Meisel, Uli Suppa & Dirk Mattfeld

Authors
  1. Stephan Meisel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Uli Suppa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dirk Mattfeld
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stephan Meisel .

Editor information

Editors and Affiliations

  1. FB Mathematik und Informatik, AG Theoretische Informatik, Universität Bremen, Linzer Str. 9a, Bremen, 28359, Germany

    Hans-Jörg Kreowski

  2. BIBA GmbH, Bremer Institut für Messtechnik, Universität Bremen, Hochschulring 20, Bremen, 28359, Germany

    Bernd Scholz-Reiter

  3. BIBA GmbH, Bremer Institut für Messtechnik, Universität Bremen, Hochschulring 20, Bremen, 28359, Germany

    Klaus-Dieter Thoben

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer -Verlag Berlin Heidelberg

About this paper

Cite this paper

Meisel, S., Suppa, U., Mattfeld, D. (2011). Serving Multiple Urban Areas with Stochastic Customer Requests. In: Kreowski, HJ., Scholz-Reiter, B., Thoben, KD. (eds) Dynamics in Logistics. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11996-5_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11996-5_6

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11995-8

  • Online ISBN: 978-3-642-11996-5

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics