Sustainable Last-Mile Delivery: Exact Algorithms

This work addresses emerging challenges in urban freight logistics by extending classical vehicle routing problems to account for multi-trip operations, heterogeneous fleets, and access restrictions in city networks. First, we study the heterogeneous fleet multi-depot multi-trip vehicle routing problem with time windows under shared depot resources, proposing a branch-and-price algorithm with novel heuristics that efficiently solves medium-sized instances. Second, we investigate the vehicle routing problem with access restrictions, where limited-traffic zones impose temporal closures on streets, and develop branch-and-price algorithms based on road networks and multi-graphs to capture Pareto-optimal paths. Finally, we generalise this setting to multiple closure periods, introducing adapted algorithms that effectively manage the added complexity. Across all chapters, computational experiments demonstrate the efficiency of the proposed methods and highlight the importance of incorporating realistic urban constraints into routing models.