• Documentation → vrpRouting v0

• Supported Versions Latest (v0)

vrp_pgr_pickDeliver - Experimental

vrp_pgr_pickDeliver - Pickup and delivery Vehicle Routing Problem

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

Availability

Version 0.0.0

• New experimental function

  • Ported vrp_pgr_pickDeliver from pgRouting v3.1.3

Synopsis

Problem: Distribute and optimize the pickup-delivery pairs into a fleet of vehicles.

• Optimization problem is NP-hard.

• pickup and Delivery with time windows.

• All vehicles are equal.

  • Same Starting location.

  • Same Ending location which is the same as Starting location.

  • All vehicles travel at the same speed.

• A customer is for doing a pickup or doing a deliver.

  • has an open time.

  • has a closing time.

  • has a service time.

  • has an (x, y) location.

• There is a customer where to deliver a pickup.

  • travel time between customers is distance / speed

  • pickup and delivery pair is done with the same vehicle.

  • A pickup is done before the delivery.

Characteristics

• All trucks depart at time 0.

• No multiple time windows for a location.

• Less vehicle used is considered better.

• Less total duration is better.

• Less wait time is better.

• the algorithm will raise an exception when

  • If there is a pickup-deliver pair than violates time window

  • The speed, max_cycles, ma_capacity have illegal values

• Six different initial will be optimized - the best solution found will be result

Signature

pgr_pickDeliver(

Orders SQL, Vehicles SQL, Matrix SQL

[factor, max_cycles, initial_sol]

RETURNS SET OF

seq, vehicle_number, vehicle_id, stop, order_id, stop_type, cargo,

travel_time, arrival_time, wait_time, service_time, departure_time

Parameters

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.

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

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.

Vehicles SQL

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

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

Result Columns

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.

Example

This example use the following data:

SELECT * FROM vrp_pgr_pickDeliver(
    $$ SELECT * FROM orders_1 ORDER BY id $$,
    $$ SELECT * FROM vehicles_1 ORDER BY id$$,
    $$ SELECT start_vid, end_vid, agg_cost::INTEGER  FROM pgr_dijkstraCostMatrix(
        'SELECT * FROM edge_table ',
        (SELECT array_agg(id) FROM (SELECT p_id AS id FROM orders_1
        UNION
        SELECT d_id FROM orders_1
        UNION
        SELECT s_id FROM vehicles_1) a))
    $$
);
 seq | vehicle_seq | vehicle_id | stop_seq | stop_type | stop_id | order_id | cargo | travel_time | arrival_time | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+---------+----------+-------+-------------+--------------+-----------+--------------+----------------
   1 |           1 |          1 |        1 |         1 |       6 |       -1 |     0 |           0 |            0 |         1 |            0 |              1
   2 |           1 |          1 |        2 |         2 |       5 |        3 |    30 |           1 |            2 |         0 |            3 |              5
   3 |           1 |          1 |        3 |         3 |      11 |        3 |     0 |           2 |            7 |         0 |            3 |             10
   4 |           1 |          1 |        4 |         2 |       9 |        2 |    20 |           2 |           12 |         0 |            2 |             14
   5 |           1 |          1 |        5 |         3 |       4 |        2 |     0 |           1 |           15 |         0 |            3 |             18
   6 |           1 |          1 |        6 |         6 |       6 |       -1 |     0 |           2 |           20 |         0 |            0 |             20
   7 |           2 |          2 |        1 |         1 |       6 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   8 |           2 |          2 |        2 |         2 |       3 |        1 |    10 |           3 |            3 |         0 |            3 |              6
   9 |           2 |          2 |        3 |         3 |       8 |        1 |     0 |           3 |            9 |         0 |            3 |             12
  10 |           2 |          2 |        4 |         6 |       6 |       -1 |     0 |           2 |           14 |         0 |            0 |             14
  11 |          -2 |          0 |        0 |        -1 |      -1 |       -1 |    -1 |          16 |           -1 |         1 |           17 |             34
(11 rows)

See Also

• Vehicle Routing Functions - Category (Experimental)

• The queries use the Sample Data network.

Indices and tables

• Index

• Search Page