pgr_pickDeliver
- Experimental¶
pgr_pickDeliver
- Problema de enrutamiento del vehículo de recogida y entrega
Advertencia
Posible bloqueo del servidor
Estas funciones pueden crear un bloque 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 con ventanas de tiempo.
Todos los vehículos son iguales.
La misma ubicación de Inicio.
La misma ubicación Final que es la misma que la ubicación de Inicio.
Todos los vehículos viajan a la misma velocidad.
Un cliente es para hacer una recogida o hacer una entrega.
tiene un tiempo abierto.
tiene tiempo de cierre.
tiene un tiempo de servicio.
tiene una ubicación (x, y).
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¶
Todos los camiones salen en el momento 0.
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.
el algoritmo generará una excepción cuando
Si hay un par de recogida-entrega que viola la ventana de tiempo
La velocidad, max_cycles, max_capacity tienen valores ilegales
Seoptimizarán seis iniciales diferentes - la mejor solución encontrada será el resultado
Firma¶
pgr_pickDeliver(Orders SQL, Vehicles SQL, Matrix SQL [, factor], [max_cycles] [,initial_sol]) RETURNS SET OF (seq, vehicle_number, vehicle_id, stop, order_id, stop_type, cargo, travel_time, arrival_time, wait_time, service_time, departure_time)
- Ejemplo:
Solve the following problem
Given the vehicles:
SELECT id, capacity, start_node_id, start_open, start_close
FROM vehicles;
id | capacity | start_node_id | start_open | start_close
----+----------+---------------+------------+-------------
1 | 50 | 11 | 0 | 50
2 | 50 | 11 | 0 | 50
(2 rows)
and the orders:
SELECT id, demand,
p_node_id, p_open, p_close, p_service,
d_node_id, d_open, d_close, d_service
FROM orders;
id | demand | p_node_id | p_open | p_close | p_service | d_node_id | d_open | d_close | d_service
----+--------+-----------+--------+---------+-----------+-----------+--------+---------+-----------
1 | 10 | 10 | 2 | 10 | 3 | 3 | 6 | 15 | 3
2 | 20 | 16 | 4 | 15 | 2 | 15 | 6 | 20 | 3
3 | 30 | 7 | 2 | 10 | 3 | 12 | 3 | 20 | 3
(3 rows)
The query:
SELECT * FROM pgr_pickDeliver(
$$SELECT id, demand,
p_node_id, p_open, p_close, p_service,
d_node_id, d_open, d_close, d_service
FROM orders$$,
$$SELECT id, capacity, start_node_id, start_open, start_close
FROM vehicles$$,
$$SELECT * from pgr_dijkstraCostMatrix(
'SELECT * FROM edges ',
(SELECT array_agg(id) FROM (SELECT p_node_id AS id FROM orders
UNION
SELECT d_node_id FROM orders
UNION
SELECT start_node_id FROM vehicles) a))
$$);
seq | vehicle_seq | vehicle_id | stop_seq | stop_type | stop_id | order_id | cargo | travel_time | arrival_time | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+---------+----------+-------+-------------+--------------+-----------+--------------+----------------
1 | 1 | 1 | 1 | 1 | 11 | -1 | 0 | 0 | 0 | 0 | 0 | 0
2 | 1 | 1 | 2 | 2 | 7 | 3 | 30 | 1 | 1 | 1 | 3 | 5
3 | 1 | 1 | 3 | 3 | 12 | 3 | 0 | 2 | 7 | 0 | 3 | 10
4 | 1 | 1 | 4 | 2 | 16 | 2 | 20 | 2 | 12 | 0 | 2 | 14
5 | 1 | 1 | 5 | 3 | 15 | 2 | 0 | 1 | 15 | 0 | 3 | 18
6 | 1 | 1 | 6 | 6 | 11 | -1 | 0 | 2 | 20 | 0 | 0 | 20
7 | 2 | 2 | 1 | 1 | 11 | -1 | 0 | 0 | 0 | 0 | 0 | 0
8 | 2 | 2 | 2 | 2 | 10 | 1 | 10 | 3 | 3 | 0 | 3 | 6
9 | 2 | 2 | 3 | 3 | 3 | 1 | 0 | 3 | 9 | 0 | 3 | 12
10 | 2 | 2 | 4 | 6 | 11 | -1 | 0 | 2 | 14 | 0 | 0 | 14
11 | -2 | 0 | 0 | -1 | -1 | -1 | -1 | 16 | -1 | 1 | 17 | 34
(11 rows)
Parámetros¶
Los parámetros son:
Columna |
Tipo |
Descripción |
---|---|---|
|
Orders SQL as described below. |
|
|
Vehicles SQL as described below. |
|
|
Matrix SQL as described below. |
Pick-Deliver optional parameters¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
1 |
Multiplicador de tiempo de viaje. Ver Factor handling |
|
|
10 |
Número máximo de ciclos a realizar en la optimización. |
|
|
4 |
Solución inicial a utilizar.
|
Orders SQL¶
Una instrucción SELECT que devuelve las siguientes columnas:
id, demand
p_node_id, p_open, p_close, [p_service,]
d_node_id, d_open, d_close, [d_service,]
Donde:
Columna |
Tipo |
Descripción |
---|---|---|
|
ANY-INTEGER |
Identificador del par de órdenes recogida-entrega. |
|
ANY-NUMERICAL |
Número de unidades en la orden |
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se abre la ubicación de recogida. |
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se cierra la ubicación de recogida. |
[ |
ANY-NUMERICAL |
La duración de la carga en el lugar de recogida.
|
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se abre la ubicación de entrega. |
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se cierra la ubicación de entrega. |
[ |
ANY-NUMERICAL |
The duration of the unloading at the delivery location.
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Columna |
Tipo |
Descripción |
---|---|---|
|
ANY-INTEGER |
The node identifier of the pickup, must match a vertex identifier in the Matrix SQL. |
|
ANY-INTEGER |
The node identifier of the delivery, must match a vertex identifier in the Matrix SQL. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Vehicles SQL¶
Una instrucción SELECT que devuelve las siguientes columnas:
id, capacity
start_node_id, start_open, start_close [, start_service,]
[end_node_id, end_open, end_close, end_service]
Donde:
Columna |
Tipo |
Descripción |
---|---|---|
|
ANY-NUMERICAL |
Identifier of the vehicle. |
|
ANY-NUMERICAL |
Maiximum capacity units |
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se abre la ubicación inicial. |
|
ANY-NUMERICAL |
La hora, en relación con 0, cuando se cierra la ubicación inicial. |
[ |
ANY-NUMERICAL |
La duración de la carga en la ubicación inicial.
|
[ |
ANY-NUMERICAL |
La hora, en relación con 0, cuando se abre la ubicación final.
|
[ |
ANY-NUMERICAL |
La hora, en relación con 0, cuando se cierra la ubicación final.
|
[ |
ANY-NUMERICAL |
La duración de la carga en la ubicación final.
|
Columna |
Tipo |
Descripción |
---|---|---|
|
ANY-INTEGER |
The node identifier of the start location, must match a vertex identifier in the Matrix SQL. |
[ |
ANY-INTEGER |
The node identifier of the end location, must match a vertex identifier in the Matrix SQL.
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Matrix SQL¶
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Return columns¶
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 |
---|---|---|
|
|
Sequential value starting from 1. |
|
|
Sequential value starting from 1 for current vehicles. The \(n_{th}\) vehicle in the solution.
|
|
BIGINT |
Current vehicle identifier.
|
|
INTEGER |
Sequential value starting from 1 for the stops made by the current vehicle. The \(m_{th}\) stop of the current vehicle.
|
|
|
|
|
|
Pickup-Delivery order pair identifier.
|
|
|
Cargo units of the vehicle when leaving the stop.
|
|
|
Travel time from previous
|
|
|
Time spent waiting for current location to open.
|
|
|
Time spent waiting for current location to open.
|
|
|
Service duration at current location.
|
|
|
|
Ver también¶
Índices y tablas