MỘT CÁCH TIẾP CẬN MỚI DỰA TRÊN GIẢI THUẬT DI TRUYỀN ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CỦA BÀI TOÁN ĐA NGUỒN ĐI, ĐA ĐÍCH ĐẾN TRÊN GOOGLE MAPS=A NEW APPROACH BASED ON GENETIC ALGORITHM FOR FINDING THE OPTIMAL ROAD IN MULTI-SOURCE, MULTI-DESTINATION OF GOOGLE MAPS

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Phước Lộc Hoàng, Thanh Hiếu Lê, Phong Nguyễn

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên, 2019

Mô tả vật lý:

Bộ sưu tập: Metadata

ID: 425208

Thêm vào giỏ

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 se-lection, 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 Địa điểm applications, and also Dijkstra algorithm. We hope that, this study brings the application grounds to solve travel problems in the real life effectively.Vấn đề tìm đường đi trong tập các nút để cho đường đi đơn ngắn nhất giữa 2 nút trong đồ thị đã được giải quyết bằng một số thuật toán như Dijkstra, Hueristic, Floyd, … Bài toán này gọi là bài toán đơn nguồn đi, đơn đích đến. Tuy nhiên, trong thực tế cuộc sống của chúng ta cần phải giải quyết bài toán phức tạp hơn là làm thế nào để tìm đường đi tối ưu nhất từ đa điểm lựa chọn xuất phát, đa điểm lựa chọn đích đến cho công việc của người đưa thư, người giao hàng hay đi du lịch hàng ngày, ... là vấn đề đang được quan tâm nghiên cứu. Những bài toán dạng này còn được gọi là bài toán đơn nguồn đi, đa đích đến hoặc đa nguồn đi, đa đích đến mà các giải thuật đang tồn tại như Dijkstra, Floyd, ... khó giải quyết được. Nghiên cứu này đề xuất thuật toán tối ưu dựa trên tiếp cận giải thuật di truyền để giải quyết bài toán tìm đường đi qua đa điểm, thuộc lớp bài toán đa nguồn đi, đa đích đến, từ đó đề xuất một ứng dụng tối ưu hóa chi phí đi lại dựa trên dữ liệu Google Maps. Kết quả thí nghiệm chỉ ra rằng phương pháp đề xuất tối ưu hơn về đường đi và thời gian khi so sánh với các ứng dụng phổ biến như Google Maps, Địa điểm và thuật toán Dijkstra. Nghiên cứu này hy vọng mang lại những nền tảng ứng dụng để giải các bài toán giao thông trong đời sống một cách hiệu quả.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR