vrp_vroomShipmentsPlain - Experimental¶
vrp_vroomShipmentsPlain
- Vehicle Routing Problem with VROOM, involving only
shipments, with plain integer values instead of TIMESTAMP or INTERVAL.
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.3.0
Function modified for VROOM 1.11.0
Version 0.2.0
New experimental function
Description¶
VROOM is an open-source optimization engine that aims at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time. This function can be used to get the solution to a problem involving only shipments.
Signature¶
Example: This example is based on the VROOM Data of the Sample Data network:
SELECT *
FROM vrp_vroomShipmentsPlain(
'SELECT * FROM vroom.shipments',
'SELECT * FROM vroom.shipments_time_windows',
'SELECT * FROM vroom.vehicles',
'SELECT * FROM vroom.breaks',
'SELECT * FROM vroom.breaks_time_windows',
'SELECT * FROM vroom.matrix'
);
seq | vehicle_seq | vehicle_id | vehicle_data | step_seq | step_type | task_id | location_id | task_data | arrival | travel_time | setup_time | service_time | waiting_time | departure | load
-----+-------------+------------+--------------+----------+-----------+---------+-------------+-----------+---------+-------------+------------+--------------+--------------+-----------+------
1 | 1 | 1 | {} | 1 | 1 | -1 | 1 | {} | 300 | 0 | 0 | 0 | 0 | 300 | {0}
2 | 1 | 1 | {} | 2 | 5 | 1 | 1 | {} | 300 | 0 | 0 | 0 | 0 | 300 | {0}
3 | 1 | 1 | {} | 3 | 3 | 4 | 1 | {} | 300 | 0 | 0 | 2250 | 6075 | 8625 | {20}
4 | 1 | 1 | {} | 4 | 4 | 4 | 4 | {} | 8700 | 75 | 0 | 2250 | 225 | 11175 | {0}
5 | 1 | 1 | {} | 5 | 3 | 5 | 2 | {} | 11265 | 90 | 0 | 2250 | 2085 | 15600 | {10}
6 | 1 | 1 | {} | 6 | 3 | 3 | 1 | {} | 15650 | 50 | 0 | 2250 | 0 | 17900 | {30}
7 | 1 | 1 | {} | 7 | 4 | 5 | 2 | {} | 17950 | 50 | 0 | 2250 | 225 | 20425 | {20}
8 | 1 | 1 | {} | 8 | 4 | 3 | 2 | {} | 20425 | 0 | 0 | 2250 | 200 | 22875 | {0}
9 | 1 | 1 | {} | 9 | 6 | -1 | 1 | {} | 22925 | 50 | 0 | 0 | 0 | 22925 | {0}
10 | 1 | 1 | {} | 0 | 0 | 0 | 0 | {} | 0 | 315 | 0 | 13500 | 8810 | 0 | {}
11 | 2 | 4 | {} | 1 | 1 | -1 | 3 | {} | 250 | 0 | 0 | 0 | 0 | 250 | {0}
12 | 2 | 4 | {} | 2 | 5 | 4 | 1 | {} | 250 | 0 | 0 | 0 | 0 | 250 | {0}
13 | 2 | 4 | {} | 3 | 3 | 2 | 5 | {} | 275 | 25 | 0 | 2250 | 100 | 2625 | {10}
14 | 2 | 4 | {} | 4 | 3 | 1 | 3 | {} | 2650 | 25 | 0 | 2250 | 0 | 4900 | {20}
15 | 2 | 4 | {} | 5 | 4 | 2 | 6 | {} | 4990 | 90 | 0 | 2250 | 0 | 7240 | {10}
16 | 2 | 4 | {} | 6 | 4 | 1 | 5 | {} | 7351 | 111 | 0 | 2250 | 17574 | 27175 | {0}
17 | 2 | 4 | {} | 7 | 6 | -1 | 3 | {} | 27200 | 25 | 0 | 0 | 0 | 27200 | {0}
18 | 2 | 4 | {} | 0 | 0 | 0 | 0 | {} | 0 | 276 | 0 | 9000 | 17674 | 0 | {}
19 | 0 | 0 | {} | 0 | 0 | 0 | 0 | {} | 0 | 591 | 0 | 22500 | 26484 | 0 | {}
(19 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Query describing pickup and delivery tasks that should happen within same route. |
|
|
Query describing valid slots for pickup and delivery service start. |
|
|
Query describing the available vehicles. |
|
|
Query describing the driver breaks. |
|
|
Query describing valid slots for break start. |
|
|
Query containing the distance or travel times between the locations. |
Optional Parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
|
\(5\) |
Exploration level to use while solving.
|
|
|
\(-1\) |
Timeout value to stop the solving process.
|
Inner Queries¶
Shipments SQL¶
A SELECT
statement that returns the following columns:
id
p_location_id, [p_setup, p_service, p_data]
d_location_id, [d_setup, d_service, d_data]
[amount, skills, priority]
Maximum values apply from vroom
p_setup
, p_service
, d_setup
, d_service
\(4294967295\)
skills
\(2147483647\)
priority
\(100\)
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Positive unique identifier of the shipment. |
|
|
ANY-INTEGER |
Positive unique identifier of the pickup location. |
|
|
ANY-INTEGER |
\(0\) |
The pickup setup duration |
|
ANY-INTEGER |
\(0\) |
The pickup service duration |
|
|
|
Any metadata information of the pickup. |
|
ANY-INTEGER |
Positive unique identifier of the pickup location. |
|
|
ANY-INTEGER |
\(0\) |
The pickup setup duration |
|
ANY-INTEGER |
\(0\) |
The pickup service duration |
|
|
|
Any metadata information of the delivery. |
|
|
|
Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc.
|
|
|
|
Array of non-negative integers defining mandatory skills.
|
|
|
\(0\) |
Value range: \([0, 100]\) |
Shipments Time Windows SQL¶
A SELECT
statement that returns the following columns:
id, tw_open, tw_close
[kind]
Column |
Type |
Description |
---|---|---|
|
ANY-INTEGER |
Positive unique identifier of the: job, pickup/delivery shipment, or break. |
|
ANY-INTEGER |
Time window opening time. |
|
ANY-INTEGER |
Time window closing time. |
|
|
Value in [‘p’, ‘d’] indicating whether the time window is for:
|
Vehicles SQL¶
A SELECT
statement that returns the following columns:
id, start_id, end_id
[capacity, skills, tw_open, tw_close, speed_factor, max_tasks, data]
Maximum values apply from vroom
skills
\(2147483647\)
priority
\(100\)
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Positive unique identifier of the vehicle. |
|
|
ANY-INTEGER |
Positive unique identifier of the start location. |
|
|
ANY-INTEGER |
Positive unique identifier of the end location. |
|
|
|
|
Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc.
|
|
|
|
Array of non-negative integers defining mandatory skills. |
|
ANY-INTEGER |
\(0\) |
Time window opening time.
|
|
ANY-INTEGER |
\(4294967295\) |
Time window closing time.
|
|
ANY-NUMERICAL |
\(1.0\) |
Vehicle travel time multiplier.
|
|
|
\(2147483647\) |
Maximum number of tasks in a route for the vehicle.
|
|
|
|
Any metadata information of the vehicle. |
Note:
At least one of the
start_id
orend_id
shall be present.If
end_id
is omitted, the resulting route will stop at the last visited task, whose choice is determined by the optimization process.If
start_id
is omitted, the resulting route will start at the first visited task, whose choice is determined by the optimization process.To request a round trip, specify both
start_id
andend_id
as the same index.A vehicle is only allowed to serve a set of tasks if the resulting load at each route step is lower than the matching value in capacity for each metric. When using multiple components for amounts, it is recommended to put the most important/limiting metrics first.
It is assumed that all delivery-related amounts for jobs are loaded at vehicle start, while all pickup-related amounts for jobs are brought back at vehicle end.
Breaks SQL¶
A SELECT
statement that returns the following columns:
id, vehicle_id
[service, data]
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Positive unique identifier of the break. Unique for the same vehicle. |
|
|
ANY-INTEGER |
Positive unique identifier of the vehicle. |
|
|
ANY-INTEGER |
\(0\) |
The break duration |
|
|
|
Any metadata information of the break. |
Breaks Time Windows SQL¶
A SELECT
statement that returns the following columns:
id, tw_open, tw_close
Column |
Type |
Description |
---|---|---|
|
ANY-INTEGER |
Positive unique identifier of the: job, pickup/delivery shipment, or break. |
|
ANY-INTEGER |
Time window opening time. |
|
ANY-INTEGER |
Time window closing time. |
Time Matrix SQL¶
A SELECT
statement that returns the following columns:
start_id, end_id, duration
[ cost]
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the start node. |
|
|
ANY-INTEGER |
Identifier of the end node. |
|
|
ANY-INTEGER |
Time to travel from |
|
|
ANY-INTEGER |
|
Cost of travel from |
Result Columns¶
Returns set of
(seq, vehicle_seq, vehicle_id, vehicle_data, step_seq, step_type, task_id,
task_data, arrival, travel_time, service_time, waiting_time, load)
Column |
Type |
Description |
---|---|---|
|
|
Sequential value starting from 1. |
|
|
Sequential value starting from 1 for current vehicles. The \(n^{th}\) vehicle in the solution. |
|
|
Current vehicle identifier.
|
|
|
Metadata information of the vehicle. |
|
|
Sequential value starting from 1 for the stops made by the current vehicle. The \(m^{th}\) stop of the current vehicle.
|
|
|
Kind of the step location the vehicle is at:
|
|
|
Identifier of the task performed at this step.
|
|
|
Identifier of the task location.
|
|
|
Metadata information of the task. |
|
ANY-INTEGER |
Estimated time of arrival at this step. |
|
ANY-INTEGER |
Travel time from previous
|
|
ANY-INTEGER |
Setup time at this step. |
|
ANY-INTEGER |
Service time at this step. |
|
ANY-INTEGER |
Waiting time at this step. |
|
ANY-INTEGER |
Estimated time of departure at this step.
|
|
|
Vehicle load after step completion (with capacity constraints) |
Note:
Unallocated tasks are mentioned at the end with
vehicle_id = -1
.The last step of every vehicle denotes the summary row, where the columns
travel_time
,service_time
andwaiting_time
denote the total time for the corresponding vehicle,The last row denotes the summary for the complete problem, where the columns
travel_time
,service_time
andwaiting_time
denote the total time for the complete problem,
Additional Example¶
Problem involving 1 shipment, using a single vehicle, similar to the VROOM Documentation Example 2 without jobs and with a shipment.
SELECT *
FROM vrp_vroomShipmentsPlain(
$shipments$
SELECT * FROM (
VALUES (100, 1, 4)
) AS C(id, p_location_id, d_location_id)
$shipments$,
NULL,
$vehicles$
SELECT * FROM (
VALUES (1, 1, 4)
) AS C(id, start_id, end_id)
$vehicles$,
NULL,
NULL,
$matrix$
SELECT * FROM (
VALUES (1, 2, 2104), (1, 3, 197), (1, 4, 1299),
(2, 1, 2103), (2, 3, 2255), (2, 4, 3152),
(3, 1, 197), (3, 2, 2256), (3, 4, 1102),
(4, 1, 1299), (4, 2, 3153), (4, 3, 1102)
) AS C(start_id, end_id, duration)
$matrix$
);
seq | vehicle_seq | vehicle_id | vehicle_data | step_seq | step_type | task_id | location_id | task_data | arrival | travel_time | setup_time | service_time | waiting_time | departure | load
-----+-------------+------------+--------------+----------+-----------+---------+-------------+-----------+---------+-------------+------------+--------------+--------------+-----------+------
1 | 1 | 1 | {} | 1 | 1 | -1 | 1 | {} | 0 | 0 | 0 | 0 | 0 | 0 | {}
2 | 1 | 1 | {} | 2 | 3 | 100 | 1 | {} | 0 | 0 | 0 | 0 | 0 | 0 | {}
3 | 1 | 1 | {} | 3 | 4 | 100 | 4 | {} | 1299 | 1299 | 0 | 0 | 0 | 1299 | {}
4 | 1 | 1 | {} | 4 | 6 | -1 | 4 | {} | 1299 | 0 | 0 | 0 | 0 | 1299 | {}
5 | 1 | 1 | {} | 0 | 0 | 0 | 0 | {} | 0 | 1299 | 0 | 0 | 0 | 0 | {}
6 | 0 | 0 | {} | 0 | 0 | 0 | 0 | {} | 0 | 1299 | 0 | 0 | 0 | 0 | {}
(6 rows)
See Also¶
The queries use the Sample Data network.
Indices and tables