Hybrid Population Based Optimization Algorithm For The Urban Transit Routing Problem

The problem that formally describes the overall planning process for a public transportation network is referred to as the Urban Transit Network Design Problem (UTNDP) and has two major components, namely routing and scheduling. This network design problem is a difficult combinatorial optimization problem that belongs to a class of problems known as NP-hard. This thesis develops a hybrid population based optimization method for the Urban Transit Routing Problem, which is the first component of the UTNDP, where the routes of a transit network are designed to meet a number of requirements such as low average passenger travel time and number of transfers. Herein, a discrete version of the Particle Swarm Optimization method is hybridized with evolution operators from Genetic Algorithms in order to determine near optimal routes for an urban transit network. The performance of the algorithm is tested using Mandl's Swiss bus network, a benchmark network used in bus transit network design, and compared with the most recent and efficient methods from the literature. The parameters producing the best values are found and sensitivity analyses are conducted. Results show that the algorithm is capable of creating routes that satisfy the demand in an acceptable computational time, yielding superior results over existing methods.