Un modelo matemático y una mateheurística para una nueva variante del pollution traveling salesman problem – Karen García Vásquez – Sala 3
10:15 – 10:35 AM
RESUMEN
UN MODELO MATEMÁTICO Y UNA VARIANTE DEL POLLUTION TRAVELING SALESMAN PROBLEM
Karen García Vásquez
Magister en Ingeniería Industrial
Universidad del Bío-Bío
Concepción, Chile
Email: karen.garcia1901@alumnos.ubiobio.cl
RESUMEN EXTENDIDO
Se presenta una nueva variante del Pollution Traveling Salesman Problem enfocada en el consumo de combustible y las emisiones de polución. El Pollution Traveling Salesman Problem generaliza el TSP, por tanto, es clasificado como NP-Hard. El PTSP consiste en el que un vehículo entregue a cada cliente una carga, que posee como atributo su masa, mediante un ciclo hamiltoniano que minimice una función objetivo que considera la velocidad de cada arco, la masa del camión, la masa de la carga del camión pendiente de entrega, y la distancia recorrida. Se presenta un nuevo modelo matemático, y se realizan extensos experimentos computacionales para determinar el comportamiento de solver de programación lineal entera (Gurobi, Cplex, COPT, HiGHS, SCIP) para cinco variantes del Pollution Traveling Salesman Problem. Basado en resultados preliminares se propone una mateheurística que permite por el medio de heurísticas mejorar soluciones enteras y/o fraccionarias en el árbol de branch-and-bound por medio del uso de Callback. Se presentarán resultados preliminares sobre la aplicación de la mateheurística. Para la implementación de heurísticas y modelos matemáticos se utilizó Julia 1.7 y JuMP 1.0; se consideraron las bibliotecas de instancias del PRP y luego fueron adaptadas al PTSP. Los resultados preliminares muestran que el mezclar heurísticas y técnicas exactas para resolver modelos matemáticos impactan en el tiempo de cómputo y en %gap obtenido.
Palabras clave: TSP, heurística, Branch-and-bound, PTSP, algoritmos híbridos
El Encuentro de Investigación de Estudiantes de Postgrado es una instancia de divulgación de los resultados de proyectos de investigación realizados por estudiantes de postgrado de instituciones de educación superior. Constituye un espacio de diálogo interdisciplinario entre estudiantes de postgrado de universidades chilenas y extranjeras, investigadoras e investigadores que abordan, desde múltiples perspectivas, problemáticas relevantes para la región y el país.
