Solving the probabilistic profitable tour problem on a line

Among the most important variants of the traveling salesman problem (TSP) are those relaxing the constraint that every locus should necessarily get visited, rather taking into account the revenues (prizes) from the visits into the objective function. In the Profitable Tour Problem (PTP) we seek for a tour visiting a suitable subset of customers with the target to maximize the net gain (profit) defined as the difference between the total revenue collected from the visited customers and the incurred traveling costs. The metric TSP can be modeled as a PTP with large revenues. As such, PTP is well-known to be NP-hard and also APX-hardness follows. Nevertheless, PTP is solvable in polynomial time on particular graph structures like lines, trees and circles. In line with the recent emphasis on robust optimization, and motivated by the current flourishing of retailed delivery services, in this paper we initiate the study of the Probabilistic Profitable Tour Problem (PPTP), the probabilistic generalization of PTP in which the customers will show up with a known probability, in their respective loci, only after the tour has been designed and committed to. Here, the selection of the customers has to be made a priori, before knowing if a customer will actually submit his request or not. While the tour has to be designed and committed to without this knowledge, the revenues will be collected only from customers who will require the service. The objective is to maximize the expected net gain obtained visiting only the customers that show up. We offer a polynomial time algorithm computing and characterizing the space of optimal solutions for the special case of the PPTP where customers are distributed on a line.