Módulo didáctico de métodos exactos y enfoques heurísticos para la resolución de problemas de ruteo de vehículos (VRP)

Abstract

El presente trabajo muestra la programación y desarrollo de un módulo didáctico de métodos de solución para problemas VRP, para lo cual se ha utilizado herramientas cuantitativas, incorporando los conocimientos adquiridos dentro de la carrera de Ingeniería en Logística de la Universidad Politécnica Estatal del Carchi, para demostrar la importancia de conocer sobre los tipos de problemas existentes, los métodos de solución y su programación, y los recursos informáticos necesarios para su resolución. Mediante este trabajo se ha podido comprobar que los métodos más adecuados son las heurísticas y meta heurísticas ya que permiten obtener soluciones válidas a un problema específico, mientras que los métodos exactos que proporcionan la respuesta óptima del problema requieren muchos recursos computacionales para su funcionamiento. El módulo didáctico permite reconocer el método más eficiente con base en el tiempo de cómputo y la respuesta operativa del problema. Para el tiempo de cómputo, el algoritmo del vecino más cercano da la mejor respuesta en dos de los tres equipos en donde se realizaron los experimentos y en el otro fue el método de Clarke y Wright lo cual permite comprobar que las heurísticas son más eficientes en lo que respecta al uso de recursos computacionales. Para la solución de los parámetros operativos del problema la mejor respuesta es la del algoritmo brutal search, ya que al ser un método exacto siempre obtendrá la respuesta óptima del problema. Para el escenario planteado, la solución encontrada por medio del método exacto es más eficiente en un 5% que la heurística del vecino más cercano y un 43% que el método de Clarke y Wright. Los tiempos de ejecución de las heurísticas no sobrepasan los 0,2 segundos, por lo tanto son mas eficientes que el método exacto que requiere de un tiempo de ejecución de alrededor de 400 segundos.