Vehicle routing problems with synchronization constraints
Final Report Abstract
This project explores a modern extension to the class of vehicle routing problems, namely VRPs with synchronization requirements. Synchronization, on the one hand side, may be indispensable to fulfill all service expectations of customers. On the other hand, synchronization opens up potentials for achieving solutions to a problem which are economically beneficial but unreachable without synchronization. Therefore, the number of scientific papers dealing with VRPs and synchronization has strongly increased in recent years. Our research is a part of this stream and contributes with the following findings: 1. A four-field classification scheme for time-space synchronization requirements is proposed. 2. Mixed Integer Linear Programming models are formulated for each of the four problem classes. 3. A unified generic optimization model is provided which captures the four specific models. 4. An efficient solution representation scheme, applicable to all problem classes, is designed. 5. New neighborhoods for local search, operating on the solution representation scheme, are systematically defined. 6. An exact solution method based on Benders’ decomposition is presented for VRPs with vehicle synchronization at fixed points (types I and II). 7. Powerful heuristics are available to solve problems of type I using an ALNS method, and problems of type I and II using an AVNS method. 8. For VRPs with vehicle synchronization at variable points (types III and IV) the proposed methods run into their boundaries. We have underestimated the drastic increase of complexity that comes along when switching from fixed point to variable point synchronization. In conclusion, this project systematizes the world of VRP with synchronization requirements and, thus, constitutes a fundamental contribution to recent research on VRPs. As a reference point, the project opens up a manifold of directions for future research like, for example, incorporating explicitly transport emissions in VRPs or finding new powerful exact solution methods, in particular for synchronization of vehicles at variable points.
Publications
- Modelling the Synchronization of Transport Means in Logistics Service Operations, in: Böse, J. W. et al. (Hrsg.): ICCL 2011, LNCS 6971, Springer Berlin Heidelberg, 2011, 74-85
Mankowska, D. S.; Bierwirth, C.; Meisel, F.
- Tourenplanung in mobilen Servicenetzwerken. In Siepermann, C. Eley, M. (Hrsg.): Logistik – Gestern, heute, morgen, Gito-Verlag Berlin 2011, 93-106
Bierwirth, C.; Mankowska, D. S.
- 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
Mankowska, D. S.; Bierwirth, C.; Meisel, F.
- Spatial and Temporal Synchronization of Vehicles in Logistics Networks, in: Klatte, D.; Lüthi, H.-J.; Schmedders, K. (Hrsg.): Operations Research Proceedings 2011, Springer, 2012, 263-268
Mankowska, D. S.; Bierwirth, C.; Meisel, F.
- Synchronized routing of active and passive means of transport, OR Spectrum (2014), 36(2):297-322
Meisel, F.; Kopfer, H.
(See online at https://doi.org/10.1007/s00291-012-0310-7) - The Home Health Care Routing and Scheduling Problem with Interdependent Services, Health Care Management Science (2014), 17(1):15-30
Mankowska, D. S.; Meisel, F.; Bierwirth, C.
(See online at https://doi.org/10.1007/s10729-013-9243-1) - Vehicle Routing with Synchronization Requirements. Dissertation thesis, Martin-Luther-University Halle-Wittenberg, 2014
Mankowska, D. S.
- Synchronization in Vehicle Routing: Benders’ Decomposition for the Home Health Care Routing and Scheduling Problem. In: Kotzab H., Pannek J., Thoben KD. (eds) Dynamics in Logistics. Part of the Lecture Notes in Logistics book series (LNLO), 2016, pp 159-169. Conference paper
Mankowska, D. S.
(See online at https://doi.org/10.1007/978-3-319-23512-7_16)
