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
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¶
Used in pgr_pickDeliverEuclidean - Experimental
Column | Type | Description |
---|---|---|
Orders SQL | TEXT |
Orders SQL as described below. |
Vehicles SQL | TEXT |
Vehicles SQL as described below. |
Used in pgr_pickDeliver - Experimental
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.
|
Inner Queries¶
Orders SQL¶
Common columns for the orders SQL in both implementations:
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 |
For pgr_pickDeliver - Experimental the pickup and delivery identifiers of the locations are needed:
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 |
---|
For pgr_pickDeliverEuclidean - Experimental the \((x, y)\) values of the 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 |
Where:
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
---|
Vehicles SQL¶
Common columns for the vehicles SQL in both implementations:
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.
|
For pgr_pickDeliver - Experimental the starting and ending identifiers of the locations are needed:
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 |
---|
For pgr_pickDeliverEuclidean - Experimental the \((x, y)\) values of the locations are needed:
Column | Type | Description |
---|---|---|
start_x |
ANY-NUMERICAL | \(x\) value of the starting location |
start_y |
ANY-NUMERICAL | \(y\) value of the starting location |
[end_x ] |
ANY-NUMERICAL | \(x\) value of the ending location
|
[end_y ] |
ANY-NUMERICAL | \(y\) value of the ending location
|
Where:
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
---|
Matrix SQL¶
Set of (start_vid, end_vid, agg_cost)
Column | Type | Description |
---|---|---|
start_vid |
BIGINT |
Identifier of the starting vertex. |
end_vid |
BIGINT |
Identifier of the ending vertex. |
agg_cost |
FLOAT |
Aggregate cost from start_vid to end_vid . |
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 |
|
Summary Row¶
Column | Type | Description |
---|---|---|
seq |
INTEGER |
Continues the sequence |
vehicle_seq |
INTEGER |
Value \(-2\) indicates it is the summary row. |
vehicle_id |
BIGINT | total capacity violations:
|
stop_seq |
INTEGER | total time windows violations:
|
stop_type |
INTEGER |
\(-1\) |
order_id |
BIGINT |
\(-1\) |
cargo |
FLOAT |
\(-1\) |
travel_time |
FLOAT |
total traveling time:
|
arrival_time |
FLOAT |
\(-1\) |
wait_time |
FLOAT |
total waiting time:
|
service_time |
FLOAT |
total service time:
|
departure_time |
FLOAT |
Summary row has the total solution time:
|
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 in boxes, a conversion of kg of feathers to number of boxes is needed.
- If the vehicle’s capacity is measured in kg, a conversion of box of apples to kg is needed.
Showing how the 2 possible conversions can be done
Let: - \(f\_boxes\): number of boxes needed 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 pgr_pickDeliverEuclidean - Experimental:
- The vehicles have \((x, y)\) pairs for start and ending locations.
- The orders Have \((x, y)\) pairs for pickup and delivery locations.
- When using pgr_pickDeliver - Experimental:
- 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. All time units have to be converted to a 0 reference and the same time units.
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.
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\) |
0:00 am | minutes | \(9*60 = 54\) | \(16.5*60 = 990\) | 10.5 |
9:00 am | hours | 0 | 7.5 | \(10.5 / 60 = 0.175\) |
9:00 am | minutes | 0 | \(7.5*60 = 540\) | 10.5 |
Factor handling¶
factor
acts as a multiplier to convert from distance values to time units
the matrix values or the euclidean values.
- When the values are already in the desired time units
factor
should be 1- When
factor
> 1 the travel times are faster - When
factor
< 1 the travel times are slower
For the pgr_pickDeliverEuclidean - Experimental:
Working with time units in seconds, and x/y in lat/lon: Factor: would depend on the location of the points and on the average velocity say 25m/s is the velocity.
Latitude | Conversion | Factor |
---|---|---|
45 | 1 longitude degree is (78846.81m)/(25m/s) | 3153 s |
0 | 1 longitude degree is (111319.46 m)/(25m/s) | 4452 s |
For the pgr_pickDeliver - Experimental:
Given \(v = d / t\) therefore \(t = d / v\)
And the factor
becomes \(1 / v\)
Where:
v: | Velocity |
---|---|
d: | Distance |
t: | Time |
For the following equivalences \(10m/s \approx 600m/min \approx 36 km/hr\)
Working with time units in seconds and the matrix been in meters: For a 1000m lenght value on the matrix:
Units | velocity | Conversion | Factor | Result |
---|---|---|---|---|
seconds | \(10 m/s\) | \(\frac{1}{10m/s}\) | \(0.1s/m\) | \(1000m * 0.1s/m = 100s\) |
minutes | \(600 m/min\) | \(\frac{1}{600m/min}\) | \(0.0016min/m\) | \(1000m * 0.0016min/m = 1.6min\) |
Hours | \(36 km/hr\) | \(\frac{1}{36 km/hr}\) | \(0.0277hr/km\) | \(1km * 0.0277hr/km = 0.0277hr\) |
See Also¶
- https://en.wikipedia.org/wiki/Vehicle_routing_problem
- The queries use the Sample Data network.
Indices and tables