Models and algorithms for routing and scheduling optimization problems

This thesis encompasses three distinct yet interrelated works, each contributing to the field of optimization. In the first work, an effective heuristic algorithm tackles the Capacitated Vehicle Routing Problem, particularly addressing large-scale instances. The algorithm employs a combination of local search and restricted Set Partitioning problem optimization, leveraging Helsgaun's LKH-3 algorithm for the local search phase. Notably, this approach consistently enhances solutions available on the CVRPLIB website. The second work delves into the extension of the FILO framework, initially designed for the Capacitated Vehicle Routing Problem. The objective is two-fold: to be competitive with state-of-the-art algorithms for simultaneous pickup and delivery problems, and to efficiently solve very large benchmark instances with numerous customers, all while maintaining linear scalability concerning problem size. A rigorous computational study validates the success in achieving both objectives. The third work centers on PLATiNO, a Synthetic Aperture Radar Earth observation satellite. Efficient activity planning is essential to maximize the satellite's potential while adhering to platform constraints. A genetic algorithm, combined with repair procedures and local search operators, addresses the intricacies of this planning. Additionally, Mixed Integer Linear Programming formulations are utilized to provide precise estimations of optimal solution values. Extensive testing on real-world benchmark instances demonstrates the algorithm's proficiency in computing near-optimal solutions within practical time limits.