Solving the k-centre problem as a method for supporting the Park and Ride facilities location decision

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


Abstract: In this article we analyze the problem of optimal location of transportation hubs in Warsaw, namely the Park and Ride location problem (P&RP).We take into account the expected travel time using public transport between particular points of the trip. In the currently existing P&R system we have 14 hub locations, and in this case the maximum travel time exceeds 50 minutes. The P&R problem can be reduced to the centers location problem (in our particular approach - the dominating set problem, DS), which is an NP hard problem. In order to determine the optimal locations for P&R two methods: the greedy and the tabu search algorithms were chosen and implemented. According to the computational experiments for the travel time restriction to 50 minutes, we obtain the DS composed of 3 hubs, in contrast to the existing 14 elements. The analysis of the P&R location in time domain is presented in this article in the context of further development of the Warsaw public transportation network, which seems to be interesting.
Author B. Prokop - Faculty of Computer Science Warsaw School of Information Technology (WIT)
B. Prokop,,
, Jan W Owsiński - Systems Research Institute (IBS PAN)
Jan W Owsiński,,
, K. Sęp - Systems Research Institute (IBS PAN)
K. Sęp,,
, Piotr Sapiecha IT
Piotr Sapiecha,,
- The Institute of Telecommunications
Publication size in sheets0.5
Book Ganzha Maria, Maciaszek Leszek A., Paprzycki Marcin (eds.): Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, Annals of Computer Science and Information Systems, vol. 5, 2016, IEEE, ISBN 978-83-60810-65-1, [ 978-83-60810-67-5, 978-83-60810-66-8], 1817 p., DOI:10.15439/978-83-60810-66-8
Keywords in EnglishApproximation algorithms, Urban areas, Public transportation, Greedy algorithms, Electronic mail, Computational modeling
Languageen angielski
2016 Prokop Sapiecha Solving the k-Centre Problem.pdf 1.7 MB
Score (nominal)15
ScoreMinisterial score [Punktacja MNiSW] = 15.0, 27-03-2017, BookChapterSeriesAndMatConfByIndicator
Ministerial score (2013-2016) [Punktacja MNiSW (2013-2016)] = 15.0, 27-03-2017, BookChapterSeriesAndMatConfByIndicator
Citation count*0
Share Share

Get link to the record

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