Vehicle Routing Functions  Category (Experimental)¶
Warning
Possible server crash
These functions might create a server crash
Warning
Experimental functions
They are not officially of the current release.
They likely will not be officially be part of the next release:
The functions might not make use of ANYINTEGER and ANYNUMERICAL
Name might change.
Signature might change.
Functionality might change.
pgTap tests might be missing.
Might need c/c++ coding.
May lack documentation.
Documentation if any might need to be rewritten.
Documentation examples might need to be automatically generated.
Might need a lot of feedback from the comunity.
Might depend on a proposed function of pgRouting
Might depend on a deprecated function of pgRouting
Pickup and delivery problem
pgr_pickDeliver  Experimental  Pickup & Delivery using a Cost Matrix
pgr_pickDeliverEuclidean  Experimental  Pickup & Delivery with Euclidean distances
Distribution problem
pgr_vrpOneDepot  Experimental  From a single depot, distributes orders
Introduction¶
Vehicle Routing Problems VRP are NPhard optimization problem, it generalises the travelling salesman problem (TSP).
The objective of the VRP is to minimize the total route cost.
There are several variants of the VRP problem,
pgRouting does not try to implement all variants.
Characteristics¶
Capacitated Vehicle Routing Problem CVRP where The vehicles have limited carrying capacity of the goods.
Vehicle Routing Problem with Time Windows VRPTW where the locations have time windows within which the vehicle’s visits must be made.
Vehicle Routing Problem with Pickup and Delivery VRPPD where a number of goods need to be moved from certain pickup locations to other delivery locations.
Limitations
No multiple time windows for a location.
Less vehicle used is considered better.
Less total duration is better.
Less wait time is better.
Pick & Delivery¶
Problem: CVRPPDTW Capacitated Pick and Delivery Vehicle Routing problem with Time Windows
Times are relative to 0
The vehicles
have start and ending service duration times.
have opening and closing times for the start and ending locations.
have a capacity.
The orders
Have pick up and delivery locations.
Have opening and closing times for the pickup and delivery locations.
Have pickup and delivery duration service times.
have a demand request for moving goods from the pickup location to the delivery location.
Time based calculations:
Travel time between customers is \(distance / speed\)
Pickup and delivery order pair is done by the same vehicle.
A pickup is done before the delivery.
Parameters¶
Pick & deliver¶
Both implementations use the following same parameters:
Column 
Type 
Default 
Description 

orders_sql 

Pick & Deliver Orders SQL query containing the orders to be processed. 

vehicles_sql 

Pick & Deliver Vehicles SQL query containing the vehicles to be used. 

factor 

1 
(Optional) Travel time multiplier. See Factor Handling 
max_cycles 

10 
(Optional) Maximum number of cycles to perform on the optimization. 
initial_sol 

4 
(Optional) Initial solution to be used.

The non euclidean implementation, additionally has:
Column 
Type 
Description 

matrix_sql 

Pick & Deliver Matrix SQL query containing the distance or travel times. 
Inner Queries¶
return columns
Pick & Deliver Orders SQL¶
In general, the columns for the orders SQL is the same in both implementation of pick and delivery:
Column 
Type 
Default 
Description 

id 
ANYINTEGER 
Identifier of the pickdelivery order pair. 

demand 
ANYNUMERICAL 
Number of units in the order 

p_open 
ANYNUMERICAL 
The time, relative to 0, when the pickup location opens. 

p_close 
ANYNUMERICAL 
The time, relative to 0, when the pickup location closes. 

d_service 
ANYNUMERICAL 
0 
The duration of the loading at the pickup location. 
d_open 
ANYNUMERICAL 
The time, relative to 0, when the delivery location opens. 

d_close 
ANYNUMERICAL 
The time, relative to 0, when the delivery location closes. 

d_service 
ANYNUMERICAL 
0 
The duration of the loading at the delivery location. 
For the non euclidean implementation, the starting and ending identifiers are needed:
Column 
Type 
Description 

p_node_id 
ANYINTEGER 
The node identifier of the pickup, must match a node identifier in the matrix table. 
d_node_id 
ANYINTEGER 
The node identifier of the delivery, must match a node identifier in the matrix table. 
For the euclidean implementation, pick up and delivery \((x,y)\) locations are needed:
Column 
Type 
Description 

