• Supported versions:

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

• Problema de recogida y entrega

  • pgr_pickDeliver - Experimental - Recogida y Entrega utilizando una Matriz de Costos.

  • pgr_pickDeliverEuclidean - Experimental - Recogida y Entrega con distancias Euclideanas.

• Problema de distribución

  • pgr_vrpOneDepot - Experimental - Desde un único depósito, distribuye los pedidos

Contenido

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

  • Introducción

    • Características

  • Recogida y Entrega

  • Parámetros

    • Recogida y Entrega

  • Consultas Internas

    • Pick & Deliver Orders SQL (Recoger y Entregar Pedidos)

    • SQL de Vehículos de Recogida y Entrega

    • Pick & Deliver Matrix SQL

  • Resultados

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

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

  • Parámetros de Manipulación

    • Manejo de Unidades de Capacidad y Demanda

    • Ubiaciones

    • Manejo del Tiempo

    • Manejo de Factores

  • Ver también

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

• Órdenes SQL de Recogida y Entrega

• SQL de Vehículos de Recogida y Entrega

• Matriz SQL de Recogida y Entrega

columnas de retorno

• Descripción de las columnas de retorno

• Descripción de las columnas de retorno para la versión Euclideana

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

• Ubicaciones

• Manejo del tiempo

• Manejo de Factor

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

Ver también

• https://en.wikipedia.org/wiki/Vehicle_routing_problem

• Las consultas utilizan la red Datos Muestra .

Índices y tablas

• Índice

• Página de Búsqueda