El problema relacionado con la búsqueda del conjunto óptimo de rutas que atiende a un conjunto de pasajeros con ubicaciones de origen y destino, así como una ventana de tiempo de tiempos de recogida permitidos, se refiere al Problema de enrutamiento del vehículo con ventanas de tiempo de recogida y entrega. Además de ser un problema de optimización de NP-Hard, es una versión muy restringida del problema general de enrutamiento de vehículos, que es NP-Hard para empezar. Como resultado, las restricciones de la recogida y la entrega y la ventana de tiempo agregan una cantidad decente de complejidad a un problema que ya era desafiante.
Este tipo de problema generalmente es inviable de resolver utilizando métodos exactos, y es muy difícil generar soluciones de buena calidad (aunque no óptimas) utilizando la heurística de construcción de soluciones. Además, a menos que [math] \ mathcal {P} = \ mathcal {NP} [/ math], sea imposible escribir un algoritmo de aproximación de tiempo polinómico para este problema en general, porque en el caso de que solo haya un vehículo y una recolección las ubicaciones y las ventanas de tiempo no están restringidas, incluye el problema del vendedor ambulante, que no se puede aproximar en tiempo polinómico para gráficos generales (es decir, sin la desigualdad triangular) a menos que [math] \ mathcal {P} = \ mathcal {NP} [/ math] .
La conclusión es que para generar de manera eficiente soluciones de calidad decentes para su problema, se deberá utilizar algún tipo de metaheurística. Hay una infinidad de opciones, pero un enfoque simple y probablemente efectivo es implementar una búsqueda de vecindario variable con vecindarios entre rutas (intercambiar dos pasajeros entre dos rutas) e intrarutas (2 opciones).
- ¿Cómo calcula Google la distancia entre dos lugares en Google Maps?
- Si existen múltiples rutas más cortas entre 2 nodos en un gráfico no dirigido, ¿es posible imprimirlas todas utilizando el algoritmo de Dijkstra?
- Alguien en mi escuela secundaria dijo que en realidad no puedo resolver un cubo de Rubik porque tengo que confiar en patrones (algoritmos). ¿Cuán verdadera es esta afirmación?
- ¿Cuáles son algunos libros similares a Programming Pearls?
- ¿Qué algoritmo es mejor para una variante 4 * 4 * 4 * 4 del último dedo del pie tic-tac considerando un límite de tiempo de 15 segundos?
