Truck driver scheduling with combined planning of rest periods, breaks and vehicle refueling

Fuel is one main cost driver in the road haulage sector. An analysis of diesel price variations across different European countries showed that a significant potential for cutting fuel expenditure can be found in international long-haul freight transportation. Here, truck drivers are often on the road for several consecutive days or even weeks. During their trips, they must comply with the rules on driving hours and rest periods which in the European Union are governed by Regulation (EC) No 561/2006. In the literature, refueling problems have attracted limited attention so far. In the present study, we show why a joint consideration of drivers’ rest periods and breaks and refueling is important and how the choice of time windows, the planning of driver activities, and the determination of refueling stops and quantities can be done accordingly. For a given sequence of customer locations and gas stations with different fuel prices along the route chosen to serve these customers we propose a mixed integer linear programming (MILP) model and describe the corresponding solution process. In this multicriteria optimization problem with the goals to minimize lateness, traveling time and fuel expenditures, we consider multiple soft time windows at customer locations. We extend the MILP model developed by Bernhardt et al. (2016) by integrating refueling decisions. Additionally, a preprocessing heuristic is described which reduces the number of gas stations to be considered along the route and thus the solution space and the computational effort. Numerical experiments were conducted for instances derived from real data that include vehicle routes for one week and information on gas stations along the vehicle routes. Different parameter settings for the preprocessing heuristic were analyzed.