Por favor, use este identificador para citar o enlazar este ítem: http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2991
Optimización multiobjetivo para el enrutamiento de vehículos con penalización ambiental en ciudades inteligentes
Multiobjective optimization of vehicle routing with environmental penalty in smart cities
LUIS BERNARDO PULIDO GAYTAN
Andrey Chernykh
Acceso Abierto
Atribución
Algoritmos evolutivos, ciudades inteligentes, enrutamiento de vehículos, metaheurísticas, optimización multiobjetivo
Evolutionary algorithms, metaheuristics, multiobjective optimization, smart cities, vehicle routing
Las ciudades albergan a más de la mitad de la población en tan solo el dos porciento de la superficie terrestre, pero consumen el 75 porciento de los recursos que se extraen del planeta. Este abrupto crecimiento demográfico en áreas urbanas ha empeorado el nivel de contaminación en la ciudad, así como los problemas de congestionamientos viales. En este intenso proceso de urbanización, la gestión exitosa del crecimiento urbano se vuelve crucial para garantizar el desarrollo sostenible a nivel económico, social y ambiental. En este contexto, las ciudades inteligentes proponen la incorporación sensata y sistemática de tecnologías para optimizar el uso de la infraestructura existente y así, lograr una ciudad sustentable e inclusiva. En esta tesis se propone el diseño, implementación y análisis de un algoritmo genético celular de optimización multiobjetivo para la resolución del problema de enrutamiento de vehículos con penalización ambiental, permitiendo disminuir el impacto ambiental en áreas altamente concurridas, al tiempo que se provee de rutas alternativas capaces de minimizar los costos asociados de trasladarse de un lugar a otro, esto bajo la premisa de que no siempre el camino más corto representa la mejor solución. El algoritmo presentado minimiza simultáneamente tres importantes objetivos: tiempo de viaje, emisión de contaminantes y una penalización ambiental, donde esta última representa el costo implícito de trasladarse por un determinado segmento del mapa. Es decir, se obtiene un conjunto de soluciones no-dominadas, las cuales representan rutas alternativas que evitan desplazarse por zonas con un alto grado de contaminación y que, a su vez, minimizan el tiempo y la cantidad de emisiones al recorrer una determinada red de rutas. Como instancia del problema, se utilizó un grafo conexo dirigido compuesto por 6104 nodos, el cual representa la topología subyacente de la red de carreteras en la ciudad de Oldemburgo. Dicho grafo se segmentó en tres diferentes tipos de zonas, las cuales simbolizan áreas con distinta penalización. El análisis experimental realizado exhibe un rendimiento competitivo del enfoque propuesto en términos de convergencia y diversidad, esto con respecto a NSGA-II y SPEA2, dos algoritmos multiobjetivo bien conocidos en la literatura.
Cities host more than half of the population in only two percent of the earth's surface and consume 75 percent of the resources extracted from the planet. This abrupt demographic growth in urban areas has worsened the level of pollution in the city, as well as the problems of road congestion. In this intense urbanization process, successful management of urban growth becomes crucial to ensure sustainable development at economic, social, and environmental levels. In this context, smart cities propose the reasonable and systematic incorporation of technologies to optimize the use of existing infrastructure and thus, achieve a sustainable and inclusive city. This thesis proposes the design, implementation, and analysis of a multiobjective optimization cellular genetic algorithm for the vehicle routing problem with environmental penalty, allowing to diminish the environmental impact in highly concurred areas, while providing alternative routes that minimize the associated costs of moving from one place to another, this under the premise that not always the shortest path represents the best solution. The presented algorithm simultaneously minimizes three important objectives: travel time, emission of pollutants, and an environmental penalty, where the latter represents the implicit ecological cost of moving through a certain segment of the map. That is, a set of non-dominated solution is obtained, which represent alternative routes that avoid traveling through areas with a high degree of pollution and that, in turn, minimize the time and quantity of emissions when traveling through a particular network of routes. As an instance of the problem, a directed graph consisting of 6104 nodes was used, which represents the underlying topology of the road network in the city of Oldenburg. This graph was segmented into three different types of zones, which symbolize areas with different penalties. The experimental analysis carried out exhibits a competitive performance of the proposed approach in terms of convergence and diversity, this with respect to NSGA II and SPEA2, well-known multiobjective algorithms in the literature.
CICESE
2019
Tesis de maestría
Español
Pulido Gaytán, L.B. 2019. Optimización multiobjetivo para el enrutamiento de vehículos con penalización ambiental en ciudades inteligentes. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 102 pp.
OTRAS
Aparece en las colecciones: Tesis - Ciencias de la Computación

Cargar archivos:


Fichero Descripción Tamaño Formato  
tesis_Pulido Gaytan Luis Bernardo_09_sep_2019.pdfVersión completa de la tesis3.24 MBAdobe PDFVisualizar/Abrir