[pgrouting-users] Introduction to VRP with time windows(Work done in Gsoc 2014)
Mukul priya
mukul2047 at gmail.com
Wed Aug 27 03:24:41 PDT 2014
Hi All,
I was a gsoc student this year for pgRouting. My job was initially to
refactor the current implementation of VRP but over the course of time the
goals were changed and finally the end result was a partially optimized VRP
with time windows .The optimization part is still in progress and i will
continue improving it .Thanks to my mentors Steve and Daniel for their
support and motivation.
Here is a how to use guide with some explaination as well : The
documentaion is same one as developed by Razequl last year with some minor
changes.
https://github.com/pgRouting/pgrouting/wiki/How-to-use-guide
*# Single Depot Vehicle Routing Problem with Time Windows*
Everything remains same as in VRP developed by Razequl last year , except
the procedure name which is cvrpOneDepot() for this version of VRP ,this
user guide was developed by Razequl ,since all the process is same i did
not find the need to develop a new one.
*## Overview*
The single depot vehicle routing problem with time windows solves the
scheduling problem related to delivering packages from a central depot to a
variety of customers while letting you prioritize delivery deliveries by
time windows. For example, you might have a delivery that must be made
between 8:00 and 10:00. You can have multiple delivery vehicles that have
varying capacity. And a list of orders that needs to be fulfilled. The
orders are assigned to vehicles and each vehicle gets an ordered list of
deliveries to make and returns to the depot.
*## How Does It Work?*
This is part of the pgRouting OpenSource project that extends PostgreSQL
database and add functionality related to solving graph problems,
specifically related to vehicle route planning. The user creates database
tables defining the vehicles and their capacity, the orders, their size,
delivery location and their delivery window. It also includes the depot
location and operating time window for the depot. Then using other
pgRouting tools a distance matrix needs to be generated between all the
orders and the depot then the problem can be solved using a TABU search
methodology.
*## Where can I get the code?*
In general you should be familiar with pgRouting v2.0.0 that can be found
at the following link. The VRP code is found in the source repository under
branch "gsoc-vrp". For a more accurate description of building and
installing pgRouting use the link below. We surfisically cover many of
these points here but only to the extent that they are specific to the VRP
code.
http://pgrouting.org/
Or you can get it out of git source repository and build and install it
with:
```
git clone https://github.com/pgRouting/pgrouting.git
cd pgrouting
git checkout gsoc-cvrptw
mkdir build
cd build
cmake -DWITH_DOC=NO ..
make && make install
cd ..
```
*### How do I install and create a database?*
The following commands will work from the command line or you can use
pgadmin3 and perform the equivalent operations.
createdb -U postgres -h localhost mytest_vrp
psql -U postgres -h localhost mytest_vrp
create extension postgis;
create extension pgrouting;
\q
You can test it with the following commands:
psql -U postgres -h localhost mytest_vrp
\i src/vrp_basic/test/VRP-any-00.data
\i src/vrp_basic/test/VRP-any-01.test
\q
*## How do I setup the tables?*
Three tables need to be passed as input parameter. They are vehicles table,
orders table and distance table. More specification follows:
*### Vehicle table:*
This is a relatively simple table consisting vehicle information. There
should be two columns. One is Vehicle_Id which is a unique id of a vehicle,
the other column is the capacity of that particular vehicle in number of
units. The total load of the vehicle cannot be over its specified capacity.
*### Orders table:*
This table contains the order information and also the information of the
single depot from where the vehicle will start and return to. This table
should contain 7 columns. They are:
- Id: A unique identifier of the order.
- x: The x or longitude of the order location.
- y: The y or latitude value of the order location.
- Order_unit: Number of unit the customer has ordered.
- Open_Time: Earliest time the customer is willing to receive the
order. The delivery to the cosutmer will start on or after this time even
if it is reached earlier. The time should be in minutes from a reference
time which is the open time of the depot. So, the open time of the depot
should be 0 and all the time should be given with respect to it. It is
user's responsibility to convert the time.
- Close_Time: Latest time teh customer is willing to receive the order.
The delivery must start on or before this time.
- Service_Time: Estimated time to serve the order. It may be
proportional to order_unit but the user should put this in. The vehicle
must stay this time in that particular order location.
*### Distance table:*
This table contains the point to point cost/ distance and traveltime
information. This table can be generated using the other functions
available in pgrouting. This table should have five columns.
- Src_Id: The id of the source.
- Dest_id: The id of the destination.
- Cost: The cost of traveling from the given source to the given
destination.
- Distance: The distance from the source to the destination.
- TravelTime: The time to travel from the source to destination.
Note that sometimes cost and distance or travel time may be the same value,
but still the user need to put all these three values.
*### How are the time windows defined?*
As mentioned earlier, the time windows are given with respect to the open
time of the depot. For example you can think of these times as minutes from
the depot open time. The open time of the depot should be considered 0.
There should also be a close time for the depot. All the vehicles are
expected to return depot by this time. The orders time window should be in
between. The user should convert the time to this format before passing it
to the solver for a real scenario. For example, if a depot opens at 8:00 am
and closes at 7:00 pm and a customer is willing to get delivery within
10:00 am and 10:40 am then the depot open time and close time will be 0 and
660 minutes respectively while the customer open and close time will be 120
and 160 minutes, respectively, from the depot open time of 0 minutes.
*### How can I compute the distance matrix?*
There are several options to compute the distance matrix. apsp_johnson or
apsp_warshall can be used. Please refer to pgrouting documentation for
further details on using these.
*## How do I solve the problem?*
Once the tables are set one can solve the problem by calling the pg
function *pgr_vrpOneDepot* with the following input parameters:
```
order_sql text,
vehicle_sql text,
cost_sql text,
depot_id integer,
```
Here order_sql is a text containing the sql for generating the order table.
vehicle_sql contains the sql for generating the vehicle table and cost_sql
contains the sql for generating the cost table. The fourth parameter
depot_id is an integer denoting which from the order table actually
represents the depot. If the tables are already in the database then simple
select over them will work. Here is a simple example of calling the
function:
```
select * from pgr_cvrpOneDepot(
'select * from vrp_orders'::text,
'select * from vrp_vehicles'::text,
'select * from vrp_distance'::text,
1 );
```
To use this one must first create tables vrp_orders, vrp_vehicles and
vrp_distance in the respective database. VRP-any-00.data under the test
directory contains sql to create such tables and sample data.
*## How do I interpret the problem results?*
The result table should have 5 columns. They are:
- Vehicle_Id: The id of the vehicle for the current route.
- Order_id: The id of order that is served.
- Order_pos: The serial of the order in the current route. For example
if order_pos is 3 that means this order is the 3rd order to be served by
this vehicle. The order_pos the depot will be either 0 or n + 1 depending
on whether the vehicle is leaving or arriving to the depot.
- Depart_time: When the vehicle is leaveing the customer. The time is
given in minute with reference to the open time of the depot.
- Arrival_Time: When the vehicle starts serving the customer. Note that
even if the vehicle reaches the customer before the open_time it can only
start serving at the open time for that customer.
Here is an example of a sample result:
```
Order_id| Order_pos| Vehicle_Id | Arrival_Time| Depart_Time
1 | 0 | 15 | -1 | 0
63 | 1 | 15 | 52 | 62
68 | 2 | 15 | 70 | 80
72 | 3 | 15 | 93 | 103
36 | 4 | 15 | 139 | 149
38 | 5 | 15 | 152 | 162
1 | 6 | 15 | 202 | -1
1 | 0 | 8 | -1 | 0
24 | 1 | 8 | 65 | 75
27 | 2 | 8 | 137 | 147
1 | 3 | 8 | 205 | -1
```
This means there are two routes. Vehicle with id 15 starts from depot at
time 0 starts service at order with id 63 at time 52, leaves from there at
time 62, starts service at order 68 at time 70, leaves from there at time
80 and so on and finally returns depot at time 202. The other vehicle also
leaves depot at time 0 serves order 24 and 27 and returns depot at time
205. For this example the depot close time was set to 240. For actual
driving direction information from this table may be used with pgrouting
functions for generating path and driving directions.
Thanks
Mukul Priya
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140827/d10de935/attachment.html>
More information about the Pgrouting-users
mailing list