[pgrouting-dev] OR tools lib

[Stephen Woodbridge]

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.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
> 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