Efficient routing algorithm based on topological analysis of the road network in Myanmar

กระบวนการหาเส้นทางอย่างมีประสิทธิภาพโดยขึ้นอยู่กับการวิเคราะห์เชิงทอพอโลยีของโครงข่ายถนนในเมียนมา

Name: Tun Tun Naing

keyword: Cantor Pairing Function

; Routing Algorithm

LCSH: Topology

LCSH: Graph theory

Abstract: In this research, an efficient routing algorithm for transportation networks is presented. Herein, the transportation network, Myanmar Road Network (MRN), is represented by a weighted-undirected graph. This research utilizes a concept of topological analysis and local information of each city to identify a routing strategy, which aims to maximize traffic flow and increase a feasibility of road selection along given paths. The proposed algorithm, here, considers a combination of degree and betweenness centralities by using the Cantor pairing function. For evaluation, two comparisons were presented. Firstly, the comparison between the distance-based routing method, namely Dijkstra’s algorithm and degree-based routing algorithm was conducted. The results showed that the given routes processed by Dijkstra’s algorithm and degree-based routing algorithm were quite similar, but the degree-based routing algorithm provided less processing times than Dijkstra’s algorithm for all tests. The second, the comparison among the degree-based routing algorithm, betweenness-based routing algorithm, and the combination of them was simulated. The results presented that the proposed work provided the shortest routes with high average degree and betweenness centralities, spent the lowest processing time for giving routes, as well as, the given routes were also efficient.

Abstract: งานวิจัยฉบับนี้นำเสนอกระบวนการหาเส้นทางอย่างมีประสิทธิภาพสำหรับโครงข่ายคมนาคม โครงข่ายถนนในเมียนมา (Myanmar Road Network) ซึ่งถูกจำลองโดยใช้กราฟถ่วงน้ำหนักแบบไม่ระบุทิศทางกระบวนการหาเส้นทางที่นำเสนอใช้หลักการการวิเคราะห์เชิงทอพอโลยีและข้อมูลเฉพาะส่วนของแต่ละเมืองเพื่อนำเสนอกลยุทธ์ในการหาเส้นทาง โดยมีเป้าหมายเพื่อเพิ่มการไหลของกระแสการจราจรและความเป็นไปได้ในการเลือกถนน กระบวนการหาเส้นทางที่นำเสนอนี้พิจารณาการรวมกันของการระบุศูนย์กลางแบบดีกรีและการคั่นกลางโดยใช้แคนเทอแพริ่งฟังก์ชัน สำหรับการประเมินค่ากระบวนการหาเส้นทางที่นำเสนอใช้การเปรียบเทียบ 2 รูปแบบคือ รูปแบบแรกการเปรียบเทียบระหว่างกระบวนการหาเส้นทางโดยขึ้นอยู่กับระยะทาง Dijkstra’s algorithm และกระบวนการหาเส้นทางโดยขึ้นอยู่กับดีกรี ผลลัพธ์แสดงให้เห็นว่าทั้งสองกระบวนการให้ผลลัพธ์เส้นทางคล้ายกัน แต่กระบวนการหาเส้นทางโดยขึ้นอยู่กับดีกรีใช้เวลาในการประมวลผล ต่ำกว่า Dijkstra’s algorithm การเปรียบเทียบแบบที่สองระหว่างกระบวนการหาเส้นทางโดยขึ้นอยู่กับดีกรี กระบวนการหาเส้นทางโดยขึ้นอยู่กับการคั่นกลาง และกระบวนการหาเส้นทางโดยขึ้นอยู่กับการรวมกันระหว่างดีกรีและการคั่นกลาง ผลลัพธ์แสดงให้เห็นว่า กระบวนการนี้นำเสนอเส้นทางที่สั้นที่สุด ด้วยค่าเฉลี่ยดีกรีและการคั่นกลางสูง ใช้เวลาในการประมวลผลต่ำ และเส้นทางผลลัพธ์ที่นำเสนอเป็นเส้นทางที่มีประสิทธิภาพ

King Mongkut's University of Technology North Bangkok. Central Library

Address: Bangkok

Email: library@kmutnb.ac.th

Name: Sunnantha Sodsee

Role: Thesis Advisor

Email : sunantha_s@hotmail.com

Created: 2015

Modified: 2017-10-13

Issued: 2017-08-11

วิทยานิพนธ์/Thesis

application/pdf

CallNumber: Thesis MIT T8N

eng

DegreeName: Master of science

Level: Master's Degree

Descipline: Information Technology

Grantor: King Mongkut's University of Technology North Bangkok

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	B16007475.pdf	3.32 MB	9	2021-05-07 20:54:51

ใช้เวลา

0.02459 วินาที