p_x 
ANYNUMERICAL 
\(x\) value of the pick up location 
p_y 
ANYNUMERICAL 
\(y\) value of the pick up location 
d_x 
ANYNUMERICAL 
\(x\) value of the delivery location 
d_y 
ANYNUMERICAL 
\(y\) value of the delivery location 
Pick & Deliver Vehicles SQL¶
In general, the columns for the vehicles_sql is the same in both implementation of pick and delivery:
Column 
Type 
Default 
Description 

id 
ANYINTEGER 
Identifier of the pickdelivery order pair. 

capacity 
ANYNUMERICAL 
Number of units in the order 

speed 
ANYNUMERICAL 
1 
Average speed of the vehicle. 
start_open 
ANYNUMERICAL 
The time, relative to 0, when the starting location opens. 

start_close 
ANYNUMERICAL 
The time, relative to 0, when the starting location closes. 

start_service 
ANYNUMERICAL 
0 
The duration of the loading at the starting location. 
end_open 
ANYNUMERICAL 
start_open 
The time, relative to 0, when the ending location opens. 
end_close 
ANYNUMERICAL 
start_close 
The time, relative to 0, when the ending location closes. 
end_service 
ANYNUMERICAL 
start_service 
The duration of the loading at the ending location. 
For the non euclidean implementation, the starting and ending identifiers are needed:
Column 
Type 
Default 
Description 

start_node_id 
ANYINTEGER 
The node identifier of the starting location, must match a node identifier in the matrix table. 

end_node_id 
ANYINTEGER 
start_node_id 
The node identifier of the ending location, must match a node identifier in the matrix table. 
For the euclidean implementation, starting and ending \((x,y)\) locations are needed:
Column 
Type 
Default 
Description 

start_x 
ANYNUMERICAL 
\(x\) value of the coordinate of the starting location. 

start_y 
ANYNUMERICAL 
\(y\) value of the coordinate of the starting location. 

end_x 
ANYNUMERICAL 
start_x 
\(x\) value of the coordinate of the ending location. 
end_y 
ANYNUMERICAL 
start_y 
\(y\) value of the coordinate of the ending location. 
Pick & Deliver Matrix SQL¶
Warning
TODO
Results¶
Description of the result (TODO Disussion: Euclidean & Matrix)¶
RETURNS SET OF
(seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
travel_time, arrival_time, wait_time, service_time, departure_time)
UNION
(summary row)
Column 
Type 
Description 

seq 
INTEGER 
Sequential value starting from 1. 
vehicle_seq 
INTEGER 
Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution. 
vehicle_id 
BIGINT 
Current vehicle identifier. 
stop_seq 
INTEGER 
Sequential value starting from 1 for the stops made by the current vehicle. The \(m_{th}\) stop of the current vehicle. 
stop_type 
INTEGER 
Kind of stop location the vehicle is at:

order_id 
BIGINT 
PickupDelivery order pair identifier.

cargo 
FLOAT 
Cargo units of the vehicle when leaving the stop. 
travel_time 
FLOAT 
Travel time from previous

arrival_time 
FLOAT 
Previous 
wait_time 
FLOAT 
Time spent waiting for current location to open. 
service_time 
FLOAT 
Service time at current location. 
departure_time 
FLOAT 
\(arrival\_time + wait\_time + service\_time\).

Summary Row
Warning
TODO: Review the summary
Column 
Type 
Description 

seq 
INTEGER 
Continues the Sequential value 
vehicle_seq 
INTEGER 

vehicle_id 
BIGINT 
Total Capacity Violations in the solution. 
stop_seq 
INTEGER 
Total Time Window Violations in the solution. 
stop_type 
INTEGER 

order_id 
BIGINT 

cargo 
FLOAT 

travel_time 
FLOAT 
total_travel_time The sum of all the travel_time 
arrival_time 
FLOAT 

wait_time 
FLOAT 
total_waiting_time The sum of all the wait_time 
service_time 
FLOAT 
total_service_time The sum of all the service_time 
departure_time 
FLOAT 
total_solution_time = \(total\_travel\_time + total\_wait\_time + total\_service\_time\). 
Description of the result (TODO Disussion: Euclidean & Matrix)¶
RETURNS SET OF
(seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
travel_time, arrival_time, wait_time, service_time, departure_time)
UNION
(summary row)
Column 
Type 
Description 

