How to approach a traveling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given time window) ? The demand for the product being sold varies by the town. Is there any published literature I can refer to approach this variant of the TSP?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Search for orienteering problem or prize-collecting TSP.
-
2$\begingroup$ This answer could be improved significantly by explaining the differences between these two, adding a few links and approaches to solving it or any other relevant context, much like Alberto's answer has done. $\endgroup$ Commented Nov 17, 2019 at 15:57
-
$\begingroup$ Agreed. I already upvoted Alberto’s answer. $\endgroup$– RobPrattCommented Nov 17, 2019 at 15:59
$\begingroup$
$\endgroup$
There are a few problems in this category. They are variants of the Travelling Salesman Problem in which you don't need to visit all customers, but can choose which ones to visit. They fall under the general name of Travelling Salesman Problems with Profits.
The main variants are:
- The Orienteering Problem (OP) in which you want to maximise the profit collected at visited customers, under an upper bound on the trip length.
- The Prize-collecting TSP in which you want to minimise the trip length, under a lower bound on the amount of profit collected.
- The Profitable Tour Problem in which instead of considering travel time, you consider travel costs. In this case you can express profits collected and travel costs with the same unit of measure (say, €). The objective is to maximise the revenue (= profit collected, minus travel costs).
Most of these problems also appear in the literature with variants (multi-vehicle, time windows, etc.) which are common for other "classic" routing problems. For example, the multi-vehicle OP is called the Team Orienteering Problem (TOP). Adding time windows gives the OPTW and TOPTW. Adding vehicle capacities gives the Capacitated TOP. Some stochastic versions include the TSP with Profits and Stochastic Customers, the OP with stochastic travel times and the OP with stochastic profits.
As per the solution methods for the Orienteering Problem (which seems the one most suited for your question), as far as I know the state-of-the-art exact algorithm is still the one by Fischetti, Salazar-Gonzalez, and Toth. In the last couple of years, new heuristics have improved on previously best-known results: a genetic algorithm and an ALNS.
