pgr_pickDeliver - Experimental

pgr_pickDeliver - Problema de enrutamiento 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

    • 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 con ventanas de tiempo.

  • Todos los vehículos son iguales.

    • La misma ubicación de Inicio.

    • La misma ubicación Final que es la misma que la ubicación de Inicio.

    • Todos los vehículos viajan a la misma velocidad.

  • Un cliente es para hacer una recogida o hacer una entrega.

    • tiene un tiempo abierto.

    • tiene tiempo de cierre.

    • tiene un tiempo de servicio.

    • tiene una ubicación (x, y).

  • 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

  • Todos los camiones salen en el momento 0.

  • 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.

  • el algoritmo generará una excepción cuando

    • Si hay un par de recogida-entrega que viola la ventana de tiempo

    • La velocidad, max_cycles, max_capacity tienen valores ilegales

  • Seoptimizarán seis iniciales diferentes - la mejor solución encontrada será el resultado

Firma

pgr_pickDeliver(Orders SQL, Vehicles SQL, Matrix SQL, [options])
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_node_id, start_open, start_close
FROM vehicles;
 id | capacity | start_node_id | start_open | start_close
----+----------+---------------+------------+-------------
  1 |       50 |            11 |          0 |          50
  2 |       50 |            11 |          0 |          50
(2 rows)

and the orders:

SELECT id, demand,
       p_node_id, p_open, p_close, p_service,
       d_node_id, d_open, d_close, d_service
FROM orders;
 id | demand | p_node_id | p_open | p_close | p_service | d_node_id | d_open | d_close | d_service
----+--------+-----------+--------+---------+-----------+-----------+--------+---------+-----------
  1 |     10 |        10 |      2 |      10 |         3 |         3 |      6 |      15 |         3
  2 |     20 |        16 |      4 |      15 |         2 |        15 |      6 |      20 |         3
  3 |     30 |         7 |      2 |      10 |         3 |        12 |      3 |      20 |         3
(3 rows)

La consulta:

SELECT * FROM pgr_pickDeliver(
  $$SELECT id, demand,
       p_node_id, p_open, p_close, p_service,
       d_node_id, d_open, d_close, d_service
    FROM orders$$,
  $$SELECT id, capacity, start_node_id, start_open, start_close
    FROM vehicles$$,
  $$SELECT * from pgr_dijkstraCostMatrix(
    'SELECT * FROM edges ',
    (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 |      11 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   2 |           1 |          1 |        2 |         2 |       7 |        3 |    30 |           1 |            1 |         1 |            3 |              5
   3 |           1 |          1 |        3 |         3 |      12 |        3 |     0 |           2 |            7 |         0 |            3 |             10
   4 |           1 |          1 |        4 |         2 |      16 |        2 |    20 |           2 |           12 |         0 |            2 |             14
   5 |           1 |          1 |        5 |         3 |      15 |        2 |     0 |           1 |           15 |         0 |            3 |             18
   6 |           1 |          1 |        6 |         6 |      11 |       -1 |     0 |           2 |           20 |         0 |            0 |             20
   7 |           2 |          2 |        1 |         1 |      11 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   8 |           2 |          2 |        2 |         2 |      10 |        1 |    10 |           3 |            3 |         0 |            3 |              6
   9 |           2 |          2 |        3 |         3 |       3 |        1 |     0 |           3 |            9 |         0 |            3 |             12
  10 |           2 |          2 |        4 |         6 |      11 |       -1 |     0 |           2 |           14 |         0 |            0 |             14
  11 |          -2 |          0 |        0 |        -1 |      -1 |       -1 |    -1 |          16 |           -1 |         1 |           17 |             34
(11 rows)

Parámetros

Los parámetros son:

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.

SQL de matriz

TEXT

SQL de matriz 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_node_id, p_open, p_close, [p_service,]
d_node_id, 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_node_id

ANY-INTEGER

El identificador de nodo de la recogida debe coincidir con un identificador de vértice en la SQL de matriz.

d_node_id

ANY-INTEGER

El identificador de nodo de la entrega debe coincidir con un identificador de vértice en la SQL de matriz.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

SQL de Vehículos

Una instrucción SELECT que devuelve las siguientes columnas:

id, capacity
start_node_id, start_open, start_close [, start_service,]
[end_node_id, 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_node_id

ANY-INTEGER

El identificador de nodo de la ubicación inicial debe coincidir con un identificador de vértice en la SQL de matriz.

[end_node_id]

ANY-INTEGER

El identificador de nodo de la ubicación final debe coincidir con un identificador de vértice en la SQL de matriz.

  • Cuando falte: Se usara``end_node_id``.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

SQL de matriz

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

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\).

Ver también

Índices y tablas