Sub-route reversal repair mechanism and differential evolution for urban transit network design problem

This thesis considers the urban transit network design problem (UTNDP) focusing on the implementation of population-based metaheuristic approaches, specifically on differential evolution (DE) and particle swarm optimization (PSO). The main goal is to develop solution methods that can be used to determine optimal transit route configuration for urban public transportation systems, specifically for system based on buses. The UTNDP consists of determining the number and itinerary of urban public transportation lines and their associated frequencies, with a given infrastructure of streets and demand points. The problem is characterized by huge search space with multiobjective in nature, and it is considered as one of the most challenging combinatorial optimization problems. Due to the NP-hard nature of the UTNDP, the evaluation of candidate solution is challenging and time consuming, in which many potential solutions are discarded on the grounds of infeasibility. A new repair mechanism that is governed by a sub-route reversal procedure is proposed and compared with existing repair mechanisms in terms of the efficiency. The proposed repair mechanism can either be used as a stand-alone or complement other existing repair mechanisms in the literature to deal with the infeasibility. From the literature of UTNDP, the most widely used metaheuristic is the genetic algorithm, at the expense of other population-based metaheuristics. Hence, we focus on urban transit routing problem and develop a framework for tackling the problem. The problem is solved both as a single and multiobjective optimization problems based on small and large benchmark instances, as well as a real-world network. In addition, the UTNDP, which comprise of the network design and the frequency setting problem is also modelled base on DE as a single objective optimization problem from the perspective of the passenger, in which simultaneous network design and frequency setting problem is tackled using a well-studied benchmark network. As a further extension, a hybrid DE-PSO for the UTNDP is developed as a multiobjective combinatorial optimization that produces a set of routes that take into account the interest of users and operators for a given set of resource-and-service constraints. All proposed algorithms are executed using Python programming language, and the computational results show that the proposed algorithms improve the best-so-far results from the literature in most cases