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

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ả.