• Documentation → vrpRouting v0

• Supported Versions Latest (v0)

Concepts

General documentation

Vehicle Routing Problems VRP are NP-hard optimization problem, it generalises the travelling salesman problem (TSP).

• The objective of the VRP is to minimize the total route cost.

• There are several variants of the VRP problem,

vrpRouting does not try to implement all variants.

Characteristics

• Capacitated Vehicle Routing Problem CVRP where The vehicles have limited carrying capacity of the goods.

• Vehicle Routing Problem with Time Windows VRPTW where the locations have time windows within which the vehicle’s visits must be made.

• Vehicle Routing Problem with Pickup and Delivery VRPPD where a number of goods need to be moved from certain pickup locations to other delivery locations.

Limitations

• No multiple time windows for a location.

• Less vehicle used is considered better.

• Less total duration is better.

• Less wait time is better.

Pick & Delivery

Problem: CVRPPDTW Capacitated Pick and Delivery Vehicle Routing problem with Time Windows

• Times are relative to 0

• The vehicles

  • have start and ending service duration times.

  • have opening and closing times for the start and ending locations.

  • have a capacity.

• The orders

  • Have pick up and delivery locations.

  • Have opening and closing times for the pickup and delivery locations.

  • Have pickup and delivery duration service times.

  • have a demand request for moving goods from the pickup location to the delivery location.

• Time based calculations:

  • Travel time between customers is \(distance / speed\)

  • Pickup and delivery order pair is done by the same vehicle.

  • A pickup is done before the delivery.

Getting Started

This is a simple guide to walk you through the steps of getting started with vrpRouting. In this guide we will cover:

Create a routing Database

The first thing we need to do is create a database and load pgrouting in the database. Typically you will create a database for each project. Once you have a database to work in, your can load your data and build your application in that database. This makes it easy to move your project later if you want to to say a production server.

For Postgresql 9.2 and later versions

createdb mydatabase
psql mydatabase -c "create extension postgis"
psql mydatabase -c "create extension pgrouting"

Handling Parameters

To define a problem, several considerations have to be done, to get consistent results. This section gives an insight of how parameters are to be considered.

• Capacity and Demand Units Handling

• Locations

• Time Handling

• Factor Handling

Capacity and Demand Units Handling

The capacity of a vehicle, can be measured in:

• Volume units like \(m^3\).

• Area units like \(m^2\) (when no stacking is allowed).

• Weight units like \(kg\).

• Number of boxes that fit in the vehicle.

• Number of seats in the vehicle

The demand request of the pickup-deliver orders must use the same units as the units used in the vehicle’s capacity.

To handle problems like: 10 (equal dimension) boxes of apples and 5 kg of feathers that are to be transported (not packed in boxes).

If the vehicle’s capacity is measured by boxes, a conversion of kg of feathers to equivalent number of boxes is needed. If the vehicle’s capacity is measured by kg, a conversion of box of apples to equivalent number of kg is needed.

Showing how the 2 possible conversions can be done

Let: - \(f_boxes\): number of boxes that would be used for 1 kg of feathers. - \(a_weight\): weight of 1 box of apples.

Capacity Units	apples	feathers
boxes	10	\(5 * f\_boxes\)
kg	\(10 * a\_weight\)	5

Locations

• When using the Euclidean signatures:

  • The vehicles have \((x, y)\) pairs for start and ending locations.

  • The orders Have \((x, y)\) pairs for pickup and delivery locations.

• When using a matrix:

  • The vehicles have identifiers for the start and ending locations.

  • The orders have identifiers for the pickup and delivery locations.

  • All the identifiers are indices to the given matrix.

Time Handling

The times are relative to 0

Suppose that a vehicle’s driver starts the shift at 9:00 am and ends the shift at 4:30 pm and the service time duration is 10 minutes with 30 seconds.

All time units have to be converted

Meaning of 0	time units	9:00 am	4:30 pm	10 min 30 secs
0:00 am	hours	9	16.5	\(10.5 / 60 = 0.175\)
9:00 am	hours	0	7.5	\(10.5 / 60 = 0.175\)
0:00 am	minutes	\(9*60 = 54\)	\(16.5*60 = 990\)	10.5
9:00 am	minutes	0	\(7.5*60 = 540\)	10.5

Factor Handling

TBD

Group of Functions

TBD

Inner Queries

Pickup-Delivery Inner Queries

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-INTEGER	Identifier of a node.
agg_cost	ANY-NUMERICAL	Cost to travel from start_vid to end_vid

Orders SQL

Orders

A SELECT statement that returns the following columns:

id, amount

p_id, p_tw_open, p_tw_close, [p_service]

