[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC

Tue Aug 26 12:28:43 PDT 2014

Hello,

On Tue, Aug 26, 2014 at 9:14 PM, Julien-Samuel Lacroix <
jlacroix at mapgears.com> wrote:

> Hi,
>
> Congratulation!
>

Thank you

>
> I would be interested in learning more about this new feature. Can you
> give us details on the inputs?
>
> What is the schema of the customer table?
> What are the 2 other arguments in the function?
>
> Can you briefly describe a simple real life use case that is represented
> by your example?
>
> Thank you,
> Julien
>
>
   Let me first explain you  the input and output format. There is a
central depot with 'm' vehicles and there are 'n' customer nodes (n/2
pickup locations and n/2 delivery locations). So the problem is, a vehicle
will start from the central depot to a pickup location, pickup the things
and delivery it to the corresponding delivery location.

  The database contains details about depot and customer nodes. Each
customer has a few attributes
(See this:
https://github.com/pgRouting/pgrouting/blob/gsoc-vrppdtw/src/vrppdtw/test/pdp-any-00.data)

 The two other arguments in the function are number of vehicles and
capacity of each vehicle.

  If you want to know more about the problem (check it here:
https://github.com/pgRouting/pgrouting/wiki/VRP-Pickup-Delivery-Problem)

* Testing:*
   git clone https://github.com/pgrouting/pgrouting
   git checkout gsoc-vrppdtw
Compile it:
    mkdir build && cd build
    cmake -DWITH_DD=ON ..
    make
    sudo make install

Create database and import data:
    sudo su postgres
    createdb my_vrpdp_test
    psql my_vrpdp_test -c "create extension postgis; create extension
pgrouting;"
    psql my_vrpdp_test -f "path/to/pgrouting/src/vrppdtw
/test/pdp-any-00.data"

Function to retrieve output:
    psql my_vrpdp_test -c "select * from pgr_gsoc_vrppdtw('select * from
customer'::text, 25, 200)"

Output format is explained in the previous mail.
I can't directly take a real world example, but I'm sure there are some
real world practical applications
       * Transportation of raw materials from suppliers to factories.
       * Internet-based pickup from sellers and delivery to buyers
       * Pickup and delivery of charitable donations from homes to
different organizations
       * Transport of medical samples from medical offices to laboratories

I hope this is a bit clear now. I'll waiting for some feedback :)

Thanks,
Manikanta

> On 14-08-26 02:09 AM, Manikanta Kondeti wrote:
>
>> Hi all,
>>
>>     I am Manikanta, a GSoC student for pgRouting. I've implemented a
>> partially optimized VRP-Pickup and Delivery Problem with time windows.
>> This algorithm has many practical uses in the real world. There is a big
>> scope to extend this problem and implement further.
>>
>>     I thank my mentors Daniel and Steve for giving me this wonderful
>> opportunity and guiding me in the right way. Solving routing problems
>> became my passion and interest. Hence I'd love to contribute to
>> pgRouting in the future as well. This GSoC will be the first step. A lot
>> more to come.
>>
>> *Repo details:*
>> https://github.com/pgRouting/pgrouting/tree/gsoc-vrppdtw/src/vrppdtw/src
>>
>> *How to test it:*
>>    * Clone it from github
>>    * Compile and build it
>>           mkdir build && cd build
>> cmake -DWITH_DD=ON ..
>>           make
>>           sudo make install
>>     * Open psql command line  (sudo su postgres)
>>            \c pgr_test__db__test     (Select Database)
>>            select * from pgr_gsoc_vrppdtw('select * from
>> customer'::text, 25, 200);
>>
>> * Output:*
>> **Output has 4 columns(seq, rid, nid, cost)
>>
>>              seq:  starts from 0(first route first node) to (last route
>> last node)
>>                rid:  Shows the route id
>>                nid: Nodes in that particular route
>>              cost:  Cost calculated till that point
>>
>>      Example: /Sample output /
>>
>>                       0 |   1 |   0 |    0
>>                       1 |   1 |  79 |  668
>>                       2 |   1 |  80 |  859
>>                       3 |   1 |  49 | 1091
>>                       4 |   1 |  47 | 1183
>>                       5 |   1 |   0 | 1201
>>                       6 |   2 |   0 |    0
>>                       7 |   2 |  81 |   47
>>                       8 |   2 |  76 |  293
>>                       9 |   2 |  70 |  477
>>                      10 |   2 |  73 |  570
>>                      11 |   2 |   0 |  625
>>
>> /  Interpretation of this will be/:
>>       From seq 0 to 5 has details about first route and seq 6 to 11
>> about second route.
>> _Route 1_: Nodes->[0 79 80 49 47 0]  Cost -> [0  658 859  1091  1183
>> 1201]
>> _Route 2:_ Nodes->[0 81 76 70 73 0]  Cost -> [0 47 293 477 570 625]
>>
>>
>>         So final costs for route1 and route2 are 1201 and 625.
>>
>> I'm planning to write a blog which contains all of these details. I'll
>> do it in a few weeks. Before that if you find any difficulties or want
>> to give me suggestions, feel free to contact me. Hope everything goes
>> well.
>>
>> Finally this is one of my best summers, thanks to my mentors & pgRouting
>> community. You're awesome :)
>>
>> Thanks
>> Manikanta
>> LSI, IIIT-H
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>
> --
> Julien-Samuel Lacroix
> T: +1 418-696-5056 #202
> Mapgears
> http://www.mapgears.com/
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140827/6856c720/attachment.html>