GSoC '21: Detailed description and signature of the new VROOM category functions to be added in vrpRouting

[krashish8]

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.

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

VROOM Category functions

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

   vrp_vroom(
     Jobs SQL, Jobs Time Windows SQL,
     Shipments SQL, Shipments 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)
   

2. vrp_vroomJobs - Vehicle Routing Problem with VROOM, involving only jobs.

   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)
   

3. vrp_vroomShipments - Vehicle Routing Problem with VROOM, involving only shipments.

   vrp_vroomShipments(
     Shipments SQL, Shipments 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)
   

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

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

Shipments SQL

A SELECT statement that returns the following columns:
  id, p_location_index [, p_service], d_location_index [, d_service]
  [, amount, skills, priority]

Column	Type	Default	Description
id	ANY-INTEGER	-	Non-negative unique identifier of the shipment.
p_location_index	ANY-INTEGER	-	Non-negative identifier of the pickup location.
p_service	INTEGER	0	Pickup service duration, in seconds
d_location_index	ANY-INTEGER	-	Non-negative identifier of the delivery location.
d_service	INTEGER	0	Delivery service duration, in seconds
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[INTEGER]	-	Array of non-negative integers defining mandatory skills.
priority	INTEGER	0	Priority level of the shipment, 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 elative 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_vid, end_vid, agg_cost

Column	Type	Description
start_vid	ANY-INTEGER	Identifier of a node.
end_vid	ANY-NUMERICAL	Identifier of a node
agg_cost	INTEGER	Time to travel from start_vid to end_vid

Result Columns

Returns SET OF
(seq, vehicle_seq, vehicle_id, step_seq, step_type, task_id, 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 nth 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 mth 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. It is -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)