[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC
Julien-Samuel Lacroix
jlacroix at mapgears.com
Tue Aug 26 17:56:38 PDT 2014
Thank you very much to both of you for the detailed explanation. I'm
looking forward to try this out.
Julien
On 14-08-26 04:18 PM, Stephen Woodbridge wrote:
> 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
>>
>
> _______________________________________________
> 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/
More information about the Pgrouting-users
mailing list