Path inference implementing the cluster path covering method

Year 2024, Volume: 30 Issue: 1, 53 - 62, 29.02.2024

Kadir Akgöl , Emre Demir İbrahim Aydoğdu

Abstract

Determination of the optimal route in transportation activities is one of the major problems in transportation. Therefore, efficient techniques deserve our utmost attention to detect optimal routes. In this study, a novel method called Cluster Path Covering (CPC) has been developed and introduced to identify a route based on a sequence of location points on a network. There are already models to minimize the total path cost between the pair of nodes following a kind of sequence. However, our method aims to minimize the path cost, including the neighbourhood accessibility of the path nodes on the network. One of the major challenges for the new model is to reveal the accessibility costs between the nodes. The methodology presents the CPC method clustering the location points on a network and indicating the optimum point for each cluster. Then, the CPC method generates the best path by connecting the specific location points representing the clusters. Moreover, the shortest covering of the neighbourhood path problem (SCNPP) is introduced in this study. The novel CPC method is utilized for SCNPP, a distinctive version of the shortest covering path problem (SCPP). The performance of the CPC method is then tested on two different benchmark networks. According to the results, it provides robust and efficient outcomes for decreasing the routes' transportation costs (e.g., distances). The issues that can be solved via the CPC method include the accessibility costs of public transportation paths and the locations of stops by minimizing the costs.

Keywords

Network design, Covering path, K-means, Urban planning

Küme yolu kaplama yöntemi uygulaması ile yol çıkarımı

Abstract

En uygun güzergâhın belirlenmesi ulaşım faaliyetlerindeki en büyük sorunlardan biridir. Bu nedenle, en uygun rotaları tespit etmek için etkili teknikler kullanılmalıdır. Bu çalışmada, bir ağ üzerindeki konum noktaları dizisine dayalı bir rotayı tanımlamak için Küme Yolu Kaplama (CPC) adı verilen özgün bir yöntem geliştirilmiş ve tanıtılmıştır. Bir dizi üzerindeki düğüm noktaları çiftleri arasındaki toplam yol maliyetini en aza indirecek modeller hâlihazırda bulunmaktadır. Ancak bizim yöntemimiz, ağdaki düğümlerin komşu olduğu muhite erişilebilirliğini de göz önünde bulundurarak yol maliyetini en aza indirmeyi amaçlamaktadır. Bu yeni yöntem için en büyük zorluklardan biri, düğümler arasındaki erişilebilirlik maliyetlerini ortaya çıkarmaktır. Metodolojimiz, bir ağ üzerindeki düğüm noktalarını kümeleyen ve her küme için optimum noktayı gösteren CPC yöntemini sunmaktadır. Bu yöntem, kümeleri temsil eden düğüm noktalarını birbirine bağlayarak en iyi yolu oluşturmaktadır. Ayrıca bu çalışmada, komşu muhiti kaplayan en kısa yol probleminin (SCNPP) tanımı yapılmıştır. Yeni CPC yöntemi, kaplayan en kısa yol probleminin (SCPP) ayırt edici bir versiyonu olan SCNPP için kullanılmaktadır. İlaveten, CPC yönteminin performansı iki farklı kıyaslama ağında test edilmiştir. Sonuçlara göre CPC yöntemi, güzergâhların ulaşım maliyetlerini (mesafeler gibi) azaltmak için güçlü ve etkin neticeleri bize sağlamaktadır. CPC yöntemi ile çözülebilecek sorunlar arasında, toplu taşıma güzergâhlarına mesafe açısından erişilebilirlik maliyetlerinin azaltılması ve durakların konumları arasındaki mesafelerin minimize edilmesi yer alabilir.

Keywords

Yol ağ tasarımı, Kaplayan yol, K-means, Kentsel planlama

References

