Resumen de Conic programming for routing and location problems

Carlos Valverde Martin

• español

  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.

• English

  This thesis develops new problems in the field of transportation, with a perspective orientated to the use of drones. In this work, new transportation models are de ned taking certain elements from localisation theory, which are solved with elements from operations research, such as optimisation. The thesis is divided into two parts. Part I consists of five chapters dealing with different aspects. Chapter 1 introduces the theoretical framework that allows us to understand the problems that are developed and the latest advances that have been achieved in the literature. Chapter 2 sets out the objectives of this work. Chapter 3 presents the results obtained to date. This is followed by a detailed discussion of these results in Chapter 4. Finally, Chapter 5 presents the general conclusions drawn from the thesis. Part II is also composed of six chapters, from Chapter 6 to Chapter 11. Each of the chapters in Part II can be approached independently and represents an original research contribution in itself. In Chapter 6, an extension of the rural postman problem is addressed that focuses on designing routes that must visit different dimensional elements rather than simply edges. This problem models route planning for drones or other vehicles, where it is necessary to visit multiple geographic locations to deliver goods or services and then move directly to the next location using straight-line travel. In this chapter, two families of mathematical programming formulations are presented. The first family is based on a model by stages and captures several features with practical applications, but has the disadvantage of using three-variable indices. The second family of formulations avoids stages and uses connectivity properties to ensure the correct definition of routes. These formulations are compared using instances with different shapes, such as second-order cone (SOC) representable sets, polyhedral, and polygonal neighbourhoods. The computational results presented in this paper demonstrate that the models are effective and that the formulations can optimally solve medium-sized instances, similar to other combinatorial problems with neighbourhoods that have been studied in the literature. To solve larger instances, a heuristic algorithm is also presented that consists of two phases: clustering and a variable neighbourhood search metaheuristic. This algorithm gives good results by generating feasible solutions close to the optimum, which can also be used to initialise the solvers with these solutions. Chapter 7 focuses on two distinct route design problems in continuous space involving neighbourhoods and barriers: the shortest path problem and the travelling salesman problem with neighbourhoods and barriers. The presence of these two elements, neigh- bourhoods and barriers, makes the problems more challenging compared to their standard counterparts. When both aspects are combined, a new problem arises that has not been addressed to date. However, this problem has relevant applications in inspection and surveillance activities, as well as in the delivery industry, especially when there is a uniformly distributed demand in certain regions. The chapter presents mathematical programming formulations for both problems, assuming linear barriers and second-order cone (SOC) representable neighbourhoods. These assumptions lead to mixed-integer formulations with second-order cones, which are preprocessed and strengthened by valid inequalities. In addition, computational experiments are carried out that show that the exact method can solve instances with 75 neighbourhoods and a range of 125 to 145 barriers. Chapter 8 addresses facility location problems in a continuous space with neighbourhoods and barriers. Specifically, the p-median problem with linear neighbourhoods and barriers is analysed in two different situations. As a first building block, the problem is approached assuming that the neighbourhoods are not visible to each other, and therefore there are no rectilinear routes linking two neighbourhoods without crossing barriers. Under this assumption, a valid mixed-integer linear programming formulation is obtained. Removing that assumption yields the more general and realistic problem, but with the drawback of being more challenging. By adapting the elements of the first formulation, another valid mixed-integer bilinear programming formulation is also developed. Both formulations handle linear barriers and neighbourhoods that are representable with secondorder cones (SOCs), which are preprocessed and reinforced with valid inequalities. These mathematical programming formulations are also instrumental in generating an adapted matheuristic algorithm that provides good quality solutions for both problems in a short computational time. The chapter also details extensive computational experience that demonstrates that exact and heuristic approaches are useful: the exact approach can solve instances with up to 50 neighbourhoods and different numbers of barriers in one hour of CPU time, while the matheuristic approach always returns excellent feasible solutions in less than 100 seconds. Chapter 9 focuses on improving route planning using drones. It examines the coordination between a mothership and a drone to find the most eficient routes to follow to visit different targets represented as graphs. The aim is to minimise the total distance travelled by both vehicles, while meeting the target visit requirements in terms of percentages. Different approaches are analysed depending on the assumptions made about the mothership route: i) the mothership can move in a continuous plane (Euclidean plane), ii) in a polygonal, or iii) in a general graph. In all cases, exact formulations are developed using second-order mixed-integer conic programming models that are compared on a test set to evaluate their performance. The complexity of these exact methods makes it dificult to find optimal solutions in a short computational time. Therefore, in addition to exact formulations, a matheuristic procedure is also presented that allows us to obtain high quality solutions in a reasonable time. Computational experiments demonstrate the usefulness of our methods in difeerent scenarios. Chapter 10 examines a model that combines the movement of a drone with a limited endurance that can visit multiple points, together with a base vehicle that can move freely in continuous space. This vehicle plays the role of charging the battery of the drone, while the drone is in charge of visiting different targets, represented by points or polygonals. In the case of polygonals, there is a requirement for the drone to traverse a speci c fraction of their lengths, representing surveillance or inspection activities. The main objective of the problem is to minimise the total weighted distance travelled by both vehicles. To address this problem, a second-order mixed-integer conic programming formulation is developed and improved, using valid inequalities and providing appropriate bounds for the bigM appearing in the model. In addition, a refined mathematical strategy is proposed that allows for the generation of quality solutions in a reduced computational time. The quality of the solutions generated by both approaches is thoroughly compared and analysed using a random set of instances with different numbers and forms of targets, which demonstrates the usefulness of our approach and its applicability in various situations. Chapter 11 discusses the optimisation challenges associated with coordinating a system composed of a mothership and a fleet of drones. Each drone is launched from the mothership to perform a specific task. Once the task is completed, the drones return to the main vehicle to recharge their batteries and prepare for a new task. These tasks involve partially visiting networks of a certain length with the purpose of providing services or performing surveillance and inspection activities. The main objective is to minimise the total travel time of the mothership while meeting certain requirements in terms of the percentage of visits to the target networks. To address this problem, exact formulations are developed using second-order cone programmes with integer variables, which are compared in a test set to evaluate their performance. In addition, a matheuristic algorithm that generates reasonable solutions is presented. Computational experiments demonstrate the usefulness of this methodology in various scenarios.