Efficient algorithms for driver scheduling with interdependent routes

Driver scheduling is an increasingly important task when solving vehicle routing problems. While vehicle routing is typically profit-oriented, incorporating driver scheduling introduces human factors which are crucial for practical operations. Efforts to efficiently tackle driver scheduling in the literature have historically focused on vehicle routing scenarios where driver routes are independent of one another. However, recent trends in logistics indicate a move towards services that induce temporal interdependencies between different vehicle routes. Real-world examples of such interdependencies include load transfers during middle- and last-mile transportation, the delivery and installation of equipment, and home health care services. All of these examples lead to  driver scheduling problems which are more complex than those featuring independent vehicle routes. This complexity is further aggravated by the fact that companies often desire a degree of schedule flexibility, which must be accommodated in combination with regulations concerning driving time.

This thesis addresses driver scheduling problems arising in contexts featuring interdependent vehicle routes, flexible departure times and a maximum route duration. While these characteristics are ubiquitous in transportation scenarios, we identify several avenues of research that deserve further attention. Our focus is on problem contexts involving the time-based optimization of driver schedules, scheduling breaks, and scheduling drivers when service locations have multiple time windows for their opening hours. We study these three problems and introduce mathematical models for each. Additionally, we draw connections between these problems and others in the operations research domain. These relations are then exploited to facilitate the design of special-purpose algorithms to solve the problems introduced in this thesis in an exact, yet incredibly efficient manner. Throughout our research, we pay close attention to not only developing algorithms that are theoretically fast with polynomial-time complexity guarantees, but also effectively implementing these algorithms to achieve the best empirical performance.

The results from this thesis confirm that solving driver scheduling in the practical context we encounter poses many computational challenges. However, we also demonstrate that it is possible to overcome these difficulties while ensuring (i) that drivers can be provided reasonable and feasible schedules even in the presence of intricate temporal interdependencies and local regulations or workload constraints, and (ii) that vehicle routing solvers incorporating driver scheduling aspects can still guarantee short computation times for practical use, even for large-scale instances. All of this in turn provides companies the instruments to incorporate driver scheduling into decision support systems for daily planning and ensure the creation of safe, healthy and balanced work schedules for their drivers.