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

• 成果类型: Article; Early Access
• 署名作者: Angelelli, Enrico; Mansini, Renata; Rizzi, Romeo
• 署名单位: University of Brescia; University of Brescia; University of Verona
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0306
• 发表日期: 2025
• 关键词: traveling salesman problems; submodular functions; delivery man; approximation; optimization; complexity

摘要

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(n2), where n is the number of nodes in the tree.