Optimización de ruta para múltiples vehículos.

12

Tengo 100 destinos y 5 vehículos y necesito codificar una solución que enrute eficientemente los vehículos a cada destino, por lo que cada destino es visitado por 1 de los vehículos. Algunos de estos destinos también podrían tener ventanas de tiempo para visitar.

Estoy usando PostgreSQL y PostGIS, y estaba buscando usar pgrouting, pero no estoy seguro de que sea adecuado para múltiples vehículos, por mi limitado conocimiento de Dijkstra, etc. Creo que están diseñados para un solo vehículo.

¿Alguna idea sobre si pgrouting puede resolver este problema, y ​​si es así, algún ejemplo de código? Si no, ¿hay alguna alternativa de código abierto que pueda hacerlo?

routing pgrouting RichW
fuente
Tengo una necesidad similar como la tuya. Estoy operando un negocio de NPO NEMT (Transporte médico no de emergencia). Necesitamos transportar a los pacientes a sus citas con tiempo para que los recojan o entreguen. La mayoría de las solicitudes se reciben por adelantado, otras están en el acto. DARP parece ser un buen algoritmo. ¿Necesita solucionador DARP por la misma razón? Nick
Nick Bazzi

Respuestas:

10

pgRouting tiene una función llamada solucionador DARP (Dial-a-Ride Problem) :

El solucionador de problemas de Dial-a-Ride (DARP) intenta minimizar el costo de transporte al tiempo que satisface las restricciones de nivel de servicio al cliente (violación de ventanas de tiempo, tiempos de espera y de viaje) y restricciones de flota (número de automóviles y capacidad, así como la ubicación del depósito).

Más sobre DARP y pgRouting:

Para usar esta nueva función, debe instalar la rama darp de pgRouting .

Las respuestas a esta pregunta sobre stackexchange pueden proporcionar información adicional: Algoritmo de enrutamiento para múltiples vehículos con múltiples caídas .

bajo oscuro
fuente
Inicialmente vi el algoritmo DARP, pero lo rocé porque no me di cuenta de que podría usarse para los correos. ¡Parece que eso hará bien el trabajo! Es una pena que la página de documentación no tenga ejemplos de uso, sin embargo, podría ser un caso de búsqueda a través del código fuente para ver cómo funciona.
RichW
1

Si bien ESRI ArcLogistics claramente no se ajusta a sus necesidades particulares de usar PostGIS o código abierto, para otros que pueden no tener las habilidades de programación o el tiempo para implementar sus propias soluciones, es una buena extensión lista para usar para ArcGIS que está diseñado para realizar las tareas que describió.

Actualmente también están ofreciendo una prueba gratuita de 30 días si quieres probarlo.

RyanKDalton
fuente
Fui a ESRI HQ la semana pasada para discutir este software para ellos, pero no parece satisfacer nuestras necesidades (necesita ejecutarse en un servidor y también es bastante costoso). Excelente pieza de kit sin embargo!
RichW
Nuestro producto FleetEngine se ejecuta como un servidor con una interfaz SOAP. 100 destinos, 5 vehículos y ventanas de tiempo están definitivamente dentro de las capacidades. Está muy cerca de la producción, contácteme para obtener una licencia de prueba. No es de código abierto o gratuito, pero por otro lado no es tan caro como ArcLogistics.
Uffe Kousgaard
1
Hola Uffe, ¿puede tener en cuenta las restricciones del vehículo (peso y dimensiones) y clasificar los paquetes en los vehículos en consecuencia? Además, ¿funciona en el Reino Unido y utiliza datos del historial de carreteras para calcular velocidades, etc.?
RichW
Si a todas tus preguntas. Utiliza complementos simples de peso / volumen. Tampoco puede empacar en 3D, sería demasiado esperar. Soporte completo para redes de calles en cualquier país también, pero necesita suministrar la red de calles. Lamentablemente no vi la respuesta antes, pensé que esta discusión había terminado. Envíame un correo electrónico a [email protected] si quieres discutirlo más a fondo.
Uffe Kousgaard