If I have a distance matrix which looks like
0 4 9999 1
4 0 2 3
9999 2 0 2
1 3 2 0
The idea being that the only cheap route from 3-4 is to 3-4 and then 4-3 to get back, but if naviating a path for the entire tsp, it never calls back on it self, so it would assume that the entire problem can be solved in 4 hops, when the best possible route will be in 5 hops.
Starting at 1
For example 1-> 2 2->3 3->4 4->3 3->1, total 11 Total 5 interconnecting nodes
1->4 4->3 3->1 total 9999+3+3 total 10005 Total 4 interconnecting nodes, but rather more expensive
Does anybody know of a tsp method that can resolve something like this and what its called? I am looking for a tsp that does not mind double back on itself.
Dave.
On 8/6/2013 5:17 PM, Dave Potts wrote:
If I have a distance matrix which looks like
0 4 9999 1
4 0 2 3
9999 2 0 2
1 3 2 0
The idea being that the only cheap route from 3-4 is to 3-4 and then
4-3 to get back, but if naviating a path for the entire tsp, it never
calls back on it self, so it would assume that the entire problem can be
solved in 4 hops, when the best possible route will be in 5 hops.
Starting at 1
For example 1-> 2 2->3 3->4 4->3 3->1, total 11 Total 5 interconnecting
nodes
1->4 4->3 3->1 total 9999+3+3 total 10005 Total 4
interconnecting nodes, but rather more expensive
Does anybody know of a tsp method that can resolve something like this
and what its called? I am looking for a tsp that does not mind double
back on itself.
This is called TSPM or TSP "Multiple Visits" if you google it. I have seen a reference to being able to convert this problem into a standard TSP problem similar to the ATSP to TSP solution.
-Steve
On 06/08/13 23:20, Stephen Woodbridge wrote:
On 8/6/2013 5:17 PM, Dave Potts wrote:
If I have a distance matrix which looks like
0 4 9999 1
4 0 2 3
9999 2 0 2
1 3 2 0
The idea being that the only cheap route from 3-4 is to 3-4 and then
4-3 to get back, but if naviating a path for the entire tsp, it never
calls back on it self, so it would assume that the entire problem can be
solved in 4 hops, when the best possible route will be in 5 hops.
Starting at 1
For example 1-> 2 2->3 3->4 4->3 3->1, total 11 Total 5 interconnecting
nodes
1->4 4->3 3->1 total 9999+3+3 total 10005 Total 4
interconnecting nodes, but rather more expensive
Does anybody know of a tsp method that can resolve something like this
and what its called? I am looking for a tsp that does not mind double
back on itself.
This is called TSPM or TSP "Multiple Visits" if you google it. I have seen a reference to being able to convert this problem into a standard TSP problem similar to the ATSP to TSP solution.
-Steve
Thanks Steve, if wonder if such a thing as Multiple Visits asymmetric travelling salesman problem solution exists
Dave.
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
On 8/6/2013 5:35 PM, Dave Potts wrote:
On 06/08/13 23:20, Stephen Woodbridge wrote:
On 8/6/2013 5:17 PM, Dave Potts wrote:
If I have a distance matrix which looks like
0 4 9999 1
4 0 2 3
9999 2 0 2
1 3 2 0
The idea being that the only cheap route from 3-4 is to 3-4 and then
4-3 to get back, but if naviating a path for the entire tsp, it never
calls back on it self, so it would assume that the entire problem can be
solved in 4 hops, when the best possible route will be in 5 hops.
Starting at 1
For example 1-> 2 2->3 3->4 4->3 3->1, total 11 Total 5 interconnecting
nodes
1->4 4->3 3->1 total 9999+3+3 total 10005 Total 4
interconnecting nodes, but rather more expensive
Does anybody know of a tsp method that can resolve something like this
and what its called? I am looking for a tsp that does not mind double
back on itself.
This is called TSPM or TSP "Multiple Visits" if you google it. I have
seen a reference to being able to convert this problem into a standard
TSP problem similar to the ATSP to TSP solution.
-Steve
Thanks Steve, if wonder if such a thing as Multiple Visits asymmetric
travelling salesman problem solution exists
I spent a couple of evenings googling for TSP papers of various flavors and have whole directory of pdf files on these.
google: TSPM "multiple visits"
Dave.
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev