Título: Shortest trails under visiting constraints

Data: 06/06/2018

Horário: 16:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Let D=(V,A) be a loopless directed graph with set of vertices V and set of arcs A, and let each arc (i,j) in A, with i,j in V, be associated with a non-negative cost. The constrained shortest path tour problem (CSPTP) is NP-Hard and consists in finding a shortest trail between two distinct vertices s in V and t in V that visits at least one element of vertex disjoint subsets T1,T2,...,TN, in this order. We formulate the CSPTP as a mixed-integer programming (MIP) model and present valid inequalities for the problem. We also design a heuristic encapsulated within a Lagrangian framework to obtain promising feasible solutions. Computational experiments performed on both randomly generated and benchmark data sets from the literature show that our MIP model consistently dominates existing CSPTP exact algorithms. It finds optimal solutions for most instances in considerably smaller execution time with respect to other approaches.

Banca:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC - Orientador)
• Profª. Drª. Ana Karolinna Maia de Oliveira (MDCC-UFC)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)