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 ahora, ¿no estoy seguro de qué enfoque tomar (VRPTW o programación de recursos o algo completamente diferente?)

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

Nuestro objetivo es asegurar que todos los remolques de desechos se transporten mientras

• minimizar la cantidad de remolques y automóviles en uso
• reunirse con ventanas de todos los tiempos para dejar el desperdicio
• "Equilibrar" los remolques, es decir, al final del día tenemos tantos remolques en cada ubicación como allí al comienzo del día

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

Otro método que consideré fue considerar primero los autos. Luego podría seleccionar la tarea más temprana y crear un gráfico de todas las tareas factibles después de eso. Si luego elegí la ruta más larga a través del gráfico que daría servicio al número máximo de cargas de remolque. Luego podría eliminar estas tareas de la lista de tareas y repetir hasta que todas las tareas fueran atendidas. Entonces necesitaría pasar esta lista de cargas de remolques para resolver la cantidad de remolques requeridos.

¡Se agradecería cualquier pensamiento en el enfoque!

Answer 1

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

He trabajado en empresas antes de que tenían software de enrutamiento de entrega y el enfoque que adoptaron fue usar un algoritmo genético para resolver un problema muy similar, aunque mucho mayor escala. Tomar un mira aquí Si no está familiarizado con el enfoque. De ese sitio:

1. Inicio] Genere una población aleatoria de cromosomas N (soluciones adecuadas para el problema)
2. Fitness] Evaluar la aptitud f (x) de cada cromosoma X en la población

3. Nueva población] Crear una nueva población repitiendo los siguientes pasos hasta que la nueva población esté completa

   Selección] Seleccione dos cromosomas parentales de una población de acuerdo con su estado físico (la mejor aptitud, la mayor oportunidad de ser seleccionados)

   Crossover] con una probabilidad de cruce sobre los padres para formar una nueva descendencia (hijos). Si no se realizó un crossover, la descendencia es una copia exacta de los padres.

   Mutación] con una probabilidad de mutación mutar nuevas descendientes en cada locus (posición en el cromosoma).

   Aceptando] coloque nuevos descendientes en una nueva población

4. Reemplazar] Use una nueva población generada para una mayor ejecución de algoritmo
5. Prueba] Si se cumple la condición final, detiene y devuelve la mejor solución en la población actual
6. Bucle] ir al paso 2

El truco para esto es codificar tus limitaciones en un "cromosoma" y escribir la función de "aptitud". La función de aptitud física tiene que tomar entradas de los resultados de una solución potencial y escupir una puntuación de cuán buena es una solución o tirarla si viola alguna de las restricciones.

Como lo mencionó Jiri, la ventaja de esta solución es que se le ocurre un mejor, aunque tal vez no sea el mejor, responda muy rápido y cuanto más tiempo se ejecute, mejor será la solución.

Answer 2

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

Probablemente desee ir con un algoritmo que pueda generar razonablemente rápidamente una solución lo suficientemente buena del problema. Asegúrese de crear una métrica para la calidad de la solución, obtendrá una buena manera de estimar el valor de la métrica para una solución ideal, luego establezca un % en el que desee que su solución sea de una solución ideal y simplemente Tome la primera solución que tiene métrica dentro de los límites. Esto tiene el beneficio adicional de si este algoritmo está tardando demasiado en calcular y lo aborta, aún puede usar la solución con la métrica calculada más baja, incluso si no está en sus límites esperados.

Sin embargo, no estoy seguro de qué enfoque para resolver el problema en sí. Sugeriría leer algunos artículos después de buscar en portal ACM. Supongo que UPS y FedEx probablemente tengan problemas similares, si las 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 suena como un gran candidato para una técnica de optimización evolutiva como la implementación del algoritmo genético que describe.

También he tenido un muy buen éxito en ciertos problemas con la optimización de enjambre de partículas (PSO). Básicamente, puede pensar en cada genoma como una partícula en algún espacio multimensional. Las coordenadas de la partícula son los parámetros de su cálculo (función de aptitud). Cada partícula se inicia al azar 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 ahora, dirección a la mejor partícula de la historia, dirección a un grupo local mejor etc ...

Al principio puede parecer bastante desalentador implementar un GA o PSO, pero le aseguro que es fácil escribir un marco pequeño que abstrae el algoritmo (GA/PSO) del dominio del problema real que está tratando de optimizar. Siempre puede volver 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 que pueda visualizar y ajustar fácilmente el algoritmo para que tenga un buen comportamiento de enjambre. Luego lo escala 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, por qué las técnicas evolutivas son atractivas es porque puede dedicar una parte fija del tiempo a la simulación y tomar la mejor respuesta hasta ahora cuando decida detenerse.

En mi experiencia, tiende a tomar tanto tiempo ajustando los parámetros a GA o PSO (una vez que tenga una implementación) como escribiría una solución heurística codificada, pero el beneficio es que cambiar la estrategia para encontrar la solución típicamente 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.

Dame un grito si necesita orientación para diseñar los marcos genéricos para cualquiera de los dos algoritmos. Debo señalar que también obtienes varios buenos marcos gratuitos de terceros. A veces me gusta codificar el mío porque entiendo todos los aspectos del algoritmo entonces y sé dónde puedo ajustar la estrategia.

Answer 4

Enfoque general:

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

Resolución:

He tenido menos éxito en el gas con limitaciones e incluso menos éxito en el gas con restricciones en las variables enteras (por ejemplo, el número de remolques en una ubicación). 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:

Estás resolviendo el problema en una red donde los últimos movimientos pueden ser reubicar un remolque vacío.

Buena suerte !

Answer 5

Busqueda local son una alternativa a los algoritmos genéticos. En el Competencia de horario internacional 2007, los algoritmos de búsqueda locales (como la búsqueda Tabu y el recocido simulado) superan claramente las entradas de algoritmo genético (1 a 4to lugar para LS versus 5to lugar para GA en la pista 1 de aproximadamente 80 competidores IIRC).

Además, eche un vistazo a algunas de las bibliotecas, como Optaplanner (Búsqueda de tabú, recocido simulado, aceptación tardía, código abierto, Java), JGAP (algoritmos genéticos, código abierto, Java), opente (búsqueda tabú, ...