Scheduling of driver activities with multiple soft time windows considering European regulations on rest periods and breaks

When considering long-haul transport requests, the durations of rest periods and breaks highly influence the overall time needed for fulfillment. In the European Union, Regulation (EC) No 561/2006 defines the rules for the number, duration and time intervals when rest periods and breaks have to be taken. The present study proposes two mixed integer linear programming models and optimization strategies that, together with a transformation algorithm, allow to plan driver activities in compliance with this regulation for a given sequence of customer locations and other stops to be visited. One of the models considers all rules, including extended rules, while the other takes into account the regular requirements. Each customer location has one or multiple time windows among which a choice has to be made. A special feature is the consideration of "soft" time windows which has not been studied in this context so far. If time windows cannot be met, the resulting schedule gives important information to the dispatcher that is necessary to set up a better schedule. In online re-planning, lateness can be revealed at an early stage such that it is possible to reorganize the schedule or to negotiate arrival times with customers before communication effort and costs increase and further delays or cancellations are unavoidable. In addition to the mathematical models, a myopic algorithm was developed that can only "see" the route until the next customer stop and the corresponding customer time window in advance and plans driver activities accordingly. Simple strategies were chosen to also integrate the optional rules. Test instances were derived from real data and include vehicle routes for one week. The numerical results obtained with the mathematical models and the myopic algorithm are analyzed and compared in terms of the run time, lateness and overall travel time.