<div dir="ltr">I forgot to explain more important constraints i.e.. Time windows.<div><br></div><div><div> 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.</div>
<div> </div>
<div><br></div><div>* These are the following constraints: </div><div>* If a vehicle get there before the time window opens it has to wait</div><div>* All vehicles have to return to the depot by the depot close time</div>
<div>* Also obviously the same vehicle that makes a pickup also has to deliver that order</div><div>* 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<br>
</div><div> </div><div><br></div><div>So the input data has x,y location of the order, +-demand where + is pickup and - is delivery</div><div> and the the open and close times for the window. </div></div><div><br></div><div>
<br></div><div>
</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 27, 2014 at 12:58 AM, Manikanta Kondeti <span dir="ltr"><<a href="mailto:mani.iiit123@gmail.com" target="_blank">mani.iiit123@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra">Hello,</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Aug 26, 2014 at 9:14 PM, Julien-Samuel Lacroix <span dir="ltr"><<a href="mailto:jlacroix@mapgears.com" target="_blank">jlacroix@mapgears.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi,<br>
<br>
Congratulation!<br></blockquote><div><br></div><div><br></div><div>Thank you </div><div class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
I would be interested in learning more about this new feature. Can you give us details on the inputs?<br>
<br>
What is the schema of the customer table?<br>
What are the 2 other arguments in the function?<br>
<br>
Can you briefly describe a simple real life use case that is represented by your example?<br>
<br>
Thank you,<br>
Julien<div><br></div></blockquote><div><br></div></div><div> 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.</div>
<div><br></div><div> The database contains details about depot and customer nodes. Each customer has a few attributes </div><div>(See this: <a href="https://github.com/pgRouting/pgrouting/blob/gsoc-vrppdtw/src/vrppdtw/test/pdp-any-00.data" target="_blank">https://github.com/pgRouting/pgrouting/blob/gsoc-vrppdtw/src/vrppdtw/test/pdp-any-00.data</a>) </div>
<div><br></div><div> The two other arguments in the function are number of vehicles and capacity of each vehicle. </div><div><br></div><div> If you want to know more about the problem (check it here: <a href="https://github.com/pgRouting/pgrouting/wiki/VRP-Pickup-Delivery-Problem" target="_blank">https://github.com/pgRouting/pgrouting/wiki/VRP-Pickup-Delivery-Problem</a>)</div>
<div><br></div><div><br></div><div><b> Testing:</b></div><div><b> </b>git clone <a href="https://github.com/pgrouting/pgrouting" target="_blank">https://github.com/pgrouting/pgrouting</a></div><div> <span style="font-family:arial,sans-serif;font-size:13px">git checkout gsoc-vrppdtw</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">Compile it: </span></div><div class=""><div><span style="font-family:arial,sans-serif;font-size:13px"> </span><span style="font-family:arial,sans-serif"> mkdir build && cd build</span></div>
<div><span style="font-family:arial,sans-serif"> cmake -DWITH_DD=ON ..</span></div><div><span style="font-family:arial,sans-serif"> make </span></div><div><span style="font-family:arial,sans-serif"> sudo make install </span></div>
<div><span style="font-family:arial,sans-serif"><br></span></div></div><div><span style="font-family:arial,sans-serif;font-size:13px">Create database and import data:</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"> sudo su postgres </span></div>
<div class="">
<div><span style="font-family:arial,sans-serif;font-size:13px"> </span><span style="font-family:arial,sans-serif;font-size:13px">createdb my_vrpdp_test</span></div><span style="font-family:arial,sans-serif;font-size:13px"> psql my_vrpdp_test -c "create extension postgis; create extension pgrouting;"</span><br style="font-family:arial,sans-serif;font-size:13px">
<div><span style="font-size:13px;font-family:arial,sans-serif"> psql my_vrpdp_test -f "path/to/pgrouting/src/</span><u style="font-size:13px;font-family:arial,sans-serif"></u><span style="font-size:13px;font-family:arial,sans-serif">vrppdtw</span><span style="font-size:13px;font-family:arial,sans-serif">/test/pdp-any-00.data"</span><span style="font-family:arial,sans-serif;font-size:13px"> </span><br>
</div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div></div><div>Function to retrieve output:</div><div> <span style="font-family:arial,sans-serif;font-size:13px">psql my_vrpdp_test -c "select * from pgr_gsoc_vrppdtw('select * from customer'::text, 25, 200)"</span></div>
<div><br></div><div>Output format is explained in the previous mail. </div><div>I can't directly take a real world example, but I'm sure there are some real world practical applications</div><div> * Transportation of raw materials from suppliers to factories. </div>
<div> * Internet-based pickup from sellers and delivery to buyers</div><div> * Pickup and delivery of charitable donations from homes to different organizations</div><div> * Transport of medical samples from medical offices to laboratories </div>
<div> <br></div><div>I hope this is a bit clear now. I'll waiting for some feedback :) <br></div><div><br></div><div>Thanks,</div><div>Manikanta </div><div><div class="h5"><div><br></div><div><br></div><div><br></div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div>
<br>
On 14-08-26 02:09 AM, Manikanta Kondeti wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>
Hi all,<br>
<br>
I am Manikanta, a GSoC student for pgRouting. I've implemented a<br>
partially optimized VRP-Pickup and Delivery Problem with time windows.<br>
This algorithm has many practical uses in the real world. There is a big<br>
scope to extend this problem and implement further.<br>
<br>
I thank my mentors Daniel and Steve for giving me this wonderful<br>
opportunity and guiding me in the right way. Solving routing problems<br>
became my passion and interest. Hence I'd love to contribute to<br>
pgRouting in the future as well. This GSoC will be the first step. A lot<br>
more to come.<br>
<br></div><div>
*Repo details:*<br>
<a href="https://github.com/pgRouting/pgrouting/tree/gsoc-vrppdtw/src/vrppdtw/src" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/tree/gsoc-vrppdtw/<u></u>src/vrppdtw/src</a><br>
<br>
*How to test it:*<br></div><div>
* Clone it from github<br>
* Compile and build it<br>
mkdir build && cd build<br>
cmake -DWITH_DD=ON ..<br>
make<br>
sudo make install<br>
* Open psql command line (sudo su postgres)<br>
\c pgr_test__db__test (Select Database)<br>
select * from pgr_gsoc_vrppdtw('select * from<br>
customer'::text, 25, 200);<br>
<br></div>
* Output:*<br>
**Output has 4 columns(seq, rid, nid, cost)<div><br>
seq: starts from 0(first route first node) to (last route<br>
last node)<br>
rid: Shows the route id<br>
nid: Nodes in that particular route<br>
cost: Cost calculated till that point<br>
<br></div>
Example: /Sample output /<div><br>
0 | 1 | 0 | 0<br>
1 | 1 | 79 | 668<br>
2 | 1 | 80 | 859<br>
3 | 1 | 49 | 1091<br>
4 | 1 | 47 | 1183<br>
5 | 1 | 0 | 1201<br>
6 | 2 | 0 | 0<br>
7 | 2 | 81 | 47<br>
8 | 2 | 76 | 293<br>
9 | 2 | 70 | 477<br>
10 | 2 | 73 | 570<br>
11 | 2 | 0 | 625<br>
<br></div><div>
/ Interpretation of this will be/:<br></div><div>
From seq 0 to 5 has details about first route and seq 6 to 11<br>
about second route.<br></div>
_Route 1_: Nodes->[0 79 80 49 47 0] Cost -> [0 658 859 1091 1183 1201]<br>
_Route 2:_ Nodes->[0 81 76 70 73 0] Cost -> [0 47 293 477 570 625]<div><br>
<br>
So final costs for route1 and route2 are 1201 and 625.<br>
<br>
I'm planning to write a blog which contains all of these details. I'll<br>
do it in a few weeks. Before that if you find any difficulties or want<br>
to give me suggestions, feel free to contact me. Hope everything goes well.<br>
<br>
Finally this is one of my best summers, thanks to my mentors & pgRouting<br>
community. You're awesome :)<br>
<br>
Thanks<br>
Manikanta<br>
LSI, IIIT-H<br>
<br>
<br></div>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
<br><span><font color="#888888">
</font></span></blockquote><span><font color="#888888">
<br>
-- <br>
Julien-Samuel Lacroix<br>
T: +1 418-696-5056 #202<br>
Mapgears<br>
<a href="http://www.mapgears.com/" target="_blank">http://www.mapgears.com/</a><br>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
</font></span></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div>