Exact and heuristic approaches for the PDPTW-SE and the SMCTSP
Resumo
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.
Referências
Barbosa, V. A. (2025). Exact and heuristic approaches for the pickup and delivery problem with time windows and scheduling on the edges, and for the single-machine coupled task scheduling problem with exact delays. Dissertação de mestrado, Universidade Federal da Bahia, Salvador.
Barbosa, V. A., Melo, R., and Januario, T. (2024). Programação por restrições e algoritmo genético de chaves aleatórias enviesadas para o problema de escalonamento de tarefas acopladas em uma única máquina minimizando o makespan. In Proceedings of LVI Brazilian Symposium on Operations Research, volume Vol 56, 2024 – 309602 of SBPO 2024, Fortaleza, CE, Brazil. Galoá.
Barbosa, V. A. and Melo, R. A. (2025). Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan. DOI: 10.48550/arXiv.2512.23150.
Barbosa, V. A., Tiwari, S., and Melo, R. A. (2023). O problema de coleta e entrega com janelas de tempo e escalonamento nas arestas. In Proceedings of LV Brazilian Symposium on Operations Research, volume Vol 55, 2023 – 161147 of SBPO 2024, São José dos Campos, SP, Brazil. Galoá.
Barbosa, V. A., Tiwari, S., and Melo, R. A. (2026). The pickup and delivery problem with time windows and scheduling on the edges. European Journal of Operational Research. DOI: 10.1016/j.ejor.2026.01.036.
Bautista, M. G. A., Suganob, N. J., Concepcion, R., Bandala, A., and Dadios, E. (2023). Automated cooking systems: Benefits, challenges, and future directions. In 2023 IEEE 15th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment, and Management (HNICEM), pages 1–6, Coron, Palawan, Philippines. IEEE.
Condotta, A. and Shakhlevich, N. (2014). Scheduling patient appointments via multi-level template: A case study in chemotherapy. Operations Research for Health Care, 3(3):129–144.
Condotta, A. and Shakhlevich, N. V. (2012). Scheduling coupled-operation jobs with exact time-lags. Discrete Applied Mathematics, 160(16-17):2370–2388.
Dumas, Y., Desrosiers, J., and Soumis, F. (1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54(1):7–22.
Jiang, A. Z. and Zhou, M. (2022). Design of Affordable Self-learning Home Cooking Robots. In 2022 IEEE International Conference on Networking, Sensing and Control (ICNSC), pages 1–6, Shanghai, China. IEEE.
Khatami, M., Salehipour, A., and Cheng, T. (2019). Data for “Coupled task scheduling with exact delays: Literature review and models”. V1. 10.17632/dd7ht5k5pn.1.
Khatami, M., Salehipour, A., and Cheng, T. (2020). Coupled task scheduling with exact delays: Literature review and models. European Journal of Operational Research, 282(1):19–39.
Lenstra, J. K. and Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227.
Li, H. and Zhao, H. (2007). Scheduling coupled-tasks on a single machine. In 2007 IEEE Symposium on Computational Intelligence in Scheduling, pages 137–142. IEEE.
Lim, A. and Li, H. (2001). A Metaheuristic for the Pickup and Delivery Problem with Time Windows . In Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001, page 160, Los Alamitos, CA, USA. IEEE Computer Society.
Liu, Z., Lu, J., Liu, Z., Liao, G., Zhang, H. H., and Dong, J. (2019). Patient scheduling in hemodialysis service. Journal of Combinatorial Optimization, 37(1):337–362.
Mepani, M. M., Gala, K. B., Mishra, T. A., Suresh Bhole, K., Gholave, J., and Daingade, S. (2022). Design of robot arm for domestic culinary assistance. Materials Today: Proceedings, 68:1930–1945. 4th International Conference on Advances in Mechanical Engineering.
Orman, A. J. and Potts, C. N. (1997). On the complexity of coupled-task scheduling. Discrete Applied Mathematics, 72(1-2):141–154.
Pérez, E., Ntaimo, L., Wilhelm, W. E., Bailey, C., and McCormack, P. (2011). Patient and resource scheduling of multi-step medical procedures in nuclear medicine. IIE Transactions on Healthcare Systems Engineering, 1(3):168–184.
Shapiro, R. D. (1980). Scheduling coupled tasks. Naval Research Logistics Quarterly, 27(3):489–498.
Sharma, K. and Reddy, S. R. N. (2024). Design of smart automated cooker a survey and feasibility study. Multimedia Tools and Applications.
Sherali, H. D. and Smith, J. C. (2005). Interleaving two-phased jobs on a single machine. Discrete Optimization, 2(4):348–361.
SINTEF (2008). Instances and best solutions for the PDPTW. Online reference at [link], last access on August 09, 2024.
Yi, J.-s., Luong, T. A., Chae, H., Ahn, M. S., Noh, D., Tran, H. N., Doh, M., Auh, E., Pico, N., Yumbla, F., Hong, D., and Moon, H. (2022). An Online Task-Planning Framework Using Mixed Integer Programming for Multiple Cooking Tasks Using a Dual-Arm Robot. Applied Sciences, 12(8):4018.
