En un problema de rutas de vehículos (Vehicle Routing Problem – VRP), en general, se trata de averiguar las rutas de una flota de transporte para dar servicio a unos clientes.
Este tipo de problemas pertenece a los problemas de optimización combinatoria. La función objetivo depende del tipo de problema, entre las mas comunes encontramos:
- minimizar el coste total de operación.
- Minimizar el tiempo total de transporte
- Minimizar la distancia total recorrida
- Minimizar el tiempo de espera.
- Maximizar el beneficio
En este caso intentaremos encontrar la ruta con la distancia minima para llegar del nodo de origen al nodo de fin, para esto utilizaremos restricciones del flujo de vehiculos en cada nodo y resolveremos el modelo utilizando la herramienta de SOLVER de Excel.
Este problema manualmente puede ser resuelto utilizando El algoritmo de Dijkstra, la idea en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
En el video explicamos el caso y como resolverlo. Espero les sea útil:
Esta metodologia puede ser usado en casos mas complejos o para otro tipo de problemas de investigación de operaciones
Buenos días:
Este método ¿podría ser aplicado para resolver el problema del cartero chino?, es decir, ¿se podría aplicar para resolver una reparto con la distancia más corta pasando por todos los puntos?
Gracias y un saludo de Roberto Gómez (diariodya@gmail.com)
Hola, quisiera saber cómo se pueden romper esos ciclos locales
Hola Tania,
tienes q ir agregando restricciones manualmente cuando encuentres los ciclos locales.
poninedo al suma igual a 0 evitas q solver seleccione esa ruta.
Saludos
Esta genial el aporte. Un cordial saludo.