Vehicle Routing Functions - 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 pgRouting

• Might depend on a deprecated function of pgRouting

Introduction¶

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,

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

Parameters¶

Pick & deliver¶

Column

Type

Description

Orders SQL

TEXT

Orders SQL as described below.

Vehicles SQL

TEXT

Vehicles SQL as described below.

Column

Type

Description

Orders SQL

TEXT

Orders SQL as described below.

Vehicles SQL

TEXT

Vehicles SQL as described below.

Matrix SQL

TEXT

Matrix SQL as described below.

Pick-Deliver optional parameters¶

Column

Type

Default

Description

factor

NUMERIC

1

Travel time multiplier. See Factor handling

max_cycles

INTEGER

10

Maximum number of cycles to perform on the optimization.

initial_sol

INTEGER

4

Initial solution to be used.

• 1 One order per truck

• 2 Push front order.

• 3 Push back order.

• 4 Optimize insert.

• 5 Push back order that allows more orders to be inserted at the back

• 6 Push front order that allows more orders to be inserted at the front

Inner Queries¶

Orders SQL¶

Common columns for the orders SQL in both implementations:

Column

Type

Description

id

ANY-INTEGER

Identifier of the pick-delivery order pair.

demand

ANY-NUMERICAL

Number of units in the order

p_open

ANY-NUMERICAL

The time, relative to 0, when the pickup location opens.

p_close

ANY-NUMERICAL

The time, relative to 0, when the pickup location closes.

[p_service]

ANY-NUMERICAL

• When missing: 0 time units are used

d_open

ANY-NUMERICAL

The time, relative to 0, when the delivery location opens.

d_close

ANY-NUMERICAL

The time, relative to 0, when the delivery location closes.

[d_service]

ANY-NUMERICAL

• When missing: 0 time units are used

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

For pgr_pickDeliver - Experimental the pickup and delivery identifiers of the locations are needed:

Column

Type

Description

p_node_id

ANY-INTEGER

The node identifier of the pickup, must match a vertex identifier in the Matrix SQL.

d_node_id

ANY-INTEGER

The node identifier of the delivery, must match a vertex identifier in the Matrix SQL.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

For pgr_pickDeliverEuclidean - Experimental the $$(x, y)$$ values of the locations are needed:

Column

Type

Description

p_x

ANY-NUMERICAL

$$x$$ value of the pick up location

p_y

ANY-NUMERICAL

$$y$$ value of the pick up location

d_x

ANY-NUMERICAL

$$x$$ value of the delivery location

d_y

ANY-NUMERICAL

$$y$$ value of the delivery location

Where:

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Vehicles SQL¶

Common columns for the vehicles SQL in both implementations:

Column

Type

Description

id

ANY-NUMERICAL

Identifier of the vehicle.

capacity

ANY-NUMERICAL

Maiximum capacity units

start_open

ANY-NUMERICAL

The time, relative to 0, when the starting location opens.

start_close

ANY-NUMERICAL

The time, relative to 0, when the starting location closes.

[start_service]

ANY-NUMERICAL

• When missing: A duration of $$0$$ time units is used.

[end_open]

ANY-NUMERICAL

The time, relative to 0, when the ending location opens.

• When missing: The value of start_open is used

[end_close]

ANY-NUMERICAL

The time, relative to 0, when the ending location closes.

• When missing: The value of start_close is used

[end_service]

ANY-NUMERICAL

• When missing: A duration in start_service is used.

For pgr_pickDeliver - Experimental the starting and ending identifiers of the locations are needed:

Column

Type

Description

start_node_id

ANY-INTEGER

The node identifier of the start location, must match a vertex identifier in the Matrix SQL.

[end_node_id]

ANY-INTEGER

The node identifier of the end location, must match a vertex identifier in the Matrix SQL.

• When missing: end_node_id is used.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

For pgr_pickDeliverEuclidean - Experimental the $$(x, y)$$ values of the locations are needed:

Column

Type

Description

start_x

ANY-NUMERICAL

$$x$$ value of the starting location

start_y

ANY-NUMERICAL

$$y$$ value of the starting location

[end_x]

ANY-NUMERICAL

$$x$$ value of the ending location

• When missing: start_x is used.

[end_y]

ANY-NUMERICAL

$$y$$ value of the ending location

• When missing: start_y is used.

Where:

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Matrix SQL¶

Set of (start_vid, end_vid, agg_cost)

Column

Type

Description

start_vid

BIGINT

Identifier of the starting vertex.

end_vid

BIGINT

Identifier of the ending vertex.

agg_cost

FLOAT

Aggregate cost from start_vid to end_vid.

Return columns¶

RETURNS SET OF
(seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
travel_time, arrival_time, wait_time, service_time,  departure_time)
UNION
(summary row)


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.

• Value $$-2$$ indicates it is the summary row.

