An Evolutionary Approach for the Optimal Design of Public Transportation Networks

An Integer Linear Programming (ILP) model for the Single Line Planning Problem - a simplified version of the Line Planning Problem - has been previously proposed in the literature. Although this approach is able to easily find optimal solutions for small instances, it fails to scale. In this work, we propose a method based on the Multi-Parent Biased Random Key Genetic Algorithm with Implicit Path-Relinking (BRKGA-MP-IPR) metaheuristic and compare to the results obtained by the ILP formulation. Our experiments revealed the BRKGA-MP-IPR is able to outperform the ILP solution for large instances, indicating the two approaches to be complementary.