pgr_pickDeliverEuclidean - Experimental

pgr_pickDeliverEuclidean - Problema de Ruteo del Vehículo de Recogida y Entrega

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear una caída del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma puede cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden faltar.

    • Posiblemente necesite codificación c/c++.

    • Puede carecer documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Puede ser necesario que los ejemplos de documentación se generen automáticamente.

    • Puede ser necesaria retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting

    • Podría depender de una función obsoleta de pgRouting

Disponibilidad

  • Versión 3.0.0

    • Reemplaza pgr_gsoc_vrppdtw

    • Nueva función experimental

Sinopsis

Problema: Distribuya y optimice los pares de recogida-entrega en una flota de vehículos.

  • El problema de optimización es NP-hard.

  • Recogida y Entrega:

    • capacitado

    • con ventanas de tiempo.

  • Los vehículos

    • tienen (x, y) ubicaciones de inicio y finalización.

    • tener un inicio y un final de los tiempos de servicio.

    • tienen horarios de apertura y cierre para las ubicaciones de inicio y finalización.

  • Un pedido es para hacer una recogida y una entrega.

    • tiene (x, y) ubicaciones de recogida y entrega.

    • tiene horarios de apertura y cierre para los lugares de recogida y entrega.

    • tiene una recogida y entrega de tiempos de servicio.

  • Hay un cliente donde entregar una recogida.

    • tiempo de viaje entre los clientes es distancia / velocidad

    • La recogida y entrega se realizan con el mismo vehículo.

    • La recogida se realiza antes de la entrega.

Características

  • No hay varias ventanas de tiempo para una ubicación.

  • Menos vehículo utilizado se considera mejor.

  • Menos duración total es mejor.

  • Menos tiempo de espera es mejor.

  • Seis diferentes soluciones iniciales opcionales

    • la mejor solución encontrada será el resultado

Firma

pgr_pickDeliverEuclidean(SQL de órdenes, SQL de vehículos, [opciones])
opcionales: [factor, max_cycles, initial_sol]
Regresa el conjunto de (seq, vehicle_number, vehicle_id, stop, order_id, stop_type, cargo, travel_time, arrival_time, wait_time, service_time, departure_time)
Ejemplo:

Solve the following problem

Dados los vehículos:

SELECT id, capacity, start_x, start_y, start_open, start_close
FROM vehicles;
 id | capacity | start_x | start_y | start_open | start_close
----+----------+---------+---------+------------+-------------
  1 |       50 |       3 |       2 |          0 |          50
  2 |       50 |       3 |       2 |          0 |          50
(2 rows)

and the orders:

SELECT id, demand,
       p_x, p_y, p_open, p_close, p_service,
       d_x, d_y, d_open, d_close, d_service
FROM orders;
 id | demand | p_x | p_y | p_open | p_close | p_service | d_x | d_y | d_open | d_close | d_service
----+--------+-----+-----+--------+---------+-----------+-----+-----+--------+---------+-----------
  1 |     10 |   3 |   1 |      2 |      10 |         3 |   1 |   2 |      6 |      15 |         3
  2 |     20 |   4 |   2 |      4 |      15 |         2 |   4 |   1 |      6 |      20 |         3
  3 |     30 |   2 |   2 |      2 |      10 |         3 |   3 |   3 |      3 |      20 |         3
(3 rows)

La consulta:

SELECT * FROM pgr_pickDeliverEuclidean(
  $$SELECT id, demand,
       p_x, p_y, p_open, p_close, p_service,
       d_x, d_y, d_open, d_close, d_service
    FROM orders$$,
  $$SELECT id, capacity, start_x, start_y, start_open, start_close
    FROM vehicles$$);
 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 |         0 |            0 |              0
   2 |           1 |          1 |        2 |         2 |        3 |    30 |             1 |             1 |         1 |            3 |              5
   3 |           1 |          1 |        3 |         3 |        3 |     0 | 1.41421356237 | 6.41421356237 |         0 |            3 |  9.41421356237
   4 |           1 |          1 |        4 |         2 |        2 |    20 | 1.41421356237 | 10.8284271247 |         0 |            2 |  12.8284271247
   5 |           1 |          1 |        5 |         3 |        2 |     0 |             1 | 13.8284271247 |         0 |            3 |  16.8284271247
   6 |           1 |          1 |        6 |         6 |       -1 |     0 | 1.41421356237 | 18.2426406871 |         0 |            0 |  18.2426406871
   7 |           2 |          2 |        1 |         1 |       -1 |     0 |             0 |             0 |         0 |            0 |              0
   8 |           2 |          2 |        2 |         2 |        1 |    10 |             1 |             1 |         1 |            3 |              5
   9 |           2 |          2 |        3 |         3 |        1 |     0 |  2.2360679775 |  7.2360679775 |         0 |            3 |  10.2360679775
  10 |           2 |          2 |        4 |         6 |       -1 |     0 |             2 | 12.2360679775 |         0 |            0 |  12.2360679775
  11 |          -2 |          0 |        0 |        -1 |       -1 |    -1 | 11.4787086646 |            -1 |         2 |           17 |  30.4787086646
