Time-oriented model as a support for solving the Park and Ride problem
Jan W. Owsiński , K. Sęp , B. Prokop , Piotr Sapiecha
AbstractThis 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.
|Publication size in sheets||0.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.|
|Score|| = 15.0, 27-03-2017, BookChapterMatConf|
= 15.0, 27-03-2017, BookChapterMatConf
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.