A multi-objective metaheuristic approach for the transit network design problem

Abstract

We study the problem of the optimal design of routes and frequencies in urban public transit systems, the Transit Network Design Problem (TNDP). We model it as a multi-objective combinatorial optimization problem, which consists in optimizing simultaneously the conflicting objectives of users and operators. A new approximative algorithm based on the GRASP metaheuristic is proposed to solve the TNDP. This algorithm can be classified as a multi-objective metaheuristic since it produces a set of non-dominated solutions in a single run. It differs from most previous approaches, which have used the Weighted Sum Method to generate a set of non-dominated solutions by running a single-objective optimization algorithm for several weights representing different trade-off levels between the conflicting objectives. Numerical results are presented, showing that the multi-objective metaheuristic is more efficient in terms of execution time than the Weighted Sum Method.