Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2023F9176

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 295–300 (2023)

Full text

Abstract. The k-means method is one of the most frequently used clustering methods due to its efficiency and ease of modification. This paper presents its modification used for clustering in graphs. The method is presented on the example of generating the hub\&spoke structure in the graph of public transport connections in Warsaw. Optimization of the public transport is one of the most important task for large cities. An efficient transport system is very important for its inhabitants. One of possible solutions is introducing the idea of hub \& spoke to communication system. In this approach is important to detect main stations, called hubs, which will create axes of high-speed connections (city trains, metro, high-speed trams), from which passengers will transfer to slower local connections to get to their rather close destinations. In the presented approach we propose to find locations of such main changeover stations using an evolutionary k-means algorithm.

References

1. J. Coyle, E. Bardi, and. R. Novack, “Transportation”, Fourth Edition, New York: West Publishing Company, 1994.
2. J. F. Campbell, and M O’Kelly, Twenty-Five Years of Hub Location Research, Transportation Science, 46(2), 2012, pp. 153-169.
3. D. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, Massachusetts, USA, 1989.
4. S. Lloyd, “Least squares quantization in PCM” In: Bell Telephone Labs Memorandum, Murray Hill NJ, reprinted in: IEEE Trans. Information Theory IT-28, Vol. 2, 1982, pp. 129-137
5. J. MacQueen, “Some methods for classification and analysis of multivariate observations”, in: Proc. 5th Berkeley Symp. Math. Statistics and Probability. Vol. 1. 1967. pp. 281-297.
6. T. Matisziw, Ch. Lee., and T. Grubesic, “An analysis of essential air service structure and performance”, Journal of Air Transport Management 18, 1, January 2012, pp. 5–11.
7. B. Mażbic-Kulma, H. Potrzebowski, J. Stańczak, and K. Sęp, “Evolutionary approach to solve hub-and-spoke problem using α-cliques”, Evolutionary Computation and Global Optimization, Prace naukowe PW, Warszawa, 2008, pp. 121-130.
8. B. Mażbic-Kulma, J. Owsiński, J. Stańczak, A. Barski and K. Sęp, Mathematical Conditions for Profitability of Simple Logistic System Transformation to the Hub and Spoke Structure, in: Atanassov, K., et al. Uncertainty and Imprecision in Decision Making and Decision Support: New Challenges, Solutions and Perspectives. IWIFSGN 2018. Advances in Intelligent Systems and Computing, vol. 1081. Springer, Cham., 2021, pp. 398-408.
9. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer Verlag, Berlin Heidelberg, 1996.
10. Z. Michalewicz, and B. Fogel, How to Solve It: Modern Heuristics, Springer-Verlag, Berlin Heidelberg, 2004.
11. M. O'Kelly, and D. Bryan, Interfacility interaction in models of hubs and spoke networks, Journal of Regional Science, 42 (1), 2002, pp. 145-165.
12. M. O’Kelly, A quadratic integer program for the location of interacting hub facilities, European Journal of Operational Research, V. 32, 1987, pp. 392-404.
13. J. Owsiński, J. Stańczak, A. Barski, and K. Sęp, Identifying main center access hubs in a city using capacity and time criteria. The evolutionary approach, Control and Cybernetics, 45(2), 2016, pp. 207-223.
14. J.-P. Rodrigue The Geography of Transport Systems, New York: Routledge, 2020
15. J. Stańczak, Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics, 32(2), 2003, pp. 411-433.
16. J. Stańczak, H. Potrzebowski, and K. Sęp, Evolutionary approach to obtain graph covering by densely connected subgraphs, Control and Cybernetics, vol. 41, No. 3, 2011, pp. 80-107.
17. J. Stańczak, and J. Owsiński, Evolutionary k-Means Clustering Method with Controlled Number of Clusters Applied to Determine the Typology of Polish Municipalities. In: Uncertainty and Imprecision in Decision Making and Decision Support: New Advances, Challenges, and Perspectives. IWIFSGN BOS/SOR 2020. Lecture Notes in Networks and Systems, vol. 338, 33. Springer, Cham, 2022, pp. 436-446.
18. J. Stańczak, A. Barski, K. Sęp, and J. Owsiński, The problem of distribution of Park-And-Ride car parks in Warsaw, International Journal of Information and Management Sciences, 27(2), 2016, pp. 179-190, http://dx.doi.org/10.6186/1JIMS.2016.27.2.6.
19. J. Stańczak, K. Sęp, and J. Owsiński, “Evolutionary methods for finding kernel & shell structures in a graph of connections” (in Polish: “Ewolucyjne metody znajdowania struktur typu "kernel & shell" w grafie połączeń”), Instytut Badań Systemowych PAN, Warszawa, 2023.
20. H. Steinhaus, Sur la division des corps matériels en parties. Bulletin de l’Académie Polonaise des Sciences, Classe 3, 1956, 12, pp. 801-804.
21. R. Wilson, Introduction to graph theory, Addison Wesley Longman, 1996.