Traveling Salesman (TSP) variation

475 views Asked by At

I'm faced with what is basically the Traveling Salesman Problem (TSP) but with an extra difficulty:

In my case the Salesman has a pool of x amount of addresses (where x varies). Each day, he has to select y amount of addresses to go to (where y varies and x >= y).

I can probably find a good TSP algorithm online. The only problem I have is to get the optimal combination of y amount of addresses out of the pool of x addresses. I know I can brute force all the possible combinations and then get the most optimal combination based on the result of the TSP algorithm on those combinations, but since the TSP algorithm will already require a lot of computing time I was hoping there would be a better way.

Basically, what I need is an algorithm that finds the smallest possible circle containing y amount of points out of a collection with x amount of addresses. Since I don't know the name of this problem/algorithm I couldn't figure out a good targeted search on google, because I'm pretty sure a similar algorithm must exist. Then the only thing that I still have to do is combine those algorithms :-)

[EDIT] Some additional information based on the comment by @hatchet: The salesman starts from home and ends there, so it's a closed circuit. On the second day, he starts from home again. Addresses he visited the day(s) before are removed from the pool. New addresses can be added and unvisited addresses might have been removed as well.

Some more clarification: In my use case the salesmen are actually inspectors that inspect contractors. They must visit each contractor 4 to 5 times a year. Since contractors don't have the same construction sites the entire year through, the addresses can change every day. I hope this makes sense, if not, I'll try to answer any additional questions as good as possible.

0

There are 0 answers