MATHEMATICAL PROGRAMMING ALGORITHMS FOR TRANSPORTATION PROBLEMS

The thesis deals with the study of transportation problems, and in particular focuses on developing new exact and heuristic algorithms for two interesting variants of the well known Vehicle Routing Problem: the multi-depot heterogeneous-fleet vehicle routing problem with time windows and the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows. The studied problems consider additional real-world requirements, often neglected in the literature. They lead to more involved problems but on the other hand more realistic ones, that call for powerful optimization methods in order to tackle such difficult applications. The proposed algorithms are based on mathematical programming techniques, such as branch-and-price, column generation and dynamic programming. The performance of the algorithms is analyzed with extensive computational experiments and compared with the most effective algorithms from the literature, showing the usefulness of the proposed methods.