Time-oriented model as a support for solving the Park and Ride problem

Jan W. Owsiński , K. Sęp , B. Prokop , Piotr Sapiecha


This research aims to explore the possibility of applying graph theory to the Park and Ride problem. We propose a model in which the vertices of the graph represent individual stops, and the edges correspond to the average travel times in a public transport network. The number of edges is then constrained by a maximum allowed travel time parameter. Our approach is based on computing a minimum dominating set (MDS) of such modeled graph in order to identify strategic locations in the network. Finding MDS of an arbitrary graph is a well known NP-hard problem. We used three methods to solve the MDS problem (greedy approach, mixed linear integer programming and metaheuristic tabu search). The locations of stops contained in the resulting set can be seen as fitting canditates for Park and Ride facilities and they can provide support in the decision making process. All computations were conducted on a Warsaw’s public transport dataset and were compared with the city’s existing Park and Ride system. We implemented both greedy and tabu search algorithms using Python with NumPy and used SageMath’s MDS algorithm based on mixed integer linear programming. In order to calculate over 16 million average travel times betweeen 4073 stops in Warsaw we have used Open Trip Planner.
Author Jan W. Owsiński - Systems Research Institute (IBS PAN)
Jan W. Owsiński,,
, K. Sęp - Systems Research Institute (IBS PAN)
K. Sęp,,
, B. Prokop - Faculty of Computer Science Warsaw School of Information Technology (WIT)
B. Prokop,,
, Piotr Sapiecha IT
Piotr Sapiecha,,
- The Institute of Telecommunications
Publication size in sheets0.5
Book Vigo Daniele, Józefowska Joanna (eds.): Proceedings of the 28th European Conference on Operational Research - Euro 2016, 2016, Politechnika Pozańska, ISBN 978-3-319-21536-5, 250 p.
URL https://www.euro-online.org/conf/euro28/treat_abstract?paperid=1664
Languageen angielski
2016 Owsiński Sęp Sapiecha Time-oriented model.pdf (file archived - login or check accessibility on faculty) 2016 Owsiński Sęp Sapiecha Time-oriented model.pdf 45.64 KB
Score (nominal)15
ScoreMinisterial score = 15.0, 27-03-2017, BookChapterMatConf
Ministerial score (2013-2016) = 15.0, 27-03-2017, BookChapterMatConf
Citation count*0
Share Share

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.