Abstract:

The majority of urban centers are experiencing structural problems due to the contrast between the intensive vehicle flow and the lack of appropriated infrastructure to handle such a traffic demand. Reorienting the streets is a possible strategy to try to address these problems. The Strong Network Orientation Problem (SNOP) stands as an alternative to handle this situation in such a way the total travel distance in a network configuration is minimized. Since the problem involves large scale systems and is considered by the literature as NP-Hard, efficient heuristics algorithms are suitable to achieve appropriate solutions. This paper presents a General Variable Neighborhood Search (GVNS) algorithm for the SNOP composed by a systematic use of four neighborhoods structures and its appliance on instances found in the literature and real cases of a city. Its building steps including local search procedures provided by a Randomized Variable Neighborhood Search (RVND) algorithm and results are also presented and discussed. Results indicate that GVNS is an efficient metaheuristic to solve SNOP, both in running time and quality solution when compared with other heuristics approaches and the exact strategy from the optimization software CPLEX for this problem.