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)

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.

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.
Owsiński J.W., Stań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