Abstract

Transportation systems are critical components of urban cities, by hugely impacting the quality of life of their citizens. The correct design of the bus routes network is a fundamental task for a successful system. Thus, Urban Transit Routing Problem (UTRP) aims to find a set of bus routes that minimises users travelling time and system operator costs. Most instances of the UTRP lack real-life demand data information, where well-known benchmark instances are very small w.r.t. current standards and/or they have been randomly generated. State-of-the-art relaxation techniques are based on inherent features of urban transport systems and they cannot significantly reduce the order of magnitude of complex instances. In this work, we propose a relaxation technique based on well-known clustering algorithms which preserves demand behaviour and road structure by keeping central and periphery locations connected. We also apply this proposal in a well-known complex study case, the RED system from Santiago of Chile, to encourage researchers to improve the approximation models for other big scenarios.