Scholarship 16/05036-1 - Meta-heurística, Otimização combinatória - BV FAPESP
Advanced search
Start date
Betweenand

A computational study for the Prize-Collecting dominating cycle problem

Grant number: 16/05036-1
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Start date until: September 01, 2016
End date until: February 28, 2017
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal Investigator:Fábio Luiz Usberti
Grantee:Luis Henrique Pauleti Mendes
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This research project proposes methodologies to solve the Prize Collecting Dominanting Cycle Problem (PCDCP). This problem is the composition of two NP-hard problems: the Dominating Set Problem and the Traveling Salesman Problem. Briefly, the aim of the PCDCP is to find a minimum cost cycle in an undirected graph. A traveler who needs to visit a set of customers (dominant vertices) traverses the cycle. The motivation of the PCDCP consists in its practical application to companies that deal with transportation, distribution and collection of products~ particularly, in the process of definition of the routes to carry out these services. In this research project, we will study methodologies to solve the PCDCP, considering the complexity of the exact solution of the PCDCP.

News published in Agência FAPESP Newsletter about the scholarship:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Please report errors in scientific publications list using this form.