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

Julien-Samuel Lacroix jlacroix at mapgears.com
Tue Aug 26 17:56:38 PDT 2014

```Thank you very much to both of you for the detailed explanation. I'm
looking forward to try this out.

Julien

On 14-08-26 04:18 PM, Stephen Woodbridge wrote:
> Mani,
>
> Thanks for a great explanation.
>
> There are a lot of real life examples of this problem, like a bicycle or
> truck messenger service. They get an order to pickup a package at
> location X and deliver it to location Y. Time windows facilitate when
> people are available for the pickup and delivery times.
>
> Another common problem that uses is this model is a Dial-A-Ride where a
> person calls in and needs to schedule transport at a given time to
> arrive at some location at a given time. Think of a wheel chair
> transport service, or moving patients between medical facilities for
> tests or care.
>
> So the vehicle can be bicycle, car, truck, bus, ambulance, whatever. The
> current implementation tries to minimize the total number of vehicles
> needed and the total travel time/distance of the solution. We currently
> use simple Euclidean distances, but the problem could be modified to
> generate a distance matrix of travel times between nodes and then
> optimized on that.
>
> There are a lot of details about these problems and changes that can be
> made to tune the problem to any specific variation of the problem needed.
>
> Mani has done a great job pulling together this problem as code in
> pgrouting and we hope he will continue to work on this as time permits
> to build on and improve the solver.
>
> -Steve
>
> On 8/26/2014 3:55 PM, Manikanta Kondeti wrote:
>> I forgot to explain more important constraints i.e.. Time windows.
>>
>>   The time windows are units of time from open of the depot. So the
>> depot opens at time=0. Each customer has a few attributes related to
>> time. (Etime: Earliest time, Ltime: Latest time, Stime: Service time).
>> Analogy will be like this, a tourist want to visit a city, so the
>>   particular location like shopping mall will have open_time(Etime) ,
>> Close_time(Ltime) and Visit time(Stime). If a vehicle arrives before
>> Etime then it has to wait, and if it arrives after Ltime, then it is not
>> a feasible solution. We need to add service time whenever a vehicle
>> arrives and does either pickup or delivery.
>>
>> * These are the following constraints:
>> * If a vehicle get there before the time window opens it has to wait
>> * All vehicles have to return to the depot by the depot close time
>> * Also obviously the same vehicle that makes a pickup also has to
>> deliver that order
>> * All trucks have the same capacity as passed to the function and a
>> truck can not exceed that capacity during it trip, if it is full, then
>> it has to make deliveries to free up space before it can make another
>> pickup
>>
>> So the input data has x,y location of the order, +-demand where + is
>> pickup and - is delivery
>>   and the the open and close times for the window.
>>
>>
>>
>>
>> On Wed, Aug 27, 2014 at 12:58 AM, Manikanta Kondeti
>> <mani.iiit123 at gmail.com <mailto:mani.iiit123 at gmail.com>> wrote:
>>
>>
>>     Hello,
>>
>>
>>     On Tue, Aug 26, 2014 at 9:14 PM, Julien-Samuel Lacroix
>>     <jlacroix at mapgears.com <mailto: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
>>
>>
>> <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
>>             <mailto:Pgrouting-users at lists.osgeo.org>
>>             http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>>             <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
>>         <mailto:Pgrouting-users at lists.osgeo.org>
>>         http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>>         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
> _______________________________________________
> 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/
```