vrp_pgr_pickDeliver - Experimental¶
vrp_pgr_pickDeliver
- 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 ANY-INTEGER and ANY-NUMERICAL
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 vrpRouting
Might depend on a deprecated function of vrpRouting
Availability
Version 0.0.0
New experimental function
Ported vrp_pgr_pickDeliver from pgRouting v3.1.3
Synopsis¶
Problem: Distribute and optimize the pickup-delivery pairs into a fleet of vehicles.
Optimization problem is NP-hard.
pickup and Delivery with time windows.
All vehicles are equal.
Same Starting location.
Same Ending location which is the same as Starting location.
All vehicles travel at the same speed.
A customer is for doing a pickup or doing a deliver.
has an open time.
has a closing time.
has a service time.
has an (x, y) location.
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¶
All trucks depart at time 0.
No multiple time windows for a location.
Less vehicle used is considered better.
Less total duration is better.
Less wait time is better.
the algorithm will raise an exception when
If there is a pickup-deliver pair than violates time window
The speed, max_cycles, ma_capacity have illegal values
Six different initial will be optimized - the best solution found will be result
Signature¶
vrp_pgr_pickDeliver(Orders SQL, Vehicles SQL, Matrix SQL [, factor, max_cycles, initial_sol])
RETURNS SET OF:
seq, vehicle_seq, vehicle_id,
stop_seq, stop_type, stop_id, order_id
cargo, travel_time, arrival_time, wait_time, service_time, departure_time
Parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
Orders SQL |
|
Orders SQL query contianing the orders to be processed. |
|
Vehicles SQL |
|
Vehicles SQL query containing the vehicles to be used. |
|
Matrix SQL |
|
Time Matrix SQL query containing the distance or travel times. |
|
factor |
|
1 |
Travel time multiplier. See Factor Handling |
max_cycles |
|
10 |
Maximum number of cycles to perform on the optimization. |
initial_sol |
|
4 |
Initial solution to be used.
|
Inner Queries¶
Orders SQL¶
A SELECT
statement that returns the following columns:
id, amount
p_id, p_tw_open, p_tw_close, [p_service,]
d_id, d_tw_open, d_tw_close, [d_service]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
ANY-INTEGER |
Identifier of the pick-delivery order pair. |
|
amount |
ANY-NUMERICAL |
Number of units in the order |
|
p_id |
ANY-INTEGER |
The identifier of the pickup node. |
|
p_tw_open |
ANY-NUMERICAL |
The time, relative to 0, when the pickup location opens. |
|
p_tw_close |
ANY-NUMERICAL |
The time, relative to 0, when the pickup location closes. |
|
p_service |
ANY-NUMERICAL |
0 |
The duration of the loading at the pickup location. |
d_id |
ANY-INTEGER |
The identifier of the delivery node. |
|
d_tw_open |
ANY-NUMERICAL |
The time, relative to 0, when the delivery location opens. |
|
d_tw_close |
ANY-NUMERICAL |
The time, relative to 0, when the delivery location closes. |
|
d_service |
ANY-NUMERICAL |
0 |
The duration of the unloading at the delivery location. |
Vehicles SQL¶
A SELECT
statement that returns the following columns:
id, capacity, [speed,]
s_id, s_tw_open, s_tw_close, [s_service,]
[e_id, e_tw_open, e_tw_close, e_service]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
ANY-INTEGER |
Identifier of the vehicle |
|
capacity |
ANY-NUMERICAL |
Capacity of the vehicle |
|
speed |
ANY-NUMERICAL |
1 |
Average speed of the vehicle. |
s_id |
ANY-INTEGER |
The node identifier of the starting location, must match a node identifier in the matrix table. |
|
s_tw_open |
ANY-NUMERICAL |
0 |
The time, relative to 0, when the starting location opens. When s_tw_open column exist then s_tw_close column is expected Default value when (s_tw_open, s_tw_close) columns do not exist |
s_tw_close |
ANY-NUMERICAL |
INFINITY |
The time, relative to 0, when the starting location closes. When s_tw_close column exist then e_tw_open column is expected Default value when (s_tw_open, s_tw_close) columns do not exist |
s_service |
ANY-NUMERICAL |
0 |
The duration of the loading at the starting location. |
e_id |
ANY-INTEGER |
s_id |
The node identifier of the ending location, must match a node identifier in the matrix table. |
e_tw_open |
ANY-NUMERICAL |
s_tw_open |
The time, relative to 0, when the ending location opens. When e_tw_open column exist then e__tw_close column is expected Default value when (e_tw_open, e_tw_close) columns do not exist |
e_tw_close |
ANY-NUMERICAL |
s_tw_close |
The time, relative to 0, when the ending location closes. When e_tw_close column exist then e_tw_open column is expected Default value when (e_tw_open, e_tw_close)` columns do not exist |
e_service |
ANY-NUMERICAL |
s_service |
The duration of the unloading at the ending location. |
Throws: * When column id is missing * When column capacity is missing * When column s_id is missing * When column s_tw_open exists but not s_tw_close * When column s_tw_close`exists but not `s_tw_open * When column e_tw_open exists but not e_tw_close * When column e_tw_close`exists but not `e_tw_open
Time Matrix SQL¶
A SELECT
statement that returns the following columns:
start_vid, end_vid, agg_cost
Column |
Type |
Description |
---|---|---|
start_vid |
ANY-INTEGER |
Identifier of a node. |
end_vid |
ANY-NUMERICAL |
Identifier of a node |
agg_cost |
ANY-NUMERICAL |
Time to travel from |
Result Columns¶
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:
|
stop_id |
INTEGER |
|
order_id |
BIGINT |
Pickup-Delivery 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\).
|
Example¶
This example use the following data:
SELECT * FROM vrp_pgr_pickDeliver(
$$ SELECT * FROM orders_1 ORDER BY id $$,
$$ SELECT * FROM vehicles_1 ORDER BY id$$,
$$ SELECT start_vid, end_vid, agg_cost::INTEGER FROM pgr_dijkstraCostMatrix(
'SELECT * FROM edge_table ',
(SELECT array_agg(id) FROM (SELECT p_id AS id FROM orders_1
UNION
SELECT d_id FROM orders_1
UNION
SELECT s_id FROM vehicles_1) a))
$$
);
seq | vehicle_seq | vehicle_id | stop_seq | stop_type | stop_id | order_id | cargo | travel_time | arrival_time | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+---------+----------+-------+-------------+--------------+-----------+--------------+----------------
1 | 1 | 1 | 1 | 1 | 6 | -1 | 0 | 0 | 0 | 1 | 0 | 1
2 | 1 | 1 | 2 | 2 | 5 | 3 | 30 | 1 | 2 | 0 | 3 | 5
3 | 1 | 1 | 3 | 3 | 11 | 3 | 0 | 2 | 7 | 0 | 3 | 10
4 | 1 | 1 | 4 | 2 | 9 | 2 | 20 | 2 | 12 | 0 | 2 | 14
5 | 1 | 1 | 5 | 3 | 4 | 2 | 0 | 1 | 15 | 0 | 3 | 18
6 | 1 | 1 | 6 | 6 | 6 | -1 | 0 | 2 | 20 | 0 | 0 | 20
7 | 2 | 2 | 1 | 1 | 6 | -1 | 0 | 0 | 0 | 0 | 0 | 0
8 | 2 | 2 | 2 | 2 | 3 | 1 | 10 | 3 | 3 | 0 | 3 | 6
9 | 2 | 2 | 3 | 3 | 8 | 1 | 0 | 3 | 9 | 0 | 3 | 12
10 | 2 | 2 | 4 | 6 | 6 | -1 | 0 | 2 | 14 | 0 | 0 | 14
11 | -2 | 0 | 0 | -1 | -1 | -1 | -1 | 16 | -1 | 1 | 17 | 34
(11 rows)
See Also¶
The queries use the Sample Data network.
Indices and tables