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

Ruiz Alamillos, María de Guía (2019). Modelado del problema Traveling Repairman Problem y comparación de técnicas para su resolución. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. Industriales (UPM).

Description

Title: Modelado del problema Traveling Repairman Problem y comparación de técnicas para su resolución
Author/s:
  • Ruiz Alamillos, María de Guía
Contributor/s:
  • Emde, Simon
  • Ortega Mier, Miguel Ángel
Item Type: Final Project
Degree: Grado en Ingeniería en Tecnologías Industriales
Date: February 2019
Subjects:
Freetext Keywords: Multiple Traveling Repairman Problem, programación entera mixta, programación de restricciones, restricción de eliminación de subtours, latency
Faculty: E.T.S.I. Industriales (UPM)
Department: Ingeniería de Organización, Administración de Empresas y Estadística
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (3MB) | Preview

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.

More information

Item ID: 54351
DC Identifier: http://oa.upm.es/54351/
OAI Identifier: oai:oa.upm.es:54351
Deposited by: Biblioteca ETSI Industriales
Deposited on: 19 Mar 2019 09:16
Last Modified: 18 May 2019 22:30
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM