[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Solving an On-Line Capacitated Vehicle Routing Problem with Structured Time Windows

  • Conference paper
  • First Online:
Operations Research Proceedings 2016

Part of the book series: Operations Research Proceedings ((ORP))

Abstract

The capacitated Vehicle Routing Problem with structured Time Windows (cVRPsTW) is concerned with finding optimal tours for vehicles with given capacity constraints to deliver goods to customers within assigned time windows that can hold several customers and have a special structure (in our case equidistant and non-overlapping). In this work, we consider an on-line variant of the cVRPsTW that arises in the online shopping service of an international supermarket chain: customers choose a delivery time window for their order online, and the fleet’s tours are updated accordingly in real time. This leads to two challenges. First, the new customers need to be inserted at a suitable place in one of the existing tours. Second, the new customers have to be inserted in real time due to very high request rates. This is why we apply a computationally cheap, two-step approach consisting of an insertion step and an improvement step. In this context, we present a Mixed-Integer Linear Program (MILP) and a heuristic that employs the MILP. In an experimental evaluation, we demonstrate the efficiency of our approaches on a variety of benchmark sets.

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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 103.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 129.99
Price includes VAT (United Kingdom)
  • Compact, lightweight 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. Baldacci, R., Mingozzi, A., Roberti, R.: Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218(1), 1–6 (2012)

    Article  Google Scholar 

  2. Campbell, A.M., Savelsbergh, M.W.P.: Decision support for consumer direct grocery initiatives. Transp. Sci. 39(3), 313–327 (2005)

    Article  Google Scholar 

  3. Ioannou, G., Kritikos, G., Prastacos, G.: A greedy look-ahead heuristic for the vehicle routing problem with time windows. J. Oper. Res. Soc. 52(5), 523–537 (2001)

    Article  Google Scholar 

  4. Lodi, A., Milano, M.: A hybrid exact algorithm for the tsptw. INFORMS J. Comput. 14, 403–417 (2002)

    Article  Google Scholar 

  5. Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics (2002)

    Google Scholar 

  6. Yang, X., Strauss, A.K., Currie, C.S.M., Eglese, R.: Choice-based demand management and vehicle routing in e-fulfillment. Transp. Sci. (2014)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Alpen-Adria Universität Klagenfurt, Klagenfurt, Austria

    Philipp Hungerländer, Kerstin Maier, Jörg Pöcher, Andrea Rendl & Christian Truden

Authors
  1. Philipp Hungerländer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kerstin Maier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jörg Pöcher
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrea Rendl
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Christian Truden
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christian Truden .

Editor information

Editors and Affiliations

  1. Institute of Computer Science, Helmut Schmidt University, Institute of Computer Science, Hamburg, Germany

    Andreas Fink

  2. Applied Mathematics, Helmut Schmidt University, Applied Mathematics, Hamburg, Germany

    Armin Fügenschuh

  3. Institute of Logistics and Organization, Helmut Schmidt University, Institute of Logistics and Organization, Hamburg, Germany

    Martin Josef Geiger

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this paper

Cite this paper

Hungerländer, P., Maier, K., Pöcher, J., Rendl, A., Truden, C. (2018). Solving an On-Line Capacitated Vehicle Routing Problem with Structured Time Windows. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_18

Download citation

Publish with us

Policies and ethics