论文标题
解决树上的概率盈利旅行问题
Solving the Probabilistic Profitable Tour Problem on a Tree
论文作者
论文摘要
盈利的旅行问题（PTP）是一个众所周知的NP路由问题，寻找访问一部分客户的旅行，同时最大化利润，因为收入的总收入与旅行成本之间的差异。当考虑基础图的特殊结构时，已知PTP可以在多项式时间内解决。但是，在许多情况下，相应的概率概括的计算复杂性仍然是一个空旷的问题。在本文中，我们分析了客户位于树上的概率PTP，并具有已知概率，以预定级的奖品进行服务。问题的目标是先优先选择一部分客户来实施服务，以最大程度地提高预期利润。我们提供了一个多项式时间算法计算$ O（n^2）$中的最佳解决方案，其中$ n $是树中的节点数量。
The profitable tour problem (PTP) is a well-known NP-hard routing problem searching for a tour visiting a subset of customers while maximizing profit 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 to commit the service so 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.
