[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC
mani.iiit123 at gmail.com
Tue Aug 26 12:28:43 PDT 2014
On Tue, Aug 26, 2014 at 9:14 PM, Julien-Samuel Lacroix <
jlacroix at mapgears.com> wrote:
> 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,
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
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:
git clone https://github.com/pgrouting/pgrouting
git checkout gsoc-vrppdtw
mkdir build && cd build
cmake -DWITH_DD=ON ..
sudo make install
Create database and import data:
sudo su postgres
psql my_vrpdp_test -c "create extension postgis; create extension
psql my_vrpdp_test -f "path/to/pgrouting/src/vrppdtw
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
* Transport of medical samples from medical offices to laboratories
I hope this is a bit clear now. I'll waiting for some feedback :)
> 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:*
>> *How to test it:*
>> * Clone it from github
>> * Compile and build it
>> mkdir build && cd build
>> cmake -DWITH_DD=ON ..
>> 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
>> _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
>> Finally this is one of my best summers, thanks to my mentors & pgRouting
>> community. You're awesome :)
>> LSI, IIIT-H
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
> Julien-Samuel Lacroix
> T: +1 418-696-5056 #202
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Pgrouting-users