(11 rows)

Parámetros

Columna

Tipo

Descripción

SQL de órdenes

TEXT

SQL de órdenes como se describe más adelante.

SQL de Vehículos

TEXT

SQL de Vehículos como se describe más adelante.

Parámetros opcionales de Recoger-Entregar

Columna

Tipo

x Defecto

Descripción

factor

NUMERIC

1

Multiplicador de tiempo de viaje. Ver Manipulación del Factor

max_cycles

INTEGER

10

Número máximo de ciclos a realizar en la optimización.

initial_sol

INTEGER

4

Solución inicial a utilizar.

  • 1 Una orden por camión

  • 2 Empuje la orden delantera.

  • 3 Empuje la orden trasera.

  • 4 Optimizar inserción.

  • 5 Orden de retroceso que permite insertar más órdenes en la parte posterior

  • 6 Orden de avance que permite insertar más órdenes en la parte frontal

SQL de órdenes

Una instrucción SELECT que devuelve las siguientes columnas:

id, demand
p_x, p_y, p_open, p_close, [p_service,]
d_x, d_y, d_open, d_close, [d_service]

Donde:

Columna

Tipo

Descripción

id

ANY-INTEGER

Identificador del par de órdenes recogida-entrega.

demand

ANY-NUMERICAL

Número de unidades en la orden

p_open

ANY-NUMERICAL

La hora, en relación con 0, cuando se abre la ubicación de recogida.

p_close

ANY-NUMERICAL

La hora, en relación con 0, cuando se cierra la ubicación de recogida.

[p_service]

ANY-NUMERICAL

La duración de la carga en el lugar de recogida.

  • Cuando falta: Son usadas 0 unidades de tiempo

d_open

ANY-NUMERICAL

La hora, en relación con 0, cuando se abre la ubicación de entrega.

d_close

ANY-NUMERICAL

La hora, en relación con 0, cuando se cierra la ubicación de entrega.

[d_service]

ANY-NUMERICAL

La duración de la descarga en el lugar de entrega.

  • Cuando falta: Son usadas 0 unidades de tiempo

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columna

Tipo

Descripción

p_x

ANY-NUMERICAL

\(x\) valor de la ubicación de recogida

p_y

ANY-NUMERICAL

\(y\) valor de la ubicación de recogida

d_x

ANY-NUMERICAL

valor \(x\) de la ubicación de entrega

d_y

ANY-NUMERICAL

valor \(y\) del lugar de entrega

Donde:

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL de Vehículos

Una instrucción SELECT que devuelve las siguientes columnas:

id, capacity
start_x, start_y, start_open, start_close [, start_service, ]
[ end_x, end_y, end_open, end_close, end_service ]

donde:

Columna

Tipo

Descripción

id

ANY-NUMERICAL

Identificador del vehículo.

capacity

ANY-NUMERICAL

Máxima capacidad

start_open

ANY-NUMERICAL

La hora, en relación con 0, cuando se abre la ubicación inicial.

start_close

ANY-NUMERICAL

La hora, en relación con 0, cuando se cierra la ubicación inicial.

[start_service]

ANY-NUMERICAL

La duración de la carga en la ubicación inicial.

  • Cuando falta: Una duración de :math: 0 unidades de tiempo son usadas.

[end_open]

ANY-NUMERICAL

La hora, en relación con 0, cuando se abre la ubicación final.

  • Cuando falte: El valor de``start_open`` se usara

[end_close]

ANY-NUMERICAL

La hora, en relación con 0, cuando se cierra la ubicación final.

  • Cuando falte: Se usara el valor de start_close

[end_service]

ANY-NUMERICAL

La duración de la carga en la ubicación final.

  • Cuando falte: Se usara una duración en start_service.

Columna

Tipo

Descripción

start_x

ANY-NUMERICAL

Valor \(x\) de la ubicación de salida

start_y

ANY-NUMERICAL

Valor \(y\) de la ubicación de salida