d_id, d_tw_open, d_tw_close, [d_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the pick-delivery order pair.
amount	ANY-NUMERICAL		Number of units in the order.
p_id	ANY-INTEGER		Identifier of the pickup node. Must match a node identifier in the Matrix SQL.
p_tw_open	ANY-INTEGER		The time, relative to 0, when the pickup location opens.
p_tw_close	ANY-INTEGER		The time, relative to 0, when the pickup location closes. \(p\_tw\_open < p\_tw\_close < 9223372036854775807\)
p_service	ANY-INTEGER	0	The duration of the loading at the pickup location.
d_id	ANY-INTEGER		Identifier of the delivery node. Must match a node identifier in the Matrix SQL.
d_tw_open	ANY-INTEGER		The time, relative to 0, when the delivery location opens.
d_tw_close	ANY-INTEGER		The time, relative to 0, when the delivery location closes. \(d\_tw\_open < d\_tw\_close <= 9223372036854775807\)
d_service	ANY-INTEGER	0	The duration of the unloading at the delivery location.

Euclidean Orders

A SELECT statement that returns the following columns:

id, amount

p_x, p_y, p_tw_open, p_tw_close, [p_service,]

d_x, d_y, d_tw_open, d_tw_close, [d_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the pick-delivery order pair.
amount	ANY-NUMERICAL		Number of units in the order.
p_x	ANY-NUMERICAL		\(x\) value of the pickup location.
p_y	ANY-NUMERICAL		\(y\) value of the pickup location.
p_tw_open	ANY-INTEGER		The time, relative to 0, when the pickup location opens.
p_tw_close	ANY-INTEGER		The time, relative to 0, when the pickup location closes. \(p\_tw\_open < p\_tw\_close < 9223372036854775807\)
p_service	ANY-INTEGER	0	The duration of the loading at the pickup location.
d_x	ANY-NUMERICAL		\(x\) value of the delivery location.
d_y	ANY-NUMERICAL		\(y\) value of the delivery location.
d_tw_open	ANY-INTEGER		The time, relative to 0, when the delivery location opens.
d_tw_close	ANY-INTEGER		The time, relative to 0, when the delivery location closes. \(d\_tw\_open < d\_tw\_close <= 9223372036854775807\)
d_service	ANY-INTEGER	0	The duration of the unloading at the delivery location.

Vehicles SQL

Vehicles

A SELECT statement that returns the following columns:

id, capacity, [speed,]

s_id, [s_tw_open, s_tw_close, s_service,]

[e_id, e_tw_open, e_tw_close, e_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the vehicle
capacity	ANY-INTEGER		Capacity of the vehicle. \(0 < capacity <= 4294967295\).
speed	ANY-NUMERICAL	1	Speed of the vehicle.
s_id	ANY-INTEGER		The node identifier of the starting location. Must match a node identifier in the Matrix SQL.
s_tw_open	ANY-INTEGER	0	The time, relative to 0, when the starting location opens.
s_tw_close	ANY-INTEGER	MAX-BIGINT	The time, relative to 0, when the starting location closes. \(s\_tw\_open < s\_tw\_close <= 9223372036854775807\)
s_service	ANY-INTEGER	0	Duration of any task at the starting location,
e_id	ANY-INTEGER	s_id	The node identifier of the ending location. Must match a node identifier in the Matrix SQL.
e_tw_open	ANY-INTEGER	s_tw_open	The time, relative to 0, when the ending location opens.
e_tw_close	ANY-INTEGER	s_tw_close	The time, relative to 0, when the ending location closes. \(e\_tw\_open < e\_tw\_close <= 9223372036854775807\)
e_service	ANY-INTEGER	s_service	The duration of any task at the ending location

Euclidean Vehicles

A SELECT statement that returns the following columns:

id, capacity, [speed,]

s_x, s_y, [s_tw_open, s_tw_close, s_service]

[e_x, e_y, e_tw_open, e_tw_close, e_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the vehicle.
capacity	ANY-INTEGER		Capacity of the vehicle. \(0 < capacity <= 4294967295\).
speed	ANY-NUMERICAL	1	Speed of the vehicle.
s_x	ANY-NUMERICAL		\(x\) value of the coordinate of the starting location.
s_y	ANY-NUMERICAL		\(y\) value of the coordinate of the starting location.
s_tw_open	ANY-INTEGER	0	The time, relative to 0, when the starting location opens.
s_tw_close	ANY-INTEGER	MAX-BIGINT	The time, relative to 0, when the starting location closes. \(s\_tw\_open < s\_tw\_close <= 9223372036854775807\)
s_service	ANY-INTEGER	0	Duration of any task at the ending location,
e_x	ANY-NUMERICAL		\(x\) value of the coordinate of the ending location.
e_y	ANY-NUMERICAL		\(y\) value of the coordinate of the ending location.
e_tw_open	ANY-INTEGER	s_tw_open	The time, relative to 0, when the ending location opens.
e_tw_close	ANY-INTEGER	s_tw_close	The time, relative to 0, when the ending location closes. \(e\_tw\_open < e\_tw\_close <= 9223372036854775807\)
e_service	ANY-INTEGER	s_service	The duration of any task at the ending location

Vroom Inner Queries

Vroom, because of the data types used internally, some maximum values apply.

For TIMESTAMP:

SELECT to_timestamp(0)::timestamp without time zone as ZERO_TIMESTAMP,
to_timestamp(4294967295)::timestamp without time zone AS MAX_TIMESTAMP;
   zero_timestamp    |    max_timestamp
---------------------+---------------------
 1970-01-01 00:00:00 | 2106-02-07 06:28:15
(1 row)

For INTERVAL:

SELECT make_interval(secs => 0) AS ZERO_INTERVAL,
make_interval(years => 136, months => 1, days => 6, hours=>6, mins => 28, secs => 15) AS MAX_INTERVAL1,
make_interval(secs => 4294967295) AS MAX_INTERVAL2;
 zero_interval |          max_interval1          | max_interval2
---------------+---------------------------------+---------------
 00:00:00      | 136 years 1 mon 6 days 06:28:15 | 1193046:28:15
(1 row)

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.

Vroom 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

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

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

General Time Windows SQL

A SELECT statement that returns the following columns:

id, tw_open, tw_close

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.

Note:

• All timings are in seconds when represented as an INTEGER.

• Every row must satisfy the condition: tw_open ≤ tw_close.

• Time windows can be interpreted by the users:

  • Relative values, e.g.

    • Let the beginning of the planning horizon \(0\).

    • for a 4 hour time window (\(4 * 3600 = 14400\) seconds) starting from the planning horizon

      • tw_open = \(0\)

      • tw_close = \(14400\)

    • Times reported in output relative to the start of the planning horizon.

  • Absolute values,

    • Let the beginning of the planning horizon 2019-07-30 08:00:00

    • for a 4 hour time window starting from the planning horizon

      • tw_open = 2019-07-30 08:00:00

      • tw_close = 2019-07-30 12:00:00

    • Times reported in output can be interpreted as TIMESTAMP.

Return columns & values

Pick-Deliver result columns

Results

Returns set of

seq, vehicle_number, vehicle_id, stop_seq, stop_type, stop_id, order_id, cargo,

travel_time, arrival_time, wait_time, service_time, departure_time

Column	Type	Description
seq	INTEGER	Sequential value starting from 1.
vehicle_seq	INTEGER	Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution.
vehicle_id	BIGINT	Current vehicle identifier.
stop_seq	INTEGER	Sequential value starting from 1 for the stops made by the current vehicle. The \(m_{th}\) stop of the current vehicle.
stop_type	INTEGER	Kind of stop location the vehicle is at: 1: Starting location 2: Pickup location 3: Delivery location 6: Ending location
stop_id	BIGINT	Identifier of the stop.
order_id	BIGINT	Pickup-Delivery order pair identifier. -1: When no order is involved on the current stop location.
cargo	BIGINT	Cargo units of the vehicle when leaving the stop.
travel_time	BIGINT	Travel time from previous stop_seq to current stop_seq. 0 When stop_type = 1
arrival_time	BIGINT	Previous departure_time plus current travel_time.
wait_time	BIGINT	Time spent waiting for current location to open.
service_time	BIGINT	Service time at current location.
departure_time	BIGINT	\(arrival\_time + wait\_time + service\_time\). When stop_type = 6 has the total_time used for the current vehicle.

Euclidean Results

Returns set of

seq, vehicle_seq, vehicle_id, stop_seq, stop_type, order_id, cargo,

travel_time, arrival_time, wait_time, service_time, departure_time

Column	Type	Description
seq	INTEGER	Sequential value starting from 1.
vehicle_seq	INTEGER	Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution.
vehicle_id	BIGINT	Current vehicle identifier.
stop_seq	INTEGER	Sequential value starting from 1 for the stops made by the current vehicle. The \(m_{th}\) stop of the current vehicle.
stop_type	INTEGER	Kind of stop location the vehicle is at: 1: Starting location 2: Pickup location 3: Delivery location 6: Ending location
order_id	BIGINT	Pickup-Delivery order pair identifier. -1: When no order is involved on the current stop location.
cargo	BIGINT	Cargo units of the vehicle when leaving the stop.
travel_time	BIGINT	Travel time from previous stop_seq to current stop_seq. 0 When stop_type = 1
arrival_time	BIGINT	Previous departure_time plus current travel_time.
wait_time	BIGINT	Time spent waiting for current location to open.
service_time	BIGINT	Service time at current location.
departure_time	BIGINT	\(arrival\_time + wait\_time + service\_time\). When stop_type = 6 has the total_time used for the current vehicle.

VROOM 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,

Performance

TBD

How to contribute

Wiki

• Edit an existing vrpRouting Wiki page.

Adding Functionaity to vrpRouting

Consult the developer’s documentation

Indices and tables

• Index

• Search Page