Tourenplanung mit Fahrzeugsynchronisation (DFG-Projekt)
Synchronisierter Tourenplan für die Mitarbeiter eines Pflegedienstes
Übersicht
Gegenstand und Ziele
Die Synchronisation von Fahrzeugen, Personen oder Diensten, die in mobilen Servicenetzen wie z. B. bei Pflegediensten oder der Hausmüllentsorgung zu gewährleisten ist, stellt äußerst komplexe Anforderungen an die Planung der jeweiligen Arbeitsvorgänge. Dieses Forschungsvorhaben zielt auf eine systematische Erfassung, Modellierung und Lösung von räumlichen und zeitlichen Synchronisationsbeziehungen zwischen mobilen Betriebsmitteln in einem Servicenetz. ab. Gegenstand der Forschung sind dabei Tourenplanungsprobleme wie sie in Transportbetrieben, Entsorgungsunternehmen und anderen Dienstleistungsbereichen zur Planung der operativen Vorgänge gelöst werden müssen. Zunächst werden vier Grundformen der Synchronisation, welche die möglichen räumlichen und zeitlichen Koordinationsbedarfe zwischen zwei Diensten unterscheiden, durch eine mathematische Modellierung mittels gemischt ganzzahliger, linearer Restriktionen beschrieben. Hieraus wird ein verallgemeinertes Restriktionssystem für die Fahrzeugsynchronisation abgeleitet. Zur Behandlung von Fahrzeugsynchronisationsbedingungen im Rahmen der Tourenplanung werden nachfolgend Separationsansätze für die ganzzahlige Optimierung erforscht. Anschließend sollen heuristische Nachbarschaftssuchverfahren und Evolutionäre Algorithmen für die Problemstellung entwickelt werden, um Lösungsansätze für große Servicenetze, wie sie in der Praxis anzutreffen sind, bereitzustellen.
Kurzdarstellung
Tourenplanung unter Berücksichtigung von Fahrzeugsynchronisation ist eine in vielen Branchen anzutreffende, interessante Mischform von verschiedenen bekannten Tourenplanungsproblemen. Dabei müssen die Fahrpläne der Fahrzeuge räumlich und/oder zeitlich miteinander gekoppelt werden, wobei mehrere Zielkriterien betrachtet werden können (z. B. Kosten der gefahrenen Touren, gegenseitige Wartezeiten der Fahrzeuge). Diese Problemstellungen wurden in der wissenschaftlichen Literatur bislang kaum betrachtet, obwohl zahlreiche Anwendungsfelder existieren. Typische Beispiele findet man im landwirtschaftlichen Bereich oder bei Paketdienstleistern. Gegenstand des Forschungsvorhabens ist eine wissenschaftliche Erschließung von Tourenplanungsproblemen mit Fahrzeugssynchronisation. Dazu zählen eine systematische Bestimmung relevanter Problemeigenschaften, deren effiziente Modellierung und das Finden exakter und heuristischer Lösungsansätze.
Literatur
Bredström, D., Rönnqvist, M.(2008): Combined vehicle routing and scheduling with temporal precedence and synchronisation constraints, European Journal of Operational Research 191: 19-31
Del Pia, A., Filippi, C.(2006): A variable neighborhood descent algorithm for a real waste collection problem with mobile depots, International Transactions in Operational Research 13: 125-141
Projektzeitraum
2009 – 2014
Projektbezogene Vorträge und Publikationen
- Mankowska, D. S., Bierwirth, C.: Uni ed model for Vehicle Routing Problem with Synchronization Requirements, Technical Report 2015/2, Link
- Mankowska, D. S., Bierwirth, C.: Vehicle Routing Problem with Synchronization at Variable Points, Technical Report 2015/1, Link
- Bierwirth, C., Mankowska, D. S., Meisel, F.: Tourenplanung in mobilen Pflegediensten, WK Logistik, Duisburg, 16.01.2015
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Vortrag mit dem Titel: Synchronization Requirements in Vehicle Routing Problems, Workshop "Optimierungsmethoden in der Logistik", Halle, 09.12.2014
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Vortrag mit dem Titel: Synchronization in Vehicle Routing Problems - An Overview, 20th Conference of the International Federation of Operational Research Societies (IFORS), Barcelona (Spanien), 17.07.2014
- Mankowska, D. S.: Vortrag mit dem Titel: Synchronization in Vehicle Routing Problems:The Health Care Routing and Scheduling Problem with Interdependent Services, eingeladener Vortrag, Forschungskolloquium des Instituts für Wirtschaftswissenschaft der TU Clausthal-Zellerfeld, 07.07.2014
- Mankowska, D. S.: Vortrag mit dem Titel: Modelle und Methoden zur Tourenplanung mit Fahrzeugsynchronisation, 16. Doktorandenworkshop DoWoNo, Clausthal-Zellerfeld, 22.05.2014
- Mankowska, D. S., Meisel, F.; Bierwirth, C.: The home health routing and scheudling problem with interdependent services, Health Care Management Science (2014) 17(1), 15-30, Link
- Mankowska, D. S.: Vortrag mit dem Titel: Synchronization in Vehicle Routing: Benders’ Decomposition for the Home Health Care Routing and Scheduling Problem, 4th International Conference on Dynamics in Logistics (LDIC 2014), Bremen, 11.02.2014
- Best Paper Award: Mankowska, D. S.: Synchronization in Vehicle Routing: Benders’ Decomposition for the Home Health Care Routing and Scheduling Problem, Lecture Notes in Logistics, im Druck
- Mankowska, D. S.; Meisel, F.; Bierwirth, C.: Vortrag mit dem Titel: A comparative study of computational solution methods for the Home Health CareRouting and Scheduling Problem with Interdependent Services, OR 2013 Conference - the International Conference on Operations Research, Rotterdam, 05.09.2013
- Mankowska, D. S.; Meisel, F.; Bierwirth, C.: Vortrag mit dem Titel: The Home Health Care Routing and Scheduling Problem with Interdependent Services, 26th European Conference on Operational Research EURO|INFORMS MMXIII, Rom, 3.07.2013
- Meisel, F.; Kopfer, H.: Synchronized routing of active and passive means of transport, OR Spectrum (2014) 36(2): 297-322, Link
- Mankowska, D. S., Meisel, F., Bierwirth, C.: A Vehicle Routing Problem with Synchronization Requirements, Research meeting on synchronization in transport, Universität Mainz, 15.11.2012
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Vortrag mit dem Titel: A Vehicle Routing Problem with Synchronzation Constraints for Multi-Services at Customters, International Annual Conference of the German OR Society, 06.09.2012, Hannover, Germany
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Vortrag mit dem Titel: A Vehicle Routing Problem with Cargo Transfer Options, LOGMS 2012 – The 2012 International Conference on Logistics and Maritime Systems, 22.08.2012, Bremen, Germany
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Vortrag mit dem Titel: Routing of Home Care Staff Members with Synchronization Requirements, Odysseus 2012: 5th International Workshop on Freight Transportation and Logistics
- Mankowska, D. S., Bierwirth, C., Meisel, F.: Routing of Home Care Staff Members with Synchronization Requirements, Odysseus 2012: 5th International Workshop on Freight Transportation and Logistics: Extended Abstracts, 271-274, Link
- Mankowska, D. S.: Synchronisationsanforderungen in der Tourenplanung , Vortrag auf dem 14. Nordost-Doktorandenworkshop, Lutherstadt Wittneberg, 10.05.2012
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: A Vehicle Routing Problem with Cargo Transfer Options, in: Günther, H.-O. et al. (Hrsg.): Proceedings of the 2012 International Conference on Logistics and Maritime Systems (LOGMS 2012), 2012, 417-427
- Bierwirth, C., Mankowska, D. S.: Tourenplanung in mobilen Servicenetzwerken, in: Siepermann, C., Eley, M. (Hrsg.): Logistik - Gestern, heute, morgen - Festschrift für Richard Vahrenkamp zur Vollendung des 65. Lebensjahres, Gito-Verlag, 2011, 93-106
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Tourenplanung mit Fahrzeugsynchronisationserfordernissen, Vortrag im Forschungskolloqium, Halle, 26.10.2011
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Spatial and temporal synchronization of mobile servers in service networks, in: Klatte, D. et al. (Hrsg.): Operations Reserach Proceedings 2011, Springer-Verlag, 2012, 263-268, Link
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Modelling the Synchronization of Transport Means in Logistics Service Operations, Vortrag auf der ICCL 2011 Tagung, Hamburg, 21.09.2011
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Spatial and temporal synchronization of mobile servers in service networks, Vortrag auf der GOR Jahrestagung, Zürich, 02.09.2011
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Modelling the Synchronization of Transport Means in Logistics Service Operations, in: Böse, J. W. et al. (Hrsg.): Computational Logistics, LNCS 6971, Springer-Verlag Berlin Heidelberg, 2011, 74-85, Link
- Mankowska, D. S.: Tourenplanung mit Fahrzeugsynchronisation. Vortrag auf dem 12. Nordost-Doktorandenworkshop, Cottbus, 22.04.2010
Link zur DFG-Seite
Projektmitarbeiter & Kontakt
- Dr. Dorota Mankowska (dorota.mankowska@wiwi.uni-halle.de)
- Prof. Dr. Frank Meisel (meisel@bwl.uni-kiel.de)
Technical Reports
Mankowska, D. S., Bierwirth, C: Vehicle Routing Problem with Synchronization at Variable Points, Technical Report 2015/1
Technical Report 2015_1.pdf
(549,9 KB) vom 05.05.2015
Mankowska, D. S., Bierwirth, C: Unfi ed model for Vehicle Routing Problem with Synchronization Requirements, Technical Report 2015/2
Technical Report 2015_2.pdf
(186,9 KB) vom 05.05.2015