[end_x]

ANY-NUMERICAL

Valor \(x\) de la ubicación del destino

  • Cuando falte: Se usará start_x.

[end_y]

ANY-NUMERICAL

Valor \(y\) del la ubicaclón del destino

  • Cuando falte: Se usará start_y.

Donde:

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

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)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

vehicle_seq

INTEGER

Valor secuencial a partir de 1 para vehículos actuales. El vehículo \(n_{th}\) en la solución.

  • Valor \(-2\) para indicar que es una fila de resumen.

vehicle_id

BIGINT

Identificador del vehículo actual.

  • Fila de resumen tiene las infracciones de capacidad total.

    • Cuando se sobrecarga o subrogar un vehículo, ocurre una infracción de capacidad.

stop_seq

INTEGER

Valor secuencial a partir de 1 para las paradas realizadas por el vehículo actual. La parada \(m_{th}\) del vehículo actual.

  • Fila de resumen tiene las infracciones de ventana de tiempo total.

    • Una infracción de ventana de tiempo ocurre cuando se llega a la ubicación después de que ésta cerró.

stop_type

INTEGER

  • Tipo de parada en la que se encuentra el vehículo

    • \(-1\): en la fila de resumen de solución

    • 1: Ubicación inicial

    • \(2\): Ubicación de recogida

    • \(3\): Lugar de entrega

    • \(6\): Ubicación final indica la fila de resumen del vehículo

order_id

BIGINT

Identificador de par de órdenes Recoger-Entregar.

  • Valor \(-1\): Cuando no hay pedidos involucrados en la ubicación de la parada actual.

cargo

FLOAT

Unidades de carga del vehículo al salir de la parada.

  • El valor \(-1\) en fila de resumen de solución.

travel_time

FLOAT

Tiempo de viaje desde el stop_seq anterior hasta el stop_seq actual.

  • El resumen tiene el tiempo total de viaje:

    • La suma de todos los travel_time.

arrival_time

FLOAT

Tiempo de espera para la apertura de la ubicación actual.

  • \(-1\) en fila de resumen de solución.

  • \(0\): en la ubicación inicial.

wait_time

FLOAT

Tiempo de espera para la apertura de la ubicación actual.

  • La fila de resumen tiene el tiempo total de espera:

    • La suma de todo el wait_time.

service_time

FLOAT

Duralción del servicio en la ubicación actual.

  • La fila de resumen tiene el tiempo total de servicio:

    • La suma de todo el service_time.

departure_time

FLOAT

  • El tiempo en el que el vehículo sale desde la parada.

    • \(arrival\_time + wait\_time + service\_time\).

  • El destino final tiene el tiempo total utilizado por el vehículo actual.

  • La fila de resumen tiene el tiempo total de solución:

    • \(total\ traveling\ time + total\ waiting\ time + total\ service\ time\).

Ejemplo

This data example lc101 is from data published at https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/

Los vehículos

There are 25 vehciles in the problem all with the same characteristics.

CREATE TABLE v_lc101(
  id BIGINT NOT NULL primary key,
  capacity BIGINT DEFAULT 200,
  start_x FLOAT DEFAULT 30,
  start_y FLOAT DEFAULT 50,
  start_open INTEGER DEFAULT 0,
  start_close INTEGER DEFAULT 1236);
CREATE TABLE
/* create 25 vehciles */
INSERT INTO v_lc101 (id)
(SELECT * FROM generate_series(1, 25));
INSERT 0 25

The original orders

The data comes in different rows for the pickup and the delivery of the same order.

CREATE table lc101_c(
  id BIGINT not null primary key,
  x DOUBLE PRECISION,
  y DOUBLE PRECISION,
  demand INTEGER,
  open INTEGER,
  close INTEGER,
  service INTEGER,
  pindex BIGINT,
  dindex BIGINT
);
CREATE TABLE
/* the original data */
INSERT INTO lc101_c(
  id,     x,    y, demand, open, close, service, pindex, dindex) VALUES
