Please use this identifier to cite or link to this item: http://bibdigital.epn.edu.ec/handle/15000/19065
Title: Algoritmos matheurísticos para un problema de planificación de rutas vehiculares y pedestres
Authors: Miniguano Trujillo, Andrés Ricardo
Zuleta Sarango, Pablo Andrés
Keywords: INVESTIGACIÓN DE OPERACIONES
ALGORITMOS MATHEURÍSTICOS
Issue Date: 9-Jan-2018
Publisher: Quito, 2018.
Citation: Miniguano Trujillo, A. R., & Zuleta Sarango, P. A. (2018). Algoritmos matheurísticos para un problema de planificación de rutas vehiculares y pedestres. 118 hojas. Quito : EPN.
Abstract: In this study we are concerned on finding solutions for a problem proposed by the National Institute of Statistics and Census (INEC), in order to improve its monthly planning of pedestrian and vehicular routes. We begin with a literature review of the vehicle routing problem related to the transport of people. Then we introduce a multi-objective mixed integer linear program model (MO-MILP) for the vehicular and pedestrian routing problem. The resulting problem belongs to the NP–hard class, so we need to design approximation techniques in order to get a feasible solution. Therefore, we include a literature review on solution methods for routing problems. Then we modify a balanced partitioning algorithm in order to get the input for routing heuristics, and we design two algorithms for pedestrian routing, these are then randomized and fuzzified. Furthermore, we present a reduced MO-MILP for the integrated vehicle routing, and we use it to obtain and improve feasible solutions with help of tabu search. Finally, we apply these methods for a case study in the city of Guayaquil with instances provided by INEC.
Description: En el presente trabajo buscamos soluciones factibles para un problema que surge al planificar la logística mensual de una de las encuestas del Instituto Ecuatoriano de Estadística y Censos (INEC), donde se necesita diseñar rutas pedestres y vehiculares. Empezamos con una revisión de la literatura relacionada al enrutamiento vehicular y al transporte de personas. Luego presentamos un modelo de programación entera mixta y multi-objetivo para el problema de planificación de rutas vehiculares y pedestres. El problema es de la clase NP-hard y. por ello, requerimos diseñar técnicas de aproximación de soluciones. Así, incluimos además una revisión bibliográfica con técnicas de solución para problemas de ruteo. Posteriormente, adaptamos un algoritmo de particionamiento balanceado de grafos al contexto de enrutamiento y diseñamos técnicas deterministas, aleatorizadas y difusas para la construcción de caminos factibles. Presentamos un modelo reducido que adapte los resultados de las técnicas de construcción y lo utilizamos, en conjunto con algoritmos de búsqueda tabú, para la obtención y mejoramiento de las soluciones. Finalmente, incluimos resultados computacionales con base a instancias reales provistas por el INEC en la ciudad de Guayaquil.
URI: http://bibdigital.epn.edu.ec/handle/15000/19065
Type: bachelorThesis
Appears in Collections:Tesis Matemáticas (MAT)

Files in This Item:
File Description SizeFormat 
CD-8465.pdf13,97 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.