Reducing the fuel cost of motor carriers by using optimal routing and refueling policies

Fuel optimizers are decision models (software products) that are increasingly recognized as effective fuel-management tools by US truckload carriers. Given the origin and the destination of a particular load, these software products seek both the route to use from origin to destination and the sequence of truck stops to use along the route so as to minimize the fuel cost of operating a vehicle. While useful, these products currently provide limited benefits to the users because they all use heuristic methods. Exact (optimal) methods are available in the academic literature, but they are not yet used in practice mainly because they lack empirical support. This article fills this gap in the literature by conducting an empirical analysis that contrasts the effectiveness of the conventional heuristic method and the emerging exact methods. Computational testing with real-world instances shows that the exact method attains noticeable cost savings over the heuristic method without significantly increasing the computational time.