pgr_pickDeliverEuclidean - Experimental

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

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo 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 (declaración de funciones) podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

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

    • Puede haber carencia de documentación.

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

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más 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

Soporte

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(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)

Parámetros

Los parámetros son:

orders_sql, vehicles_sql [,factor, max_cycles, initial_sol]

Donde:

Columna

Tipo

Valores predeterminados

Descripción

orders_sql

TEXT

Pick & Deliver Orders SQL consulta que contiene las órdenes que se van a procesar.

vehicles_sql

TEXT

La consulta Pick & Deliver Vehicles SQL contiene los vehículos que se van a utilizar.

factor

NUMERIC

1

(Opcional) Multiplicador de tiempo de viaje. Ver Manejo de Factores

max_cycles

INTEGER

10

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

initial_sol

INTEGER

4

(Opcional) Solución inicial a utilizar.

  • 1 Un 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

Pick & Deliver Orders SQL (Recoger y Entregar Pedidos)

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

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador del par de órdenes recogida-entrega.

demanda

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.

d_service

ANY-NUMERICAL

0

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

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

0

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

Para la implementación euclidiana, se necesitan ubicaciones \((x,y)\) de recogida y entrega:

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

SQL de Vehículos de Recogida y Entrega

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

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador del par de órdenes recogida-entrega.

capacidad

ANY-NUMERICAL

Número de unidades en la orden

speed

ANY-NUMERICAL

1

Velocidad media del vehículo.

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

0

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

end_open

ANY-NUMERICAL

start_open

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

end_close

ANY-NUMERICAL

start_close

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

end_service

ANY-NUMERICAL

start_service

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

Para la implementación euclidiana, se necesitan ubicaciones \((x,y)\) de inicio y finalización:

Columna

Tipo

Valores predeterminados

Descripción

start_x

ANY-NUMERICAL

valor \(x\) de la coordenada de la ubicación inicial.

start_y

ANY-NUMERICAL

valor \(y\) de la coordenada de la ubicación de inicio.

end_x

ANY-NUMERICAL

start_x

valor \(x\) de la coordenada de la ubicación final.

end_y

ANY-NUMERICAL

start_y

\(y\) valor de la coordenada de la ubicación final.

Descripción del resultado (TODO Disussion: Euclidean & Matrix)

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.

vehicle_id

BIGINT

Identificador actual del vehículo.

stop_seq

INTEGER

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

stop_type

INTEGER

Tipo de ubicación de parada en la que se encuentra el vehículo:

  • 1: Ubicación de inicio

  • 2: Ubicación de recogida

  • 3: Lugar de entrega

  • 6: Ubicación final

order_id

BIGINT

Identificador de par de órdenes Recogida-Entrega.

  • -1: Cuando no hay ningún pedido involucrado en la ubicación actual de la parada.

cargo

FLOAT

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

travel_time

FLOAT

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

  • 0 cuando stop_type = 1

arrival_time

FLOAT

Anterior departure_time más actual travel_time.

wait_time

FLOAT

Tiempo dedicado a la apertura de ubicación actual.

service_time

FLOAT

Tiempo de servicio en la ubicación actual.

departure_time

FLOAT

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

  • Cuando stop_type = 6 tiene el total_time utilizado para el vehículo actual.

Fila de Resumen

Advertencia

TODO: Review the summary

Columna

Tipo

Descripción

seq

INTEGER

Continúa el valor Secuencial

vehicle_seq

INTEGER

-2 para indicar es una fila de resumen

vehicle_id

BIGINT

Total de Violaciones de Capacidad en la solución.

stop_seq

INTEGER

Tiempo Total de Violaciones de la Ventana en la solución.

stop_type

INTEGER

-1

order_id

BIGINT

-1

cargo

FLOAT

-1

travel_time

FLOAT

total_travel_time La suma de todo el tiempo_de_viaje

arrival_time

FLOAT

-1

wait_time

FLOAT

total_waiting_time La suma de todo el tiempo_de_espera

service_time

FLOAT

total_service_time La suma de todo el tiempo_de_servicio

departure_time

FLOAT

total_solution_time = \(total\_travel\_time + total\_wait\_time + total\_service\_time\).

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Ejemplo

En este ejemplo se utilizan los siguientes datos: TODO put link

SELECT * FROM pgr_pickDeliverEuclidean(
    'SELECT * FROM orders ORDER BY id',
    'SELECT * 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 |          1 |        1 |         1 |       -1 |     0 |             0 |             0 |         0 |            0 |              0
   8 |           2 |          1 |        2 |         2 |        1 |    10 |             1 |             1 |         1 |            3 |              5
   9 |           2 |          1 |        3 |         3 |        1 |     0 |  2.2360679775 |  7.2360679775 |         0 |            3 |  10.2360679775
  10 |           2 |          1 |        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)

Ver también

Índices y tablas