• Documentation → vrpRouting 0

• Supported Versions Latest (0.0)

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

vrp_pgr_pickDeliver(Orders SQL, Vehicles SQL, Matrix SQL [, factor, max_cycles, initial_sol])
RETURNS SET OF:
    seq, vehicle_seq, vehicle_id,
    stop_seq, stop_type, stop_id, order_id
    cargo, travel_time, arrival_time, wait_time, service_time, departure_time

Parameters

Column	Type	Default	Description
Orders SQL	TEXT		Orders SQL query contianing the orders to be processed.
Vehicles SQL	TEXT		Vehicles SQL query containing the vehicles to be used.
Matrix SQL	TEXT		Time Matrix SQL query containing the distance or travel times.
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, demand
p_node_id, p_open, p_close, [p_service,]
d_node_id, d_open, d_close, [d_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the pick-delivery order pair.
demand	ANY-NUMERICAL		Number of units in the order
p_node_id	ANY-INTEGER		The identifier of the pickup node.
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	0	The duration of the loading at the pickup location.
d_node_id	ANY-INTEGER		The identifier of the delivery node.
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	0	The duration of the unloading at the delivery location.

Vehicles SQL

A SELECT statement that returns the following columns:

id, capacity, [speed,]
start_node_id, start_open, start_close, [start_service,]
[end_node_id, end_open, end_close, end_service]

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the pick-delivery order pair.
capacity	ANY-NUMERICAL		Number of units in the order
speed	ANY-NUMERICAL	1	Average speed of the vehicle.
start_node_id	ANY-INTEGER		The node identifier of the starting location, must match a node identifier in the matrix table.
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	0	The duration of the loading at the starting location.
end_node_id	ANY-INTEGER	start_node_id	The node identifier of the ending location, must match a node identifier in the matrix table.
end_open	ANY-NUMERICAL	start_open	The time, relative to 0, when the ending location opens.
end_close	ANY-NUMERICAL	start_close	The time, relative to 0, when the ending location closes.
end_service	ANY-NUMERICAL	start_service	The duration of the unloading at the ending location.

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	ANY-NUMERICAL	Time to travel from start_vid to end_vid

Result Columns

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	INTEGER
order_id	BIGINT	Pickup-Delivery order pair identifier. -1: When no order is involved on the current stop location.
cargo	FLOAT	Cargo units of the vehicle when leaving the stop.
travel_time	FLOAT	Travel time from previous stop_seq to current stop_seq. 0 When stop_type = 1
arrival_time	FLOAT	Previous departure_time plus current travel_time.
wait_time	FLOAT	Time spent waiting for current location to open.
service_time	FLOAT	Service time at current location.
departure_time	FLOAT	\(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 ORDER BY id $$,
    $$ SELECT * FROM vehicles ORDER BY id$$,
    $$ SELECT * from pgr_dijkstraCostMatrix(
        'SELECT * FROM edge_table ',
        (SELECT array_agg(id) FROM (SELECT p_node_id AS id FROM orders
        UNION
        SELECT d_node_id FROM orders
        UNION
        SELECT start_node_id FROM vehicles) 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 |         0 |            0 |              0
   2 |           1 |          1 |        2 |         2 |       5 |        3 |    30 |           1 |            1 |         1 |            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