Formulations and heuristics for routing and scheduling problems

Nome do aluno

 

Vítor Alves Barbosa

 

Título do trabalho

 

Formulations and heuristics for routing and scheduling problems

 

Resumo do trabalho

 

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.

 

Orientador

 

Rafael Augusto de Melo

 

Membro Titular 1

 

Marcio Costa Santos

 

Link para o curriculum lattes

 

http://lattes.cnpq.br/4258661430014987

 

Membro Titular 2

 

Celso da Cruz Carneiro Ribeiro

 

Link para o curriculum lattes

 

http://lattes.cnpq.br/3614186131432854

 

Suplente 1

 

Tiago de Oliveira Januario

 

Link para o curriculum lattes

 

http://lattes.cnpq.br/7975984954243833

 

Data do exame

 

12 Aug, 2024

 

Horário do exame

 

11:00 AM

 

 

Data da Defesa: 
12/08/2024 - 11:00
Tipo de Defesa: 
Qualificação de Mestrado