A Polynomial-Time Algorithm for the Probabilistic Profitable Tour Problem on a Tree

The profitable tour problem (PTP) is a well-known NP-hard routing problem that searches for a tour visiting a subset of customers while maximizing profit measured as the difference between total revenue collected and traveling costs. PTP is known to be solvable in polynomial time when special structures of the underlying graph are considered. However, the computational complexity of the corresponding probabilistic generalizations is still an open issue in many cases. In this paper, we analyze the probabilistic PTP where customers are located on a tree and need, with a known probability, for a service provision at a predefined prize. The problem objective is to select a priori a subset of customers with whom the service has to be contractualized to maximize the expected profit. We provide a polynomial-time algorithm computing the optimal solution in O(n^2), where n is the number of nodes in the tree.