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
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)
Example: | Solve the following problem |
---|
Given the vehicles:
SELECT id, capacity, start_node_id, start_open, start_close
FROM vehicles;
id | capacity | start_node_id | start_open | start_close
----+----------+---------------+------------+-------------
1 | 50 | 11 | 0 | 50
2 | 50 | 11 | 0 | 50
(2 rows)
and the orders:
SELECT id, demand,
p_node_id, p_open, p_close, p_service,
d_node_id, d_open, d_close, d_service
FROM orders;
id | demand | p_node_id | p_open | p_close | p_service | d_node_id | d_open | d_close | d_service
----+--------+-----------+--------+---------+-----------+-----------+--------+---------+-----------
1 | 10 | 10 | 2 | 10 | 3 | 3 | 6 | 15 | 3
2 | 20 | 16 | 4 | 15 | 2 | 15 | 6 | 20 | 3
3 | 30 | 7 | 2 | 10 | 3 | 12 | 3 | 20 | 3
(3 rows)
The query:
SELECT * FROM pgr_pickDeliver(
$$SELECT id, demand,
p_node_id, p_open, p_close, p_service,
d_node_id, d_open, d_close, d_service
FROM orders$$,
$$SELECT id, capacity, start_node_id, start_open, start_close
FROM vehicles$$,
$$SELECT * from pgr_dijkstraCostMatrix(
'SELECT * FROM edges ',
(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 | 11 | -1 | 0 | 0 | 0 | 0 | 0 | 0
2 | 1 | 1 | 2 | 2 | 7 | 3 | 30 | 1 | 1 | 1 | 3 | 5
3 | 1 | 1 | 3 | 3 | 12 | 3 | 0 | 2 | 7 | 0 | 3 | 10
4 | 1 | 1 | 4 | 2 | 16 | 2 | 20 | 2 | 12 | 0 | 2 | 14
5 | 1 | 1 | 5 | 3 | 15 | 2 | 0 | 1 | 15 | 0 | 3 | 18
6 | 1 | 1 | 6 | 6 | 11 | -1 | 0 | 2 | 20 | 0 | 0 | 20
7 | 2 | 2 | 1 | 1 | 11 | -1 | 0 | 0 | 0 | 0 | 0 | 0
8 | 2 | 2 | 2 | 2 | 10 | 1 | 10 | 3 | 3 | 0 | 3 | 6
9 | 2 | 2 | 3 | 3 | 3 | 1 | 0 | 3 | 9 | 0 | 3 | 12
10 | 2 | 2 | 4 | 6 | 11 | -1 | 0 | 2 | 14 | 0 | 0 | 14
11 | -2 | 0 | 0 | -1 | -1 | -1 | -1 | 16 | -1 | 1 | 17 | 34
(11 rows)
Parameters¶
The parameters are:
Column | Type | Description |
---|---|---|
Orders SQL | TEXT |
Orders SQL as described below. |
Vehicles SQL | TEXT |
Vehicles SQL as described below. |
Matrix SQL | TEXT |
Matrix SQL as described below. |
Pick-Deliver optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
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.
|
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 | 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. |
[p_service ] |
ANY-NUMERICAL | 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 | The duration of the unloading at the delivery location.
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Column | Type | Description |
---|---|---|
p_node_id |
ANY-INTEGER | The node identifier of the pickup, must match a vertex identifier in the Matrix SQL. |
d_node_id |
ANY-INTEGER | The node identifier of the delivery, must match a vertex identifier in the Matrix SQL. |
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|
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 | Description |
---|---|---|
id |
ANY-NUMERICAL | Identifier of the vehicle. |
capacity |
ANY-NUMERICAL | Maiximum capacity units |
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 | The duration of the loading at the starting location.
|
[end_open ] |
ANY-NUMERICAL | The time, relative to 0, when the ending location opens.
|
[end_close ] |
ANY-NUMERICAL | The time, relative to 0, when the ending location closes.
|
[end_service ] |
ANY-NUMERICAL | The duration of the loading at the ending location.
|
Column | Type | Description |
---|---|---|
start_node_id |
ANY-INTEGER | The node identifier of the start location, must match a vertex identifier in the Matrix SQL. |
[end_node_id ] |
ANY-INTEGER | The node identifier of the end location, must match a vertex identifier in the Matrix SQL.
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|
Matrix SQL¶
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Return columns¶
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 |
|
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 |
Time spent waiting for current location to open.
|
wait_time |
FLOAT |
Time spent waiting for current location to open.
|
service_time |
FLOAT |
Service duration at current location.
|
departure_time |
FLOAT |
|
See Also¶
Indices and tables