Contributions to Close-Enough Arc Routing Problems

Miguel Reula Martín
Department Didàctica de les Matemàtiques. Universitat de València
ORCid: 0000-0002-6978-6780 miguel.reula@uv.es

Directores:
Ángel Corberán Salvador (Universitat de València)
José María Sanchis Llopis (Universitat Politècnica de València)
Isaac Plana Andani (Universitat de València)

Keywords: Logística, Transporte, Close-enough, Estudio Poliédrico, Branch and Cut, Branch and Pice, Heurísticos.

MSC Subject classifications: 90C11, 90C27, 90B10.

En los últimos años, el sector logístico ha desarrollado una serie de innovaciones tecnológicas relevantes que han provocado numerosos cambios en el negocio. Entre ellos, podemos destacar la tecnología de identificación por radiofrecuencia (RFID) y la disponibilidad de datos en tiempo real a través de la geolocalización. Es por ello, que la investigación operativa sigue evolucionando y plantea la necesidad de definir y estudiar nuevos problemas, así como la incorporación de nuevas características a los ya existentes. Con estos avances tecnológicos, aparecen escenarios que no requieren que el vehículo alcance la ubicación del cliente, sino sólo que se acerque a éste para realizar el servicio. Esta situación es conocida como “close-enough” en los problemas de rutas, ya que el vehículo sólo necesita pasar lo suficientemente cerca de la posición del cliente (Close-Enough Routing Problems – CERPs).

Tecnología de identificación por radiofrecuencia

Si además para cada cliente el servicio se lleva a cabo cuando el vehículo atraviesa los arcos de un grafo, resulta el Close-Enough Arc Routing Problem (CEARP). El CEARP consiste en encontrar una ruta de coste mínimo que empiece y termine en el depósito y que atraviese algunas de las calles de una red de carreteras de manera que se preste servicio a todos los clientes. Notar que, como un cliente es atendido cuando el vehículo se acerca a una determinada distancia, se conocen qué calles debe recorrer el vehículo para atender a cada cliente. La principal característica de este problema es que, a diferencia de los Problemas de Rutas por Arcos tradicionales, el conjunto de calles que hay que recorrer no se conoce de antemano, sino que es una variable de decisión.

Una de las aplicaciones más directas del CEARP se encuentra en la lectura automática de contadores, ya que la tecnología RFID permite recoger a distancia los datos de consumo de los contadores de gas, electricidad o agua, en lugar de tener que hacerlo puerta a puerta como era habitual hace años. El contador envía una señal que describe el consumo y que es captada por el receptor si se encuentra a una distancia determinada. Así, dada una red de carreteras en la que se encuentran los contadores, los vehículos con un receptor de radiofrecuencia sólo tienen que entrar en la zona de cobertura del contador para realizar el servicio.

Otras aplicaciones de estos problemas se encuentran empleando drones en tareas logísticas. Para la gestión de inventarios en las grandes empresas, los investigadores del MIT han desarrollado un sistema que permite a los drones aéreos leer las etiquetas RFID desde decenas de metros de distancia e identificar la ubicación de las etiquetas con un error medio de unos 19 centímetros. Por lo tanto, para realizar el inventario, el dron no necesita atravesar todos los pasillos del almacén para la recogida de datos. Por otra parte, el CEARP también ha sido utilizado para modelizar el recorrido a realizar por los drones con receptores RFID o cámaras incorporadas que realizan el control de calidad de mantenimiento o la vigilancia de las redes.

En la tesis (Reula 2021) estudiamos tres problemas de optimización combinatoria NP-hard que surgen en el contexto de los Close-Enough ARPs. El primero es el Profitable CEARP para un solo vehículo, y el segundo y el tercero son el Distance-Constrained CEARP y el Min-Max CEARP, respectivamente, ambos para múltiples vehículos. Para resolver estos tres problemas, se han desarrollado métodos exactos y heurísticos que no sólo abordan los problemas previamente definidos en la literatura científica, sino también nuevas generalizaciones que acercan los resultados teóricos a las necesidades reales que pueden surgir. De hecho, la finalidad de la tesis es doble. Por un lado, contribuir a un estudio en profundidad de las variantes definidas del CEARP. Por otro lado, aportar nuevas ideas y conocimientos al campo de la Investigación Operativa que puedan ser útiles para abordar otros problemas combinatorios de naturaleza similar.

