Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand

Main Article Content

Natalia Andrea Garzon Eliana María González Neira Ignacio Pérez Vélez


In this paper we study the Tranport Network Design Problem (TNDP). It consists in finding the ideal combination of routes and frequencies that allow the decision maker to balance the interests of the users and the transit operators, which are opposite. The TNDP uses as input a graph, with their transportation costs (in this case time), and the demands associated to each pair of nodes. Our proposed approach to solve the TNDP is based on a Variable Neighborhood Search (VNS) metaheuristic. VNS has been used to solve different kinds of combinatorial optimization problems and it consists in searching competitive solutions by iterative changes of the neighborhood. The VNS is tested first for the case study designed by Mandl, which consists in 15 nodes and 21 arcs, and a symmetric demand matrix. Posteriorly the VNS was tested for other 11 instances of (15, 30 and 45 nodes). In the first place, the model was run for that original case to compare it with other authors who worked this problem in the past. Then, we tested the VNS approach for a changing demand model in 3 moments of the day (Morning, afternoon and night) to prove the positive results obtained in the first exercise and give a greater scope to the problem solution.


Download data is not yet available.

Article Details

How to Cite
GARZON, Natalia Andrea; GONZÁLEZ NEIRA, Eliana María; PÉREZ VÉLEZ, Ignacio. Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand. Ingeniería y Ciencia | ing.cienc., [S.l.], v. 13, n. 25, p. 29-69, may 2017. ISSN 2256-4314. Available at: <>. Date accessed: 20 sep. 2017. doi:
Network design problem; public transportation; variable neighborhood search; multi-objective optimization.