nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

A New Lower Bound for the Static Dial-a-Ride Problem with Ride and Waiting Time Minimization

verfasst von : Christian Pfeiffer, Arne Schulz

Erschienen in: Dynamics in Logistics

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

The paper focuses on the static dial-a-ride problem with ride and waiting time minimization. This is an important problem setting of significant practical relevance, as several ridesharing providers launched in recent years in large cities. In contrast to the standard dial-a-ride problem, these providers focus on the general public. Therefore, they are amongst others in competition with taxis and private cars, which makes a more customer-oriented objective necessary. We minimize the sum of relative detours of all customers. The paper introduces upper bounds for the arrival times and an initial lower bound for the objective value. Our approach is tested in a computational study with realistic test instances.

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 Digital Twin Features for the Intelligent Container

Nächstes Kapitel An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations

CleverShuttle: Shared rides for a better furture (2022). https://www.clevershuttle.de/en/. Accessed 03 Jan 2022

Cordeau, J.F.: A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3), 573–586 (2006)MathSciNetCrossRef

Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29–46 (2007)MathSciNetCrossRef

Detti, P., Papalini, F., de Lara, G.Z.M.: A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega 70, 1–14 (2017)CrossRef

Diana, M., Dessouky, M.M.: A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows. Transp. Res. Part B Methodol. 38(6), 539–557 (2004)CrossRef

Gschwind, T., Irnich, S.: Effective handling of dynamic time windows and its applications to solving the dial-a-ride problem. Transp. Sci. 49(2), 335–354 (2015)CrossRef

Heilporn, G., Cordeau, J.F., Laporte, G.: An integer l-shaped algorithm for the dial-a-ride problem with stochastic customer delays. Discret. Appl. Math. 159(9), 883–895 (2011)MathSciNetCrossRef

Ho, S.C., Szeto, W.Y., Kuo, Y.H., Leung, J.M.Y., Petering, M., Tou, T.W.H.: A survey of dial-a-ride problems: literature review and recent developments. Transp. Res. Part B Methodol. 111, 395–421 (2018)CrossRef

ioki GmbH: ioki—inspiring smart mobility (2022). https://ioki.com/en/home/. Accessed 03 Jan 2022

10.

Jaw, J.J., Odoni, A.R., Psaraftis, H.N., Wilson, N.H.: A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transp. Res. Part B Methodol. 20(3), 243–257 (1986)CrossRef

11.

Jorgensen, R.M., Larsen, J., Bergvinsdottir, K.B.: Solving the dial-a-ride problem using genetic algorithms. J. Oper. Res. Soc. 58(10), 1321–1331 (2007)CrossRef

12.

MOIA GmbH: Reunion begins here (2022). https://www.moia.io/en. Accessed 03 Jan 2022

13.

Molenbruch, Y., Braekers, K., Caris, A., den Berghe, G.V.: Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation. Comput. Oper. Res. 77, 58–71 (2017)MathSciNetCrossRef

14.

Nie, W.: Waiting: integrating social and psychological perspectives in operations management. Omega 28(6), 611–629 (2000)CrossRef

15.

Paquette, J., Cordeau, J.F., Laporte, G., Pascoal, M.M.: Combining multicriteria analysis and tabu search for dial-a-ride problems. Transp. Res. Part B Methodol. 52, 1–16 (2013)CrossRef

16.

Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery models: part ii: transportation between pickup and delivery locations. J. für Betriebswirtschaft 58(2), 81–117 (2008)CrossRef

17.

Parragh, S.N., Doerner, K.F., Hartl, R.F., Gandibleux, X.: A heuristic two-phase solution approach for the multi-objective dial-a-ride problem. Networks 54(4), 227–242 (2009)MathSciNetCrossRef

18.

Parragh, S.N., de Sousa, J.P., Almada-Lobo, B.: The dial-a-ride problem with split requests and profits. Transp. Sci. 49(2), 311–334 (2015)CrossRef

19.

Pfeiffer, C., Schulz, A.: An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectr. 44, 87–119 (2022)MathSciNetCrossRef

20.

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

21.

Ropke, S., Cordeau, J.F., Laporte, G.: Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4), 258–272 (2007)MathSciNetCrossRef

22.

Sexton, T.R., Bodin, L.D.: Optimizing single vehicle many-to-many operations with desired delivery times: I. Scheduling. Transp. Sci. 19(4), 378–410 (1985)MathSciNetCrossRef

Titel: A New Lower Bound for the Static Dial-a-Ride Problem with Ride and Waiting Time Minimization
verfasst von: Christian Pfeiffer
Arne Schulz
Verlag: Springer International Publishing
Buch: Dynamics in Logistics
Print ISBN: 978-3-031-05358-0

Electronic ISBN: 978-3-031-05359-7

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-05359-7_19

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"

Premium Partner