VROOM - 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 vrpRouting
Might depend on a deprecated function of vrpRouting
Contents
Functions
Synopsis¶
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.
VROOM can solve several well-known types of vehicle routing problems (VRP).
TSP (travelling salesman problem)
CVRP (capacitated VRP)
VRPTW (VRP with time windows)
MDHVRPTW (multi-depot heterogeneous vehicle VRPTW)
PDPTW (pickup-and-delivery problem with TW)
VROOM can also solve any mix of the above problem types.
Characteristics¶
VROOM models a Vehicle Routing Problem with vehicles
, jobs
and shipments
.
The vehicles denote the resources that pick and/or deliver the jobs and shipments. They are characterised by:
Capacity on arbitrary number of metrics
Skills
Working hours
Driver breaks
Start and end defined on a per-vehicle basis
Start and end can be different
Open trip optimization (only start or only end defined)
The jobs denote the single-location pickup and/or delivery tasks, and the shipments denote the pickup-and-delivery tasks that should happen within the same route. They are characterised by:
Delivery/pickup amounts on arbitrary number of metrics
Service time windows
Service duration
Skills
Priority
Terminologies¶
Tasks: Either jobs or shipments are referred to as tasks.
Skills: Every task and vehicle may have some set of skills. A task can be served by only that vehicle which has all the skills of the task.
Priority: Tasks may have some priority assigned, which is useful when all tasks cannot be performed due to constraints, so the tasks with low priority are left unassigned.
Amount (for shipment), Pickup and delivery (for job): They denote the multidimensional quantities such as number of items, weights, volume, etc.
Capacity (for vehicle): Every vehicle may have some capacity, denoting the multidimensional quantities. A vehicle can serve only those sets of tasks such that the total sum of the quantity does not exceed the vehicle capacity, at any point of the route.
Time Window: An interval of time during which some activity can be performed, such as working hours of the vehicle, break of the vehicle, or service start time for a task.
Break: Array of time windows, denoting valid slots for the break start of a vehicle.
Setup time: Setup times serve as a mean to describe the time it takes to get started for a task at a given location. This models a duration that should not be re-applied for other tasks following at the same place. So the total “action time” for a task is
setup + service
upon arriving at a new location orservice
only if performing a new task at the previous vehicle location.Service time: The additional time to be spent by a vehicle while serving a task.
Travel time: The total time the vehicle travels during its route.
Waiting time: The total time the vehicle is idle, i.e. it is neither traveling nor servicing any task. It is generally the time spent by a vehicle waiting for a task service to open.
Inner Queries¶
Jobs SQL¶
A SELECT
statement that returns the following columns:
id, location_id
[, setup, service, delivery, pickup, skills, priority, data]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Positive unique identifier of the job. |
|
location_id |
|
Positive identifier of the job location. |
|
setup |
|
‘00:00:00’::INTERVAL or \(0\) |
Job setup duration. |
service |
|
‘00:00:00’::INTERVAL or \(0\) |
Job service duration. |
delivery |
|
Empty Array |
Array of non-negative integers describing multidimensional quantities for delivery such as number of items, weight, volume etc.
|
pickup |
|
Empty Array |
Array of non-negative integers describing multidimensional quantities for pickup such as number of items, weight, volume etc.
|
skills |
|
Empty Array |
Array of non-negative integers defining mandatory skills. |
priority |
|
0 |
Priority level of the job
|
data |
|
‘{}’::JSONB |
Any metadata information of the job. |
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
Shipments SQL¶
A SELECT
statement that returns the following columns:
id, p_location_id [, p_setup, p_service], d_location_id [, d_setup, d_service]
[, amount, skills, priority, p_data, d_data]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Positive unique identifier of the shipment. |
|
p_location_id |
|
Positive identifier of the pickup location. |
|
p_setup |
|
‘00:00:00’::INTERVAL or \(0\) |
Pickup setup duration. |
p_service |
|
‘00:00:00’::INTERVAL or \(0\) |
Pickup service duration. |
d_location_id |
|
Positive identifier of the delivery location. |
|
d_setup |
|
‘00:00:00’::INTERVAL or \(0\) |
Delivery setup duration. |
d_service |
|
‘00:00:00’::INTERVAL or \(0\) |
Delivery service duration. |
amount |
|
Empty Array |
Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc.
|
skills |
|
Empty Array |
Array of non-negative integers defining mandatory skills. |
priority |
|
0 |
Priority level of the shipment.
|
p_data |
|
‘{}’::JSONB |
Any metadata information of the pickup shipment. |
d_data |
|
‘{}’::JSONB |
Any metadata information of the delivery shipment. |
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
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]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Positive unique identifier of the vehicle. |
|
start_id |
|
Positive identifier of the vehicle start location. |
|
end_id |
|
Positive identifier of the vehicle end location. |
|
capacity |
|
Empty Array |
Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc.
|
skills |
|
Empty Array |
Array of non-negative integers defining mandatory skills. |
tw_open |
|
‘1970-01-01 00:00:00’::TIMESTAMP or \(0\) |
Time window opening time. |
tw_close |
|
‘2106-02-07 06:28:15’::TIMESTAMP or \(4294967295\) |
Time window closing time. |
speed_factor |
|
\(1.0\) |
Vehicle travel time multiplier.
|
max_tasks |
|
\(2147483647\) |
Maximum number of tasks in a route for the vehicle.
|
data |
|
‘{}’::JSONB |
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.
tw_open ≤ tw_close
Breaks SQL¶
A SELECT
statement that returns the following columns:
id, vehicle_id [, service, data]
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Positive unique identifier of the break. (unique for the same vehicle). |
|
vehicle_id |
|
Positive unique identifier of the vehicle. |
|
service |
|
‘00:00:00’::INTERVAL or \(0\) |
The break duration. |
data |
|
‘{}’::JSONB |
Any metadata information of the break. |
Time Windows SQL¶
A SELECT
statement that returns the following columns:
id [, kind], tw_open, tw_close
Column |
Type |
Description |
---|---|---|
id |
|
Positive unique identifier of the job, pickup/delivery shipment, or break. |
kind |
|
Only required for shipments time windows. 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 timings are in seconds when represented as an
INTEGER
.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_id, end_id, duration [, cost]
Column |
Type |
Default |
Description |
---|---|---|---|
start_id |
|
Identifier of the start node. |
|
end_id |
|
Identifier of the end node. |
|
duration |
|
Time to travel from |
|
cost |
|
duration |
Cost to 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 |
---|---|---|
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.
|
vehicle_data |
|
Metadata information of the vehicle |
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.
|
location_id |
|
Identifier of the task location.
|
task_data |
|
Metadata information of the task |
arrival |
|
Estimated time of arrival at this step. |
travel_time |
|
Travel time from previous
|
setup_time |
|
Setup time at this step. |
service_time |
|
Service time at this step. |
waiting_time |
|
Waiting time upon arrival at this step. |
departure |
|
Estimated time of arrival at this step.
|
load |
|
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,