(  1,    45,   68,   -10,   912,   967,   90,   11,    0),
(  2,    45,   70,   -20,   825,   870,   90,    6,    0),
(  3,    42,   66,    10,    65,   146,   90,    0,   75),
(  4,    42,   68,   -10,   727,   782,   90,    9,    0),
(  5,    42,   65,    10,    15,    67,   90,    0,    7),
(  6,    40,   69,    20,   621,   702,   90,    0,    2),
(  7,    40,   66,   -10,   170,   225,   90,    5,    0),
(  8,    38,   68,    20,   255,   324,   90,    0,   10),
(  9,    38,   70,    10,   534,   605,   90,    0,    4),
( 10,    35,   66,   -20,   357,   410,   90,    8,    0),
( 11,    35,   69,    10,   448,   505,   90,    0,    1),
( 12,    25,   85,   -20,   652,   721,   90,   18,    0),
( 13,    22,   75,    30,    30,    92,   90,    0,   17),
( 14,    22,   85,   -40,   567,   620,   90,   16,    0),
( 15,    20,   80,   -10,   384,   429,   90,   19,    0),
( 16,    20,   85,    40,   475,   528,   90,    0,   14),
( 17,    18,   75,   -30,    99,   148,   90,   13,    0),
( 18,    15,   75,    20,   179,   254,   90,    0,   12),
( 19,    15,   80,    10,   278,   345,   90,    0,   15),
( 20,    30,   50,    10,    10,    73,   90,    0,   24),
( 21,    30,   52,   -10,   914,   965,   90,   30,    0),
( 22,    28,   52,   -20,   812,   883,   90,   28,    0),
( 23,    28,   55,    10,   732,   777,    0,    0,  103),
( 24,    25,   50,   -10,    65,   144,   90,   20,    0),
( 25,    25,   52,    40,   169,   224,   90,    0,   27),
( 26,    25,   55,   -10,   622,   701,   90,   29,    0),
( 27,    23,   52,   -40,   261,   316,   90,   25,    0),
( 28,    23,   55,    20,   546,   593,   90,    0,   22),
( 29,    20,   50,    10,   358,   405,   90,    0,   26),
( 30,    20,   55,    10,   449,   504,   90,    0,   21),
( 31,    10,   35,   -30,   200,   237,   90,   32,    0),
( 32,    10,   40,    30,    31,   100,   90,    0,   31),
( 33,     8,   40,    40,    87,   158,   90,    0,   37),
( 34,     8,   45,   -30,   751,   816,   90,   38,    0),
( 35,     5,   35,    10,   283,   344,   90,    0,   39),
( 36,     5,   45,    10,   665,   716,    0,    0,  105),
( 37,     2,   40,   -40,   383,   434,   90,   33,    0),
( 38,     0,   40,    30,   479,   522,   90,    0,   34),
( 39,     0,   45,   -10,   567,   624,   90,   35,    0),
( 40,    35,   30,   -20,   264,   321,   90,   42,    0),
( 41,    35,   32,   -10,   166,   235,   90,   43,    0),
( 42,    33,   32,    20,    68,   149,   90,    0,   40),
( 43,    33,   35,    10,    16,    80,   90,    0,   41),
( 44,    32,   30,    10,   359,   412,   90,    0,   46),
( 45,    30,   30,    10,   541,   600,   90,    0,   48),
( 46,    30,   32,   -10,   448,   509,   90,   44,    0),
( 47,    30,   35,   -10,  1054,  1127,   90,   49,    0),
( 48,    28,   30,   -10,   632,   693,   90,   45,    0),
( 49,    28,   35,    10,  1001,  1066,   90,    0,   47),
( 50,    26,   32,    10,   815,   880,   90,    0,   52),
( 51,    25,   30,    10,   725,   786,    0,    0,  101),
( 52,    25,   35,   -10,   912,   969,   90,   50,    0),
( 53,    44,    5,    20,   286,   347,   90,    0,   58),
( 54,    42,   10,    40,   186,   257,   90,    0,   60),
( 55,    42,   15,   -40,    95,   158,   90,   57,    0),
( 56,    40,    5,    30,   385,   436,   90,    0,   59),
( 57,    40,   15,    40,    35,    87,   90,    0,   55),
( 58,    38,    5,   -20,   471,   534,   90,   53,    0),
( 59,    38,   15,   -30,   651,   740,   90,   56,    0),
( 60,    35,    5,   -40,   562,   629,   90,   54,    0),
( 61,    50,   30,   -10,   531,   610,   90,   67,    0),
( 62,    50,   35,    20,   262,   317,   90,    0,   68),
( 63,    50,   40,    50,   171,   218,   90,    0,   74),
( 64,    48,   30,    10,   632,   693,    0,    0,  102),
( 65,    48,   40,    10,    76,   129,   90,    0,   72),
( 66,    47,   35,    10,   826,   875,   90,    0,   69),
( 67,    47,   40,    10,    12,    77,   90,    0,   61),
( 68,    45,   30,   -20,   734,   777,   90,   62,    0),
( 69,    45,   35,   -10,   916,   969,   90,   66,    0),
( 70,    95,   30,   -30,   387,   456,   90,   81,    0),
( 71,    95,   35,    20,   293,   360,   90,    0,   77),
( 72,    53,   30,   -10,   450,   505,   90,   65,    0),
( 73,    92,   30,   -10,   478,   551,   90,   76,    0),
( 74,    53,   35,   -50,   353,   412,   90,   63,    0),
( 75,    45,   65,   -10,   997,  1068,   90,    3,    0),
( 76,    90,   35,    10,   203,   260,   90,    0,   73),
( 77,    88,   30,   -20,   574,   643,   90,   71,    0),
( 78,    88,   35,    20,   109,   170,    0,    0,  104),
( 79,    87,   30,    10,   668,   731,   90,    0,   80),
( 80,    85,   25,   -10,   769,   820,   90,   79,    0),
( 81,    85,   35,    30,    47,   124,   90,    0,   70),
( 82,    75,   55,    20,   369,   420,   90,    0,   85),
( 83,    72,   55,   -20,   265,   338,   90,   87,    0),
( 84,    70,   58,    20,   458,   523,   90,    0,   89),
( 85,    68,   60,   -20,   555,   612,   90,   82,    0),
( 86,    66,   55,    10,   173,   238,   90,    0,   91),
( 87,    65,   55,    20,    85,   144,   90,    0,   83),
( 88,    65,   60,   -10,   645,   708,   90,   90,    0),
( 89,    63,   58,   -20,   737,   802,   90,   84,    0),
( 90,    60,   55,    10,    20,    84,   90,    0,   88),
( 91,    60,   60,   -10,   836,   889,   90,   86,    0),
( 92,    67,   85,    20,   368,   441,   90,    0,   93),
( 93,    65,   85,   -20,   475,   518,   90,   92,    0),
( 94,    65,   82,   -10,   285,   336,   90,   96,    0),
( 95,    62,   80,   -20,   196,   239,   90,   98,    0),
( 96,    60,   80,    10,    95,   156,   90,    0,   94),
( 97,    60,   85,    30,   561,   622,    0,    0,  106),
( 98,    58,   75,    20,    30,    84,   90,    0,   95),
( 99,    55,   80,   -20,   743,   820,   90,  100,    0),
( 100,   55,   85,    20,   647,   726,   90,    0,   99),
( 101,   25,   30,   -10,   725,   786,   90,   51,    0),
( 102,   48,   30,   -10,   632,   693,   90,   64,    0),
( 103,   28,   55,   -10,   732,   777,   90,   23,    0),
( 104,   88,   35,   -20,   109,   170,   90,   78,    0),
( 105,    5,   45,   -10,   665,   716,   90,   36,    0),
( 106,   60,   85,   -30,   561,   622,   90,   97,    0);
INSERT 0 106

