Mixing
TSP approach for Round Trip
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I have a problem to solve.
Below is the problem statement.
I am currently at a location X.
I have to start from X, and travel to these cities-A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V and then return back to X.
In what sequence i should cover these cities so that my round-trip distance is minimized?
Data: n x n matrix containing the distance across individual cities, and also distance between X and cities.
I know this is a Traveling salesmen problem,which is NP hard
I am looking for the best approximation technique/algorithm to use to solve this.
I have tried TSP Nearest Neighbours approach( which i consider as basic) and Clarke-Wright algorithm (not benificial.)
I'm looking for any leads/papers/open source projects(preferrably in python).
Note: Maximum cities <=50.I'm also looking for the methods which can give near to optimal result in least possible time.
algorithm computer-science genetic-algorithm traveling-salesman
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
|
show 2 more comments
I have a problem to solve.
Below is the problem statement.
I am currently at a location X.
I have to start from X, and travel to these cities-A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V and then return back to X.
In what sequence i should cover these cities so that my round-trip distance is minimized?
Data: n x n matrix containing the distance across individual cities, and also distance between X and cities.
I know this is a Traveling salesmen problem,which is NP hard
I am looking for the best approximation technique/algorithm to use to solve this.
I have tried TSP Nearest Neighbours approach( which i consider as basic) and Clarke-Wright algorithm (not benificial.)
I'm looking for any leads/papers/open source projects(preferrably in python).
Note: Maximum cities <=50.I'm also looking for the methods which can give near to optimal result in least possible time.
algorithm computer-science genetic-algorithm traveling-salesman
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
1
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
You will have to define what best is.
– domen
Jan 3 at 14:28
|
show 2 more comments
I have a problem to solve.
Below is the problem statement.
I am currently at a location X.
I have to start from X, and travel to these cities-A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V and then return back to X.
In what sequence i should cover these cities so that my round-trip distance is minimized?
Data: n x n matrix containing the distance across individual cities, and also distance between X and cities.
I know this is a Traveling salesmen problem,which is NP hard
I am looking for the best approximation technique/algorithm to use to solve this.
I have tried TSP Nearest Neighbours approach( which i consider as basic) and Clarke-Wright algorithm (not benificial.)
I'm looking for any leads/papers/open source projects(preferrably in python).
Note: Maximum cities <=50.I'm also looking for the methods which can give near to optimal result in least possible time.
algorithm computer-science genetic-algorithm traveling-salesman
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
I have a problem to solve.
Below is the problem statement.
I am currently at a location X.
I have to start from X, and travel to these cities-A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V and then return back to X.
In what sequence i should cover these cities so that my round-trip distance is minimized?
Data: n x n matrix containing the distance across individual cities, and also distance between X and cities.
I know this is a Traveling salesmen problem,which is NP hard
I am looking for the best approximation technique/algorithm to use to solve this.
I have tried TSP Nearest Neighbours approach( which i consider as basic) and Clarke-Wright algorithm (not benificial.)
I'm looking for any leads/papers/open source projects(preferrably in python).
Note: Maximum cities <=50.I'm also looking for the methods which can give near to optimal result in least possible time.
algorithm computer-science genetic-algorithm traveling-salesman
algorithm computer-science genetic-algorithm traveling-salesman
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
edited Jan 3 at 13:46
Shubham
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
asked Jan 3 at 12:03
ShubhamShubham
1,88841852
1,88841852
1
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
You will have to define what best is.
– domen
Jan 3 at 14:28
|
show 2 more comments
1
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
You will have to define what best is.
– domen
Jan 3 at 14:28
1
1
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
You will have to define what best is.
– domen
Jan 3 at 14:28
You will have to define what best is.
– domen
Jan 3 at 14:28
|
show 2 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f54021932%2ftsp-approach-for-round-trip%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f54021932%2ftsp-approach-for-round-trip%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
Is that all the cities or can n be bigger?
– merlyn
Jan 3 at 12:49
@merlyn This is just for an example, maximum cities can be 50.
– Shubham
Jan 3 at 13:46
"I'm looking for any leads/papers/open source projects(preferrably in python)." asking for off-site resources is off-topic on StackOverflow. To discuss algorithms such as this (and if you can reword it to be on topic) you might be best posting on Computer Science but be sure to check what is considered on topic there too
– Scriptable
Jan 3 at 13:58
@Shubham 50 seems small enough that modern TSP solvers can simply find the optimal solution.
– merlyn
Jan 3 at 14:01
You will have to define what best is.
– domen
Jan 3 at 14:28