TSP variation: time limit, visit as many nodes as possible
use seller context again:
if the seller is not obliged to visit ALL customers, but he is given a time limit in which he must display as many customers as possible. how can we find the best route?
an even more advanced version means that every customer is marked with a cash prize, so our seller wants to maximize the total cash benefit from those customers he actually visits, as long as he finishes visiting them for a limited time
I tried to find some research papers. but the closest I found work on k-TSP in which the seller is asked to maximize the overall gain on a path less than k hops long. this is completely different since the edge time value does not exist or is equal to 1.
Does anyone know of any existing research work on this issue?
thanks Jan
source to share
Take a look at jsprit . It allows you to determine:
- a traveling salesman with a limited duration, i.e. early start and lastArrival at the start / depot location,
- profit for each client to visit and
- an objective function that takes this profit into account.
This way jsprit determines the clients you need to visit up to max. your profit, taking into account transportation costs and time constraints. All other clients fall into the list of unwritten jobs. Please note that jsprit uses a heuristic approach to solve this kind of problem.
source to share