Mixing
Traveling salesman problem: why visit each city only once?
$begingroup$
According to wikipedia, the Traveling Salesman Problem (TSP) is:
Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city exactly once
and returns to the origin city?
Okay, that's a cool problem, but the part about "visiting each city exactly once" makes little sense to me. If I were a traveling salesman, I would just want to minimize the length (time, cost, whatever) of my route, and if visiting the same city $17$ times achieves this (say, because that city has an especially "central" position in the graph) then so be it. There seems to be little sense in restricting attention to Hamiltonian cycles (i.e. cycles in which each vertex occurs precisely once); in particular, I would imagine that this restriction simultaneously makes the problem harder (computationally) and also less applicable (e.g. to problems "from the real world.")
Wikipedia goes on to say that:
The problem was first formulated in 1930 and is one of the most
intensively studied problems in optimization.
In light of my previous comments, I find this surprising.
Question. Why has the TSP been so intensively studied, while the variant (which I find more natural) has apparently received much less
attention?
In simple terms: why visit each city only once?
Let me just add that according to wikipedia, the general problem does not include the assumption that the triangle inequality holds; that special case is called the metric TSP. In this case, the restriction to Hamiltonian cycles is of course innocuous.
graph-theory optimization math-history motivation
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
$endgroup$
add a comment |
$begingroup$
According to wikipedia, the Traveling Salesman Problem (TSP) is:
Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city exactly once
and returns to the origin city?
Okay, that's a cool problem, but the part about "visiting each city exactly once" makes little sense to me. If I were a traveling salesman, I would just want to minimize the length (time, cost, whatever) of my route, and if visiting the same city $17$ times achieves this (say, because that city has an especially "central" position in the graph) then so be it. There seems to be little sense in restricting attention to Hamiltonian cycles (i.e. cycles in which each vertex occurs precisely once); in particular, I would imagine that this restriction simultaneously makes the problem harder (computationally) and also less applicable (e.g. to problems "from the real world.")
Wikipedia goes on to say that:
The problem was first formulated in 1930 and is one of the most
intensively studied problems in optimization.
In light of my previous comments, I find this surprising.
Question. Why has the TSP been so intensively studied, while the variant (which I find more natural) has apparently received much less
attention?
In simple terms: why visit each city only once?
Let me just add that according to wikipedia, the general problem does not include the assumption that the triangle inequality holds; that special case is called the metric TSP. In this case, the restriction to Hamiltonian cycles is of course innocuous.
graph-theory optimization math-history motivation
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
$endgroup$
1
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
1
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29
add a comment |
$begingroup$
According to wikipedia, the Traveling Salesman Problem (TSP) is:
Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city exactly once
and returns to the origin city?
Okay, that's a cool problem, but the part about "visiting each city exactly once" makes little sense to me. If I were a traveling salesman, I would just want to minimize the length (time, cost, whatever) of my route, and if visiting the same city $17$ times achieves this (say, because that city has an especially "central" position in the graph) then so be it. There seems to be little sense in restricting attention to Hamiltonian cycles (i.e. cycles in which each vertex occurs precisely once); in particular, I would imagine that this restriction simultaneously makes the problem harder (computationally) and also less applicable (e.g. to problems "from the real world.")
Wikipedia goes on to say that:
The problem was first formulated in 1930 and is one of the most
intensively studied problems in optimization.
In light of my previous comments, I find this surprising.
Question. Why has the TSP been so intensively studied, while the variant (which I find more natural) has apparently received much less
attention?
In simple terms: why visit each city only once?
Let me just add that according to wikipedia, the general problem does not include the assumption that the triangle inequality holds; that special case is called the metric TSP. In this case, the restriction to Hamiltonian cycles is of course innocuous.
graph-theory optimization math-history motivation
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
$endgroup$
According to wikipedia, the Traveling Salesman Problem (TSP) is:
Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city exactly once
and returns to the origin city?
Okay, that's a cool problem, but the part about "visiting each city exactly once" makes little sense to me. If I were a traveling salesman, I would just want to minimize the length (time, cost, whatever) of my route, and if visiting the same city $17$ times achieves this (say, because that city has an especially "central" position in the graph) then so be it. There seems to be little sense in restricting attention to Hamiltonian cycles (i.e. cycles in which each vertex occurs precisely once); in particular, I would imagine that this restriction simultaneously makes the problem harder (computationally) and also less applicable (e.g. to problems "from the real world.")
Wikipedia goes on to say that:
The problem was first formulated in 1930 and is one of the most
intensively studied problems in optimization.
In light of my previous comments, I find this surprising.
Question. Why has the TSP been so intensively studied, while the variant (which I find more natural) has apparently received much less
attention?
In simple terms: why visit each city only once?
Let me just add that according to wikipedia, the general problem does not include the assumption that the triangle inequality holds; that special case is called the metric TSP. In this case, the restriction to Hamiltonian cycles is of course innocuous.
graph-theory optimization math-history motivation
graph-theory optimization math-history motivation
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
edited May 7 '15 at 6:21
goblin
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
asked May 6 '15 at 15:25
goblingoblin
36.9k1159193
36.9k1159193
1
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
1
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29
add a comment |
1
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
1
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29
1
1
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
1
1
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
$endgroup$
add a comment |
$begingroup$
I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.
In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1269983%2ftraveling-salesman-problem-why-visit-each-city-only-once%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
$endgroup$
add a comment |
$begingroup$
Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
$endgroup$
add a comment |
$begingroup$
Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
$endgroup$
Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
answered May 6 '15 at 15:31
Empy2Empy2
33.5k12261
33.5k12261
add a comment |
add a comment |
$begingroup$
I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.
In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
$endgroup$
add a comment |
$begingroup$
I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.
In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
$endgroup$
add a comment |
$begingroup$
I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.
In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
$endgroup$
I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.
In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
answered Jan 11 at 15:05
Özgen ErenÖzgen Eren
1234
1234
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1269983%2ftraveling-salesman-problem-why-visit-each-city-only-once%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Forget about the "exactly". One is given a symmetric $(ntimes n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds.
$endgroup$
– Christian Blatter
May 6 '15 at 15:44
1
$begingroup$
Angry husbands.
$endgroup$
– Will Jagy
May 6 '15 at 18:28
$begingroup$
The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies.
$endgroup$
– Rahul
May 7 '15 at 6:29