A Polynomial-Time Algorithm for the Probabilistic Profitable Tour Problem on a Tree
研究了树上概率型盈利旅行问题，提出一个多项式时间算法，在O(n^2)内计算最优解，帮助在不确定需求下最大化期望利润。
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 [Formula: see text], where n is the number of nodes in the tree.