Vehicle Routing Problems with Synchronization Constraints (funded by Deutsche Forschungsgemeinschaft)
Synchronised route plan for the staff of a home health care company
Overview
Scope and Objectives
The topic of this project is Vehicle Routing Problem with Synchronization Constraints, which plays an important role for logistics service providers in service networks. The aim of this research is to provide a classification of the various types of spatial and temporal synchronization requirements for transport means in logistics applications. For supporting the planning of logistics service operations, the research aims for a new mixed-integer programming model for vehicle routing under synchronization constraints. A further issue of the research is to develop problem-specific solutions methods (e. g. cutting plane method) and heuristics for solving real-life problems.
Short Description
Research on vehicle routing problems in service networks is a very active field of research due to the variety of practical applications. An important extension to the class of vehicle routing problems is the coupling of routes of two or more vehicles, as is required by companies who offer mobile services with synchronized vehicle operations. So far, vehicle synchronization is hardly considered in the literature.
The vehicle routing problem with synchronization constraints is to find vehicle routes for serving a set of customers, where some customers must be served by more than one vehicle. For this purpose, the type of required service is specified for each customer, e. g. in terms of the skills of the operators or the number of operators needed to provide the service. For each customer there may also exist a time window, in which the service must take place. One of the objectives is to minimize the total distance traveled by all vehicles. We model a service network representing customer locations as nodes and servers as heterogeneous vehicles to differentiate between various skills of staff members. Different requirements regarding the synchronization of servers (vehicles) can be involved in such a problem. A temporal synchronization means that several vehicles have to visit the customer at a same time, or in a prescribed order of time. A spatial synchronization means that the point of service synchronization is either prescribed or a matter of planning.
Literature
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
Project duration
2009-2014
Publications and talks (project related)
- 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.: talk with the title: Synchronization Requirements in Vehicle Routing Problems, Workshop "Optimization methods in logistics", Halle, 09.12.2014
- Mankowska, D. S., Bierwirth, C., Meisel, F.: talk with the title: Synchronization in Vehicle Routing Problems - An Overview, 20th Conference of the International Federation of Operational Research Societies (IFORS), Barcelona (Spain), 17.07.2014
- Mankowska, D. S.: talk with the title: Synchronization in Vehicle Routing Problems:The Health Care Routing and Scheduling Problem with Interdependent Services, eingeladener Vortrag, Forschungskolloquium Institut für Wirtschaftswissenschaft der TU Clausthal-Zellerfeld, 07.07.2014
- Mankowska, D. S.: talk with the title: 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.: talk with the title: 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, in press
- Mankowska, D. S.; Meisel, F.; Bierwirth, C.: talk with the title: 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.: talk with the title: The Home Health Care Routing and Scheduling Problem with Interdependent Services, 26th European Conference on Operational Research EURO|INFORMS MMXIII, Rom 03.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.: talk with the title: 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.: talk with the title: 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.: talk with the title: 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.: Talk with the title: Synchronization Requirements in Vehicle Routing Problems, 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. (Eds.): 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.: Talk with the Title: Tourenplanung mit Fahrzeugsynchronisationserfordernissen, Research Colloqium, Halle, 26.10.2011
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Spatial and temporal synchronization of mobileservers in service networks, in: Klatte, D. et al. (Eds.): Operations Research 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, International Conference on Computational Logistics 2011, Hamburg, 21.09.2011
- Mankowska, D. S.; Bierwirth, C.; Meisel, F.: Talk with the title: Spatial and temporal synchronization of mobile servers in service networks, International Conference on Operational Research, Zurich, 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. (Eds.): Computational Logistics, LNCS 6971, Springer-Verlag Berlin Heidelberg, 2011, 74-85, Link
- Mankowska, D. S.: Talk with title: Tourenplanung mit Fahrzeugsynchronisation. 12. Mitteldeutscher Doktorandenworkshop, Cottbus, 22.04.2010, Germany
Link to DFG homepage
Contact
- 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