Exploring heuristic pricing methods to accelerate branch-and-price for the EVRPTW

The growing interest in electric transport solutions, mainly due to technological advances and environmental benefits, introduces new challenges. These include the need to adapt traditional route planning tools to accommodate the unique characteristics of electric vehicles. In the problem studied here, a fleet of electric trucks is tasked with delivering service to various customers, each with specific time windows for delivery. This problem is known as the Electric Vehicle Routing Problem with Time Windows (EVRPTW) and can be solved to optimality using a branch-and-price algorithm. A key component of this method is column generation, which involves the iterative construction of efficient single-vehicle routes in a pricing problem known as the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). For column generation to converge, it is sufficient to find an improving, but not necessarily optimal, new route when solving the pricing problem. Therefore, in this thesis, we explore the possibility of improving the performance of the branch-and-price algorithm by solving the pricing problem heuristically. Primarily, we explore three different heuristics employed in previous research, where modifications of these methods are made to account for the specific structure of the problem studied. The performance of the heuristics is evaluated using benchmark instances for the EVRPTW. The results show that significant acceleration is achieved by solving the pricing problem heuristically and that combining the different heuristics generally yields additional performance gains.