Erschienen in:

2023 | OriginalPaper | Buchkapitel

3. Optimierungsprobleme

verfasst von : Jan Brinkmann

Erschienen in: Aktives Ausgleichen von Bike-Sharing-Systemen

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Zusammenfassung

Das Kapitel behandelt die Literatur zum Ausgleich von BSS durch manuelle Verlagerung. Es werden verschiedene Arten von Fahrzeugroutingproblemen vorgestellt, darunter das Traveling-Salesman-Problem (TSP) und das Vehicle-Routing-Problem (VRP). Besondere Aufmerksamkeit wird dem Inventory-Routing-Problem (IRP) für BSS geschenkt, das sowohl stochastische als auch deterministische Anfragen berücksichtigt. Die Autoren stellen eine umfassende Klassifizierung der Literatur vor, die verschiedene Modelle und Ziele der Verlagerungsprozesse beschreibt. Einzigartig ist die Berücksichtigung von Zeitfenstern und Kapazitätsbeschränkungen, die die Komplexität der Problemlösung erhöhen. Die Analyse zeigt, wie verschiedene Ansätze zur Minimierung von Fahrzeugtourenlängen, Verlagerungen und fehlgeschlagenen Anfragen beitragen können. Die detaillierte Darstellung der Literatur und die Klassifizierung der Modelle bieten wertvolle Einblicke für Forscher und Praktiker in der Logistik und Verkehrsplanung.

KI-Generiert

Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.

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 Bike-Sharing-Systeme

Nächstes Kapitel Dynamische Entscheidungsfindung

Wir möchten anmerken, dass auch bei deterministisch-statischen Optimierungsproblemen manchmal mehrere Entscheidungspunkte verwendet werden. Dies geschieht aufgrund der Dekomposition.

Streng genommen wird in dem betreffenden Artikel kein IRP untersucht, wenn entweder keine Bestandsaufnahme oder keine Routing-Entscheidungen getroffen werden. Dennoch kann es sein, dass eine dieser Entscheidungen aufgrund der Zersetzung nicht berücksichtigt wird. Wir nehmen die Artikel in unsere Klassifizierung auf, da sie in engem Zusammenhang mit IRP für BSS stehen.

Natürlich können die Fahrzeugtourlängen in Gesamtfahrzeiten umgerechnet werden.

Alvarez-Valdes R, Belenguer JM, Benavent E, Bermudez JD, Muñoz F, Vercher E, Verdejo F (2016) Optimizing the level of service quality of a bike-sharing system. Omega 64:163–175. https://doi.org/10.1016/j.omega.2015.09.007CrossRef

Arabzad SM, Shirouyehzad H, Bashiri M, Tavakkoli-Moghaddam R, Najafi E (2018) Rebalancing static bike-sharing systems: a two-period two-commodity multi-depot mathematical model. Transport 33:718–726. https://doi.org/10.3846/transport.2018.1558CrossRef

Brinkmann J, Ulmer MW, Mattfeld DC (2015) Short-term strategies for stochastic inventory routing in bike sharing systems. Transp Res Proc 10:364–373. https://doi.org/10.1016/j.trpro.2015.09.086CrossRef

Brinkmann J, Ulmer MW, Mattfeld DC (2016) Inventory routing for bikes sharing systems. Transp Res Proc 19:316–327. https://doi.org/10.1016/j.trpro.2016.12.091CrossRef

Brinkmann J, Ulmer MW, Mattfeld DC (2019a) Dynamic lookahead policies for stochastic-dynamic inventory routing in bike sharing systems. Comput Oper Res 106:260–279. https://doi.org/10.1016/j.cor.2018.06.004MathSciNetCrossRefMATH

Brinkmann J, Ulmer MW, Mattfeld DC (2019b) The multi-vehicle stochastic-dynamic inventory routing problem for bike sharing systems. Bus Res. https://doi.org/10.1007/s40685-019-0100-z

Bulhões T, Subramanian A, Erdoǧan G, Laporte G (2018) The static bike relocation problem with multiple vehicles and visits. Eur J Oper Res 264(2):508–523. https://doi.org/10.1016/j.ejor.2017.06.028MathSciNetCrossRefMATH

Caggiani L, Ottomanelli M (2012) A modular soft computing based method for vehicles repositioning in bike-sharing systems. Proc Soc Behav Sci 54:675–684. https://doi.org/10.1016/j.sbspro.2012.09.785ElsevierCrossRef

Caggiani L, Ottomanelli M (2013) A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems. Proc Soc Behav Sci 87:203–210. https://doi.org/10.1016/j.sbspro.2013.10.604CrossRef

