vrp_vroomJobs - Experimental¶
vrp_vroomJobs
- Vehicle Routing Problem with VROOM, involving only jobs.
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.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 jobs.
Signature¶
vrp_vroomJobs(
Jobs SQL, Jobs Time Windows SQL,
Vehicles SQL, Breaks SQL, Breaks Time Windows SQL,
Matrix SQL) -- Experimental on v0.2
RETURNS SET OF
(seq, vehicle_seq, vehicle_id, step_seq, step_type, task_id,
arrival, travel_time, service_time, waiting_time, load)
Example: This example is based on the VROOM Data of the Sample Data network:
SELECT *
FROM vrp_vroomJobs(
'SELECT * FROM vroom.jobs',
'SELECT * FROM vroom.jobs_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 | step_seq | step_type | task_id | arrival | travel_time | service_time | waiting_time | load
-----+-------------+------------+----------+-----------+---------+---------+-------------+--------------+--------------+-------
1 | 1 | 1 | 1 | 1 | -1 | 300 | 0 | 0 | 0 | {20}
2 | 1 | 1 | 2 | 5 | 1 | 300 | 0 | 0 | 0 | {20}
3 | 1 | 1 | 3 | 2 | 1 | 300 | 0 | 250 | 3325 | {20}
4 | 1 | 1 | 4 | 6 | -1 | 3875 | 0 | 0 | 0 | {20}
5 | 2 | 2 | 1 | 1 | -1 | 275 | 0 | 0 | 0 | {100}
6 | 2 | 2 | 2 | 5 | 2 | 275 | 0 | 10 | 0 | {100}
7 | 2 | 2 | 3 | 2 | 2 | 335 | 50 | 250 | 915 | {100}
8 | 2 | 2 | 4 | 2 | 5 | 1590 | 140 | 250 | 0 | {100}
9 | 2 | 2 | 5 | 2 | 3 | 1890 | 190 | 250 | 835 | {100}
10 | 2 | 2 | 6 | 2 | 4 | 2975 | 190 | 250 | 550 | {100}
11 | 2 | 2 | 7 | 6 | -1 | 3775 | 190 | 0 | 0 | {100}
(11 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
Jobs SQL |
|
Jobs SQL query describing the single-location pickup and/or delivery tasks. |
Jobs Time Windows SQL |
|
Time Windows SQL query describing valid slots for job service start. |
Vehicles SQL |
|
Vehicles SQL query describing the available vehicles. |
Breaks SQL |
|
Breaks SQL query describing the driver breaks. |
Breaks Time Windows SQL |
|
Time Windows SQL query describing valid slots for break start. |
Matrix SQL |
|
Time Matrix SQL query containing the distance or travel times between the locations. |
Inner Queries¶
Jobs SQL¶
A SELECT
statement that returns the following columns:
id, location_index
[, service, delivery, pickup, skills, priority]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Non-negative unique identifier of the job. |
|
location_index |
|
Non-negative identifier of the job location. |
|
service |
|
0 |
Job service duration, in seconds |
delivery |
|
Array of non-negative integers describing multidimensional quantities for delivery such as number of items, weight, volume etc.
|
|
pickup |
|
Array of non-negative integers describing multidimensional quantities for pickup such as number of items, weight, volume etc.
|
|
skills |
|
Array of non-negative integers defining mandatory skills. |
|
priority |
|
0 |
Priority level of the job
|
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
Vehicles SQL¶
A SELECT
statement that returns the following columns:
id, start_index, end_index
[, capacity, skills, tw_open, tw_close, speed_factor]
Column |
Type |
Description |
---|---|---|
id |
|
Non-negative unique identifier of the job. |
start_index |
|
Non-negative identifier of the vehicle start location. |
end_index |
|
Non-negative identifier of the vehicle end location. |
capacity |
|
Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc.
|
skills |
|
Array of non-negative integers defining mandatory skills. |
tw_open |
|
Time window opening time. |
tw_close |
|
Time window closing time. |
speed_factor |
|
Vehicle travel time multiplier. |
Note:
At least one of the
start_index
orend_index
shall be present.If
end_index
is omitted, the resulting route will stop at the last visited task, whose choice is determined by the optimization process.If
start_index
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_index
andend_index
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.
tw_open ≤ tw_close
Breaks SQL¶
A SELECT
statement that returns the following columns:
id, vehicle_id [, service]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Non-negative unique identifier of the break. (unique for the same vehicle). |
|
vehicle_id |
|
Non-negative unique identifier of the vehicle. |
|
service |
|
0 |
The break duration, in seconds |
Time Windows SQL¶
A SELECT
statement that returns the following columns:
id [, kind], tw_open, tw_close
Column |
Type |
Description |
---|---|---|
id |
|
Non-negative unique identifier of the job, pickup/delivery shipment, or break. |
kind |
|
Only required for shipments. Value in [‘p’, ‘d’] indicating whether the time window is for:
|
tw_open |
|
Time window opening time. |
tw_close |
|
Time window closing time. |
Note:
All timing are in seconds.
Every row must satisfy the condition:
tw_open ≤ tw_close
.It is up to users to decide how to describe time windows:
Relative values, e.g. [0, 14400] for a 4 hours time window starting at the beginning of the planning horizon. In that case all times reported in output with the arrival column are relative to the start of the planning horizon.
Absolute values, “real” timestamps. In that case all times reported in output with the arrival column can be interpreted as timestamps.
Time Matrix SQL¶
A SELECT
statement that returns the following columns:
start_index, end_index, agg_cost
Column |
Type |
Description |
---|---|---|
start_vid |
|
Identifier of the start node. |
end_vid |
|
Identifier of the end node. |
agg_cost |
|
Time to travel from |
Result Columns¶
Column |
Type |
Description |
---|---|---|
seq |
|
Sequential value starting from 1. |
vehicle_seq |
|
Sequential value starting from 1 for current vehicles. The \(n^{th}\) vehicle in the solution. |
vehicle_id |
|
Current vehicle identifier. |
step_seq |
|
Sequential value starting from 1 for the stops made by the current vehicle. The \(m^{th}\) stop of the current vehicle. |
step_type |
|
Kind of the step location the vehicle is at:
|
task_id |
|
Identifier of the task performed at this step.
|
arrival |
|
Estimated time of arrival at this step, in seconds. |
travel_time |
|
Cumulated travel time upon arrival at this step, in seconds |
service_time |
|
Service time at this step, in seconds |
waiting_time |
|
Waiting time upon arrival at this step, in seconds. |
load |
|
Vehicle load after step completion (with capacity constraints) |
Additional Example¶
Problem involving 2 jobs, using a single vehicle, corresponding to the VROOM Documentation Example 2.
SELECT *
FROM vrp_vroomJobs(
$jobs$
SELECT * FROM (
VALUES (1414, 2), (1515, 3)
) AS C(id, location_index)
$jobs$,
NULL,
$vehicles$
SELECT * FROM (
VALUES (1, 1, 4)
) AS C(id, start_index, end_index)
$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_vid, end_vid, agg_cost)
$matrix$
);
seq | vehicle_seq | vehicle_id | step_seq | step_type | task_id | arrival | travel_time | service_time | waiting_time | load
-----+-------------+------------+----------+-----------+---------+---------+-------------+--------------+--------------+------
1 | 1 | 1 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | {}
2 | 1 | 1 | 2 | 2 | 1414 | 2104 | 2104 | 0 | 0 | {}
3 | 1 | 1 | 3 | 2 | 1515 | 4359 | 4359 | 0 | 0 | {}
4 | 1 | 1 | 4 | 6 | -1 | 5461 | 5461 | 0 | 0 | {}
(4 rows)