Exact and heuristic approaches for the PDPTW-SE and the SMCTSP
This thesis studies exact and heuristic optimization methods for highly constrained routing and scheduling problems. We focus on problems where operational decisions tightly couple routing and temporal coordination, making them particularly challenging from a combinatorial optimization perspective. The first contribution introduces the pickup and delivery problem with time windows and scheduling on the edges (PDPTW-SE), a new problem that integrates vehicle routing and machine scheduling decisions in scenarios where vehicles require scheduled machine assistance to overcome inter-region obstacles, such as the straits between islands or the vertical separation in multi-floor buildings. We propose an arc-based mixed-integer programming (MIP) strengthened by preprocessing and valid inequalities, together with a multi-start heuristic with an LP-based improvement procedure (MSLP). We also introduce a benchmark set representing different application scenarios. Computational experiments show that the strengthened MIP significantly improves solution quality, while the heuristic scales to larger tested instances for which the exact approach did not find feasible solutions within the time limit. The second contribution addresses the single-machine coupled-task scheduling problem (SMCTSP) to minimize the makespan. We propose a constraint programming (CP) model and a biased random-key genetic algorithm (BRKGA) enhanced with restarts, perturbation strategies, and local search. Experiments on benchmark instances demonstrate state-of-the-art performance: the CP model obtained the best-known solutions for 163 out of the 180 hardest instances, while the BRKGA achieved superior solution quality under short time limits. The results of this research have already led to publications in the Brazilian Symposium of Operational Research (SBPO) and the European Journal of Operational Research (EJOR), reinforcing the scientific relevance of the thesis.