bachelorThesis
Solución al problema de ruteo de vehículos con capacidad limitada "CVRP" a través de la heurística de barrido y la implementación del algoritmo genético de Chu-beasley
Autor
Orrego Cardozo, Juan Pablo
Institución
Resumen
Los problemas de ruteo de vehículos han sido objeto de investigación intensiva por más de 50 años, debido al gran interés científico que éstos tienen por ser considerados NP-completos y donde algunas instancias Euclidianas con 75 nodos aún no han sido resueltas hasta su óptimo (Prins, Christian (2004)). Por otra parte, se debe a su importancia cómo modelo de optimización, en cantidades de campos de aplicación, como son, transporte, logística, comunicaciones, manufactura, militar, entre otros. El problema “tradicional” CVRP (por sus siglas en inglés Capacitated Vehicle Routing Problem) puede ser descrito en su forma más sencilla como una flota de vehículos con capacidades uniformes que tiene que satisfacer la demanda de un grupo de clientes a través de un conjunto de rutas que empiezan y terminan en un almacén común y que representan el menor costo posible, así como la identificación del orden de visita a los mismos (Gendreau et al. (2012)). Como consecuencia de los altos niveles actuales de congestión vehicular, de los fuertes consumos de energía de los vehículos de carga, así como del impacto negativo que estos últimos tienen en el medio ambiente como emisiones, accidentes, ruido y vibraciones; en los últimos años uno de los problemas que más ha interesado a la logística urbana “City Logistics” ha sido el de optimizar globalmente los sistemas de transporte, considerando los costos y beneficios de esquemas tanto públicos como privados. Estos conceptos de City Logistics, han sido implementados y son objeto de interés presentes en muchos modelos desarrollados recientemente para predecir y establecer sistemas inteligentes de transporte (Taniguchi y Thompson (2002)). Cómo caso particular se relacionan posteriormente todos los modelos generales y explícitos del VRP y sus variantes.