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

Abstract

In this work, two optimization problems related to routing and scheduling are studied. The first study addresses the pickup and delivery problem with time windows and scheduling on the edges (PDPTW-SE). The challenge lies in determining routes for a heterogeneous fleet of vehicles to transport requests with specific pickup and delivery locations, considering that some traversals require synchronized operations with a limited number of machines and their use must be properly scheduled. The objective is to minimize the total completion time while respecting capacity, time window, and precedence constraints. To this end, a mixed-integer programming (MIP) formulation with preprocessing and valid inequalities, along with a multistart heuristic with a linear programming-based improvement procedure are developed. A benchmark set of instances is also proposed, consisting of two families of instances representing different applications of the problem. In the computational experiments, the solver on the MIP formulation solves instances with up to twelve requests and finds feasible solutions for 95.0% of the smaller instances. The heuristic, in turn, obtains feasible solutions with low deviations compared to the solver on the MIP formulation for all smaller instances, in addition to be the only proposed approach to consistently find feasible solutions for the larger instances with 40 and 60 requests. The second study addresses the single-machine coupled-task scheduling problem (SMCTSP). This is a job scheduling problem in which each job consists of two coupled, non-preemptive tasks separated by an exact delay. The objective is to minimize the completion time of the last scheduled task. The problem was modeled using constraint programming (CP), and a biased random-key genetic algorithm (BRKGA) was developed, incorporating a warm-start solution generator, periodic restarts with varying intensities, and a local search algorithm. Computational experiments showed that the proposed BRKGA provides high-quality solutions with reduced computational times compared to the CP model. On the other hand, the CP model significantly outperformed the BRKGA solutions when run for one hour with multiple threads. Finally, the proposed approaches combined obtained new best solutions for 93.33% of the instances that had not yet been solved to optimality by previous approaches in the literature.