Algoritmos matheurísticos para un problema de planificación de rutas vehiculares y pedestres

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.