Chemla D, Meunier F, Wolfler Calvo R (2013) Bike sharing systems: solving the static rebalancing problem. Discret Optim 10(2):120–146. https://doi.org/10.1016/j.disopt.2012.11.005MathSciNetCrossRefMATH

Chiariotti F, Pielli C, Zanella A, Zorzi M (2018) A dynamic approach to rebalancing bike-sharing systems. Sensors 18(2):512. https://doi.org/10.3390/s18020512CrossRef

Coelho LC, Cordeau JF, Laporte G (2014b) Thirty years of inventory routing. Transplant Sci 48(1):1–19. https://doi.org/10.1287/trsc.2013.0472CrossRef

Contardo C, Morency C, Rousseau LM (2012) Balancing a dynamic public bike-sharing system. In: CIRRELT-2012-09. https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-09.pdf. Zugegriffen am 08.12.2014

Cruz F, Subramanian A, Bruck BP, Iori M (2017) A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Comput Oper Res 79:19–33. https://doi.org/10.1016/j.cor.2016.09.025MathSciNetCrossRefMATH

Datner S, Raviv T, Tzur M, Chemla D (2017) Setting inventory levels in a bike sharing network. Transplant Sci 53(1):62–76. https://doi.org/10.1287/trsc.2017.0790CrossRef

Dell’Amico M, Hadjicostantinou E, Iori M, Novellani S (2014) The bike sharing rebalancing problem: mathematical formulations and benchmark instances. Omega 45:7–19. https://doi.org/10.1016/j.omega.2013.12.001CrossRef

Dell’Amico M, Iori M, Novellani S, Stützle T (2016) A destroy and repair algorithm for the bike sharing rebalancing problem. Comput Oper Res 71:149–162. https://doi.org/10.1016/j.cor.2016.01.011MathSciNetCrossRefMATH

Dell’Amico M, Iori M, Novellani S, Subramanian A (2018) The bike sharing rebalancing problem with stochastic demands. Transp Res B Methodol 118:362–380. https://doi.org/10.1016/j.trb.2018.10.015CrossRef

Di Gaspero L, Rendl A, Urli T (2013a) A hybrid ACO+CP for balancing bicycle sharing systems. Hybrid metaheuristics, Lecture notes in computer science, Bd 7919. Springer, Berlin, S 198–212. https://doi.org/10.1007/978-3-642-38516-2_16CrossRef

Di Gaspero L, Rendl A, Urli T (2013b) Constraint-based approaches for balancing bike sharing systems. Principles and practice of constraint programming, Lecture notes in computer science, Bd 8124. Springer, Berlin, S 758–773. https://doi.org/10.1007/978-3-642-40627-0_56CrossRefMATH

Erdoǧan G, Laporte G, Calvo RW (2014) The static bicycle relocation problem with demand intervals. Eur J Oper Res 238(2):451–457. https://doi.org/10.1016/j.ejor.2014.04.013MathSciNetCrossRefMATH

Erdoǧan G, Battarra M, Calvo RW (2015) An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. Eur J Oper Res 245(3):667–679. https://doi.org/10.1016/j.ejor.2015.03.043MathSciNetCrossRefMATH

Espegren HM, Kristianslund J, Andersson H, Fagerholt K (2016) The static bicycle repositioning problem – literature survey and new formulation. Computational logistics, Lecture notes in computer science, Bd 9855. Springer, Cham, S 337–351. https://doi.org/10.1007/978-3-319-44896-1_22CrossRef

Forma IA, Raviv T, Tzur M (2015) A 3-step math heuristic for the static repositioning problem in bike-sharing systems. Transp Res B Methodol 71:230–247. https://doi.org/10.1016/j.trb.2014.10.003CrossRef

Fricker C, Gast N (2016) Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity. EURO J Transp Logist 5(3):261–291. https://doi.org/10.1007/s13676-014-0053-5CrossRef

Ghosh S, Trick MA, Varakantham P (2016) Robust repositioning to counter unpredictable demand in bike sharing systems. In: Proceedings of the twenty-fifth international joint conference on artificial intelligence (IJCAI-16). http://www.ijcai.org/Proceedings/2016. Zugegriffen am 11.12.2017

Ghosh S, Varakantham P, Adulyasak Y, Jaillet P (2017) Dynamic repositioning to reduce lost demand in bike sharing systems. J Artif Intell Res 58:387–430. https://doi.org/10.1613/jair.5308CrossRef

Ho SC, Szeto WY (2014) Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transp Res Part E: Logist Transp Rev 69:180–198. https://doi.org/10.1016/j.tre.2014.05.017CrossRef

