Conic programming for routing and location problems

Esta tesis doctoral desarrolla nuevos problemas en el campo de los modelos de transporte, con una perspectiva orientada al uso de drones. En este trabajo se definen nuevos modelos de transporte, tomando ciertos elementos de los problemas de localización, los cuales se resuelven con herramientas de la investigación operativa, como la optimización. La tesis se divide en dos partes. La Parte I se compone de cinco capítulos que abordan diferentes aspectos. El Capítulo 1 introduce el marco teórico que permite comprender los problemas que se desarrollan y cuáles son los últimos avances alcanzados en la literatura. En el Capítulo 2 se establecen qué objetivos se persiguen en este trabajo. El Capítulo 3 presenta los resultados obtenidos hasta la fecha. A continuación, en el Capítulo 4, se lleva a cabo una discusión detallada de dichos resultados. Finalmente, en el Capítulo 5 se presentan las conclusiones generales extraídas de la tesis. La Parte II también está compuesta por seis capítulos, del 6 al 11. Cada uno de los capítulos en la Parte II puede ser abordado de manera independiente y representa una contribución original de investigación en sí mismo. En el Capítulo 6, se aborda una extensión del problema del cartero rural que se centra en diseñar rutas que deben visitar diferentes elementos dimensionales en lugar de simplemente aristas. Este problema modela la planificación de rutas para drones u otros vehículos, donde es necesario visitar múltiples ubicaciones geográficas para entregar bienes o servicios, y luego pasar directamente a la siguiente ubicación utilizando desplazamientos en línea recta. En este capítulo, se presentan dos familias de formulaciones de programación matemática. La primera familia se basa en un modelo por etapas y captura diversas características con aplicaciones prácticas, pero tiene la desventaja de utilizar índices de tres variables. La segunda familia de formulaciones prescinde de estas etapas y utiliza propiedades de conectividad para garantizar la correcta definición de las rutas. Estas formulaciones se comparan utilizando instancias con diferentes formas, como conjuntos representables con conos de segundo orden (SOC), entornos poliédricos y poligonales. Los resultados computacionales presentados en este trabajo demuestran que los modelos son efectivos y que las formulaciones pueden resolver de manera óptima instancias de tamaño mediano, similares a otros problemas combinatorios con entornos que han sido estudiados en la literatura. Para resolver instancias más grandes, también se presenta un algoritmo heurístico que consta de dos fases: agrupación y un metaheurístico de búsqueda local. Este algoritmo ofrece buenos resultados al generar soluciones factibles cercanas al óptimo que, además, puede utilizarse para inicializar los solvers con dichas soluciones. El Capítulo 7 se enfoca en dos problemas distintos de diseño de rutas en el espacio continuo que involucran entornos y barreras: el problema del camino más corto y el problema del viajante de comercio con entornos y barreras. La presencia de estos dos elementos, entornos y barreras, hace que los problemas sean más desafiantes en comparación con sus contrapartes estándar. Al combinar ambos aspectos, surge un nuevo problema que hasta la fecha no ha sido abordado. No obstante, este problema tiene aplicaciones relevantes en actividades de inspección y vigilancia, así como en la industria de reparto, especialmente cuando existe una demanda uniformemente distribuida en ciertas regiones. En el capítulo se presentan formulaciones de programación matemática para ambos problemas, asumiendo barreras lineales y entornos representables con conos de segundo orden. Estos supuestos conducen a formulaciones enteras mixtas con conos de segundo orden , las cuales son sometidas a preprocesamiento y se refuerzan mediante desigualdades válidas. Además, se llevan a cabo experimentos computacionales que demuestran que el método exacto puede resolver instancias con 75 entornos y un rango de 125 a 145 barreras. El Capítulo 8 aborda problemas de localización de instalaciones en un espacio continuo con vecinos y barreras. Específicamente, se analiza el problema de la p-mediana con vecinos y barreras lineales en dos situaciones diferentes. Como primer bloque de construcci ón, se aborda el problema asumiendo que los entornos no son visibles entre sí y, por lo tanto, no existen rutas rectilíneas que unan dos entornos sin cruzar barreras. Bajo esta hipótesis, se obtiene una formulación válida de programación lineal entera mixta. Al eliminar esa hipótesis, se obtiene el problema más general y realista, pero con el inconveniente de ser más desafiante. Adaptando los elementos de la primera formulación, también se desarrolla otra formulación válida de programación bilineal entera mixta. Ambas formulaciones manejan barreras lineales y entornos que son representables con conos de segundo orden, los cuales se preprocesan y fortalecen con desigualdades válidas. Estas formulaciones de programación matemática también son fundamentales para generar un algoritmo matheurístico adaptado que proporciona soluciones de buena calidad para ambos problemas en un tiempo de cómputo corto. El capítulo también detalla una amplia experiencia computacional que demuestra que los enfoques exactos y heurísticos son útiles: el enfoque exacto puede resolver instancias con hasta 50 entornos y diferentes números de barreras en una hora de tiempo de CPU, mientras que el matheurístico siempre devuelve excelentes soluciones factibles en menos de 100 segundos. El Capítulo 9 se centra en mejorar la planificación de rutas utilizando drones. Se examina la coordinación entre un nave principal y un dron para encontrar las rutas más eficientes que deben seguir para visitar diferentes objetivos representados como grafos. El objetivo es minimizar la distancia total recorrida por ambos vehículos, al mismo tiempo que se cumplen los requisitos de visitas a los objetivos en términos de porcentajes. Se analizan distintos enfoques según las suposiciones realizadas sobre la ruta de la nave principal: i) la nave se puede mover en un plano continuo (plano euclídeo), ii) en una poligonal, o iii) en un grafo general. En todos los casos, se desarrollan formulaciones exactas mediante modelos de programación cónica entera mixta de segundo orden que se comparan en un conjunto de pruebas para evaluar su rendimiento. La complejidad de estos métodos exactos dificulta la búsqueda de soluciones óptimas en un tiempo de cálculo reducido. Por lo tanto, además de las formulaciones exactas, también presentamos un procedimiento matheurístico que permite obtener soluciones de alta calidad en un tiempo razonable. Los experimentos computacionales demuestran la utilidad de nuestros métodos en diferentes escenarios. En el Capítulo 10 se examina un modelo que combina el movimiento de un dron con cierta autonomía que puede visitar múltiples puntos, junto con un vehículo base que puede moverse libremente en el espacio continuo. Este vehículo desempeña el papel de cargar la batería del dron, mientras que el dron se encarga de visitar diferentes objetivos, representados por puntos o poligonales. En el caso de las poligonales, se establece el requisito de que el dron atraviese una fracción específica de sus longitudes, que representan actividades de vigilancia o inspección. El objetivo principal del problema consiste en minimizar la distancia total ponderada recorrida por ambos vehículos. Para abordar este problema, se desarrolla y mejora una formulación de programación cónica entera mixta de segundo orden, utilizando desigualdades válidas y proporcionando límites adecuados para las M grandes que aparecen en el modelo. Además, se propone una estrategia matemática re- finada que permite obtener soluciones de calidad en un tiempo de cálculo reducido. La calidad de las soluciones generadas por ambos enfoques se compara y analiza exhaustivamente utilizando un conjunto aleatoria de instancias con diferentes números y formas de objetivos, lo que demuestra la utilidad de nuestro enfoque y su aplicabilidad en diversas situaciones. En el Capítulo 11 se analizan los desafíos de optimización asociados a la coordinación de un sistema compuesto por un vehículo principal y una ota de drones. Cada dron es lanzado desde el vehículo principal para llevar a cabo una tarea especí ca. Una vez completada la tarea, los drones regresan al vehículo principal para recargar sus baterías y prepararse para una nueva tarea. Estas tareas implican visitar parcialmente grafos con una longitud determinada, con el propósito de brindar servicios o realizar actividades de vigilancia e inspección. El objetivo principal consiste en minimizar el tiempo total de los desplazamientos realizados por el vehículo principal, al mismo tiempo que se cumplen ciertos requisitos en términos de porcentajes de visitas a los grafos objetivo. Para abordar este problema, se desarrollan formulaciones exactas utilizando programas de conos de segundo orden con variables enteras, los cuales son comparados en un conjunto de pruebas para evaluar su rendimiento. Además, se presenta un algoritmo matheurístico que genera soluciones razonables. Los experimentos computacionales demuestran la utilidad de esta metodología en diversos escenarios.

Author dc:creator

• Valverde Martín, Carlos

Advisor dc:contributor.advisor

• Puerto Albandoz, Justo

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/11441/156604

OAI identifier oai:identifier

oai:idus.us.es:11441/156604