A computational study for the Prize-Collecting dominating cycle problem

• Grant number: 16/05036-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2016
• End date: 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.