seq 
INTEGER 
Sequential value starting from 1. 
vehicle_seq 
INTEGER 
Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution. 
vehicle_id 
BIGINT 
Current vehicle identifier. 
stop_seq 
INTEGER 
Sequential value starting from 1 for the stops made by the current vehicle. The \(m_{th}\) stop of the current vehicle. 
stop_type 
INTEGER 
Kind of stop location the vehicle is at:

order_id 
BIGINT 
PickupDelivery order pair identifier.

cargo 
FLOAT 
Cargo units of the vehicle when leaving the stop. 
travel_time 
FLOAT 
Travel time from previous

arrival_time 
FLOAT 
Previous 
wait_time 
FLOAT 
Time spent waiting for current location to open. 
service_time 
FLOAT 
Service time at current location. 
departure_time 
FLOAT 
\(arrival\_time + wait\_time + service\_time\).

Summary Row
Warning
TODO: Review the summary
Column 
Type 
Description 

seq 
INTEGER 
Continues the Sequential value 
vehicle_seq 
INTEGER 

vehicle_id 
BIGINT 
Total Capacity Violations in the solution. 
stop_seq 
INTEGER 
Total Time Window Violations in the solution. 
stop_type 
INTEGER 

order_id 
BIGINT 

cargo 
FLOAT 

travel_time 
FLOAT 
total_travel_time The sum of all the travel_time 
arrival_time 
FLOAT 

wait_time 
FLOAT 
total_waiting_time The sum of all the wait_time 
service_time 
FLOAT 
total_service_time The sum of all the service_time 
departure_time 
FLOAT 
total_solution_time = \(total\_travel\_time + total\_wait\_time + total\_service\_time\). 
Where:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Handling Parameters¶
To define a problem, several considerations have to be done, to get consistent results. This section gives an insight of how parameters are to be considered.
Capacity and Demand Units Handling¶
The capacity of a vehicle, can be measured in:
Volume units like \(m^3\).
Area units like \(m^2\) (when no stacking is allowed).
Weight units like \(kg\).
Number of boxes that fit in the vehicle.
Number of seats in the vehicle
The demand request of the pickupdeliver orders must use the same units as the units used in the vehicle’s capacity.
To handle problems like: 10 (equal dimension) boxes of apples and 5 kg of feathers that are to be transported (not packed in boxes).
If the vehicle’s capacity is measured by boxes, a conversion of kg of feathers to equivalent number of boxes is needed. If the vehicle’s capacity is measured by kg, a conversion of box of apples to equivalent number of kg is needed.
Showing how the 2 possible conversions can be done
Let:  \(f_boxes\): number of boxes that would be used for 1 kg of feathers.  \(a_weight\): weight of 1 box of apples.
Capacity Units 
apples 
feathers 

boxes 
10 
\(5 * f\_boxes\) 
kg 
\(10 * a\_weight\) 
5 
Locations¶
When using the Euclidean signatures:
The vehicles have \((x, y)\) pairs for start and ending locations.
The orders Have \((x, y)\) pairs for pickup and delivery locations.
When using a matrix:
The vehicles have identifiers for the start and ending locations.
The orders have identifiers for the pickup and delivery locations.
All the identifiers are indices to the given matrix.
Time Handling¶
The times are relative to 0
Suppose that a vehicle’s driver starts the shift at 9:00 am and ends the shift at 4:30 pm and the service time duration is 10 minutes with 30 seconds.
All time units have to be converted
Meaning of 0 
time units 
9:00 am 
4:30 pm 
10 min 30 secs 

0:00 am 
hours 
9 
16.5 
\(10.5 / 60 = 0.175\) 
9:00 am 
hours 
0 
7.5 
\(10.5 / 60 = 0.175\) 
0:00 am 
minutes 
\(9*60 = 54\) 
\(16.5*60 = 990\) 
10.5 
9:00 am 
minutes 
0 
\(7.5*60 = 540\) 
10.5 
Factor Handling¶
Warning
TODO
See Also¶
The queries use the Sample Data network.
Indices and tables