LOCATION AND ROUTING PROBLEMS: A UNIFIED APPROACH

This thesis is about location and routing problems. We propose a unified algorithmic approach, based on the branch-and-cut-and-price paradigm, for the exact solution of general location and routing problems involving both costs and profits. In particular three different types of N P -hard problems are taken into account: the first is an extension, arising in the context of waste collection management, of the well studied Vehicle Routing Problem. The second is based on the Multi-Depot Vehicle Routing Problem with profits and has applications in the exploration of planetary surfaces. The last problem is about the distribution of drugs in emergency situations. For every problem a detailed description and a mathematical formulation are given. The largest part of the thesis is dedicated to the careful explanation of how our method can be efficiently implemented in every of the problems taken into account. In particular we propose new algorithmic ideas and several modifications and extensions to many procedures already presented in the literature. However, all components of our algorithms are fully presented and analyzed pointing out every methodological and practical issue. Extensive computational experiments and comparisons are carried out to evaluate the performance of our approach and the tractability of the problems addressed.