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 ANYINTEGER and ANYNUMERICAL
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
Pickup and delivery problem
pgr_pickDeliver  Experimental  Pickup & Delivery using a Cost Matrix
pgr_pickDeliverEuclidean  Experimental  Pickup & Delivery with Euclidean distances
Distribution problem
pgr_vrpOneDepot  Experimental  From a single depot, distributes orders
Introduction¶
Vehicle Routing Problems VRP are NPhard 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¶
Used in pgr_pickDeliverEuclidean  Experimental
Column 
Type 
Description 


Orders SQL as described below. 


Vehicles SQL as described below. 
Used in pgr_pickDeliver  Experimental
Column 
Type 
Description 


Orders SQL as described below. 


Vehicles SQL as described below. 


Matrix SQL as described below. 
PickDeliver optional parameters¶
Column 
Type 
Default 
Description 



1 
Travel time multiplier. See Factor handling 


10 
Maximum number of cycles to perform on the optimization. 


4 
Initial solution to be used.

Inner Queries¶
Orders SQL¶
Common columns for the orders SQL in both implementations:
Column 
Type 
Description 


ANYINTEGER 
Identifier of the pickdelivery order pair. 

ANYNUMERICAL 
Number of units in the order 

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

ANYNUMERICAL 
The time, relative to 0, when the pickup location closes. 
[ 
ANYNUMERICAL 
The duration of the loading at the pickup location.


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

ANYNUMERICAL 
The time, relative to 0, when the delivery location closes. 
[ 
ANYNUMERICAL 
The duration of the unloading at the delivery location.

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
For pgr_pickDeliver  Experimental the pickup and delivery identifiers of the locations are needed:
Column 
Type 
Description 


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

ANYINTEGER 
The node identifier of the delivery, must match a vertex identifier in the Matrix SQL. 
Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
For pgr_pickDeliverEuclidean  Experimental the \((x, y)\) values of the locations are needed:
Column 
Type 
Description 


ANYNUMERICAL 
\(x\) value of the pick up location 

ANYNUMERICAL 
\(y\) value of the pick up location 

ANYNUMERICAL 
\(x\) value of the delivery location 

ANYNUMERICAL 
\(y\) value of the delivery location 
Where:
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Vehicles SQL¶
Common columns for the vehicles SQL in both implementations:
Column 
Type 
Description 


ANYNUMERICAL 
Identifier of the vehicle. 

ANYNUMERICAL 
Maiximum capacity units 

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

ANYNUMERICAL 
The time, relative to 0, when the starting location closes. 
[ 
ANYNUMERICAL 
The duration of the loading at the starting location.

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

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

[ 
ANYNUMERICAL 
The duration of the loading at the ending location.

For pgr_pickDeliver  Experimental the starting and ending identifiers of the locations are needed:
Column 
Type 
Description 


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

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
For pgr_pickDeliverEuclidean  Experimental the \((x, y)\) values of the locations are needed:
Column 
Type 
Description 


ANYNUMERICAL 
\(x\) value of the starting location 

ANYNUMERICAL 
\(y\) value of the starting location 
[ 
ANYNUMERICAL 
\(x\) value of the ending location

[ 
ANYNUMERICAL 
\(y\) value of the ending location

Where:
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Matrix SQL¶
Set of (start_vid, end_vid, agg_cost)
Column 
Type 
Description 



Identifier of the starting vertex. 


Identifier of the ending vertex. 


Aggregate cost from 
Result 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 



Sequential value starting from 1. 


Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution.


BIGINT 
Current vehicle identifier.


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






PickupDelivery order pair identifier.



Cargo units of the vehicle when leaving the stop.



Travel time from previous



Time spent waiting for current location to open.



Time spent waiting for current location to open.



Service duration at current location.




Summary Row¶
Column 
Type 
Description 



Continues the sequence 


Value \(2\) indicates it is the summary row. 

BIGINT 
total capacity violations:


INTEGER 
total time windows violations:



\(1\) 


\(1\) 


\(1\) 


total traveling time:



\(1\) 


total waiting time:



total service time:



Summary row has the total solution 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 pickupdeliver 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 1When
factor
> 1 the travel times are fasterWhen
factor
< 1 the travel times are slower
For the pgr_pickDeliverEuclidean  Experimental:
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\) 
See Also¶
The queries use the Sample Data network.
Indices and tables