Supported versions:

pgr_pickDeliverEuclidean - Experimental¶

pgr_pickDeliverEuclidean - Problema de Ruteo del Vehículo de Recogida y Entrega

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

Disponibilidad

Versión 3.0.0
- Nueva función experimental

Sinopsis¶

Problema: Distribuya y optimice los pares de recogida-entrega en una flota de vehículos.

El problema de optimización es NP-hard.
Recogida y Entrega:
- capacitado
- con ventanas de tiempo.
Los vehículos
- tienen (x, y) ubicaciones de inicio y finalización.
- tener un inicio y un final de los tiempos de servicio.
- tienen horarios de apertura y cierre para las ubicaciones de inicio y finalización.
Un pedido es para hacer una recogida y una entrega.
- tiene (x, y) ubicaciones de recogida y entrega.
- tiene horarios de apertura y cierre para los lugares de recogida y entrega.
- tiene una recogida y entrega de tiempos de servicio.
Hay un cliente donde entregar una recogida.
- tiempo de viaje entre los clientes es distancia / velocidad
- La recogida y entrega se realizan con el mismo vehículo.
- La recogida se realiza antes de la entrega.

Características¶

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.
Seis diferentes soluciones iniciales opcionales
- la mejor solución encontrada será el resultado

Firma¶

pgr_pickDeliverEuclidean(orders_sql, vehicles_sql [,factor, max_cycles, initial_sol])
RETURNS SET OF (seq, vehicle_seq, vehicle_id, stop_seq, stop_type, order_id,
    cargo, travel_time, arrival_time, wait_time, service_time, departure_time)

Parámetros¶

Los parámetros son:

orders_sql, vehicles_sql [,factor, max_cycles, initial_sol]

Donde:

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 Pick & Deliver Vehicles SQL 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` Un 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

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

Una instrucción SELECT que devuelve las siguientes columnas:

id, demand
p_x, p_y, p_open, p_close, [p_service, ]
d_x, d_y, d_open, d_close, [d_service, ]

Donde:

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

Una instrucción SELECT que devuelve las siguientes columnas:

id, capacity
start_x, start_y, start_open, start_close [, start_service, ]
[ end_x, end_y, end_open, end_close, end_service ]

Donde:

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

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

Ejemplo¶

En este ejemplo se utilizan los siguientes datos: TODO put link

SELECT * FROM pgr_pickDeliverEuclidean(
    'SELECT * FROM orders ORDER BY id',
    'SELECT * from vehicles'
);
 seq | vehicle_seq | vehicle_id | stop_seq | stop_type | order_id | cargo |  travel_time  | arrival_time  | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+----------+-------+---------------+---------------+-----------+--------------+----------------
   1 |           1 |          1 |        1 |         1 |       -1 |     0 |             0 |             0 |         0 |            0 |              0
   2 |           1 |          1 |        2 |         2 |        3 |    30 |             1 |             1 |         1 |            3 |              5
   3 |           1 |          1 |        3 |         3 |        3 |     0 | 1.41421356237 | 6.41421356237 |         0 |            3 |  9.41421356237
   4 |           1 |          1 |        4 |         2 |        2 |    20 | 1.41421356237 | 10.8284271247 |         0 |            2 |  12.8284271247
   5 |           1 |          1 |        5 |         3 |        2 |     0 |             1 | 13.8284271247 |         0 |            3 |  16.8284271247
   6 |           1 |          1 |        6 |         6 |       -1 |     0 | 1.41421356237 | 18.2426406871 |         0 |            0 |  18.2426406871
   7 |           2 |          1 |        1 |         1 |       -1 |     0 |             0 |             0 |         0 |            0 |              0
   8 |           2 |          1 |        2 |         2 |        1 |    10 |             1 |             1 |         1 |            3 |              5
   9 |           2 |          1 |        3 |         3 |        1 |     0 |  2.2360679775 |  7.2360679775 |         0 |            3 |  10.2360679775
  10 |           2 |          1 |        4 |         6 |       -1 |     0 |             2 | 12.2360679775 |         0 |            0 |  12.2360679775
  11 |          -2 |          0 |        0 |        -1 |       -1 |    -1 | 11.4787086646 |            -1 |         2 |           17 |  30.4787086646
(11 rows)

Ver también¶

Funciones de Ruteo de Vehículos - Categoría (Experimental)
Las consultas utilizan la red Datos Muestra .

Índices y tablas