Branch-and-Price Algorithms for Vehicle Routing Problems
In this thesis we consider some routing problems and exact algorithms to solve them based on the branch-and-price framework. We consider three variants of the Vehicle Routing Problem (VRP): the Capacitated Vehicle Routing Problem (CVRP): is the basic and most studied version of VRP; the Vehicle Routing Problem with Distribution and Collection (VRPDC): is the variation of the CVRP arising when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehicles of limited capacity and where the customers can be visited in any order; the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW): is the variation of the capacitated VRP arising when customers must be served within a specifed period during the day. These Vehicle Rouring Problems are strongly NP-hard; thus we search for exact solutions in reasonable computing time. Since the computational effort required by branch-and-price based algorithms is affected mainly by the effcient solution of the so called pricing subproblem, we devote the main part of the thesis to enlarge the knowledge on pricing algorithms. In particular we present some new ideas to improve the known dynamic programming algorithms. We experimentally compare different strategies to solve the subproblem and their effect on the solution of the VRPs.