Diseño de algoritmo de enrutamiento de vehículos/programación de recursos

Question

Mi primera publicación aquí - con la esperanza de que pueda ayudarme a diseñar un algoritmo que he estado considerando por un tiempo - no estoy seguro de qué enfoque tomar (VRPTW o programación de recursos o algo más por completo !?)

Para ponerlo en un ejemplo de palabra real, tenemos una gran cantidad de residuos de jardín en un pequeño número de ubicaciones (generalmente menos de 5). Todos los desechos deben ser transportados a otros lugares dentro de los plazos establecidos. Para mover los desechos del jardín tenemos remolques que deben ser remolcados por automóviles. Los desperdicios de jardín solo se pueden tirar en el depósito de desechos en ciertos momentos (ventanas de tiempo). En algunos sitios podemos dejar el remolque para que lo llene o vacíe la gente de allí, pero en otros lugares el conductor del automóvil tiene que hacerlo él mismo y el automóvil debe permanecer allí. Se pueden calcular todos los tiempos (es decir, tiempos de carga/descarga, tiempos de tránsito, etc.). Los automóviles pueden moverse entre sitios sin un remolque, los remolques pueden ser remolcados vacíos, pero los remolques no pueden moverse entre ubicaciones.

Nuestro objetivo es asegurar que todas las cargas de remolque de los residuos son transportados mientras

• reducir al mínimo el número de remolques y coches en uso
• reunión todas las ventanas de tiempo para dejar a los residuos
• “equilibrar” la remolques - es decir, al final del día tenemos tantos remolques en cada ubicación como estaban al comienzo del día

Pensé en abordar esto como una algoritmo de programación de recursos, pero no estoy seguro de cómo manejar el "equilibrio" de los trailers.

Otro método que consideré fue considerar primero los autos. Luego podría seleccionar la tarea más antigua y crear un gráfico de todas las tareas posibles después de eso. Si luego elegí el camino más largo a través del gráfico que serviría la cantidad máxima de cargas de remolque. Luego pude eliminar estas tareas de la lista de tareas y repetir hasta que se repararon todas las tareas. Entonces necesitaría revisar esta lista de cargas de remolque para calcular la cantidad de trailers requeridos.

¡Se agradecerá cualquier idea sobre el enfoque!

Answer 1

Estoy de acuerdo con Jiri ...desea un algoritmo heurístico que se acerque razonablemente con una solución aceptable rápidamente y luego lo refine desde allí.

He trabajado en empresas antes que el software de enrutamiento de entrega y el enfoque que tomaron fue utilizar un algoritmo genético para resolver un problema muy similar, aunque a una escala mucho mayor. Tome un look here si no está familiarizado con el enfoque. A partir de ese sitio:

1. [Inicio] Generar población aleatoria de n cromosomas (soluciones adecuadas para el problema)
2. [Fitness] Evaluar la idoneidad f (x) de cada cromosoma x en la población

3. [nuevo población] Crear una nueva población mediante la repetición de los pasos siguientes hasta que la nueva población se ha completado

   [Selección] Seleccione dos cromosomas de los padres de una población de acuerdo a su estado físico (el mejor estado físico, la mayor posibilidad de ser seleccionado)

   [Crossover] Con una probabilidad de cruce cruza a los padres para formar una nueva descendencia (niños). Si no se realizó el cruce, la descendencia es una copia exacta de los padres.

   [Mutación] Con una probabilidad de mutación, mutar nuevas crías en cada locus (posición en el cromosoma).

   [Aceptar] Coloque nuevas crías en una nueva población

4. [Reemplazar] Use nueva población generada por un plazo adicional de algoritmo
5. [Test] Si la condición final es satisfecha, detener y devolver el mejor solución en la población actual
6. [Loop] Ir al paso 2

el truco para esto es la codificación de sus limitaciones en un "cromosoma" y escribir la función de "fitness". La función de acondicionamiento físico tiene que tomar las entradas de los resultados de una posible solución y escupir una puntuación de qué tan buena es una solución o eliminarla si viola alguna de las restricciones.

Como lo menciona Jiri, la ventaja de esta solución es que ofrece una respuesta viable, aunque tal vez no la mejor, muy rápidamente y cuanto más tiempo la deje funcionar, mejor será la solución.

Answer 2

Estamos hablando de un algoritmo completo de NP aquí seguro, más allá de un número de autos y trailers no va a ser una tarea en la que obtendría una mejor solución de todas las soluciones posibles y luego podría descartar eso e ir de nuevo para evitar el camino más largo como sugieres. Si diseña su algoritmo de esa manera, es muy probable que un día agregue un poco más de automóviles y remolques y que nunca termine de calcular la solución.

