pgr_pickDeliverEuclidean  Experimental¶
pgr_pickDeliverEuclidean
 Pickup and delivery Vehicle Routing Problem
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
Availability
Version 3.0.0
Replaces
pgr_gsoc_vrppdtw
New experimental function
Synopsis¶
Problem: Distribute and optimize the pickupdelivery pairs into a fleet of vehicles.
Optimization problem is NPhard.
Pickup and Delivery:
capacitated
with time windows.
The vehicles
have (x, y) start and ending locations.
have a start and ending service times.
have opening and closing times for the start and ending locations.
An order is for doing a pickup and a a deliver.
has (x, y) pickup and delivery locations.
has opening and closing times for the pickup and delivery locations.
has a pickup and deliver service times.
There is a customer where to deliver a pickup.
travel time between customers is distance / speed
pickup and delivery pair is done with the same vehicle.
A pickup is done before the delivery.
Characteristics¶
No multiple time windows for a location.
Less vehicle used is considered better.
Less total duration is better.
Less wait time is better.
Six different optional different initial solutions
the best solution found will be result
Signature¶
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)
Parameters¶
The parameters are:
orders_sql, vehicles_sql [,factor, max_cycles, initial_sol]
Where:
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.

Pick & Deliver Orders SQL¶
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 
Pick & Deliver Vehicles SQL¶
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. 
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
Example¶
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)
See Also¶
The queries use the Sample Data network.
Indices and tables