En los primeros capítulos se presenta el contexto en el que surgen los problemas estudiados en esta tesis. Empezamos describiendo algunos conceptos esenciales de la Programación Matemática, además de ofrecer una visión general de algunos problemas de rutas clásicos que han sido ampliamente estudiados en la literatura científica. Para concluir la sección introductoria, se presenta el estado del arte y las aplicaciones del mundo real de los Close-Enough Routing Problems.

A continuación, en el capítulo 5 nos centramos en el estudio de la primera generalización del CEARP, el Profitable CEARP (PCEARP). En este problema, se asocia un beneficio a cada cliente y se recolecta (sólo una vez) cuando se sirve al cliente. El objetivo es encontrar un recorrido que maximice la diferencia entre el beneficio total recaudado de servir a los clientes y la distancia de recorrida. El capítulo comienza definiendo formalmente el problema, proponiendo una formulación y realizando un estudio poliédrico en profundidad. Para su resolución, se ha diseñado e implementado una heurística y un algoritmo Branch and Cut.

La heurística combina un procedimiento constructivo y una búsqueda local de manera que somos capaces de proporcionar al algoritmo exacto cotas inferiores iniciales. En el algoritmo Branch and Cut se estudian todos los procedimientos de separación para la identificación de las desigualdades violadas y el orden en que se aplican. Ambos algoritmos han requerido de un ajuste y evaluación mediante diversos experimentos y un amplio análisis estadístico. El capítulo es el resultado de una colaboración con el profesor Bianchessi, de la Università degli Studi di Milano, destino de mi estancia de investigación. Este trabajo se encuentra publicado en Bianchessi, Corberan, et al. (2022)

Los capítulos 6 y 7 tratan el Distance-Constrained CEARP (DC-CEARP). Se trata de un CEARP en el que una flota de vehículos, o bien un vehículo varias veces, realiza el servicio a los clientes. Esta generalización del problema consiste en encontrar un conjunto de rutas que salgan y entren en el depósito y sirvan a todos los clientes, de forma que la longitud (en distancia o tiempo) de cada ruta no supere un determinado valor. El objetivo es minimizar la longitud total recorrida.

El Capítulo 6 se define formalmente el problema introduciendo la notación utilizada y presentando la formulación más prometedora propuesta en la literatura. Dado que de la batería de instancias que existen del problema hay un buen número de instancias sin resolver, empezamos con el diseño e implementación de una matheurística multi-arranque que incorpora un método efectivo de Branch and Cut para el CEARP con el fin de optimizar las rutas obtenidas. Pueden encontrarse más detalles en Corberán et al. (2019)

Posteriormente, en el Capítulo 7 también aborda el DC-CEARP, pero en este caso se realiza un estudio más detallado del problema. Comenzamos proponiendo una nueva formulación que combina las mejores características de las formulaciones ya existentes en la literatura ya que, a pesar de tener más variables, se pretende reforzar su relajación lineal. Para esta formulación hemos realizado un estudio exhaustivo de su poliedro asociado y hemos propuesto varias familias de desigualdades válidas. Además, basándonos en los algoritmos de separación para las nuevas desigualdades, hemos propuesto un algoritmo de Branch and Cut que proporciona muy buenos resultados. Este trabajo se encuentra publicado en Corberan et al. (2021)

En el Capítulo 8 estudiamos la última versión, la Min-Max CEARP (MM-CEARP) para una flota de vehículos homogéneos. Teniendo en cuenta el tipo de aplicaciones del CEARP, esta variante trata de equilibrar la longitud de las rutas minimizando la duración de la ruta más larga. El problema consiste en encontrar un conjunto de rutas, todas ellas con inicio y fin en el depósito, que sirvan conjuntamente a todos los clientes, y con un objetivo minmax, es decir de minimizar la máxima ruta.

Basándonos en la experiencia previa en el DC-CEARP, los algoritmos Branch and Cut eran muy complicados de resolver cuando intentábamos resolver instancias con muchos vehículos. Por lo tanto, nos planteamos el reto de diseñar e implementar un algoritmo Branch and Price capaz de resolver instancias con un gran número de vehículos. Comenzamos presentando y proporcionando dos modelos diferentes para el problema: una formulación basada en arcos, con variables de flujo y servicio, que se ha utilizado para desarrollar un algoritmo Branch and Cut, y una formulación basada en variables por ruta, que se ha utilizado para el desarrollo de un algoritmo de Branch and Price. También desarrollamos un algoritmo heurístico que utilizamos para proporcionar soluciones iniciales factibles a los algoritmos exactos. El Branch and Cut se basa en el algoritmo exacto desarrollado en la literatura para el DC-CEARP. Al igual que el heurístico para el PCEARP, el capítulo es el resultado de una colaboración con el profesor Bianchessi y los resultados obtenidos se encuentran publicados en Bianchessi, Corberán, et al. (2022).

