An Efficient Timing Algorithm for Drivers with Rest Periods

We consider a timing problem arising from a vehicle routing context: it consists of optimally inserting rest periods of given duration into drivers’ schedules, when the sequence of customers to visit is given, time windows are associated with customers and an upper limit is imposed on the driving time with no rest periods. We illustrate some properties that allow reformulating the problem in simpler terms, and provide the basis to design a very efficient exact optimization algorithm whose worst-case time complexity is \(O(n \log {n})\) , where n is the number of customers to be visited.