Vehicle Routing Problem with Synchronization Constraints (This research is funded by Deutsche Forschungsgemeinschaft)
Synchronization of two vehicles at three synchronization points
Overwiev
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
Research Time
2009-2013
Contact
The research project is conducted by Dipl. -Math. Dorota Mankowska (dorota.mankowska@wiwi.uni-halle.de)
Publications and talks (project related)
- 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.: 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, accepted for publication in Operations Research Proceedings 2011
- 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