• Documentation → vrpRouting v0

• Supported Versions Latest (v0)

vrp_vroom - Experimental

vrp_vroom - Vehicle Routing Problem with VROOM, involving both jobs and shipments.

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 both jobs and shipments.

Signature

Summary

vrp_vroom(
  Jobs SQL, Jobs Time Windows SQL,
  Shipments SQL, Shipments Time Windows SQL,
  Vehicles SQL, Breaks SQL, Breaks Time Windows SQL,
  Matrix SQL [, exploration_level] [, timeout])  -- Experimental on v0.2

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, departure, load)

Optional parameters are named parameters and have a default value.

Using defaults

vrp_vroom(
  Jobs SQL, Jobs Time Windows SQL,
  Shipments SQL, Shipments Time Windows SQL,
  Vehicles SQL, Breaks SQL, Breaks Time Windows SQL,
  Matrix SQL)

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, departure, load)

Example: This example is based on the modified VROOM Data of the Sample Data network. The modification in the tables is mentioned at the end of the Sample Data.

SELECT *
FROM vrp_vroom(
  'SELECT * FROM vroom.jobs',
  'SELECT * FROM vroom.jobs_time_windows',
  '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 | {}        | 2021-09-02 09:05:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:05:00 | {30}
   2 |           1 |          1 | {}           |        2 |         5 |       1 |           1 | {}        | 2021-09-02 09:05:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:05:00 | {30}
   3 |           1 |          1 | {}           |        3 |         2 |       2 |           2 | {}        | 2021-09-02 09:05:50 | 00:00:50    | 00:00:00   | 00:04:10     | 00:15:00     | 2021-09-02 09:25:00 | {30}
   4 |           1 |          1 | {}           |        4 |         3 |       5 |           2 | {}        | 2021-09-02 09:25:00 | 00:00:00    | 00:00:00   | 00:37:30     | 03:17:30     | 2021-09-02 13:20:00 | {40}
   5 |           1 |          1 | {}           |        5 |         3 |       3 |           1 | {}        | 2021-09-02 13:20:50 | 00:00:50    | 00:00:00   | 00:37:30     | 00:00:00     | 2021-09-02 13:58:20 | {60}
   6 |           1 |          1 | {}           |        6 |         4 |       5 |           2 | {}        | 2021-09-02 13:59:10 | 00:00:50    | 00:00:00   | 00:37:30     | 00:03:45     | 2021-09-02 14:40:25 | {50}
   7 |           1 |          1 | {}           |        7 |         4 |       3 |           2 | {}        | 2021-09-02 14:40:25 | 00:00:00    | 00:00:00   | 00:37:30     | 00:03:20     | 2021-09-02 15:21:15 | {30}
   8 |           1 |          1 | {}           |        8 |         6 |      -1 |           1 | {}        | 2021-09-02 15:22:05 | 00:00:50    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 15:22:05 | {30}
   9 |           1 |          1 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 00:03:20    | 00:00:00   | 02:34:10     | 03:39:35     | 1970-01-01 00:00:00 | {}
  10 |           2 |          2 | {}           |        1 |         1 |      -1 |           1 | {}        | 2021-09-02 09:04:35 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:04:35 | {70}
  11 |           2 |          2 | {}           |        2 |         5 |       2 |           1 | {}        | 2021-09-02 09:04:35 | 00:00:00    | 00:00:00   | 00:00:10     | 00:00:00     | 2021-09-02 09:04:45 | {70}
  12 |           2 |          2 | {}           |        3 |         2 |       5 |           4 | {}        | 2021-09-02 09:06:00 | 00:01:15    | 00:00:00   | 00:04:10     | 00:11:05     | 2021-09-02 09:21:15 | {70}
  13 |           2 |          2 | {}           |        4 |         2 |       3 |           3 | {}        | 2021-09-02 09:22:05 | 00:00:50    | 00:00:00   | 00:04:10     | 00:23:20     | 2021-09-02 09:49:35 | {70}
  14 |           2 |          2 | {}           |        5 |         2 |       4 |           3 | {}        | 2021-09-02 09:49:35 | 00:00:00    | 00:00:00   | 00:04:10     | 00:09:10     | 2021-09-02 10:02:55 | {70}
  15 |           2 |          2 | {}           |        6 |         6 |      -1 |           3 | {}        | 2021-09-02 10:02:55 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 10:02:55 | {70}
  16 |           2 |          2 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 00:02:05    | 00:00:00   | 00:12:40     | 00:43:35     | 1970-01-01 00:00:00 | {}
  17 |           3 |          3 | {}           |        1 |         1 |      -1 |           1 | {}        | 2021-09-02 09:00:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:00:00 | {20}
  18 |           3 |          3 | {}           |        2 |         5 |       3 |           1 | {}        | 2021-09-02 09:00:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:00:00 | {20}
  19 |           3 |          3 | {}           |        3 |         2 |       1 |           1 | {}        | 2021-09-02 09:00:00 | 00:00:00    | 00:00:00   | 00:04:10     | 01:00:25     | 2021-09-02 10:04:35 | {20}
  20 |           3 |          3 | {}           |        4 |         3 |       4 |           1 | {}        | 2021-09-02 10:04:35 | 00:00:00    | 00:00:00   | 00:37:30     | 00:41:40     | 2021-09-02 11:23:45 | {40}
  21 |           3 |          3 | {}           |        5 |         4 |       4 |           4 | {}        | 2021-09-02 11:25:00 | 00:01:15    | 00:00:00   | 00:37:30     | 00:03:45     | 2021-09-02 12:06:15 | {20}
  22 |           3 |          3 | {}           |        6 |         6 |      -1 |           1 | {}        | 2021-09-02 12:07:30 | 00:01:15    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 12:07:30 | {20}
  23 |           3 |          3 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 00:02:30    | 00:00:00   | 01:19:10     | 01:45:50     | 1970-01-01 00:00:00 | {}
  24 |           4 |          4 | {}           |        1 |         1 |      -1 |           3 | {}        | 2021-09-02 09:04:10 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:04:10 | {0}
  25 |           4 |          4 | {}           |        2 |         5 |       4 |           1 | {}        | 2021-09-02 09:04:10 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 09:04:10 | {0}
  26 |           4 |          4 | {}           |        3 |         3 |       2 |           5 | {}        | 2021-09-02 09:04:35 | 00:00:25    | 00:00:00   | 00:37:30     | 00:01:40     | 2021-09-02 09:43:45 | {10}
  27 |           4 |          4 | {}           |        4 |         3 |       1 |           3 | {}        | 2021-09-02 09:44:10 | 00:00:25    | 00:00:00   | 00:37:30     | 00:00:00     | 2021-09-02 10:21:40 | {20}
  28 |           4 |          4 | {}           |        5 |         4 |       2 |           6 | {}        | 2021-09-02 10:23:10 | 00:01:30    | 00:00:00   | 00:37:30     | 00:00:00     | 2021-09-02 11:00:40 | {10}
  29 |           4 |          4 | {}           |        6 |         4 |       1 |           5 | {}        | 2021-09-02 11:02:31 | 00:01:51    | 00:00:00   | 00:37:30     | 04:52:54     | 2021-09-02 16:32:55 | {0}
  30 |           4 |          4 | {}           |        7 |         6 |      -1 |           3 | {}        | 2021-09-02 16:33:20 | 00:00:25    | 00:00:00   | 00:00:00     | 00:00:00     | 2021-09-02 16:33:20 | {0}
  31 |           4 |          4 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 00:04:36    | 00:00:00   | 02:30:00     | 04:54:34     | 1970-01-01 00:00:00 | {}
  32 |           0 |          0 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 00:12:31    | 00:00:00   | 06:36:00     | 11:03:34     | 1970-01-01 00:00:00 | {}
(32 rows)

Parameters

Parameter	Type	Description
Jobs SQL	TEXT	Jobs SQL query describing the single-location pickup and/or delivery tasks.
Jobs Time Windows SQL	TEXT	Time Windows SQL query describing valid slots for job service start.
Shipments SQL	TEXT	Shipments SQL query describing pickup and delivery tasks that should happen within same route.
Shipments Time Windows SQL	TEXT	Time Windows SQL query describing valid slots for pickup and delivery service start.
Vehicles SQL	TEXT	Vehicles SQL query describing the available vehicles.
Breaks SQL	TEXT	Breaks SQL query describing the driver breaks.
Breaks Time Windows SQL	TEXT	Time Windows SQL query describing valid slots for break start.
Matrix SQL	TEXT	Time Matrix SQL query containing the distance or travel times between the locations.

Optional Parameters

Parameter	Type	Default	Description
exploration_level	INTEGER	\(5\)	Exploration level to use while solving. Ranges from [0, 5] A smaller exploration level gives faster result.
timeout	INTERVAL	‘-00:00:01’::INTERVAL	Timeout value to stop the solving process. Gives the best possible solution within a time limit. Note that some additional seconds may be required to return back the data. Any negative timeout value is ignored.

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	ANY-INTEGER		Positive unique identifier of the job.
location_id	ANY-INTEGER		Positive identifier of the job location.
setup	INTERVAL	‘00:00:00’::INTERVAL	Job setup duration.
service	INTERVAL	‘00:00:00’::INTERVAL	Job service duration.
delivery	ARRAY[ANY-INTEGER]	Empty Array	Array of non-negative integers describing multidimensional quantities for delivery such as number of items, weight, volume etc. All jobs must have the same value of array_length(delivery, 1)
pickup	ARRAY[ANY-INTEGER]	Empty Array	Array of non-negative integers describing multidimensional quantities for pickup such as number of items, weight, volume etc. All jobs must have the same value of array_length(pickup, 1)
skills	ARRAY[INTEGER]	Empty Array	Array of non-negative integers defining mandatory skills.
priority	INTEGER	0	Priority level of the job Ranges from [0, 100]
data	JSONB	‘{}’::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	ANY-INTEGER		Positive unique identifier of the shipment.
p_location_id	ANY-INTEGER		Positive identifier of the pickup location.
p_setup	INTERVAL	‘00:00:00’::INTERVAL	Pickup setup duration.
p_service	INTERVAL	‘00:00:00’::INTERVAL	Pickup service duration.
d_location_id	ANY-INTEGER		Positive identifier of the delivery location.
d_setup	INTERVAL	‘00:00:00’::INTERVAL	Delivery setup duration.
d_service	INTERVAL	‘00:00:00’::INTERVAL	Delivery service duration.
amount	ARRAY[ANY-INTEGER]	Empty Array	Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc. All shipments must have the same value of array_length(amount, 1)
skills	ARRAY[INTEGER]	Empty Array	Array of non-negative integers defining mandatory skills.
priority	INTEGER	0	Priority level of the shipment. Ranges from [0, 100]
p_data	JSONB	‘{}’::JSONB	Any metadata information of the pickup shipment.
d_data	JSONB	‘{}’::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	ANY-INTEGER		Positive unique identifier of the vehicle.
start_id	ANY-INTEGER		Positive identifier of the vehicle start location.
end_id	ANY-INTEGER		Positive identifier of the vehicle end location.
capacity	ARRAY[ANY-INTEGER]	Empty Array	Array of non-negative integers describing multidimensional quantities such as number of items, weight, volume etc. All vehicles must have the same value of array_length(capacity, 1)
skills	ARRAY[INTEGER]	Empty Array	Array of non-negative integers defining mandatory skills.
tw_open	TIMESTAMP	‘1970-01-01 00:00:00’::TIMESTAMP	Time window opening time.
tw_close	TIMESTAMP	‘2106-02-07 06:28:15’::TIMESTAMP	Time window closing time.
speed_factor	ANY-NUMERICAL	\(1.0\)	Vehicle travel time multiplier. Max value of speed factor for a vehicle shall not be greater than 5 times the speed factor of any other vehicle.
max_tasks	INTEGER	\(2147483647\)	Maximum number of tasks in a route for the vehicle. A job, pickup, or delivery is counted as a single task.
data	JSONB	‘{}’::JSONB	Any metadata information of the vehicle.

Note:

• At least one of the start_id or end_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 and end_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	ANY-INTEGER		Positive unique identifier of the break. (unique for the same vehicle).
vehicle_id	ANY-INTEGER		Positive unique identifier of the vehicle.
service	INTERVAL	‘00:00:00’::INTERVAL	The break duration.
data	JSONB	‘{}’::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	ANY-INTEGER	Positive unique identifier of the job, pickup/delivery shipment, or break.
kind	CHAR	Only required for shipments time windows. Value in [‘p’, ‘d’] indicating whether the time window is for: Pickup shipment, or Delivery shipment.
tw_open	TIMESTAMP	Time window opening time.
tw_close	TIMESTAMP	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	ANY-INTEGER		Identifier of the start node.
end_id	ANY-INTEGER		Identifier of the end node.
duration	INTERVAL		Time to travel from start_id to end_id
cost	INTEGER	duration	Cost to travel from start_id to end_id

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	BIGINT	Sequential value starting from 1.
vehicle_seq	BIGINT	Sequential value starting from 1 for current vehicles. The \(n^{th}\) vehicle in the solution. 0: Summary row for the complete problem
vehicle_id	BIGINT	Current vehicle identifier. -1: Vehicle denoting all the unallocated tasks. 0: Summary row for the complete problem
vehicle_data	JSONB	Metadata information of the vehicle
step_seq	BIGINT	Sequential value starting from 1 for the stops made by the current vehicle. The \(m^{th}\) stop of the current vehicle. 0: Summary row
step_type	INTEGER	Kind of the step location the vehicle is at: 0: Summary row 1: Starting location 2: Job location 3: Pickup location 4: Delivery location 5: Break location 6: Ending location
task_id	BIGINT	Identifier of the task performed at this step. 0: Summary row -1: If the step is starting/ending location.
location_id	BIGINT	Identifier of the task location. 0: Summary row
task_data	JSONB	Metadata information of the task
arrival	TIMESTAMP	Estimated time of arrival at this step.
travel_time	INTERVAL	Travel time from previous step_seq to current step_seq. 0: When step_type = 1
setup_time	INTERVAL	Setup time at this step.
service_time	INTERVAL	Service time at this step.
waiting_time	INTERVAL	Waiting time upon arrival at this step.
departure	TIMESTAMP	Estimated time of arrival at this step. \(arrival + service\_time + waiting\_time\).
load	BIGINT	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 and waiting_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 and waiting_time denote the total time for the complete problem,

Additional Example

Problem involving 2 jobs and 1 shipment, using a single vehicle, similar to the VROOM Documentation Example 2 with a shipment.

SELECT *
FROM vrp_vroom(
  $jobs$
    SELECT * FROM (
      VALUES (1414, 2), (1515, 3)
    ) AS C(id, location_id)
  $jobs$,
  NULL,
  $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 start_id, end_id, make_interval(secs => duration) AS duration 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 | {}        | 1970-01-01 00:00:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 00:00:00 | {}
   2 |           1 |          1 | {}           |        2 |         3 |     100 |           1 | {}        | 1970-01-01 00:00:00 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 00:00:00 | {}
   3 |           1 |          1 | {}           |        3 |         2 |    1414 |           2 | {}        | 1970-01-01 00:35:04 | 00:35:04    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 00:35:04 | {}
   4 |           1 |          1 | {}           |        4 |         2 |    1515 |           3 | {}        | 1970-01-01 01:12:39 | 00:37:35    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 01:12:39 | {}
   5 |           1 |          1 | {}           |        5 |         4 |     100 |           4 | {}        | 1970-01-01 01:31:01 | 00:18:22    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 01:31:01 | {}
   6 |           1 |          1 | {}           |        6 |         6 |      -1 |           4 | {}        | 1970-01-01 01:31:01 | 00:00:00    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 01:31:01 | {}
   7 |           1 |          1 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 01:31:01    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 00:00:00 | {}
   8 |           0 |          0 | {}           |        0 |         0 |       0 |           0 | {}        | 1970-01-01 00:00:00 | 01:31:01    | 00:00:00   | 00:00:00     | 00:00:00     | 1970-01-01 00:00:00 | {}
(8 rows)

See Also

• VROOM - Category (Experimental)

• The queries use the Sample Data network.

• Wikipedia: Vehicle Routing problems

• VROOM: Vehicle Routing Open-source Optimization Machine

• VROOM API Documentation

Indices and tables

• Index

• Search Page