vehicle_id

BIGINT

Current vehicle identifier.

• Sumary row has the total capacity violations.

stop_seq

INTEGER

Sequential value starting from 1 for the stops made by the current vehicle. The $$m_{th}$$ stop of the current vehicle.

• Sumary row has the total time windows violations.

• A time window violation happens when arriving after the location has closed.

stop_type

INTEGER

• Kind of stop location the vehicle is at

• $$-1$$: at the solution summary row

• $$1$$: Starting location

• $$2$$: Pickup location

• $$3$$: Delivery location

• $$6$$: Ending location and indicates the vehicle’s summary row

order_id

BIGINT

Pickup-Delivery order pair identifier.

• Value $$-1$$: When no order is involved on the current stop location.

cargo

FLOAT

Cargo units of the vehicle when leaving the stop.

• Value $$-1$$ on solution summary row.

travel_time

FLOAT

Travel time from previous stop_seq to current stop_seq.

• Summary has the total traveling time:

• The sum of all the travel_time.

arrival_time

FLOAT

Time spent waiting for current location to open.

• $$-1$$: at the solution summary row.

• $$0$$: at the starting location.

wait_time

FLOAT

Time spent waiting for current location to open.

• Summary row has the total waiting time:

• The sum of all the wait_time.

service_time

FLOAT

Service duration at current location.

• Summary row has the total service time:

• The sum of all the service_time.

departure_time

FLOAT

• The time at which the vehicle departs from the stop.

• $$arrival\_time + wait\_time + service\_time$$.

• The ending location has the total time used by the current vehicle.

• Summary row has the total solution time:

• $$total\ traveling\ time + total\ waiting\ time + total\ service\ time$$.

Summary Row¶

Column

Type

Description

seq

INTEGER

Continues the sequence

vehicle_seq

INTEGER

Value $$-2$$ indicates it is the summary row.

vehicle_id

BIGINT

total capacity violations:

stop_seq

INTEGER

total time windows violations:

• A time window violation happens when arriving after the location has closed.

stop_type

INTEGER

$$-1$$

order_id

BIGINT

$$-1$$

cargo

FLOAT

$$-1$$

travel_time

FLOAT

total traveling time:

• The sum of all the travel_time.

arrival_time

FLOAT

$$-1$$

wait_time

FLOAT

total waiting time:

• The sum of all the wait_time.

service_time

FLOAT

total service time:

• The sum of all the service_time.

departure_time

FLOAT

Summary row has the total solution time:

• $$total\ traveling\ time + total\ waiting\ time + total\ service\ time$$.

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¶

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 in boxes, a conversion of kg of feathers to number of boxes is needed.

• If the vehicle’s capacity is measured in kg, a conversion of box of apples to kg is needed.

Showing how the 2 possible conversions can be done

Let: - $$f\_boxes$$: number of boxes needed 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 pgr_pickDeliverEuclidean - Experimental:

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

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

• When using pgr_pickDeliver - Experimental:

• 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. All time units have to be converted to a 0 reference and the same time units.

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.

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$$

0:00 am

minutes

$$9*60 = 54$$

$$16.5*60 = 990$$

10.5

9:00 am

hours

0

7.5

$$10.5 / 60 = 0.175$$

9:00 am

minutes

0

$$7.5*60 = 540$$

10.5

Factor handling¶

factor acts as a multiplier to convert from distance values to time units the matrix values or the euclidean values.

• When the values are already in the desired time units

• factor should be 1

• When factor > 1 the travel times are faster

• When factor < 1 the travel times are slower

Working with time units in seconds, and x/y in lat/lon: Factor: would depend on the location of the points and on the average velocity say 25m/s is the velocity.

Latitude

Conversion

Factor

45

1 longitude degree is (78846.81m)/(25m/s)

3153 s

0

1 longitude degree is (111319.46 m)/(25m/s)

4452 s

For the pgr_pickDeliver - Experimental:

Given $$v = d / t$$ therefore $$t = d / v$$ And the factor becomes $$1 / v$$

Where:

v:

Velocity

d:

Distance

t:

Time

For the following equivalences $$10m/s \approx 600m/min \approx 36 km/hr$$

Working with time units in seconds and the matrix been in meters: For a 1000m lenght value on the matrix:

Units

velocity

Conversion

Factor

Result

seconds

$$10 m/s$$

$$\frac{1}{10m/s}$$

$$0.1s/m$$

$$1000m * 0.1s/m = 100s$$

minutes

$$600 m/min$$

$$\frac{1}{600m/min}$$

$$0.0016min/m$$

$$1000m * 0.0016min/m = 1.6min$$

Hours

$$36 km/hr$$

$$\frac{1}{36 km/hr}$$

$$0.0277hr/km$$

$$1km * 0.0277hr/km = 0.0277hr$$