vrp_pgr_pickDeliverEuclidean - Experimental

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

Synopsis

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

  • Optimization problem is NP-hard.

  • Pickup and Delivery:

    • capacitated

    • with time windows.

  • The vehicles

    • have (x, y) start and ending locations.

    • have a start and ending service times.

    • have opening and closing times for the start and ending locations.

  • An order is for doing a pickup and a a deliver.

    • has (x, y) pickup and delivery locations.

    • has opening and closing times for the pickup and delivery locations.

    • has a pickup and deliver service times.

  • 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

  • No multiple time windows for a location.

  • Less vehicle used is considered better.

  • Less total duration is better.

  • Less wait time is better.

  • Six different optional different initial solutions

    • the best solution found will be result

Signature

vrp_pgr_pickDeliverEuclidean(Orders SQL, Vehicles SQL [, factor, max_cycles, initial_sol])
RETURNS SET OF:
    seq, vehicle_seq, vehicle_id,
    stop_seq, stop_type, 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.

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_x, p_y, p_tw_open, p_tw_close, [p_service,]
d_x, d_y, d_tw_open, d_tw_close, [d_service]

Column

Type

Default

Description

id

ANY-INTEGER

Identifier of the pick-delivery order pair.

amount

ANY-INTEGER

Number of units in the order

p_x

ANY-NUMERICAL

\(x\) value of the pick up location

p_y

ANY-NUMERICAL

\(y\) value of the pick up location

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_service

ANY-INTEGER

0

The duration of the loading at the pickup location.

d_x

ANY-NUMERICAL

\(x\) value of the delivery location

d_y

ANY-NUMERICAL

\(y\) value of the delivery location

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_service

ANY-INTEGER

0

The duration of the loading at the delivery location.

Vehicles SQL

A SELECT statement that returns the following columns:

id, capacity, [speed,]
s_x, s_y, s_tw_open, s_tw_close, [s_service,]
[e_x, e_y, 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_x

ANY-NUMERICAL

\(x\) value of the coordinate of the starting location.

s_y

ANY-NUMERICAL

\(y\) value of the coordinate of the starting location.

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_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 loading at the ending location.

e_x

ANY-NUMERICAL

s_x

\(x\) value of the coordinate of the ending location. Default value when (e_x, e_y) columns do not exist Default value when e_y column does not exist

e_y

ANY-NUMERICAL

s_y

\(y\) value of the coordinate of the ending location. When e_y column exist then e_x column is expected Default value when (e_x, e_y) columns do not exist

Throws: * When column id is missing * When column capacity is missing * When column s_x is missing * When column s_y 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_y exists but not e_x * When column e_x exists but not e_y * When column e_tw_open exists but not e_tw_close * When column e_tw_close`exists but not `e_tw_open

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

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_pickDeliverEuclidean(
    'SELECT * FROM orders_1 ORDER BY id',
    'SELECT * from vehicles_1'
);
 seq | vehicle_seq | vehicle_id | stop_seq | stop_type | order_id | cargo | travel_time | arrival_time | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+----------+-------+-------------+--------------+-----------+--------------+----------------
   1 |           1 |          1 |        1 |         1 |       -1 |     0 |           0 |            0 |         1 |            0 |              1
   2 |           1 |          1 |        2 |         2 |        3 |    30 |           1 |            2 |         0 |            3 |              5
   3 |           1 |          1 |        3 |         3 |        3 |     0 |           1 |            6 |         0 |            3 |              9
   4 |           1 |          1 |        4 |         2 |        2 |    20 |           1 |           10 |         0 |            2 |             12
   5 |           1 |          1 |        5 |         3 |        2 |     0 |           1 |           13 |         0 |            3 |             16
   6 |           1 |          1 |        6 |         6 |       -1 |     0 |           3 |           19 |         0 |            0 |             19
   7 |           2 |          2 |        1 |         1 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   8 |           2 |          2 |        2 |         2 |        1 |    10 |           2 |            2 |         0 |            3 |              5
   9 |           2 |          2 |        3 |         3 |        1 |     0 |           2 |            7 |         0 |            3 |             10
  10 |           2 |          2 |        4 |         6 |       -1 |     0 |           0 |           10 |         0 |            0 |             10
  11 |          -2 |          0 |        0 |        -1 |       -1 |    -1 |          11 |           -1 |         1 |           17 |             29
(11 rows)

See Also

Indices and tables