pgr_pickDeliverEuclidean
 Pickup and delivery Vehicle Routing Problem
Warning
Possible server crash
Warning
Experimental functions
Availability
pgr_gsoc_vrppdtw
Support
Problem: Distribute and optimize the pickupdelivery pairs into a fleet of vehicles.
pgr_pickDeliverEuclidean(orders_sql, vehicles_sql [,factor, max_cycles, initial_sol])
RETURNS SET OF (seq, vehicle_seq, vehicle_id, stop_seq, stop_type, order_id,
cargo, travel_time, arrival_time, wait_time, service_time, departure_time)
The parameters are:
orders_sql, vehicles_sql [,factor, max_cycles, initial_sol]
Where:
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.

A SELECT statement that returns the following columns:
id, demand
p_x, p_y, p_open, p_close, [p_service, ]
d_x, d_y, d_open, d_close, [d_service, ]
Where:
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 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 
A SELECT statement that returns the following columns:
id, capacity
start_x, start_y, start_open, start_close [, start_service, ]
[ end_x, end_y, end_open, end_close, end_service ]
where:
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 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. 
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 
This example use the following data: TODO put link
SELECT * FROM pgr_pickDeliverEuclidean(
'SELECT * FROM orders ORDER BY id',
'SELECT * from vehicles'
);
seq  vehicle_seq  vehicle_id  stop_seq  stop_type  order_id  cargo  travel_time  arrival_time  wait_time  service_time  departure_time
+++++++++++
1  1  1  1  1  1  0  0  0  0  0  0
2  1  1  2  2  3  30  1  1  1  3  5
3  1  1  3  3  3  0  1.41421356237  6.41421356237  0  3  9.41421356237
4  1  1  4  2  2  20  1.41421356237  10.8284271247  0  2  12.8284271247
5  1  1  5  3  2  0  1  13.8284271247  0  3  16.8284271247
6  1  1  6  6  1  0  1.41421356237  18.2426406871  0  0  18.2426406871
7  2  1  1  1  1  0  0  0  0  0  0
8  2  1  2  2  1  10  1  1  1  3  5
9  2  1  3  3  1  0  2.2360679775  7.2360679775  0  3  10.2360679775
10  2  1  4  6  1  0  2  12.2360679775  0  0  12.2360679775
11  2  0  0  1  1  1  11.4787086646  1  2  17  30.4787086646
(11 rows)
Indices and tables