Solving the probabilistic profitable tour problem on a line

DOI10.1007/S11590-022-01960-ZMaRDI QIDQ6081600zbMATH OpenOpenAlexFDO

Authors Enrico Angelelli, Renata Mansini, Romeo Rizzi

Publication date 26 October 2023

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.07378

zbMATH Keywords

polynomial time complexityprobabilistic profitable tour problemtraveling salesman problem with profits

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: 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 a revenue (prize) for visiting customers. In the Profitable Tour Problem (PTP), we seek for a tour visiting a subset of customers while maximizing net gain (profit) as difference between total revenue collected from visited customers and 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. Following recent emphasis on robust optimization, and motivated by current flourishing of retail delivery services, we study the Probabilistic Profitable Tour Problem (PPTP), the generalization of PTP where customers will show up with a known probability, in their respective loci,only after the tour has been planned. Here, the selection of customers has to be made a priori, before knowing if a customer will actually submit his request or will not. While the tour has to be designed without this knowledge, revenues will only be collected from customers who will require the service. The objective is to maximize the expected net gain obtained by visiting only the customers that show up. We provide 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.

Recommendations

• The multi-vehicle probabilistic covering tour problem
• Further results on the probabilistic traveling salesman problem
• scientific article; zbMATH DE number 1264413
• scientific article; zbMATH DE number 1818013
• Traveling salesman problems with profits and stochastic customers
• A Priori Optimization of the Probabilistic Traveling Salesman Problem
• Approximating the asymmetric profitable tour
• Approximating the asymmetric profitable tour
• On a linear-programming, combinatorial approach to the traveling-salesman problem

Cites work

• A branch-and-cut algorithm for the capacitated profitable tour problem
• Complexity and approximation for traveling salesman problems with profits
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• Orienteering problem: a survey of recent variants, solution approaches and applications
• The fractional prize-collecting Steiner tree problem on trees (extended abstract)
• The probabilistic orienteering problem

Cited in

(1)

• Splitting a giant tour using integer linear programming

This page was built for publication: Solving the probabilistic profitable tour problem on a line

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081600)