[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC
Stephen Woodbridge
woodbri at swoodbridge.com
Tue Aug 26 13:18:13 PDT 2014
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
>
More information about the Pgrouting-users
mailing list