nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Anticipation in Dynamic Vehicle Routing

verfasst von : Marlin W. Ulmer

Erschienen in: Operations Research Proceedings 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

For many routing applications, decision making is conducted under incomplete information. The information is only revealed successively during the execution of the routing. In many cases, dispatchers adapt their decisions dynamically to new information. Nevertheless, to avoid myopic decisions, dispatchers have to anticipate future events in current decision making. In this paper, we propose the use of a Markov decision process (MDP) to model stochastic dynamic vehicle routing problems (SDVRPs). For the integration of stochasticity in dynamic decision making, we present novel methods of approximate dynamic programming (ADP). These methods are extensions and combinations of general ADP-methods and are tailored to match the characteristics of SDVRPs. A comparison with conventional state-of-the-art benchmark heuristics for a SDVRP with stochastic customer requests proves the ADP-methods to be highly advantageous.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Solving the Time-Dependent Shortest Path Problem Using Super-Optimal Wind

Nächstes Kapitel Shapley Value Based Allocation for Multi-objective Cooperative Problems

Notably, in the following, we present non-parametric VFA because parametric VFAs are often not able to capture the complex value function structure of SDVRPs [11].

Gendreau, M., Jabali, O., & Rei, W. (2016). 50th anniversary invited article-future research directions in stochastic vehicle routing. Transportation Science, 50(4), 1163–1173.CrossRef

Ghiani, G., Manni, E., & Thomas, B. W. (2012). A comparison of anticipatory algorithms for the dynamic and stochastic traveling salesman problem. Transportation Science, 46(3), 374–387.CrossRef

Kim, S.-H., & Nelson, B. L. (2001). A fully sequential procedure for indifference-zone selection in simulation. ACM Transactions on Modeling and Computer Simulation (TOMACS), 11(3), 251–273.CrossRef

Powell, W. B. (2011). Approximate dynamic programming: solving the curses of dimensionality (2nd ed.)., Wiley series in probability and statistics New York: Wiley.CrossRef

Psaraftis, H. N., Wen, M., & Kontovas, C. A. (2016). Dynamic vehicle routing problems: Three decades and counting. Networks, 67(1), 3–31.CrossRef

Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. New York: Wiley.

Savelsbergh, M., & Van Woensel, T. (2016). 50th anniversary invited article-city logistics: Challenges and opportunities. Transportation Science, 50(2), 579–590.CrossRef

Speranza, M. G. (2016). Trends in transportation and logistics. European Journal of Operational Research.

Thomas, B. W. (2007). Waiting strategies for anticipating service requests from known customer locations. Transportation Science, 41(3), 319–331.CrossRef

10.

Ulmer, M. W. (2017). Approximate dynamic programming for dynamic vehicle routing (Vol. 61)., Operations research/computer science interfaces series Berlin: Springer.

11.

Ulmer, M. W. & Thomas, B. W. (2017). Meso-parametric value function approximation for dynamic customer acceptances in delivery routing (submitted).

12.

Ulmer, M. W., Mattfeld, D. C., Hennig, M., & Goodson, J. C. (2015). A rollout algorithm for vehicle routing with stochastic customer requests. Logistics management (pp. 217–227)., Lecture notes in logistics Berlin: Springer.

13.

Ulmer, M. W., Heilig, L., & Voß, S. (2017). On the value and challenge of real-time information in dynamic dispatching of service vehicles. Business & Information. Systems Engineering, 59(3), 161–171.CrossRef

14.

Ulmer, M. W., Mattfeld, D. C., & Köster, F. (2017). Budgeting time for dynamic vehicle routing with stochastic customer requests. Transportation Science.

15.

Ulmer, M. W., Goodson, J. C., Mattfeld, D. C., & Hennig, M. Offline–online approximate dynamic programming for dynamic vehicle routing with stochastic requests. Transportation Science (to appear).

Titel: Anticipation in Dynamic Vehicle Routing
verfasst von: Marlin W. Ulmer
Verlag: Springer International Publishing
Buch: Operations Research Proceedings 2017
Print ISBN: 978-3-319-89919-0

Electronic ISBN: 978-3-319-89920-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-89920-6_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"