New Insights on Prize Collecting Path Problems

  • Edcarllos Santos
  • Alfredo Candia-Véjar
  • Luiz Satoru Ochi
  • Luidi Simonetti
  • Uéverton S. Souza

Resumo


Given a graph G and a pair s,t in V(G), where each edge e has a weight t(e) and each vertex v has a value p(v) such that t(e) represent a transportation time and p(v) a prize collecting. Prize Collecting Path (PCP) consists of finding a (s,t)-path that minimizes the total transportation time minus the total prize of nodes in such path. PCP is at core of numerous relevant applications in several fields like telecommunications, transportation and logistics. In this paper, the complexity behavior of the problem is analyzed. For some cases we prove that PCP is NP-complete, these results lead to the generation of new sets of benchmark instances that are computationally hard according to natural characteristics of the problem. In addition, polynomial time algorithms are described for other cases and a mathematical formulation is introduced to solve general instances of PCP.

Publicado
06/07/2017
Como Citar

Selecione um Formato
SANTOS, Edcarllos; CANDIA-VÉJAR, Alfredo; OCHI, Luiz Satoru; SIMONETTI, Luidi; SOUZA, Uéverton S.. New Insights on Prize Collecting Path Problems. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3182.