[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC
Manikanta Kondeti
mani.iiit123 at gmail.com
Tue Aug 26 12:55:23 PDT 2014
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>
wrote:
>
> 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/6d41a7f9/attachment-0001.html>
More information about the Pgrouting-users
mailing list