Luận văn "Phương pháp tối ưu đàn kiến giải bài toán định tuyến xe" sẽ nghiên cứu, tìm hiểu các phương pháp metaheuristic nói chung và phương pháp tối ưu đàn kiến nói riêng để giải quyết bài toán VRP. Mời các bạn cùng tham khảo nội dung chi tiết. | Luận văn thạc Khoa học máy tính Phương pháp tối ưu đàn kiến giải bài toán định tuyến xe ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VŨ HOÀNG VƯƠNG PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN ĐỊNH TUYẾN XE LUẬN VĂN THẠC SĨ Ngành Khoa học máy tính HÀ NỘI - 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VŨ HOÀNG VƯƠNG PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN ĐỊNH TUYẾN XE LUẬN VĂN THẠC SĨ Ngành Khoa học máy tính Cán bộ hướng dẫn TS. ĐỖ ĐỨC ĐÔNG HÀ NỘI - 2019 ABSTRACT Bài toán định tuyến xe VRP Vehicle Routing Problem liên quan trực tiếp tới dịch vụ giao hàng của một công ty. Bài toán yêu cầu tìm đường đi tối ưu cho các xe chở hàng xuất phát từ một hoặc nhiều kho hàng để giao hàng cho một tập khách hàng cho trước. Có nhiều tiêu chuẩn tối ưu nhưng thông dụng nhất vẫn là tối thiểu hóa chi phí vận chuyển hoặc tổng độ dài quãng đường di chuyển của các xe. Bài toán VRP có ý nghĩa lớn trong công nghiệp. Việc tối ưu các tuyến đường vận chuyển có thể tiết kiệm cho các công ty tới 5 . Thống kê cho thấy chi phí vận chuyển chiếm tỉ trọng lớn cấu thành trong một sản phẩm 10 . Do đó mọi chi phí tiết kiệm được bằng cách giải tốt VRP cho dù nhỏ hơn 5 đều có ý nghĩa lớn. Bài toán VRP cũng có nhiều ý nghĩa trong khoa học bài toán đã được chứng minh là NP-khó. Do đó những thuật toán chính xác dùng để giải chúng chỉ có thể giải được bài toán với kích thước nhỏ. Để giải được bài toán với kích thước lớn đã có nhiều công trình nghiên cứu áp dụng các phương pháp metaheuristic cho bài toán VRP ví dụ như dùng giải thuật di truyền GA genetic algorithm tìm kiếm Tabu Tabu search thuật toán luyện kim Simulated annealing . Một số thuật toán metaheuristic tốt nhất hiện nay có thể cho lời giải với độ tốt kém đến 1 so với lời giải tối ưu cho các bài toán lên tới hàng trăm điểm giao hàng. Luận văn sẽ nghiên cứu tìm hiểu các phương pháp metaheuristic nói chung và phương pháp tối ưu đàn kiến nói riêng để giải quyết bài toán VRP. Từ khóa VRP vehicle routing problem CVRP .
