0
$\begingroup$

In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the salesman is flying between cities. If he's driving however, road networks tend not to be dense. You can drive from any city to any other city, but often you'll be hitting other cities on the way.

As an example, the picture below shows the graph of the road network for Ukraine. If you drive from Chernihiv (way North) to Odesa (way South), you will hit Kyiv and other cities on the way.

So, what if a salesman wants a driving tour that visits all cities in Ukraine? One thought is to construct the transitive closure of the road network graph and then apply standard traveling salesman algorithms to it.

But, this will include tours that are obviously sub-optimal because they'll (for example) go from Chernihiv to Odesa and then back to Kyiv, instead of simply stopping at Kyiv on the way.

Is there a way to take the structure of the graph into account while devising a tour that covers all cities? Of course, we can't guarantee that a Hamiltonian tour exists and we could be forced to visit some cities multiple times.

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Do you need to visit each city exactly once? $\endgroup$
    – Steven
    Nov 6, 2022 at 19:57
  • $\begingroup$ No. That might be impossible in general. $\endgroup$ Nov 6, 2022 at 20:07
  • 2
    $\begingroup$ If you don't need the graph to be metric then you can just set the weight of the missing edges to $+\infty$. $\endgroup$
    – Steven
    Nov 6, 2022 at 20:13
  • $\begingroup$ What is a metric graph? $\endgroup$ Nov 6, 2022 at 20:26
  • 1
    $\begingroup$ A graph in which edge weights satisfy the triangle inequality. For any triple of vertices $u,v,x$, $w(u,v) \le w(u,x) + w(x,v)$, where $w(a,b)$ denotes the weight of the (generic) edge $(a,b)$. $\endgroup$
    – Steven
    Nov 6, 2022 at 20:59

1 Answer 1

1
$\begingroup$

Let $G$ be your original graph and let $G'$ be its transitive closure.

Let $C'$ be an optimal tour in $G'$, and let $C$ be the tour in which you replace each edge $(u,v)$ of $C'$ with a shortest path between $u$ and $v$ in $G$. The tour $C$ is optimal in $G$ (even if it visits a city more than once).

To see this, let $w(C')$ (resp. $w(C)$) denote the cost of $C'$ (resp. $C'$). Let $w^*$ be the cost of an optimal tour of $G$. Clearly $w(C) \ge w^*$. Since all tour in $G$ are also tours in $G'$, we have $w(C') \le w^*$. Finally the cost of $C$ is at most the cost of $C'$ by construction. Therefore: $$ w^* \le w(C) = w(C') \le w^*. $$

$\endgroup$
7
  • $\begingroup$ $w(C')$ (resp. $w(C)$) what does this statement mean? $\endgroup$ Nov 6, 2022 at 20:25
  • $\begingroup$ resp. stands for respectively. It's just a compact way to define two quantities at once. I'm defining $w(C')$ as the cost of $C'$ and $w(C)$ as the cost of $C$. $\endgroup$
    – Steven
    Nov 6, 2022 at 20:54
  • $\begingroup$ Thanks. I've accepted the answer. But I was also looking for some algorithms that might be able to solve the modified problem efficiently. Would appreciate any pointers. $\endgroup$ Nov 6, 2022 at 21:54
  • $\begingroup$ The problem is NP-hard and is essentially equivalent to the classical TSP once you take the metric closure. See here for (exponential, approximation, or heuristic) algorithms. $\endgroup$
    – Steven
    Nov 6, 2022 at 21:58
  • $\begingroup$ Thanks, I get that it's NP-hard like the original problem. But there must be algorithms that are better at solving this version (ex: simulated annealing that doesn't consider paths that "hop" cities). $\endgroup$ Nov 6, 2022 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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