• [1] Peng C, Yu S, Zhang L. "Emergency evacuation route planning of cruise ship based on intelligent optimization algorithm". Intelligent Networked Things: 5th China Conference, CINT 2022, Urumqi, China, 7-8 August 2022.
• [2] Liu B, Ni W, Liu RP, Guo YJ, Zhu H. "Optimal routing of unmanned aerial vehicle for joint goods delivery and in-situ sensing". IEEE Transactions on Intelligent Transportation Systems, 24(3), 3594-3599, 2022.
• [3] Das R, Sahoo L, Samanta S, Simic V, Senapati TJM. "Identifying the shortest path of a semidirected graph and its application". Mathematics, 10(24), 1-13, 2022.
• [4] Dantzig G, Fulkerson R, Johnson S. "Solution of a large-scale traveling-salesman problem". Journal of the Operations Research Society of America, 2(4), 393-410, 1954.
• [5] Lin S, Kernighan BW. "An effective heuristic algorithm for the traveling-salesman problem". Operations Research, 21(2), 498-516, 1973.
• [6] Xu R, Wunsch D. "Survey of clustering algorithms". IEEE Transactions on Neural Networks, 16(3), 645-678, 2005.
• [7] Dijkstra EW. "A note on two problems in connexion with graphs". Numerische Mathematik, 1(1), 269-271, 1959.
• [8] Ford JLR. Network Flow Theory. 1st ed. California, USA, Rand Corporation, 1956.
• [9] Ortúzar JdD, Willumsen LG. Modelling Transport. 4th ed. New York, USA, John Wiley and Sons, 2011.
• [10] Santos L, Coutinho-Rodrigues J, Current JR. "An improved solution algorithm for the constrained shortest path problem". Transportation Research Part B: Methodological, 41(7), 756-771, 2007.
• [11] Lombard K, Church R. "The gateway shortest path problem: generating alternative routes for a corridor location problem". Geographical Systems, 1(1), 25-45, 1993.
• [12] Demir E. Identification and Characterization of Network Paths. PhD Thesis, University of Missouri, Columbia, USA, 2013.
• [13] Bera A, Misra S, Chatterjee C, Mao S. "CEDAN: Cost-effective data aggregation for UAV-Enabled IoT networks". IEEE Transactions on Mobile Computing, 22(9), 5053-5063, 2022.
• [14] Campuzano G, Lalla-Ruiz E, Mes M. "The drone-assisted variable speed asymmetric traveling salesman problem". Computers & Industrial Engineering, 176, 1-20, 2023.
• [15] Ziyadullaev D, Muhamediyeva D, Ziyaeva S, Xoliyorov U, Kayumov K, Ismailov O. "Development of a traditional transport system based on the bee colony algorithm". E3S Web of Conferences 365, Strazburg, France, 30 January 2023.
• [16] Moon C, Kim J, Choi G, Seo Y. "An efficient genetic algorithm for the traveling salesman problem with precedence constraints". European Journal of Operational Research, 140(3), 606-617, 2002.
• [17] Wong L-P, Low MYH, Chong CS. "A bee colony optimization algorithm for traveling salesman problem". 2008 Second Asia International Conference on Modelling & Simulation (AMS), Kuala Lumpur, Malaysia, 13-15 May 2008.
• [18] Niblett TJ, Church RL. "The shortest covering path problem: a new perspective and model". International Regional Science Review, 39(1), 131-151, 2016.
• [19] Current J, ReVelle C, Cohon J. "Symposium on location problems: in memory of leon cooper: the shortest covering path problem: an application of locational constraints to network design". Journal of Regional Science, 24(2), 161-183, 1984.
• [20] Current JR, Velle CR, Cohon J. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation". European Journal of Operational Research, 21(2), 189-199, 1985.
• [21] Current JR, Schilling DA. "The covering salesman problem". Transportation Science, 23(3), 208-213, 1989.
• [22] Cheranchery MF, Maitra B. "Priority areas of intervention for improving urban bus services: Experience in Kolkata, India". Transportation Research Record: Journal of the Transportation Research Board, 2634, 17-27, 2017.
• [23] Das S, Pandit D. "Importance of user perception in evaluating level of service for bus transit for a developing country like India: a review". Transport Reviews, 33(4), 402-420, 2013.
• [24] Hu KC. "Evaluating city bus service based on zone of tolerance of expectation and normalized importance". Transport Reviews, 30(2), 195-217, 2010.
• [25] Dell’Olio L, Ibeas A, Cecín P. "Modelling user perception of bus transit quality". Transport Policy, 17(6), 388-397, 2010.
• [26] Wall G, McDonald M. "Improving bus service quality and information in Winchester". Transport Policy, 14(2), 165-179, 2007.
• [27] Yannis T, Georgia A. "A complete methodology for the quality control of passenger services in the public transport business". European Transport/Trasporti Europei, 38, 1-16, 2008.
• [28] Gökaşar I, Buran B, Dündar S. "Modelling the quality of bus services by using factor analysis on urban bus satisfaction survey data: Case of IETT". Pamukkale University Journal of Engineering Sciences, 24(6), 1079-1086, 2018.
• [29] Ruiz M, Segui-Pons JM, Mateu-LLadó J. "Improving bus service levels and social equity through bus frequency modelling". Journal of Transport Geography, 58, 220-233, 2017.
• [30] De Oña J, De Oña R, Eboli L, Mazzulla G. "Perceived service quality in bus transit service: a structural equation approach". Transport Policy, 29, 219-226, 2013.
• [31] Ceder A, Wilson NH. "Bus network design". Transportation Research Part B: Methodological, 20(4), 331-344, 1986.
• [32] Lesley LJS. "Optimum bus-stop spacing". Traffic Engineering & Control, 17(10), 399-401, 1976.
• [33] Van Nes R, Bovy P. "Importance of objectives in urban transit-network design". Transportation Research Record: Journal of the Transportation Research Board, 1735, 25-34, 2000.
• [34] Chien SI, Qin Z. "Optimization of bus stop locations for improving transit accessibility". Transportation Planning and Technology, 27(3), 211-227, 2004.
• [35] Alonso B, Moura JL, dell'Olio L, Ibeas Á. "Bus stop location under different levels of network congestion and elastic demand". Transport, 26(2), 141-148, 2011.
• [36] Moura JL, Alonso B, Ibeas Á, Ruisánchez FJ. "A two-stage urban bus stop location model". Networks and Spatial Economics, 12(3), 403-420, 2012.
• [37] Huang D, Liu Z, Fu X, Blythe PT. "Multimodal transit network design in a hub-and-spoke network framework". Transportmetrica A: Transport Science, 14(8), 706-735, 2018.
• [38] Honma Y, Kuby M. "Node-based vs. path-based location models for urban hydrogen refueling stations: Comparing convenience and coverage abilities". International Journal of Hydrogen Energy, 44(29), 15246-15261, 2019.
• [39] Hartigan JA, Wong MA. "Algorithm AS 136: A k-means clustering algorithm". Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1), 100-108, 1979.
• [40] Hartigan JA. Clustering Algorithms. 1st ed. New Jersey, USA, John Wiley & Sons, 1975.
• [41] Telgarsky M, Vattani A. "Hartigan’s method: k-means clustering without voronoi". Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, Sardinia, Italy, 13-15 May 2010.
• [42] Karypis MSG, Kumar V, Steinbach M. "A comparison of document clustering techniques". KDD-2000 Workshop on Text Mining, Boston, MA, USA, 20 August 2000.