Probablemente quiera ir con un algoritmo que pueda generar bastante rápidamente una solución lo suficientemente buena del problema. Asegúrese de crear una métrica para la calidad de la solución, obtenga una buena forma de estimar el valor de la métrica para una solución ideal, luego establezca un% dentro del cual desea que su solución sea de una solución ideal y simplemente tome la primera solución que tenga métrica dentro de los límites. Esto tiene la ventaja adicional de que si este algoritmo tarda demasiado tiempo en computarse y lo cancela, aún puede usar la solución con la métrica calculada más baja, incluso si no está dentro de los límites esperados.

No estoy seguro de qué enfoque tomar la solución del problema en sí mismo. Sugeriría leer algunos artículos después de buscar en acm portal. Supongo que UPS y Fedex probablemente tengan problemas similares, si los agrega como palabras clave a una búsqueda en Google, podría obtener algunos resultados más útiles.

Answer 3

Tiendo a estar de acuerdo con Robert. Esto me parece un gran candidato para una técnica de optimización evolutiva, como la implementación del Algoritmo Genético que él describe.

También he tenido muy buenos resultados en ciertos problemas con la Optimización de Enjambre de Partículas (PSO). Básicamente, se puede pensar en cada genoma como una partícula en algún espacio multidimensional. Las coordenadas de la partícula son los parámetros de su cálculo (función de aptitud). Cada partícula se inicia aleatoriamente con una velocidad aleatoria. Para cada iteración de la simulación, actualiza la posición de cada partícula con su vector de viaje actual, y luego agrega componentes de otros vectores como: dirección a la mejor partícula hasta el momento, dirección a la mejor partícula, dirección a un grupo local mejor etc ...

Puede parecer desalentador al principio implementar un GA o PSO, pero le aseguro que es fácil escribir un pequeño marco que abstraiga el algoritmo (GA/PSO) del dominio real del problema que estás tratando de optimizar Siempre puede recurrir a Wikipedia para obtener detalles de los algoritmos.

Una vez que tengo un marco, normalmente comienzo con un problema de 2 parámetros (probablemente una simplificación de su problema, o ubicaciones X e Y en una imagen), para poder visualizar y ajustar fácilmente el algoritmo para obtener buen comportamiento de enjambre Luego lo escalo a más dimensiones.

Me gusta este enfoque porque me permite optimizar fácilmente los problemas que tienen partes bastante complejas e intrincadas en la declaración del problema real (como los automóviles y los remolques).

Además, la razón por la cual las técnicas evolutivas son atractivas es porque puede dedicar una porción fija de tiempo a la simulación y obtener la mejor respuesta hasta el momento cuando decide detenerse.

En mi experiencia, tiendes tanto tiempo ajustando los parámetros al GA o al PSO (una vez que tienes una implementación) como si estuvieras escribiendo una solución heurística codificada, pero el beneficio es que cambias la estrategia para encontrar la solución generalmente solo requiere cambios de parámetros o intercambiar algoritmos muy bien definidos con otra implementación, en lugar de codificar una estrategia completamente diferente para resolver el problema heurísticamente desde cero.

Por favor, dame un grito si necesitas una guía sobre el diseño de los marcos genéricos para cualquiera de los dos algoritmos. Debo señalar que también hay muchos buenos frameworks de terceros gratuitos. A veces me gusta codificar la mía porque entiendo todos los aspectos del algoritmo y sé dónde puedo ajustar la estrategia.

Answer 4

Enfoque general:

Dado que el problema es pequeño, sugeriría un enfoque donde se agrega coches y remolques hasta obtener una solución factible en lugar de tratar de minimizar los coches y remolques.

Solución:

que he tenido menos éxito en el gas con las limitaciones e incluso menos éxito en el gas con restricciones sobre las variables enteras (por ejemplo, el número de remolques en un lugar). Puede ser que la programación de restricciones sea un mejor enfoque ya que solo desea generar una solución factible para un número determinado de automóviles y remolques en lugar de tratar de minimizar la distancia recorrida.

Observación:

que se está resolviendo el problema en una red en la que los últimos movimientos pueden ser de trasladar un remolque vacío.

¡Buena suerte!

Answer 5

Local Search son una alternativa a los algoritmos genéticos. En el Concurso internacional de cronometraje , los algoritmos de búsqueda local (como la búsqueda tabu y el recocido simulado) superaron claramente las entradas del algoritmo genético (del 1 al 4 para LS frente al 5 ° lugar para GA en la pista 1 de aproximadamente 80 competidores IIRC).

Además, eche un vistazo a algunas de las bibliotecas, como OptaPlanner (Tabu Search, recocido simulado, aceptación tardía, código abierto, java), JGap (algoritmos genéticos, código abierto, java), OpenTS (Tabu Búsqueda, ...