Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
EURO Journal on Transportation and Logistics
Published in: EURO Journal on Transportation and Logistics 4/2019

19-04-2018 | Research Paper

Preemptive depot returns for dynamic same-day delivery

Published in: EURO Journal on Transportation and Logistics | Issue 4/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we explore same-day delivery routing and particularly how same-day delivery vehicles can better integrate dynamic requests into delivery routes by taking advantage of preemptive depot returns. A preemptive depot return occurs when a delivery vehicle returns to the depot before delivering all of the packages currently on-board the vehicle. In this paper, we assume that a vehicle serves requests in a particular delivery area. Beginning the day with some known deliveries, the vehicle seeks to serve the known requests as well as additional new requests that are received throughout the day. To serve the new requests, the vehicle must return to the depot to pick up the packages for delivery. In contrast to previous work on same-day delivery routing, in this paper, we allow the vehicle to return to the depot before serving all loaded packages. To solve the problem, we couple an approximation of the value of choosing any particular subset of requests for delivery with a routing heuristic. Our approximation procedure is based on approximate dynamic programming and allows us to capture both the current value of a subset selection decision and its impact on future rewards. Using extensive computational tests, we demonstrate the value of preemptive depot returns and the value of the proposed approximation scheme in supporting preemptive returns. We also identify characteristics of instances for which preemptive depot returns are most likely to offer improvement.
next article The stochastic discrete berth allocation problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
Azi N, Gendreau M, Potvin J-Y (2012) A dynamic vehicle routing problem with multiple delivery routes. Ann Oper Res 199(1):103–112CrossRef
Barto AG (1998) Reinforcement learning: an introduction. MIT Press, Cambridge
Bent RW, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper Res 52(6):977–987CrossRef
Berbeglia G, Cordeau J-F, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202(1):8–15CrossRef
Bertsimas DJ, Chervi P, Peterson M (1995) Computational approaches to stochastic vehicle routing problems. Transp Sci 29(4):342–352CrossRef
BI Intelligence (2017) National retail federation estimates 8-12 2017. [Online; accessed 10 Nov 2017]
Ehmke JF, Campbell AM (2014) Customer acceptance mechanisms for home deliveries in metropolitan areas. Eur J Oper Res 233(1):193–207CrossRef
Ehmke JF, Campbell AM, Urban TL (2015) Ensuring service levels in routing problems with time windows and stochastic travel times. Eur J Oper Res 240(2):539–550CrossRef
Ghiani G, Manni E, Quaranta A, Triki C (2009) Anticipatory algorithms for same-day courier dispatching. Transp Res Part E Logist Transp Rev 45(1):96–106CrossRef
Ghiani G, Manni E, Romano A (2017) Scalable anticipatory policies for the dynamic and stochastic pickup and delivery problem. Submitted for publication
Ghiani G, Manni E, Thomas BW (2012) A comparison of anticipatory algorithms for the dynamic and stochastic traveling salesman problem. Transp Sci 46(3):374–387CrossRef
Goodson JC, Thomas BW, Ohlmann JW (2016) Restocking-based rollout policies for the vehicle routing problem with stochastic demand and duration limits. Transp Sci 50(2):591–607CrossRef
Goodson JC, Thomas BW, Ohlmann JW (2017) A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs. Eur J Oper Res 258(1):216–229CrossRef
Hyytiä E, Penttinen A, Sulonen R (2012) Non-myopic vehicle and route selection in dynamic darp with travel time and workload objectives. Comput Oper Res 39(12):3021–3030CrossRef
Kall P, Wallace S (1994) Stochastic programming. Wiley, New York
Keyes D (2017) E-commerce will make up 17 company is the main reason. [Online; accessed 10 Nov 2017]
Klapp MA, Erera AL, Toriello A (2016) The dynamic dispatch waves problem for same-day delivery. Submitted for publication
Klapp MA, Erera AL, Toriello A (2018) The one-dimensional dynamic dispatch waves problem. Transp Sci 52(2):402–415CrossRef
Larsen A, Madsen O, Solomon M (2002) Partially dynamic vehicle routing-models and algorithms. J Oper Res Soc 53(6):637–646CrossRef
Mes M, van der Heijden M, Schuur P (2010) Look-ahead strategies for dynamic pickup and delivery problems. OR Spectr 32(2):395–421CrossRef
Mitrović-Minić S, Laporte G (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp Res Part B Methodol 38(7):635–655CrossRef
Muñoz Carpintero D, Sàez D, Corès CE, Núñez A (2015) A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach. Transp Sci 49(2):239–253CrossRef
Powell W (2011) Approximate dynamic programming: solving the curses of dimensionality, 2nd edn. Wiley, HobokenCrossRef
Pureza V, Laporte G (2008) Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. INFOR Inf Syst Oper Res 46(3):165–176
Rosenkrantz DJ, Stearns RE, Lewis P (1974) Approximate algorithms for the traveling salesperson problem. In: IEEE conference record of 15th annual symposium on switching and automata theory, 1974. IEEE, pp 33–42
Sáez D, Cortés CE, Núñez A (2008) Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering. Comput Oper Res 35(11):3412–3438CrossRef
Secomandi N (2003) Analysis of a rollout approach to sequencing problems with stochastic routing applications. J Heurist 9(4):321–352CrossRef
Thomas K (2017) CVS will offer next-day delivery of prescription drugs. [Online; accessed 10 Nov 2017]
Ulmer MW, Thomas BW (2018) Enough waiting for the cable guy-estimating arrival times for service vehicle routing. Transp Sci (to appear)
Ulmer MW, Goodson JC, Mattfeld DC, Thomas BW (2017) Dynamic vehicle routing: literature review and modeling framework (under review)
Ulmer MW, Mattfeld DC, Köster F (2018b) Budgeting time for dynamic vehicle routing with stochastic customer requests. Transp Sci 52(1):20–37CrossRef
Wahba P (2017) Best buy and Macy’s ramp up same-day delivery in race with Amazon. [Online; accessed 10 Nov 2017]
Yang W, Mathur K, Ballou R (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34(1):99–112CrossRef
Metadata
Title
Preemptive depot returns for dynamic same-day delivery
Publication date
19-04-2018
Published in
EURO Journal on Transportation and Logistics / Issue 4/2019
Print ISSN: 2192-4376
Electronic ISSN: 2192-4384
DOI
https://doi.org/10.1007/s13676-018-0124-0