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

## Bartosz Prokop, Jan Owsiński, Krzysztof Sęp, Piotr Sapiecha

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 1223–1228 (2016)

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.

### References

- 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
- 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
- Berge C., Hypergraphs: Combinatorics of Finite Sets, Elsevier, 254 pp., 1984
- 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
- Chartrand G., Lesniak L., Zhank P. Graphs & Digraphs, CRC Press, 2010
- Cohen R., Havin S., Complex Networks: Structure, Robustness and Function, Cambridge University Press, Cambridge, 2010
- Ding-Zhu Du, Peng-Jun Wan, Connected Dominating Set: Theory and Applications, Springer Optimization and Its Applications, 2012
- Erciyes K., Complex Networks: An Algorithmic Perspective, CRC Press, 320 pp., 2014
- Farhan B., Murray A., Siting Park and Ride facilities using a multi-objective spatial optimization model, Computers & Operations Research 35, 2008
- Fortunato S., Community detection in graphs, Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino, I-ITALY, 2010
- Haynes T., Hedetniemi S., Slater P., Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998
- Henning M., Yeo A., Total Domination in Graph, Springer Monographs in Mathematics, 2013
- Hochbaum D. S., Shmoys D. B., A best possible heuristic for thek-center problem, Mathematics of Operations Research, 10:180-184, 1985.
- Hochbaum D. S., Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 596 pp., 1995
- 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
- Glover F., Laguna M., Tabu search, Springer Verlag, Handbook of Combinatorial Optimization, pp. 3261-3362, 2013
- 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.
- 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
- Schöbel A., Optimization in Public Transportation, Springer Verlag, Optimization and Its Applications, 2006
- Takes F. W., Algorithms for Analyzing and Mining Real-World Graphs, PhD thesis was employed at Leiden University, 2014
- Vazirani V. V., Approximation Algorithms, Springer Verlag, Berlin Heidelberg, 2003
- The source of data, Warsaw public transport timetable, http://www.ztm.waw.pl, 2016