Ho SC, Szeto WY (2017) A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem. Transp Res B Methodol 95:340–363. https://doi.org/10.1016/j.trb.2016.11.003CrossRef

Kadri AA, Labadi K, Kacem I (2015) An integrated petri net and genetic algorithm based approach for performance optimization of bicycle-sharing systems. Eur J Ind Eng 9(5):638–663. https://doi.org/10.1504/EJIE.2015.071777CrossRef

Kadri AA, Kacem I, Labadi K (2016) A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems. Comput Ind Eng 95:42–52. https://doi.org/10.1016/j.cie.2016.02.002CrossRef

Kadri AA, Kacem I, Labadi K (2018) Lower and upper bounds for scheduling multiple balancing vehicles in bicycle-sharing systems. Soft Comput. https://doi.org/10.1007/s00500-018-3258-y

Kloimüllner C, Raidl GR (2017a) Full-load route planning for balancing bike sharing systems by logic-based benders decomposition. Networks 69(3):270–289. https://doi.org/10.1002/net.21736MathSciNetCrossRefMATH

Kloimüllner C, Papazek P, Hu B, Raidl GR (2014) Balancing bicycle sharing systems: an approach for the dynamic case. Evolutionary computation in combinatorial optimization, Lecture notes in computer science, Bd 8600. Springer, Berlin, S 73–84. https://doi.org/10.1007/978-3-662-44320-0_7CrossRef

Kloimüllner C, Papazek P, Hu B, Raidl GR (2015) A cluster-first route-second approach for balancing bicycle sharing systems. In: Computer aided systems theory – EUROCAST 2015, Lecture notes in computer science, Bd 9520. Springer, Cham, S 439–446. https://doi.org/10.1007/978-3-319-27340-2_55CrossRef

Laporte G, Mercure H, Nobert Y (1986) An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16(1):33–46. https://doi.org/10.1002/net.3230160104MathSciNetCrossRefMATH

Legros B (2019) Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station. Eur J Oper Res 272(2):740–753. https://doi.org/10.1016/j.ejor.2018.06.051MathSciNetCrossRefMATH

Li Y, Szeto WY, Long J, Shui CS (2016) A multiple type bike repositioning problem. Transp Res B Methodol 90:263–278. https://doi.org/10.1016/j.trb.2016.05.010CrossRef

Lu CC (2016) Robust multi-period fleet allocation models for bike-sharing systems. Netw Spat Econ 16(1):61–82. https://doi.org/10.1007/s11067-013-9203-9MathSciNetCrossRefMATH

Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J Assoc Comput Mach 7(4):326–329. https://doi.org/10.1145/321043.321046MathSciNetCrossRefMATH

Neumann Saavedra BA (2018) Service network design of bike sharing systems with resource-management consideration. PhD thesis, Technische Universität Braunschweig. https://katalog.ub.tu-braunschweig.de/vufind/Record/1015689094

Neumann Saavedra BA, Vogel P, Mattfeld DC (2015) Anticipatory service network design of bike sharing systems. Transp Res Proc 10:355–363. https://doi.org/10.1016/j.trpro.2015.09.085CrossRef

Neumann Saavedra BA, Crainic TG, Gendron B, Mattfeld DC, Römer M (2016) Service network design of bike sharing systems with resource constraints. Computational logistics, Lecture notes in computer science, Bd 9855. Springer, Cham, S 352–366. https://doi.org/10.1007/978-3-319-44896-1_23CrossRef

Papazek P, Raidl GR, Rainer-Harbach M, Hu B (2013) A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems. In: Computer aided systems theory – EUROCAST 2013: 14th international conference, Lecture notes in computer science. Springer, Berlin, S 372–379. https://doi.org/10.1007/978-3-642-53856-8_47CrossRef

Papazek P, Kloimüllner C, Hu B, Raidl GR (2014) Balancing bicycle sharing systems: an analysis of path relinking and recombination within a GRASP hybrid. In: Parallel Problem solving from nature – PPSN XIII, Bd 8672. Lecture notes in computer science. Springer, Cham, S 792–801. https://doi.org/10.1007/978-3-319-10762-2_78CrossRef

Rainer-Harbach M, Papazek P, Hu B, Raidl GR (2013) Balancing bicycle sharing systems: a variable neighborhood search approach. Evolutionary computation in combinatorial optimization, Lecture notes in computer science, Bd 7832. Springer, Berlin, S 121–132. https://doi.org/10.1007/978-3-642-37198-1_11CrossRef

Rainer-Harbach M, Papazek P, Raidl GR, Hu B, Kloimüllner C (2015) PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems. J Glob Optim 63(3):597–629. https://doi.org/10.1007/s10898-014-0147-5MathSciNetCrossRefMATH

