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

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.

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.

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

ANY-INTEGER

Non-negative unique identifier of the job.

location_index

ANY-INTEGER

Non-negative identifier of the job location.

service

INTEGER

0

Job service duration, in seconds

delivery

ARRAY[ANY-INTEGER]

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]

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]

Array of non-negative integers defining mandatory skills.

priority

INTEGER

0

Priority level of the job

  • Ranges from [0, 100]

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

ANY-INTEGER

Non-negative unique identifier of the job.

start_index

ANY-INTEGER

Non-negative identifier of the vehicle start location.

end_index

ANY-INTEGER

Non-negative identifier of the vehicle end location.

capacity

ARRAY[ANY-INTEGER]

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]

Array of non-negative integers defining mandatory skills.

tw_open

INTEGER

Time window opening time.

tw_close

INTEGER

Time window closing time.

speed_factor

ANY-NUMERICAL

Vehicle travel time multiplier.

Note:

  • At least one of the start_index or end_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 and end_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

ANY-INTEGER

Non-negative unique identifier of the break. (unique for the same vehicle).

vehicle_id

ANY-INTEGER

Non-negative unique identifier of the vehicle.

service

INTEGER

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

ANY-INTEGER

Non-negative unique identifier of the job, pickup/delivery shipment, or break.

kind

CHAR

Only required for shipments. Value in [‘p’, ‘d’] indicating whether the time window is for:

  • Pickup shipment, or

  • Delivery shipment.

tw_open

INTEGER

Time window opening time.

tw_close

INTEGER

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

ANY-INTEGER

Identifier of the start node.

end_vid

ANY-INTEGER

Identifier of the end node.

agg_cost

INTEGER

Time to travel from start_vid to end_vid

Result Columns

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.

vehicle_id

BIGINT

Current vehicle identifier.

step_seq

BIGINT

Sequential value starting from 1 for the stops made by the current vehicle. The \(m^{th}\) stop of the current vehicle.

step_type

INTEGER

Kind of the step location the vehicle is at:

  • 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.

  • -1: If the step is starting/ending location.

arrival

INTEGER

Estimated time of arrival at this step, in seconds.

travel_time

INTEGER

Cumulated travel time upon arrival at this step, in seconds

service_time

INTEGER

Service time at this step, in seconds

waiting_time

INTEGER

Waiting time upon arrival at this step, in seconds.

load

BIGINT

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)