[pgrouting-dev] Question on current implementation of VRPPWT algorithm

Hello Miguel,

I'm putting this response on the pgRouting dev list so others can learn from it also.

On 7/11/2015 7:44 PM, Miguel Ángel Jiménez Achinte wrote:

Dear Mr. Woodbridge,

I am Miguel Jiménez, a master student at Icesi University (Colombia),
and I would be grateful if you could provide some information on the

I have been doing some research on implementations solving the Pick up
and Deliver problem; until now I found the DARP function in pgrouting
1.x and a gsoc implementation in the pgrouting 2 repository. However, I
had some problems compiling the first one, and I am getting a weird
connection lost error with the second one (sometimes when I try the

This code was developed by a Google Summer of Code student, so you testing and functionality might be very limited.

The lost connection issue is because the code is generating a segv error somewhere in the code. You should be able to debug this and get a stack trace.

start psql and connect to your database
select pg_backend_pid();
then in another window
sudo gdb --pid=<pid from query above>
Back in you psql window run your sql query
when it crash you will get a message in the gdb window
type bt<return> to get a back trace of the calling stack

then you can look through the called functions and see what variables look bad and maybe determine why. If you are not familiar with gdb find a tutorial and read through it.

I noted that some days ago you started to work in the gsoc branch of
pgrouting, I was wondering if you can give me some advice about the
error I am receiving. Is it because of the implementation? I know it is
an experimental branch, but I would like to be sure it is not my

Yes it was a first step toward moving the code into rev 2.1 or 3.0. I'm sure the code needs some review and fixes and more test cases. It would be great if you wanted to do some work on it and improve the code.

I am testing the test case in the project:

select * from pgr_gsoc_vrppdtw('select * from customer order by
id'::text, 25,200);

I have not looked at this code in a while so I'm afraid that I won't be much help at the moment.

I also noted that you are currently working in another implementation,
do you know if there is a plan by the pgrouting team to implement this
functionality? I look forward to hear good news on this topic, thanks in

Yes, a couple of us were working on a VRP problems in

We started working on a pickup and delivery problem solution but had to stop to complete the trash collection problem. I'm not sure if the pick-deliver code even works anymore because there have been a lot of changes in the baseClasses while we were working on the trash collection problem and we have not compiled and tested pick-deliver in a long time.

Regarding pgRouting functionality, we would like to have some basic VRP solvers available, but since we have to work to pay the bills and keep the lights on, it is hard to find time to work on these projects without some source of funding.

If you want to work on this as part of your University projects we would be happy to take a pull request and give what help we can.

Best regards,


*Miguel Ángel Jiménez Achinte
*Young Researcher, i2T/DRISO research team
+57 (2) 555 2334 ext. 8672
Universidad Icesi