New and tractable formulations for the eco-driving and the eco-routing-and-driving problems

Eco-driving and eco-routing problems are both concerned with minimizing the fuel consumption of a single vehicle; the former does so by optimizing the vehicle's speed profile on a given road segment, and the latter selects the best path for a vehicle from a given origin to a given destination. This paper studies a problem that combines the two, namely an eco-routing-and-driving problem, in which the path and the speed profile on each link of the chosen path are optimized simultaneously. Using the comprehensive modal emissions model as the fuel consumption model, this paper describes new and tractable formulations for both the ecodriving and the eco-routing-and-driving problems through discretization, convexification and approximation, leading to a linear program for the former and a mixed-integer linear program for the latter. Computational results indicate that the new formulation of the eco-driving problem yields significant reductions in the solution time as compared to alternative formulations and algorithms, and that the new formulation of the eco-routing-and-driving problem affords further reductions in fuel consumption when compared with other methods.