A computational study for the Prize-Collecting dominating cycle problem

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.