Razequl, Daniel, Dave P,
I found this site which looks like it might be interesting for future integration into pgRouting.
http://or-tools.googlecode.com/svn/trunk/
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/index.html
Specifically it has some implementations of VRP and TSP variables and other algorithms related to Operation Research problems. And It is available under an Apache License which is fairly liberal.
-Steve
On 26/07/13 02:30, Stephen Woodbridge wrote:
Razequl, Daniel, Dave P,
I found this site which looks like it might be interesting for future integration into pgRouting.
http://or-tools.googlecode.com/svn/trunk/
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/index.htmlSpecifically it has some implementations of VRP and TSP variables and other algorithms related to Operation Research problems. And It is available under an Apache License which is fairly liberal.
-Steve
Hmm
What are you suggesting, a quick port in to pgroute?
I am need an ATRP solution, while I have been playing a around with the current TSP implementation, I noticed it has several flaws, some of which I have hacks for.
1. All nodes must be in numerical order with no gaps ie 1,2,3,4 not 1,2,4,5.
2. There is no way of saying that there is no journey between node 2 and 5
3. The error check is limited, if I my mistake include a value of 0 for a journey of 2 to 5 instead of 2 2 its not picked up
Dave.
On 7/26/2013 12:11 AM, Dave Potts wrote:
On 26/07/13 02:30, Stephen Woodbridge wrote:
Razequl, Daniel, Dave P,
I found this site which looks like it might be interesting for future
integration into pgRouting.http://or-tools.googlecode.com/svn/trunk/
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/index.htmlSpecifically it has some implementations of VRP and TSP variables and
other algorithms related to Operation Research problems. And It is
available under an Apache License which is fairly liberal.-Steve
Hmm
What are you suggesting, a quick port in to pgroute?
That is one possibility, We seem to be moving into the realm of OR with TSP, ATSP, VRP and things that might be follow-ons the that.
I am need an ATRP solution, while I have been playing a around with the
current TSP implementation, I noticed it has several flaws, some of
which I have hacks for.1. All nodes must be in numerical order with no gaps ie 1,2,3,4 not
1,2,4,5.
Right, I use wrapper code to handle this.
2. There is no way of saying that there is no journey between node 2 and 5
Right, because in the symmetric case that this code supports you just remove the row, so it is not a problem. BTW, now that you fixed the integer vs float issue in the code, you might want to try setting the cost to a high number for this case and see if it will work now. It might still fail in the Hamiltonian Path code though.
3. The error check is limited, if I my mistake include a value of 0 for
a journey of 2 to 5 instead of 2 2 its not picked up
Have a zero cost between nodes is not a problem, but you are correct that we do not do a lot of checking in this code.
If you have code checked into your git fork I would be happy to look at it and potentially pull stuff some of the changes.
Thanks,
-Steve