Las órdenes

The original data needs to be converted to an appropiate table:

WITH deliveries AS (SELECT * FROM lc101_c WHERE dindex = 0)
SELECT
  row_number() over() AS id, p.demand,
  p.id as p_node_id, p.x AS p_x, p.y AS p_y, p.open AS p_open, p.close as p_close, p.service as p_service,
  d.id as d_node_id, d.x AS d_x, d.y AS d_y, d.open AS d_open, d.close as d_close, d.service as d_service
INTO c_lc101
FROM deliveries as d JOIN lc101_c as p ON (d.pindex = p.id);
SELECT 53
SELECT * FROM c_lc101 LIMIT 1;
 id | demand | p_node_id | p_x | p_y | p_open | p_close | p_service | d_node_id | d_x | d_y | d_open | d_close | d_service
----+--------+-----------+-----+-----+--------+---------+-----------+-----------+-----+-----+--------+---------+-----------
  1 |     10 |         3 |  42 |  66 |     65 |     146 |        90 |        75 |  45 |  65 |    997 |    1068 |        90
(1 row)

The query

Showing only the relevant information to compare with the best solution information published on https://www.sintef.no/projectweb/top/pdptw/100-customers/

  • The best solution found for lc101 is a travel time: 828.94

  • This implementation’s travel time: 854.54

SELECT travel_time, 828.94 AS best
FROM pgr_pickDeliverEuclidean(
  $$SELECT * FROM c_lc101 $$,
  $$SELECT * FROM v_lc101 $$,
  max_cycles => 2, initial_sol => 4) WHERE vehicle_seq = -2;
    travel_time    |  best
-------------------+--------
 854.5412705652799 | 828.94
(1 row)

Ver también

Índices y tablas