Raviv T, Kolka O (2013) Optimal inventory management of a bike-sharing station. IIE Trans 45(10):1077–1093. https://doi.org/10.1080/0740817X.2013.770186CrossRef

Raviv T, Tzur M, Forma IA (2013) Static repositioning in a bike-sharing system: models and solution approaches. EURO J Transp Logist 2(3):187–229. https://doi.org/10.1007/s13676-012-0017-6CrossRef

Ricker VHH (2015) Ein Dekompositionsansatz für das taktisch-operative management von bike-sharing-systemen. PhD thesis, Technische Universität Braunschweig. http://www.digibib.tu-bs.de/?docid=00062118

Rosenkrantz D, Stearns R, Lewis P II (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J Comput 6(3):563–581. https://doi.org/10.1137/0206041MathSciNetCrossRefMATH

Rudloff C, Lackner B (2014) Modeling demand for bikesharing systems – neighboring stations as source for demand and reason for structural breaks. Transp Res Rec: J Transp Res Board 2430:1–11. https://doi.org/10.3141/2430-01CrossRef

Savelsbergh MWP, Sol M (1995) The general pickup and delivery problem. Transplant Sci 29(1):17–29. https://doi.org/10.1287/trsc.29.1.17CrossRefMATH

Schuijbroek J, Hampshire RC, van Hoeve WJ (2017) Inventory rebalancing and vehicle routing in bike sharing systems. Eur J Oper Res 257(3):992–1004. https://doi.org/10.1016/j.ejor.2016.08.029MathSciNetCrossRefMATH

Shui CS, Szeto WY (2017) Dynamic green bike repositioning problem – a hybrid rolling horizon artificial bee colony algorithm approach. Transp Res Part D Transp Environ. https://doi.org/10.1016/j.trd.2017.06.023

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265. https://doi.org/10.1287/opre.35.2.254MathSciNetCrossRefMATH

Szeto WY, Shui CS (2018) Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem. Transp Res B: Methol 109:176–211. https://doi.org/10.1016/j.trb.2018.01.007CrossRef

Szeto WY, Liu Y, Ho SC (2016) Chemical reaction optimization for solving a static bike repositioning problem. Transp Res Part D: Transp Environ 47:104–135. https://doi.org/10.1016/j.trd.2016.05.005CrossRef

Tang Q, Fu Z, Qiu M (2019) A bilevel programming model and algorithm for the static bike repositioning problem. J Adv Transp. https://doi.org/10.1155/2019/8641492

Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications, 2. Aufl. Society for Industrial and Applied Mathematics, PhiladelphiaCrossRefMATH

Ulmer MW, Heilig L, Voß S (2017a) On the value and challenge of real-time information in dynamic dispatching of service vehicles. Bus Inf Syst Eng 59:161–171. https://doi.org/10.1007/s12599-017-0468-2CrossRef

Vogel P, Neumann Saavedra BA, Mattfeld DC (2014) A hybrid metaheuristic to solve the resource allocation problem in bike sharing systems. Hybrid metaheuristics, Lecture notes in computer science, Bd 8457. Springer, Cham, S 16–29. https://doi.org/10.1007/978-3-319-07644-7_2CrossRef

Vogel P, Ehmke JF, Mattfeld DC (2017) Cost-efficient allocation of bikes to stations in bike sharing systems. Computational logistics, Lecture notes in computer science, Bd 10,572. Springer, Cham, S 498–512. https://doi.org/10.1007/978-3-319-68496-3_33CrossRefMATH

Wang Y, Szeto WY (2018) Static green repositioning in bike sharing systems with broken bikes. Transp Res Part D: Transp Environ 65:438–457. https://doi.org/10.1016/j.trd.2018.09.016CrossRef

Yan S, Lin JR, Chen YC, Xie FR (2017) Rental bike location and allocation under stochastic demands. Comput Ind Eng 107:1–11. https://doi.org/10.1016/j.cie.2017.02.018CrossRef

Zhang D, Yu C, Desai J, Lau HYK, Srivathsan S (2017) A time-space network flow approach to dynamic repositioning in bicycle sharing systems. Transp Res B Methodol 103:188–207. https://doi.org/10.1016/j.trb.2016.12.006

Titel: Optimierungsprobleme
verfasst von: Jan Brinkmann
Verlag: Springer International Publishing
Buch: Aktives Ausgleichen von Bike-Sharing-Systemen
Print ISBN: 978-3-031-16535-1

Electronic ISBN: 978-3-031-16536-8

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-16536-8_3

Springer Professional

Zusammenfassung

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"