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

The identifier of the pickup node.

p_tw_open

ANY-NUMERICAL

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

p_tw_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_id

ANY-INTEGER

The identifier of the delivery node.

d_tw_open

ANY-NUMERICAL

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

d_tw_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,]
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-NUMERICAL

Capacity of the vehicle

speed

ANY-NUMERICAL

1

Average speed of the vehicle.

s_id

ANY-INTEGER

The node identifier of the starting location, must match a node identifier in the matrix table.

s_tw_open

ANY-NUMERICAL

0

The time, relative to 0, when the starting location opens. When s_tw_open column exist then s_tw_close column is expected Default value when (s_tw_open, s_tw_close) columns do not exist

s_tw_close

ANY-NUMERICAL

INFINITY

The time, relative to 0, when the starting location closes. When s_tw_close column exist then e_tw_open column is expected Default value when (s_tw_open, s_tw_close) columns do not exist

s_service

ANY-NUMERICAL

0

The duration of the loading 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 table.

e_tw_open

ANY-NUMERICAL

s_tw_open

The time, relative to 0, when the ending location opens. When e_tw_open column exist then e__tw_close column is expected Default value when (e_tw_open, e_tw_close) columns do not exist

e_tw_close

ANY-NUMERICAL

s_tw_close

The time, relative to 0, when the ending location closes. When e_tw_close column exist then e_tw_open column is expected Default value when (e_tw_open, e_tw_close)` columns do not exist

e_service

ANY-NUMERICAL

s_service

The duration of the unloading at the ending location.

Throws: * When column id is missing * When column capacity is missing * When column s_id is missing * When column s_tw_open exists but not s_tw_close * When column s_tw_close`exists but not `s_tw_open * When column e_tw_open exists but not e_tw_close * When column e_tw_close`exists but not `e_tw_open

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

Indices and tables