La tesis contiene un profundo estudio computacional para cada uno de los algoritmos propuestos para la resolución de cada problema estudiado. Finaliza con las conclusiones de la investigación realizada y la presentación de futuras líneas de trabajo.

Agradecimientos

Esta investigación se ha financiado con una beca FPI BES-2016-077473, del Ministerio de Economía y Competitividad (MINECO) y con los proyectos MTM2015-68097-P y PGC2018-099428-B-I00. Agradecer también a mis directores Ángel Corberán, José María Sanchis e Isaac Plana.

Referencias

Bianchessi, N., A. Corberan, I. Plana, M. Reula, and J. M. Sanchis. 2022. “The Profitable Close-Enough Arc Routing Problem.” Computers & Operations Research 140: 105653.
Bianchessi, N., A. Corberán, I. Plana, M. Reula, and J. M. Sanchis. 2022. “The Min-Max Close-Enough Arc Routing Problem.” European Journal of Operational Research 300 (3): 837–51.
Corberan, A., I. Plana, M. Reula, and J. M. Sanchis. 2021. “On the Distance-Constrained Close Enough Arc Routing Problem.” European Journal of Operational Research 291 (1): 32–51.
Corberán, A., I. Plana, M. Reula, and J. M. Sanchis. 2019. “A Matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem.” TOP 27: 312–26.
Reula, M. 2021. “Contributions to Close-Enough Arc Routing Problems.” PhD thesis, Estadística e Investigación Operativa, Universitat de València. https://roderic.uv.es/handle/10550/79991.

Más BEIO

Can we really predict injuries in team sports?

This paper illustrates from a statistical perspective what challenges need to be addressed from data collection, analysis of player performance and scientific reflection on questions of interest for informed decision making in sports medicine.

What does the research tell us about the understanding of the random variables and its probability distributions?

La variable aleatoria representa uno de los conceptos clave en el modelamiento de fenómenos aleatorios a través de las distribuciones de probabilidad. Por tanto, este estudio tiene como objetivo analizar y describir las principales investigaciones que la literatura reporta sobre variable aleatoria y su distribución de probabilidad. Los resultados muestran la existencia de algunas propuestas de enseñanza en torno a estas nociones, las cuales se caracterizan por utilizar tecnología.

Técnicas estadísticas en geolingüística. Modelización onomástica

Esta tesis se centra en la introducción de nuevos métodos estadísticos para el tratamiento de datos y la modelización en geolingüística, concretamente, en los apellidos de Galicia. El trabajo realizado contempla dos problemas principales: (i) la construcción de regiones de apellidos en Galicia y (ii) la modelización de patrones espaciales y espacio-temporales de apellidos en esta región.

Conceptos de modelización en la formación universitaria de los analistas de datos

A lo largo de los años hemos observado que los titulados en programas universitarios relacionados con el análisis de datos solemos tener cuando finalizamos nuestros estudios una visión parcial del proceso de modelización de problemas. En este artículo repasamos algunos de los conceptos que los analistas de datos van a tener que manejar cuando se incorporen al entorno empresarial y que tal vez podrían ser incluidos en los planes de estudio de esas titulaciones.

Contributions to Close-Enough Arc Routing Problems

En esta tesis doctoral nos centramos en el estudio y la resolución de problemas de Rutas por Arcos basados en el concepto Close-Enough, que se refiere a servir a los clientes al pasar a una cierta distancia de ellos. Para resolverlos de manera óptima, se han diseñado e implementado algoritmos Branch and Price y Branch and Cut. Además, al ser un problema NP-hard, hemos propuesto algoritmos metaheurísticos para obtener soluciones buenas en un tiempo de computación considerable. Tesis defendida por Miguel Reula Martín.

Una mirada feminista y cariñosa a la Sociedad de Estadística e Investigación Operativa

Descripción gráfica y numérica de la composición de las socias y socios de la Sociedad de Estadística e Investigación Operativa cuyo objetivo es conocer con más detalle las características de sus miembros, especialmente en relación a su género binario, edad, tipo de membresía en relación a la sección en la que se integran, antigüedad y comunidad autónoma de procedencia.