Formulations and heuristics for routing and scheduling problems

Vítor Alves Barbosa

Formulations and heuristics for routing and scheduling problems

In this work, we study two optimization problems related to routing and scheduling. The first problem introduces a generalization of the well-known pickup and delivery problem with time windows (PDPTW), which we refer to as the PDPTW and scheduling on the edges (PDPTW-SE). This problem involves determining routes for transportation requests, each with specific pickup and delivery locations, using a heterogeneous fleet of vehicles. Additionally, certain machines must be employed when traversing some edges, and the vehicle routing must also define the schedule for these machines. The goal is to minimize the completion time while ensuring that capacity, time windows, and precedence constraints are satisfied. We propose a compact mixed-integer program and a multistart heuristic with a linear program improvement procedure. We also propose a benchmark set composed of two families of instances, each representing different applications of the problem. The performed computational experiments show that the formulation could solve instances with up to twelve requests and find feasible solutions for 90.0% of the 320 considered instances. The second problem considers a single-machine coupled task scheduling problem to minimize the makespan. In this problem, a set of jobs has to be scheduled, each composed of two tasks interspersed by an exact delay. No preemption is allowed, and the goal consists of minimizing the completion time of the last scheduled task. We propose a constraint programming model and a biased random-key genetic algorithm (BRKGA). Preliminary results show that the constraint programming model can achieve high-quality solutions and strong dual bounds within the provided time limit. Moreover, it can find a solution that at least matches the best-known available in the literature for all the instances but one in our preliminary set. The obtained solutions are strictly better than the best-known ones for more than 70% of the tested instances. Additionally, the BRKGA can find solutions with reasonably low gaps within short computational times.

Rafael Augusto de Melo

Marcio Costa Santos

http://lattes.cnpq.br/4258661430014987

Celso da Cruz Carneiro Ribeiro

http://lattes.cnpq.br/3614186131432854

Tiago de Oliveira Januario

http://lattes.cnpq.br/7975984954243833

12 Aug, 2024

11:00 AM