Modelado del problema Traveling Repairman Problem y comparación de técnicas para su resolución

Abstract

En el contexto actual de globalización, la competitividad y la búsqueda de métodos y actividades dirigidas a su mejora, se ha convertido en una necesidad estratégica para las empresas. De esta forma, el término optimización cobra especial relevancia, entendido como la forma de administrar los recursos disponibles de la manera más eficiente posible. Uno de los ámbitos donde se encuentra más presente esta filosofía de mejora, es el logístico. La actividad logística se ha convertido por su crecimiento y consolidación en uno de los sectores esenciales para la economía española. Por este motivo, la gestión eficiente de las actividades que lo integran, dota a las empresas de una ventaja sustancial frente a sus competidores. En este contexto, se enmarca este estudio, dirigido a determinar aquellas rutas que permitan optimizar el transporte de productos o la visita a clientes situados en distintos puntos. En este documento se estudia el problema de los múltiples agentes reparadores o Multiple Traveling Repairman Problem (k-TRP), con objeto de comparar dos técnicas de modelado y resolución. Esta formulación, a diferencia de la mayoría de los problemas de enrutamiento de vehículos, está centrada en el cliente en lugar de tratar de determinar las rutas de mínima distancia. El objetivo del k-TRP es encontrar las m rutas inconexas, correspondientes a los m vehículos disponibles, minimizando la suma de los tiempos de espera de cada uno de los clientes. Este problema está sujeto a una serie de limitaciones que deben verificarse: todos los clientes deben ser visitados una única vez, todos los vehículos deben partir de un origen común y todas las rutas deben estar conectadas con el punto de partida. Para la formulación y resolución del problema, se han empleado dos procedimientos con características y representaciones distintas. En un primer momento se aborda el problema desde un punto de vista matemático, empleando la programación entera mixta, técnica que permite modelar y resolver problemas cuyas variables pueden ser tanto enteras como continuas. Adicionalmente, se presentan los mecanismos de resolución más empleados en estos modelos, donde destacan el Branch & Bound y los planos de corte, así como las distintas combinaciones de los mismos. Además, se exponen de forma detallada las distintas formulaciones características para las restricciones de eliminación de subtours o Subtour Elimination Constraints (SEC), que implican que todas las rutas estén conectadas con el origen. Las formuladas por Dantzig, Fulkerson y Johnson (DFJ) imponen que el número de vértices y arcos que forman una subruta deben ser iguales, logrando así la rotura del subciclo. Sin embargo, las restricciones de Miller- Tucker -Zemlin (MTZ), eliminan las subrutas estableciendo una serie de contradicciones, generando restricciones con menos fuerza. Esto también se verifica en el análisis realizado a los poliedros resultantes de la adición de cada una de las restricciones. Sin embargo, se comprueba la redundancia de la incorporación de las restricciones de DFJ a la formulación matemática, ya que para el cálculo de la función objetivo, se requiere la utilización de variables que establezcan un orden en la ruta, variables que se encuentran en las restricciones de MTZ. En segundo lugar, se estudia la posibilidad de formular el k-TRP con la técnica de programación de restricciones (PR), creando uno de los primeros modelos con PR para este problema. Adicionalmente, se desarrolla un análisis de sus mecanismos de resolución, basados en la eliminación de valores del dominio de variables. Para la verificación de su eficiencia, ambos modelos se implementan en los programas AIMMS y MiniZinc respectivamente. En el caso de la formulación matemática, se emplean mecanismos de resolución en el que se combinan B&B con herramientas de planos de corte y métodos heurísiticos, comprobando que son suficientes para la resolución del problema. Sin embargo, en el modelador MiniZinc, los mecanismos de resolución del solver empleado no resultan suficientes, teniendo que incorporar herramientas adicionales para la agilización de la resolución. El contraste de ambos modelos que constituyen el objeto de este trabajo permite concluir que, los resultados computacionales obtenidos en el modelo de programación matemática son mucho mejores que los resultantes de la programación con restricciones para instancias de tamaño medio.