Optimal (approximated) path Algorithm (distance + priority)

Question

I need to write an algorithm for the following scenario:

Given a set of points (cities) on a map I have to visit. Each of these cities has a priority, from 1 (you need to go there ASAP) to 5 (no rush, but go there eventually). I have limited ressources so I can not visit all the priority-1 cities at first. (E.g if NY and SF have priority 1 and Washington has Priority 5, I'm looking for a path NY-Washington-SF not NY-SF-Washington).

I don't know it it matters, but n (# of cities) will usually be around 10-20.

I found a presentation of "The Hierarchical Traveling Salesman Problem" (Panchamgam, Xiong, Golden and Wasi) which is kind of what I'm looking for but the corresponding article is not publicly accessible.

Can you recommend existing algorithms for such scenarios? Or point me in the right direction what to search for?

An approximation would be alright. My scenario is not as life-threatening as in the scenario described by Panchamgam et. al. It's important to avoid unnecessary detours caused by the priorities without ignoring them completely.

Answer 1

In standard TSP you want to minimize the total length of the route. In your case you want to basically optimize two metrics: the length of the route, and how early high priority cities appear on the route. You need to put these two metrics into a single metric, and how you do that might have an impact on the algorithm choice. For example, map the city priorities to penalties, e.g.

1  ->  16
2  ->  8
3  ->  4
4  ->  2
5  ->  1

Then use as the metric you want to minimize the total sum of (city_penalty * distance_to_city_from_start_on_route). This pushes the high priority cities to the beginning of the route in general but allows for out of priority order traversal if otherwise the route becomes too long. Obviously the penalty values should be experimentally tuned.

With this metric, you can then use e.g. standard stochastic search approach --- start with a route and then swap cities or edges on the route in order to decrease the metric (use simulated annealing or tabu search).

Answer 2

An upper bound of 20ish puts dynamic programming in play. There's an O(n^2 2^n)-time algorithm for plain old traveling salesman path that goes like this. For each end vertex (n) and subset of vertices containing that end vertex (2^(n - 1)), we're going to determine the cheapest tour that visits the entire subset. Iterate over the subsets so that each set comes after its proper subsets (e.g., represent the sets as bit vectors and count from 0 to 2^n - 1). For each end vertex v in a subset S, the cheapest tour of S is either just v (if S = {v}) or it consists of a cheapest tour of S - {v} (computed already) followed by v. Each vertex w in S - {v} is a possibility for the next to last vertex of the tour of S - {v}.

You haven't completely specified how the priorities interact with the goal of minimizing the distance. One could, for example, translate the priorities into deadlines (you must visit this vertex before traveling x distance). The dynamic program adapts easily for this setting: the only modification needed is to assign cost +infinity if the time to reach the specified end vertex is too great. There are a lot of other possibilities here; you can have an objective consisting of a sum over each individual vertex of some vertex-dependent function of the distance to reach that vertex.

From an engineering standpoint, the nice thing about implementing an exact algorithm is that it is much easier to test (just compare with brute force).