Models and algorithms for routing and network optimization problems

This PhD thesis explores three major optimization challenges in modern transportation and communication systems. The first chapter addressed the Flying Sidekick Traveling Salesman Problem with Variable Drone Speeds (FSTSP-VDS), a novel variant of the TSP that models coordinated truck-drone delivery with dynamically adjustable drone speeds. This chapter proposes the first exact method for the FSTSP-VDS, assuming a convex drone energy-per-meter function, even if the drone power consumption is non-linear with respect to speed. Results indicate that adaptive speed control can reduce delivery completion times by more than 32%. A genetic algorithm is also proposed to handle larger instances, significantly outperforming existing heuristics. The second chapter addressed the Capacitated Vehicle Routing Problem (CVRP). This chapter investigates the independent optimization of different solution components while maintaining feasibility. It uncovers a counterintuitive structural property of the CVRP that allows for a novel sequence-based decomposition approach, offering new insights into parallel optimization for routing problems. The third chapter addressed the Routing and Wavelength Assignment (RWA) in Optical Networks under a shared protection policy to ensure communication survivability. Integer Linear Programming relaxations and an iterated local search metaheuristic are proposed. Computational experiments on realistic instances show that these algorithms achieve feasible solutions with tight optimality gaps, effectively balancing network efficiency and survivability.