`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

Columna

Tipo

x Defecto

Descripción

factor

NUMERIC

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

max_cycles

INTEGER

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

initial_sol

INTEGER

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¶

Funciones de Ruteo de Vehículos - Categoría (Experimental)
Las consultas utilizan la red Datos Muestra .

Índices y tablas

pgr_pickDeliverEuclidean - Experimental¶

Sinopsis¶

Características¶

Firma¶

Parámetros¶

Parámetros opcionales de Recoger-Entregar¶

SQL de órdenes¶

SQL de Vehículos¶

Columnas de resultados¶

Ejemplo¶

Los vehículos¶

The original orders¶

Las órdenes¶

The query¶

Ver también¶

`pgr_pickDeliverEuclidean` - Experimental¶

Los vehículos ¶

The original orders ¶

Las órdenes ¶

The query ¶