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 com- bining a number of features. Namely, we account for driver hours of ser- vice regulations, time-dependent travel times, time-dependent fuel con- sumption and refueling deviations. The latter stems from the fact that we consider non homogeneous fuel prices at refueling stations. Consider- ing a given origin and destination along with the mentioned features, we propose a mixed integer linear programming (MILP) model that deter- mines 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.