Funciones de Ruteo de Vehículos - Categoría (Experimental)

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

Versiones anteriores de esta página

  • Versiones soportadas: actua​l(3.1) 3.0

Introducción

Problemas de Ruteo de Vehículos VRP son problemas de optimización NP-hard , que generaliza el problema del vendedor viajante (TSP).

  • El objetivo del VRP es minimizar el costo total de la ruta.

  • Hay distintas variantes del problema VRP,

pgRouting no intenta implementar todas las variantes.

Características

  • Problema de Ruteo de Vehículos Capacitados CVRP donde los vehículos tienen una capacidad de transporte limitada de las mercancías.

  • Problema de Ruteo del Vehículo con Ventanas de Tiempo VRPTW donde las ubicaciones tienen ventanas de tiempo dentro de las cuales se deben realizar las visitas del vehículo.

  • Problema de Ruteo de Vehículos con Recogida y Entrega VRPPD donde una serie de mercancías necesitan ser trasladadas de ciertas ubicaciones de recogida a otros lugares de entrega.

Limitaciones

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

Recogida y Entrega

Problema: CVRPPDTW Problema de Ruteo de vehículos de recogida y entrega capacitado con Ventanas de Tiempo

  • Los tiempos son relativos a 0

  • Los vehículos

    • tienen tiempos de duración del servicio de inicio y fin.

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

    • tienen cierta capacidad.

  • Las órdenes

    • Tener lugares de recogida y entrega.

    • Tener horarios de apertura y cierre para las ubicaciones de recogida y entrega.

    • Tener tiempos de servicio de recogida y entrega.

    • solicitar el traslado de mercancías desde el lugar de recogida hasta el lugar de entrega.

  • Cálculos basados en el tiempo:

    • El tiempo de viaje entre los clientes es \(distancia / velocidad\)

    • El par de órdenes de recogida y entrega se realiza por el mismo vehículo.

    • La recogida se realiza antes de la entrega.

Parámetros

Recogida y Entrega

Ambas implementaciones utilizan los siguientes parámetros:

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 SQL de Vehículos de Recogida y Entrega 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 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

La implementación no euclidiana, además tiene:

Columna

Tipo

Descripción

matrix_sql

TEXT

La consulta Matriz SQL de Recogida y Entrega contiene la distancia o tiempos de viaje.

Consultas Internas

columnas de retorno

Pick & Deliver Orders SQL (Recoger y Entregar Pedidos)

En general, las columnas para las órdenes SQL es la misma tanto en la implementación de recogida como de entrega:

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 no euclidiana, se necesitan los identificadores inicial y final:

Columna

Tipo

Descripción

p_node_id

ANY-INTEGER

El identificador de nodo de la recogida debe coincidir con un identificador de nodo en la tabla de matriz.

d_node_id

ANY-INTEGER

El identificador de nodo de la entrega debe coincidir con un identificador de nodo en la tabla de matriz.

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

En general, las columnas para vehicles_sql son las mismas tanto en la implementación de recogida como en la entrega:

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 no euclidiana, se necesitan los identificadores inicial y final:

Columna

Tipo

Valores predeterminados

Descripción

start_node_id

ANY-INTEGER

El identificador de nodo de la ubicación inicial debe coincidir con un identificador de nodo en la tabla de la matriz.

end_node_id

ANY-INTEGER

start_node_id

El identificador de nodo de la ubicación final debe coincidir con un identificador de nodo en la tabla de matriz.

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.

Pick & Deliver Matrix SQL

Advertencia

TODO

Resultados

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

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

Parámetros de Manipulación

Para definir un problema, hay que hacer varias consideraciones, para obtener resultados consistentes. En esta sección se proporciona una idea de cómo se deben considerar los parámetros.

Manejo de Unidades de Capacidad y Demanda

La capacidad de un vehículo, se puede medir en:

  • Unidades de volumen como \(m^3\).

  • Unidades de área como \(m^2\) (cuando no se permite el apilamiento).

  • Unidades de peso como \(kg\).

  • Número de cajas que caben en el vehículo.

  • Número de asientos en el vehículo

La solicitud de demanda de las órdenes de recogida-entrega debe utilizar las mismas unidades que las utilizadas en la capacidad del vehículo.

Para manejar problemas como: 10 (dimensión igual) cajas de manzanas y 5 kg de plumas que se van a transportar (no embaladas en cajas).

Si la capacidad del vehículo se mide mediante cajas, se necesita una conversión de kg de plumas a número equivalente de cajas. Si la capacidad del vehículo se mide por kg, se necesita una conversión de caja de manzanas a número equivalente de kg.

Mostrar cómo se pueden hacer las 2 conversiones posibles

Sea: - \(f_boxes\): el número de cajas que se utilizarían para 1 kg de plumas. - \(a_weight\): peso de 1 caja de manzanas.

Unidades de Capacidad

Manzanas

plumas

cajas

10

\(5 * f\_cajas\)

kg

\(10 * a\_peso\)

5

Ubiaciones

  • Al utilizar las firmas Euclidianas:

    • Los vehículos tienen \((x, y)\) pares para las ubicaciones de inicio y fin.

    • Los pedidos tienen \((x, y)\) pares para ubicaciones de recogida y entrega.

  • Cuando se utiliza una matriz:

    • Los vehículos tienen identificadores para las ubicaciones de inicio y finalización.

    • Los pedidos tienen identificadores para las ubicaciones de recogida y entrega.

    • Todos los identificadores son índices de la matriz dada.

Manejo del Tiempo

Los tiempos son relativos a 0

Supongamos que el conductor de un vehículo comienza el turno a las 9:00 am y termina el turno a las 4:30 pm y la duración del tiempo de servicio es de 10 minutos con 30 segundos.

Todas las unidades de tiempo tienen que ser convertidas

Significado de 0

unidades de tiempo

9:00 am

4:30 pm

10 min 30 seg

0:00 am

horas

9

16.5

\(10.5 / 60 = 0.175\)

9:00 am

horas

0

7.5

\(10.5 / 60 = 0.175\)

0:00 am

minutos

\(9*60 = 54\)

\(16.5*60 = 990\)

10.5

9:00 am

minutos

0

\(7.5*60 = 540\)

10.5

Manejo de Factores

Advertencia

TODO