Warning
Possible server crash
Warning
Experimental functions
Contents
Previous versions of this page
Vehicle Routing Problems VRP are NPhard optimization problem, it generalises the travelling salesman problem (TSP).
pgRouting does not try to implement all variants.
Limitations
Problem: CVRPPDTW Capacitated Pick and Delivery Vehicle Routing problem with Time Windows
Both implementations use the following same parameters:
Column  Type  Default  Description 

orders_sql  TEXT 
Pick & Deliver Orders SQL query containing the orders to be processed.  
vehicles_sql  TEXT 
Pick & Deliver Vehicles SQL query containing the vehicles to be used.  
factor  NUMERIC 
1  (Optional) Travel time multiplier. See Factor Handling 
max_cycles  INTEGER 
10  (Optional) Maximum number of cycles to perform on the optimization. 
initial_sol  INTEGER 
4  (Optional) Initial solution to be used.

The non euclidean implementation, additionally has:
Column  Type  Description 

matrix_sql  TEXT 
Pick & Deliver Matrix SQL query containing the distance or travel times. 
return columns
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 
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. 
Warning
TODO
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 departure_time plus current travel_time . 
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  2 to indicate is a summary row 
vehicle_id  BIGINT  Total Capacity Violations in the solution. 
stop_seq  INTEGER  Total Time Window Violations in the solution. 
stop_type  INTEGER  1 
order_id  BIGINT  1 
cargo  FLOAT  1 
travel_time  FLOAT  total_travel_time The sum of all the travel_time 
arrival_time  FLOAT  1 
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\). 
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 departure_time plus current travel_time . 
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  2 to indicate is a summary row 
vehicle_id  BIGINT  Total Capacity Violations in the solution. 
stop_seq  INTEGER  Total Time Window Violations in the solution. 
stop_type  INTEGER  1 
order_id  BIGINT  1 
cargo  FLOAT  1 
travel_time  FLOAT  total_travel_time The sum of all the travel_time 
arrival_time  FLOAT  1 
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 
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.
The capacity of a vehicle, can be measured in:
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 
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 
Warning
TODO
Indices and tables