MỘT CÁCH TIẾP CẬN MỚI DỰA TRÊN GIẢI THUẬT DI TRUYỀN ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CỦA BÀI TOÁN ĐA NGUỒN ĐI, ĐA ĐÍCH ĐẾN TRÊN GOOGLE MAPS

Tóm Tắt

Các tác giả

1. Hoàng Phước Lộc , Trường Cao đẳng Sư phạm Quảng Trị
2. Nguyễn Phong, Trường Cao đẳng Sư phạm Quảng Trị
3. Lê Thanh Hiếu, Trường Đại học Sư phạm Huế

Tóm tắt

Vấn đề tìm đường đi trong tập các nút để cho đường đi đơn ngắn nhất giữa 2 nút trong đồ thị đã được giải quyết bằng một số thuật toán như Dijkstra, Hueristic, Floyd, … Bài toán này gọi là bài toán đơn nguồn đi, đơn đích đến. Tuy nhiên, trong thực tế cuộc sống của chúng ta cần phải giải quyết bài toán phức tạp hơn là làm thế nào để tìm đường đi tối ưu nhất từ đa điểm lựa chọn xuất phát, đa điểm lựa chọn đích đến cho công việc của người đưa thư, người giao hàng hay đi du lịch hàng ngày, … là vấn đề đang được quan tâm nghiên cứu. Những bài toán dạng này còn được gọi là bài toán đơn nguồn đi, đa đích đến hoặc đa nguồn đi, đa đích đến mà các giải thuật đang tồn tại như Dijkstra, Floyd, … khó giải quyết được. Nghiên cứu này đề xuất thuật toán tối ưu dựa trên tiếp cận giải thuật di truyền để giải quyết bài toán tìm đường đi qua đa điểm, thuộc lớp bài toán đa nguồn đi, đa đích đến, từ đó đề xuất một ứng dụng tối ưu hóa chi phí đi lại dựa trên dữ liệu Google Maps. Kết quả thí nghiệm chỉ ra rằng phương pháp đề xuất tối ưu hơn về đường đi và thời gian khi so sánh với các ứng dụng phổ biến như Google Maps, Địa điểm và thuật toán Dijkstra. Nghiên cứu này hy vọng mang lại những nền tảng ứng dụng để giải các bài toán giao thông trong đời sống một cách hiệu quả.

Từ khóa

Đường đi ngắn nhất, Đồ thị, Google Maps, Giải thuật di truyền, Đa nguồn đi đa đích đến

Toàn văn:

PDF

Tài liệu tham khảo

[1]. R. Avash and J. Ashi, “Genetic Algorithm based Logistics Route Planning,” International Journal of Innovation, Management and Technology, vol. 1, pp. 4, 2009.

[2]. K. Faisal and A. Nabil, “An Efficient Multiple Sources Single-Destination MSSD) Heuristic Algorithm Using Nodes Exclusions,” International Journal of Soft Computing · January 2015, vol. 10, pp. 6, 2015.

[3]. Z. Liang and W. Wenjia, “A New Path Search Algorithm for Providing Paths among Multiple Origins and One Single Destination”International Journal of Computer Science and Application (IJCSA), vol. 3, pp. 5, 2014.

[4]. S. Yagvalkya, C. S. Subhash, and B. Manisha, “Comparison of Dijkstra’s Shortest Path Algorithm with Genetic Algorithm for Static and Dynamic Routing Network,” International Journal of Electronics and Computer Science Engineering, vol. 1, pp. 10, 2016.

[5]. K. Rakesh and K. Mahesh, “Exploring Genetic Algorithm for Shortest Path Optimization in Data Networks,” Global Journal of Computer Science and Technology, vol. 10, p. 5, 2010.

[6]. V. Hars, B. Shreejith, H. Wanjun, R. Miguel, S. Arularasi, T. Limin, M. Paolo, T. Marco, and F. Andrea, “Finding a Simple Path with Multiple Must-include Nodes,” 2009.

[7]. G. Bilal and S. J. L., “Genetic Algorithm Finding the Shortest Path in Networks,” presented at the Fifth International Conference on Genetic and Evolutionary Computing, San Diego, California, USA, 2011.

[8]. V. Anusuya and R. Kavitha, “Genetic Algorithm for Finding Shortest Path in a Network,” Intern. J. Fuzzy Mathematical Archive, vol. 2, pp. 6, 2013.

[9]. C. Anu and K. P. Neeraj, “Genetic algorithm for shortest path in packet switching networks,” Journal of Theoretical and Applied Information Technology, vol. 29, pp. 11, 2011.

[10]. Y. H. Ahmed and M. R. Hassan, “A Genetic Algorithm To Solve The Minimum-Cost Paths Tree Problem,” International Journal of Computer Networks & Communications (IJCNC), vol. 7, pp. 11, 2015.

[11]. A. Sachith, G. Baladasan, and K. Saluka, “A Genetic Algorithm Approach to Solve the Shortest Path Problem for Road Maps,” in International Conference on Information and Automation, Colombo, Sri Lanka, 2005.

[12]. A. Umit, R. K. Ismail, G. Cevdet, Y. Beyza, and M. O. Ilhami, “An Idea for Finding the Shortest Driving Time Using Genetic Algorithm Based Routing Approach on Mobile Devices,” International Journal of Mathematics and Computers In Simulation, vol. 6, pp. 8, 2012.

[13]. B. Saeed and A. A. Alia, “Developing a Genetic Algorithm for Solving Shortest Path Problem,” presented at the International conference on Urpan planing and transportation, Heraklion, Crete Island, Greece, 2008.

[14]. A. Nouara and C. Mohamed, “Mobile Robots Path Planning using Genetic Algorithms,” in The Seventh International Conference on Autonomic and Autonomous Systems, 2011.

[15]. B. Eşref and B. Selami, “A Hybrid Genetic Algorithm for Mobile Robot Shortest Path Problem,” International Journal of Intelligent Systems and Applications in Engineering, vol. 1, pp. 8, 2016.

[16]. S. Aravindh and G. Michael, “Hybrid Of Ant Colony Optimization And Genetic Algorithm For Shortest Path In Wireless Mesh Networks,” Journal of Global Research in Computer Science, vol. 3, pp. 4, 2012.

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu