Thanks for a great explanation.
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.
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@gmail.com <mailto:mani.iiit123@gmail.com>> wrote:
Hello,
On Tue, Aug 26, 2014 at 9:14 PM, Julien-Samuel Lacroix
<jlacroix@mapgears.com <mailto:jlacroix@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@lists.osgeo.__org
<mailto:Pgrouting-users@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@lists.osgeo.__org
<mailto:Pgrouting-users@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users