Title: Line planning and passenger routing problem with application to the Quito transportation system

Authors: Ramiro Torres

Addresses: Department of Mathematics, Escuela Politécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador

Abstract: An important phase in the strategic planning process of a public transportation system is the line planning problem. It consists in determining a set of lines together with their frequencies such that a given transportation demand is satisfied. In this work an integer programming model for the integrated line planning and passenger routing problem is proposed. The model aims to improve the benefit and comfort of the passengers, namely maximising direct connection trips, and it also proposes to minimise the total cost for the operator. Restricted to linear transportation networks that are relevant for the Quito public transportation system, NP-hardness results and polynomial algorithms for special cases are presented. Performance of heuristic procedures for solving the integrated problem is evaluated over real-world and simulated instances.

Keywords: public transport optimisation; line planning problem; LPP passenger routing; computational complexity.

DOI: 10.1504/IJMOR.2021.116960

International Journal of Mathematics in Operational Research, 2021 Vol.19 No.3, pp.332 - 353

Received: 19 Dec 2019
Accepted: 30 Apr 2020
Published online: 10 Aug 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article