Synchronization in Simultaneous Vehicle and Crew Routing and Scheduling Problems with Breaks

Abstract

In this thesis, we investigate a practical simultaneous vehicle and crew routing and scheduling problem arising in distribution transportation: goods need to be delivered from a central depot to customers using trailers and truck+driver combinations. Trailers may need to be reloaded by other personnel at the depot during the planning. Allowing drivers to switch trailers during reloading has great savings potential but difficult synchronization constraints arise. The problem becomes even more complex if social legislation on driving times for drivers is considered. We solve this problem by two-stage decomposition: first generation of trailer routes and then as- signment of route sections (trips) to truck+driver resource shifts, including a simplified driving rule for break planning in both stages. Different resource assignment solution methods able to handle synchronization constraints (temporal interdependencies) are investigated and compared, including construction heuristics and column generation methods with exact and heuristic pric- ing. The exact pricing problem is modelled as an ESPPRC with additionally linear node costs and it is solved exactly by a labelling algorithm. Mathematical properties can be used to sig- nificantly speed-up this exact pricing method. Further, different (predictive) break scheduling strategies during the trailer routing stage are investigated. Computational experiments on both modified benchmark instances (100–200 customers) and real-world data from a major Australian distributor show ~10–25% less truck+drivers are needed when switching trailers during reloading is allowed.