Approaches for Vehicle Routing Problems with Energy Considerations and Selective Backhauls

In the related PhD thesis, we focus on integer and linear programming approaches to problems in two groups of Vehicle Routing Problems (VRPs): one considering energy consumption and other that considers backhauls and uncertainty. Besides its relation to costs, minimizing energy consumption in vehicle routing potentially mitigate environmental impacts, as is the case of the Cumulative VRP (CmVRP), which minimizes a simplified measure of a load-dependent energy consumption. To the CmVRP, we propose a new formulation whose relaxation is stronger than the ones it is based on and employ a branch-cut-and-price (BCP) algorithm based on an existing formulation to present state-of-the-art results. We propose variants of the Capacitated VRP and CmVRP that consider energy limits per vehicle. To them, we devise BCP approaches where the pricing subproblems rely on discretized loads per arc and present extensive results. To the best of our knowledge, this is the first time a load-dependent energy consumption is limited by the means of the pricing. Finally, we tackle the VRP with Selective Backhauls, in which, after visiting customers, each vehicle may visit a single backhaul to collect an amount of an uncertain revenue. To this problem, a robust optimization model and a branch-and-cut algorithm are devised and experimented.