a variation of TSP : limit time, visit as many nodes as possible

Question

again let's use the salesman context:

if the salesman is not required to visit ALL customers, but is given a time constraint, in which he must vist as many customers as possible. how can we find the best route?

an even more slightly advanced version is, say each customer is marked with a monetary gain, so our salesman wants to maximize the total monetary gain from those customers that he actually visits, as long as he finishes visiting them within the time constraint

I tried to search for some research papers. but the closest I found is the work on k-TSP, in which the salesman is asked to maximize the total gain on a path less than k hops long. this is quite different since the edge time cost does not exist, or is just 1.

anybody knows of any existing research work on this problem?

thanks Yang

Answer 1

Look at jsprit. It lets you define:

• a traveling salesman with a time constraint, i.e. earliestStart and latestArrival at start/depot location,
• profits for each customer to visit and
• an objective function that considers these profits.

Thus jsprit determines the customers you need to visit to max. your profits considering transport costs and time constraints. All other customers end up in an unassigned job list. Note that jsprit uses an heuristic approach to solve such a problem.