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

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 or service 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]

Maximum values apply from vroom

setup and service

  • INTERVAL: make_interval(secs => 4294967295) and

  • ANY-INTEGER: \(4294967295\)

skills

  • \(2147483647\)

priority

  • \(100\)

Column

Type

Default

Description

id

ANY-INTEGER

Positive unique identifier of the job.

location_id

ANY-INTEGER

Positive unique identifier of the location of the job.

setup

ANY-INTERVAL

INTERVAL 0

The Job setup duration.

service

ANY-INTERVAL

INTERVAL 0

The Job service duration. Max value:

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)

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)

skills

ARRAY[ANY-INTEGER]

[]

Array of non-negative integers defining mandatory skills.

priority

INTEGER

\(0\)

Value range: \([0, 100]\)

data

JSONB

'{}'::JSONB

Any metadata information of the job.

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

  • INTERVAL: make_interval(secs => 4294967295) and

  • ANY-INTEGER: \(4294967295\)

skills

  • \(2147483647\)

priority

  • \(100\)

Column

Type

Default

Description

id

ANY-INTEGER

Positive unique identifier of the shipment.

p_location_id

ANY-INTEGER

Positive unique identifier of the pickup location.

p_setup

ANY-INTERVAL

INTERVAL 0

The pickup setup duration

p_service

ANY-INTERVAL

INTERVAL 0

The pickup service duration

p_data

JSONB

'{}'::JSONB

Any metadata information of the pickup.

d_location_id

ANY-INTEGER

Positive unique identifier of the pickup location.

d_setup

ANY-INTERVAL

INTERVAL 0

The pickup setup duration

d_service

ANY-INTERVAL

INTERVAL 0

The pickup service duration

d_data

JSONB

'{}'::JSONB

Any metadata information of the delivery.

amount

ARRAY[ANY-INTEGER]

[]

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[ANY-INTEGER]

[]

Array of non-negative integers defining mandatory skills.

  • \(values \leq 2147483647\)

priority

INTEGER

\(0\)

Value range: \([0, 100]\)

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

id

ANY-INTEGER

Positive unique identifier of the vehicle.

start_id

ANY-INTEGER

Positive unique identifier of the start location.

end_id

ANY-INTEGER

Positive unique identifier of the 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[ANY-INTEGER]

[]

Array of non-negative integers defining mandatory skills.

tw_open

ANY-TIMESTAMP

TW-OPEN-DEFAULT

Time window opening time.

  • tw_open leq tw_close

tw_close

ANY-TIMESTAMP

TW-CLOSE-DEFAULT

Time window closing time.

  • tw_open leq tw_close

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.

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

ANY-INTERVAL

INTERVAL 0

The break duration

data

JSONB

'{}'::JSONB

Any metadata information of the break.

Time Windows SQL

A SELECT statement that returns the following columns:

id, tw_open, tw_close
[kind]

Column

Type

Description

id

ANY-INTEGER

Positive unique identifier of the: job, pickup/delivery shipment, or break.

tw_open

ANY-TIMESTAMP

Time window opening time.

tw_close

ANY-TIMESTAMP

Time window closing time.

kind

CHAR

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

  • Pickup shipment, or

  • Delivery shipment.

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

ANY-INTERVAL

Time to travel from start_id to end_id

cost

ANY-INTERVAL

duration

Cost of 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.

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

BIGINT

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

ANY-TIMESTAMP

Estimated time of arrival at this step.

travel_time

ANY-INTERVAL

Travel time from previous step_seq to current step_seq.

  • 0: When step_type = 1

setup_time

ANY-INTERVAL

Setup time at this step.

service_time

ANY-INTERVAL

Service time at this step.

waiting_time

ANY-INTERVAL

Waiting time at this step.

departure

ANY-TIMESTAMP

Estimated time of departure 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,

See Also

Indices and tables