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

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.
Nội dung trích xuất từ tài liệu:
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 ISSN: 1859-2171 TNU Journal of Science and Technology 208(15): 89 - 96 e-ISSN: 2615-9562 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 Hoàng Phước Lộc1*, Nguyễn Phong1, Lê Thanh Hiếu2 1 Trường Cao đẳng Sư phạm Quảng Trị, 2Trườ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 Ngày nhận bài: 30/9/2019; Ngày hoàn thiện: 14/10/2019; Ngày đăng: 25/10/2019 A NEW APPROACH BASED ON GENETIC ALGORITHM FOR FINDING THE OPTIMAL ROAD IN MULTI-SOURCE, MULTI-DESTINATION OF GOOGLE MAPS Hoang Phuoc Loc1*, Nguyen Phong1, Le Thanh Hieu2 1 Quang Tri Teacher Training College, 2Hue University of Education ABSTRACT Searching path problem in two points of graph is solved by some algorithms such as Dijkstra, Hueristic, Floyd, etc. This problem is belong to single source, single destination problem. However, in our real life, we need to solve more complexity problems, which are how to find the optimal path through multi-source selection, multi-destination for some works such as postman, roundsman or travel man, etc. are interesting research problems. The Dijkstra and Floyd algorithms can not solve the finding path problem in multi-source and multi-destination. This research proposes an optimal algorithm based on genetic algorithm approach to solve finding path problem through multi-point, which belong to class of multi-source, multi-destination problem. And also proposes an application for optimizing travel cost based on Google Maps database. The experiment results pointed out that the proposed method is more optimal in time and travel cost in comparison with some real applications such as the Google Maps and Địa điểm applications, and also Dijkstra algorithm. We hope that, this study brings the application grounds to solve travel problems in the real life effectively. Key words: Shortest path, Graph, Google Maps, Genetic algorithm, Multiple sources multiple destinations Received: 30/9/2019; Revised: 14/10/2019; Published: 25/10/2019 * Corresponding author. Email: loc_hp@qtttc.edu.vn http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn 89  Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 1. Giới thiệu thấy, với thuật toán Heuristic tìm ra đường đi Tìm đường đi ngắn nhất là bài toán được áp tốt nhất trong đa nguồn đi của n nút nhưng chỉ dụng rộng rãi trong giao thông, truyền thông giải quyết được trong một đích đến đơn của và trong mạng máy tính. Nó giải quyết những đồ thị [2]. Liang và Wenjia ở [3] cũng đề xuất thách thức để xác định một đường đi với lộ một thuật toán mới để tìm đường đi trong đồ trình chi phí nhỏ nhất về khoảng cách, thời thị đa nguồn đi và một đích đến để giải quyết gian hay giá trị từ nguồn đến đích thỏa mãn bài toán dịch vụ định tuyến trong truyền những yêu cầu nào đó của người sử dụng. thông. Có thể nói rằng, các giải thuật Trong lớp các bài toán tìm đường đi ngắn Heuristic cũng tỏ ra hạn chế để giải quyết bài nhất, bài toán giao thông là một bài toán lớn, toán ĐNĐ, ĐĐĐ đã được chứng minh là bài có tác động sâu rộng đến đời sống của con toán có độ phức tạp NP-đầy đủ. người về nhu cầu vận chuyển, đi lại với một Với những hạn chế về chi phí đường đi của lộ trình thông minh và ít chi phí nhất. Do đó, thuật toán Dijkstra và các thuật toán Heuristic ứng dụng khoa học công nghệ vào phát triển trong việc giải quyết các bài toán tìm đường các dịch vụ hỗ trợ để lựa chọn phương án đi ngắn nhất trên đồ thị, trên mạng định tuyến giao thông tốt nhất là một yêu cầu luôn được hay định đường đi của robot. Giải thuật di đặt ra với những nhà nghiên cứu. truyền (GA) ra đời và mang lại những ưu thế Tuy nhiên, những công bố liên ...