17
$\begingroup$

How to approach a travelling 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?

Thanks

$\endgroup$
17
$\begingroup$

Search for orienteering problem or prize-collecting TSP.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks this was helpful $\endgroup$ – user23369 Nov 14 '19 at 19:27
  • 1
    $\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$ – NotThatGuy Nov 17 '19 at 15:57
  • $\begingroup$ Agreed. I already upvoted Alberto’s answer. $\endgroup$ – RobPratt Nov 17 '19 at 15:59
11
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

You can adapt the algorithm of this paper TSPTW. It is almost the same problem. Check these other papers cited in that site:

enter image description here

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.