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

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

• Problema de recogida y entrega

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

  • pgr_pickDeliverEuclidean - Experimental - Recoger y Entregar con distancias Euclideanas

• Problema de distribución

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

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

Usado en pgr_pickDeliverEuclidean - Experimental

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.

Usado en pgr_pickDeliver - Experimental

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

Consultas Internas

SQL de órdenes

En general, las columnas para las órdenes SQL es la misma en ambas implementaciones:

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

Para pgr_pickDeliver - Experimental los identificadores de ubicación de la carga y envío son necesarias:

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

Para pgr_pickDeliverEuclidean - Experimental los valores \((x, y)\) de las ubicaciones son necesarias:

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

Donde:

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL de Vehículos

Las columnas comunas para vehículos SQL son las mismas en ambas implementaciones:

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.

Para pgr_pickDeliver - Experimental se necesitan los identificadores de salida y destino:

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

Para pgr_pickDeliverEuclidean - Experimental los valores \((x, y)\) de las ubicaciones son necesarias:

Columna	Tipo	Descripción
start_x	ANY-NUMERICAL	Valor \(x\) de la ubicación de salida
start_y	ANY-NUMERICAL	Valor \(y\) de la ubicación de salida
[end_x]	ANY-NUMERICAL	Valor \(x\) de la ubicación del destino Cuando falte: Se usará start_x.
[end_y]	ANY-NUMERICAL	Valor \(y\) del la ubicaclón del destino Cuando falte: Se usará start_y.

Donde:

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL de matriz

Conjunto de (start_vid, end_vid, agg_cost)

Columna	Tipo	Descripción
start_vid	BIGINT	Identificador del vértice de salida.
end_vid	BIGINT	Identificador del vértice destino.
agg_cost	FLOAT	Costo afregado desde start_vid hasta end_vid.

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

Fila de Resumen

Columna	Tipo	Descripción
seq	INTEGER	Continúa la secuencia
vehicle_seq	INTEGER	Valor \(-2\) para indicar que es una fila de resumen.
vehicle_id	BIGINT	infracciones de capacidad total: Cuando se sobrecarga o subrogar un vehículo, ocurre una infracción de capacidad.
stop_seq	INTEGER	Cantidad total de violaciones de ventanas de tiempo: Una infracción de ventana de tiempo ocurre cuando se llega a la ubicación después de que ésta cerró.
stop_type	INTEGER	\(-1\)
order_id	BIGINT	\(-1\)
cargo	FLOAT	\(-1\)
travel_time	FLOAT	tiempo total transportándose: La suma de todos los travel_time.
arrival_time	FLOAT	\(-1\)
wait_time	FLOAT	tiempo total de espera*: La suma de todo el wait_time.
service_time	FLOAT	tiempo total de servicio: La suma de todo el service_time.
departure_time	FLOAT	La fila de resumen tiene el tiempo total de solución: \(total\ traveling\ time + total\ waiting\ time + total\ service\ time\).

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 en kg, se necesita una conversión de cajas de manzanas a kg.

Mostrar cómo se pueden hacer las 2 conversiones posibles

Sea: - \(f_boxes\): el número de cajas necesarias 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

• Cuando se use pgr_pickDeliverEuclidean - Experimental:

  • 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 use pgr_pickDeliver - Experimental:

  • 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

El tiempo es relativo a 0. Todas las unidades de tiempo se convierte a la referencia de 0 y las mismas unidades de tiempo.

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.

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\)
0:00 am	minutos	\(9*60 = 54\)	\(16.5*60 = 990\)	10.5
9:00 am	horas	0	7.5	\(10.5 / 60 = 0.175\)
9:00 am	minutos	0	\(7.5*60 = 540\)	10.5

Manipulación del Factor

factor funciona como un multiplicador que convierte valores de distancia a unidades de tiempo, ya sea en valores matriciales o euclidianos.

• Los valores ya están en la unidad de tiempo deseada

  • factor debería ser 1

  • Cuando factor > 1 el tiempo de viaje es más rápido

  • Cuando factor > 1 el tiempo de viaje es más lento

Para el pgr_pickDeliverEuclidean - Experimental:

Trabajando con la unidad de tiempo en segundos, con x/y en lat/lon : Factor: dependería en la ubicación de los puntos y la velocidad promedio, digamos con velocidad de 25m/s.

Latitud	Conversión	Factor
45	1 grado de longitud es (78846.81m)/(25m/s)	3153 s
0	1 grado de longitud es (111319.46 m)/(25m/s)	4452 s

Para el pgr_pickDeliver - Experimental:

Dado \(v = d / t`entonces :math:`t = d / v\) y el factor se convierte en \(1 / v\)

Donde:

v:

Velocidad

d:

Distancia

t:

Tiempo

Para las siguientes equivalencias \(10m/s \approx 600m/min \approx 36 km/hr\)

Trabajando con segundos para las unidades de tiempo y la matriz en metros: Para un valor de longitud de 1000m en la matriz:

Unidades	velocidad	Conversión	Factor	Resultado
segundos	\(10 m/s\)	\(\frac{1}{10m/s}\)	\(0.1s/m\)	\(1000m * 0.1s/m = 100s\)
minutos	\(600 m/min\)	\(\frac{1}{600m/min}\)	\(0.0016min/m\)	\(1000m * 0.0016min/m = 1.6min\)
Horas	\(36 km/hr\)	\(\frac{1}{36 km/hr}\)	\(0.0277hr/km\)	\(1km * 0.0277hr/km = 0.0277hr\)

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