Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Solving the k -Centre Problem as a method for supporting the Park and Ride facilities location decision

, , ,

DOI: http://dx.doi.org/10.15439/2016F300

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 12231228 ()

Full text

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.


  1. Aros-Vera F., Marianov V., Mitchell J., p-Hub approach for the optimal park-and-ride facility location problem, European Journal of Operational Research 226, 2013
  2. Bast H., Delling D., Goldberg A., Müller-Hannemann M., Pajor T., Sanders P., Wagner D., Werneck R. F., Route Planning in Transportation Networks, Cornell University Library, https://arxiv.org/abs/1504.05140, 2015
  3. Berge C., Hypergraphs: Combinatorics of Finite Sets, Elsevier, 254 pp., 1984
  4. Bunke H., Wang P. S. P., Graph classification and clustering based on vector space embedding, World Scientific Publishing Co. Pte. Ltd., Singapore, Series in Machine Perception and Artificial Intelligence, Vol. 77, 2010
  5. Chartrand G., Lesniak L., Zhank P. Graphs & Digraphs, CRC Press, 2010
  6. Cohen R., Havin S., Complex Networks: Structure, Robustness and Function, Cambridge University Press, Cambridge, 2010
  7. Ding-Zhu Du, Peng-Jun Wan, Connected Dominating Set: Theory and Applications, Springer Optimization and Its Applications, 2012
  8. Erciyes K., Complex Networks: An Algorithmic Perspective, CRC Press, 320 pp., 2014
  9. Farhan B., Murray A., Siting Park and Ride facilities using a multi-objective spatial optimization model, Computers & Operations Research 35, 2008
  10. Fortunato S., Community detection in graphs, Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino, I-ITALY, 2010
  11. Haynes T., Hedetniemi S., Slater P., Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998
  12. Henning M., Yeo A., Total Domination in Graph, Springer Monographs in Mathematics, 2013
  13. Hochbaum D. S., Shmoys D. B., A best possible heuristic for thek-center problem, Mathematics of Operations Research, 10:180-184, 1985.
  14. Hochbaum D. S., Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 596 pp., 1995
  15. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 344 pp., New York 1979
  16. Glover F., Laguna M., Tabu search, Springer Verlag, Handbook of Combinatorial Optimization, pp. 3261-3362, 2013
  17. Mladenovižc N., Labbe M., Hansen P., Solving the p-center problem with tabu search and variable neighborhood search, Networks 42, 1: 48-64, 2003.
  18. Owsiński J.W., Stańczak J., Barski A., Sęp K., Sapiecha P., Graph based approach to the minimum hub problem in transportation network, porcedings of FEDCSiS 2015, pp. 1641 1648, 2015
  19. Schöbel A., Optimization in Public Transportation, Springer Verlag, Optimization and Its Applications, 2006
  20. Takes F. W., Algorithms for Analyzing and Mining Real-World Graphs, PhD thesis was employed at Leiden University, 2014
  21. Vazirani V. V., Approximation Algorithms, Springer Verlag, Berlin Heidelberg, 2003
  22. The source of data, Warsaw public transport timetable, http://www.ztm.waw.pl, 2016