Loek van Montfort: Vehicle routing problems with synchronization 22 May 2025 16:00 - 17:00

Vehicle routing problems with synchronization constraints are a highly relevant problem class in which routes of different vehicles depend on each other. Applications and solution methods for problems from this class in fields such as home-healthcare routing, urban freight transportation, or aircraft scheduling have been discussed and studied. Many articles focus on one or only a few types of synchronization requirements such as simultaneously visiting customers with more than one vehicle. In this work, we study a class of vehicle routing problems with synchronization constraints considering different types of temporal dependencies. Next to simultaneous visits, the latter include non-overlapping visits as well as minimum and maximum times between visits. One main assumption in the considered problem setting is that temporal dependencies need to be considered only for a subset of all visits. This holds true in many practical applications such as home-healthcare where the required care of a significant proportion of patients can usually be performed by one visit of a single caregiver or through multiple independent visits (within the planning horizon). Other patients may require multiple visits during the planning horizon for performing different temporal dependent tasks or (simultaneous) visits of multiple caregivers. For the latter type of patients, different temporal dependencies between these visits arise. We introduce a new integer programming formulation for this class of problems that is based on decomposing vehicles routes into sets of fragments. We also discuss a column generation based solution method and show its ability to handle a large variety of temporal synchronization constraints. In a computational study, we analyze the performance of our solution method for different problem settings and synchronization requirements.