Traveling Salesman with paths instead of points
$begingroup$
I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path.
For an open path, like a line or an arc, I would most often walk to one end of the path, walk the length of the path, then walk to another path.
For a closed path, like a circle or a square, I would most often walk to a point on the path near my previous stop, walk the perimeter of the path, then walk to another path.
I say "most often" above because it would also be valid to visit a path, not necessarily at an endpoint, walk along part of it, then leave to another path, later coming back to finish the abandoned walk.
The purpose of this problem is to minimize total travel distance for a laser cutter or CNC mill that needs to cut along all the paths.
Are there any existing algorithms (or open source tools) for solving this problem?
EDIT: Two paths never cross. Anywhere that might happen will have been altered from 4 vertices and 2 paths to 5 vertices and 4 paths by a previous step in my workflow.
graph-theory simulation hamiltonian-path eulerian-path
asked Mar 8 '17 at 19:41
SparrSparr
48129
$endgroup$
add a comment |
$begingroup$
I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path.
For an open path, like a line or an arc, I would most often walk to one end of the path, walk the length of the path, then walk to another path.
For a closed path, like a circle or a square, I would most often walk to a point on the path near my previous stop, walk the perimeter of the path, then walk to another path.
I say "most often" above because it would also be valid to visit a path, not necessarily at an endpoint, walk along part of it, then leave to another path, later coming back to finish the abandoned walk.
The purpose of this problem is to minimize total travel distance for a laser cutter or CNC mill that needs to cut along all the paths.
Are there any existing algorithms (or open source tools) for solving this problem?
EDIT: Two paths never cross. Anywhere that might happen will have been altered from 4 vertices and 2 paths to 5 vertices and 4 paths by a previous step in my workflow.
graph-theory simulation hamiltonian-path eulerian-path
asked Mar 8 '17 at 19:41
SparrSparr
48129
$endgroup$
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11
add a comment |
$begingroup$
I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path.
For an open path, like a line or an arc, I would most often walk to one end of the path, walk the length of the path, then walk to another path.
For a closed path, like a circle or a square, I would most often walk to a point on the path near my previous stop, walk the perimeter of the path, then walk to another path.
I say "most often" above because it would also be valid to visit a path, not necessarily at an endpoint, walk along part of it, then leave to another path, later coming back to finish the abandoned walk.
The purpose of this problem is to minimize total travel distance for a laser cutter or CNC mill that needs to cut along all the paths.
Are there any existing algorithms (or open source tools) for solving this problem?
EDIT: Two paths never cross. Anywhere that might happen will have been altered from 4 vertices and 2 paths to 5 vertices and 4 paths by a previous step in my workflow.
graph-theory simulation hamiltonian-path eulerian-path
asked Mar 8 '17 at 19:41
SparrSparr
48129
$endgroup$
I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path.
For an open path, like a line or an arc, I would most often walk to one end of the path, walk the length of the path, then walk to another path.
For a closed path, like a circle or a square, I would most often walk to a point on the path near my previous stop, walk the perimeter of the path, then walk to another path.
I say "most often" above because it would also be valid to visit a path, not necessarily at an endpoint, walk along part of it, then leave to another path, later coming back to finish the abandoned walk.
The purpose of this problem is to minimize total travel distance for a laser cutter or CNC mill that needs to cut along all the paths.
Are there any existing algorithms (or open source tools) for solving this problem?
EDIT: Two paths never cross. Anywhere that might happen will have been altered from 4 vertices and 2 paths to 5 vertices and 4 paths by a previous step in my workflow.
graph-theory simulation hamiltonian-path eulerian-path
graph-theory simulation hamiltonian-path eulerian-path
asked Mar 8 '17 at 19:41
SparrSparr
48129
asked Mar 8 '17 at 19:41
SparrSparr
48129
edited Mar 9 '17 at 23:58
Sparr
asked Mar 8 '17 at 19:41
SparrSparr
48129
asked Mar 8 '17 at 19:41
SparrSparr
48129
asked Mar 8 '17 at 19:41
SparrSparr
48129
48129
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11
add a comment |
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
$endgroup$
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
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%2f2178081%2ftraveling-salesman-with-paths-instead-of-points%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
$endgroup$
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
add a comment |
$begingroup$
As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
$endgroup$
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
add a comment |
$begingroup$
As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
$endgroup$
As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
answered Mar 9 '17 at 9:35
SmylicSmylic
4,53921225
4,53921225
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
add a comment |
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
1
1
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP.
$endgroup$
– Jules
Mar 9 '17 at 10:08
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process.
$endgroup$
– Sparr
Mar 9 '17 at 18:29
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
$begingroup$
All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP.
$endgroup$
– Smylic
Mar 9 '17 at 20:32
1
1
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
$begingroup$
Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer.
$endgroup$
– Smylic
Mar 9 '17 at 20:55
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%2f2178081%2ftraveling-salesman-with-paths-instead-of-points%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
$begingroup$
I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph.
$endgroup$
– Rahul
Mar 8 '17 at 21:46
$begingroup$
@Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions).
$endgroup$
– Sparr
Mar 8 '17 at 22:05
$begingroup$
I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem.
$endgroup$
– Rahul
Mar 9 '17 at 2:53
$begingroup$
You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :(
$endgroup$
– Sparr
Mar 9 '17 at 6:11