pgr_pickDeliver - Experimental¶
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 pgRouting
- Might depend on a deprecated function of pgRouting
Availability
- Version 3.0.0
- New experimental function
Support
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¶
pgr_pickDeliver(orders_sql, vehicles_sql, matrix_sql [, factor, max_cycles, initial_sol])
RETURNS SET OF (seq, vehicle_number, vehicle_id, stop, order_id, stop_type, cargo,
travel_time, arrival_time, wait_time, service_time, departure_time)
Parameters¶
The parameters are:
orders_sql, vehicles_sql, matrix_sql [, factor, max_cycles, initial_sol]
Column | Type | Default | Description |
---|---|---|---|
orders_sql | TEXT |
Pick & Deliver Orders SQL query contianing the orders to be processed. | |
vehicles_sql | TEXT |
Pick & Deliver Vehicles SQL query containing the vehicles to be used. | |
matrix_sql | TEXT |
Pick & Deliver Matrix SQL query containing the distance or travel times. | |
factor | NUMERIC |
1 | Travel time multiplier. See Factor Handling |
max_cycles | INTEGER |
10 | Maximum number of cycles to perform on the optimization. |
initial_sol | INTEGER |
4 | Initial solution to be used.
|
Pick & Deliver Orders SQL¶
A SELECT statement that returns the following columns:
id, demand
p_node_id, p_open, p_close, [p_service, ]
d_node_id, d_open, d_close, [d_service, ]
where:
Column | Type | Default | Description |
---|---|---|---|
id | ANY-INTEGER | Identifier of the pick-delivery order pair. | |
demand | ANY-NUMERICAL | Number of units in the order | |
p_open | ANY-NUMERICAL | The time, relative to 0, when the pickup location opens. | |
p_close | ANY-NUMERICAL | The time, relative to 0, when the pickup location closes. | |
d_service | ANY-NUMERICAL | 0 | The duration of the loading at the pickup location. |
d_open | ANY-NUMERICAL | The time, relative to 0, when the delivery location opens. | |
d_close | ANY-NUMERICAL | The time, relative to 0, when the delivery location closes. | |
d_service | ANY-NUMERICAL | 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 | ANY-INTEGER | The node identifier of the pickup, must match a node identifier in the matrix table. |
d_node_id | ANY-INTEGER | The node identifier of the delivery, must match a node identifier in the matrix table. |
Pick & Deliver Vehicles SQL¶
A SELECT statement that returns the following columns:
id, capacity
start_node_id, start_open, start_close [, start_service, ]
[ end_node_id, end_open, end_close, end_service ]
where:
Column | Type | Default | Description |
---|---|---|---|
id | ANY-INTEGER | Identifier of the pick-delivery order pair. | |
capacity | ANY-NUMERICAL | Number of units in the order | |
speed | ANY-NUMERICAL | 1 | Average speed of the vehicle. |
start_open | ANY-NUMERICAL | The time, relative to 0, when the starting location opens. | |
start_close | ANY-NUMERICAL | The time, relative to 0, when the starting location closes. | |
start_service | ANY-NUMERICAL | 0 | The duration of the loading at the starting location. |
end_open | ANY-NUMERICAL | start_open | The time, relative to 0, when the ending location opens. |
end_close | ANY-NUMERICAL | start_close | The time, relative to 0, when the ending location closes. |
end_service | ANY-NUMERICAL | 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 | ANY-INTEGER | The node identifier of the starting location, must match a node identifier in the matrix table. | |
end_node_id | ANY-INTEGER | start_node_id | The node identifier of the ending location, must match a node identifier in the matrix table. |
Pick & Deliver Matrix SQL¶
A SELECT statement that returns the following columns:
Warning
TODO
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Example¶
This example use the following data: TODO put link
SELECT * FROM pgr_pickDeliver(
$$ SELECT * FROM orders ORDER BY id $$,
$$ SELECT * FROM vehicles ORDER BY id$$,
$$ SELECT * from pgr_dijkstraCostMatrix(
'SELECT * FROM edge_table ',
(SELECT array_agg(id) FROM (SELECT p_node_id AS id FROM orders
UNION
SELECT d_node_id FROM orders
UNION
SELECT start_node_id FROM vehicles) 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 | 0 | 0 | 0
2 | 1 | 1 | 2 | 2 | 5 | 3 | 30 | 1 | 1 | 1 | 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 | 1 | 1 | 1 | 6 | -1 | 0 | 0 | 0 | 0 | 0 | 0
8 | 2 | 1 | 2 | 2 | 3 | 1 | 10 | 3 | 3 | 0 | 3 | 6
9 | 2 | 1 | 3 | 3 | 8 | 1 | 0 | 3 | 9 | 0 | 3 | 12
10 | 2 | 1 | 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¶
- Vehicle Routing Functions - Category (Experimental)
- The queries use the Sample Data network.
Indices and tables