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

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

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

Índices y tablas