GSoc 2013 Project Information
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.
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.
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.
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-vrp
mkdir build
cd build
cmake -DWITH_DOC=NO ..
make && make install
cd ..
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
Three tables need to be passed as input parameter. They are vehicles table, orders table and distance table. More specification follows:
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.
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.
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.
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.
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.
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_vrpOneDepot(
'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.
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.
