Premium
The complexity of integrating passenger routing decisions in public transportation models
Author(s) -
Schmidt Marie,
Schöbel Anita
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21600
Subject(s) - computer science , public transport , routing (electronic design automation) , operations research , transportation planning , process (computing) , relation (database) , path (computing) , resource (disambiguation) , mathematical optimization , shortest path problem , flow network , line (geometry) , transport engineering , graph , computer network , mathematics , engineering , data mining , theoretical computer science , geometry , operating system
To model and solve optimization problems arising in public transportation, data about the passengers are necessary and have to be included in the models in any phase of the planning process. Many approaches assume a two‐step procedure: in a first step, the data about the passengers are distributed over the public transportation network (PTN) using traffic‐assignment procedures. In a second step, the actual planning of lines, timetables, and so forth takes place. This approach ignores that, assuming that the network is sufficiently dense, for most passengers, there are many possible ways to reach their destinations in the PTN, thus the actual connections the passengers will take strongly depend on the decisions made during the planning phase. In this article, we investigate the influence of integrating the traffic assignment procedure in the optimization process on the complexity of the line planning problem. Our objective is to maximize the passengers' benefit, namely to minimize the overall travel time of the passengers in the network. We present new models and systematically analyze their complexities. Exploiting a relation to the resource‐constrained shortest path problem, we are able to derive pseudopolynomial and polynomial algorithms for special cases. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 228–243 2015