Vehicle Routing Functions - Category (Experimental)¶
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
- Pickup and delivery problem
- pgr_pickDeliver - Experimental - Pickup & Delivery using a Cost Matrix
- pgr_pickDeliverEuclidean - Experimental - Pickup & Delivery with Euclidean distances
- Distribution problem
- pgr_vrpOneDepot - Experimental - From a single depot, distributes orders
Contents
Previous versions of this page
Introduction¶
Vehicle Routing Problems VRP are NP-hard optimization problem, it generalises the travelling salesman problem (TSP).
- The objective of the VRP is to minimize the total route cost.
- There are several variants of the VRP problem,
pgRouting does not try to implement all variants.
Characteristics¶
- Capacitated Vehicle Routing Problem CVRP where The vehicles have limited carrying capacity of the goods.
- Vehicle Routing Problem with Time Windows VRPTW where the locations have time windows within which the vehicle’s visits must be made.
- Vehicle Routing Problem with Pickup and Delivery VRPPD where a number of goods need to be moved from certain pickup locations to other delivery locations.
Limitations
- No multiple time windows for a location.
- Less vehicle used is considered better.
- Less total duration is better.
- Less wait time is better.
Pick & Delivery¶
Problem: CVRPPDTW Capacitated Pick and Delivery Vehicle Routing problem with Time Windows
- Times are relative to 0
- The vehicles
- have start and ending service duration times.
- have opening and closing times for the start and ending locations.
- have a capacity.
- The orders
- Have pick up and delivery locations.
- Have opening and closing times for the pickup and delivery locations.
- Have pickup and delivery duration service times.
- have a demand request for moving goods from the pickup location to the delivery location.
- Time based calculations:
- Travel time between customers is \(distance / speed\)
- Pickup and delivery order pair is done by the same vehicle.
- A pickup is done before the delivery.
Parameters¶
Pick & deliver¶
Both implementations use the following same parameters:
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.
|
The non euclidean implementation, additionally has:
Column | Type | Description |
---|---|---|
matrix_sql | TEXT |
Pick & Deliver Matrix SQL query containing the distance or travel times. |
Inner Queries¶
return columns
Pick & Deliver Orders SQL¶
In general, the columns for the orders SQL is the same in both implementation of pick and delivery:
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. |
For the euclidean implementation, pick up and delivery \((x,y)\) locations are needed:
Column | Type | Description |
---|---|---|
p_x | ANY-NUMERICAL | \(x\) value of the pick up location |
p_y | ANY-NUMERICAL | \(y\) value of the pick up location |
d_x | ANY-NUMERICAL | \(x\) value of the delivery location |
d_y | ANY-NUMERICAL | \(y\) value of the delivery location |
Pick & Deliver Vehicles SQL¶
In general, the columns for the vehicles_sql is the same in both implementation of pick and delivery:
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. |
For the euclidean implementation, starting and ending \((x,y)\) locations are needed:
Column | Type | Default | Description |
---|---|---|---|
start_x | ANY-NUMERICAL | \(x\) value of the coordinate of the starting location. | |
start_y | ANY-NUMERICAL | \(y\) value of the coordinate of the starting location. | |
end_x | ANY-NUMERICAL | start_x | \(x\) value of the coordinate of the ending location. |
end_y | ANY-NUMERICAL | start_y | \(y\) value of the coordinate of the ending location. |
Pick & Deliver Matrix SQL¶
Warning
TODO
Results¶
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 | 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 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\). |
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 | 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 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:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Handling Parameters¶
To define a problem, several considerations have to be done, to get consistent results. This section gives an insight of how parameters are to be considered.
Capacity and Demand Units Handling¶
The capacity of a vehicle, can be measured in:
- Volume units like \(m^3\).
- Area units like \(m^2\) (when no stacking is allowed).
- Weight units like \(kg\).
- Number of boxes that fit in the vehicle.
- Number of seats in the vehicle
The demand request of the pickup-deliver orders must use the same units as the units used in the vehicle’s capacity.
To handle problems like: 10 (equal dimension) boxes of apples and 5 kg of feathers that are to be transported (not packed in boxes).
If the vehicle’s capacity is measured by boxes, a conversion of kg of feathers to equivalent number of boxes is needed. If the vehicle’s capacity is measured by kg, a conversion of box of apples to equivalent number of kg is needed.
Showing how the 2 possible conversions can be done
Let: - \(f_boxes\): number of boxes that would be used for 1 kg of feathers. - \(a_weight\): weight of 1 box of apples.
Capacity Units | apples | feathers |
---|---|---|
boxes | 10 | \(5 * f\_boxes\) |
kg | \(10 * a\_weight\) | 5 |
Locations¶
- When using the Euclidean signatures:
- The vehicles have \((x, y)\) pairs for start and ending locations.
- The orders Have \((x, y)\) pairs for pickup and delivery locations.
- When using a matrix:
- The vehicles have identifiers for the start and ending locations.
- The orders have identifiers for the pickup and delivery locations.
- All the identifiers are indices to the given matrix.
Time Handling¶
The times are relative to 0
Suppose that a vehicle’s driver starts the shift at 9:00 am and ends the shift at 4:30 pm and the service time duration is 10 minutes with 30 seconds.
All time units have to be converted
Meaning of 0 | time units | 9:00 am | 4:30 pm | 10 min 30 secs |
---|---|---|---|---|
0:00 am | hours | 9 | 16.5 | \(10.5 / 60 = 0.175\) |
9:00 am | hours | 0 | 7.5 | \(10.5 / 60 = 0.175\) |
0:00 am | minutes | \(9*60 = 54\) | \(16.5*60 = 990\) | 10.5 |
9:00 am | minutes | 0 | \(7.5*60 = 540\) | 10.5 |
Factor Handling¶
Warning
TODO
See Also¶
- https://en.wikipedia.org/wiki/Vehicle_routing_problem
- The queries use the Sample Data network.
Indices and tables