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

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