The Long-Haul Transportation Problem with Refueling Deviations and Time-Dependent Travel Time

Basing on the operations of an Italian company, we model and solve a long-haul day-ahead transportation planning problem combining a number of features. Namely, we account for driver hours of service regulations, time-dependent travel times, time-dependent fuel consumption and refueling deviations. The latter stems from the fact that we consider non homogeneous fuel prices at refueling stations. Considering a given origin and destination along with the mentioned features, we propose a mixed integer linear programming (MILP) model that determines the minimum refueling cost route. These costs are established by modeling the time-dependent fuel consumption of the truck, accounting for different travel speeds due to recurrent traffic congestion. Given the challenge in solving the problem, we propose a heuristic algorithm to handle it efficiently. We test our model and algorithm on 42 realistic instances accounting for road network distances. Our result show that our heuristic produces high quality results within competitive run times.