Xem trước tài liệu

Đang tải tài liệu...

Thông tin chi tiết tài liệu

Định dạng: PDF
Số trang: 71 trang
Dung lượng: Đang cập nhật

Giới thiệu nội dung

Bài toán thuê xe du lịch có hạn ngạch

Tác giả: Đinh Thị Thủy

Lĩnh vực: Công nghệ thông tin, Khoa học máy tính

Nội dung tài liệu:

Luận văn thạc sĩ này tập trung nghiên cứu về “Bài toán thuê xe du lịch có hạn ngạch” (q-CaRS), một vấn đề tối ưu tổ hợp thuộc lớp bài toán NP-khó. Bài toán này là một mở rộng của bài toán người bán hàng có hạn ngạch (QTSP) và được ứng dụng trong việc lựa chọn tour du lịch, đặt mục tiêu tối thiểu hóa chi phí di chuyển đồng thời đảm bảo mức độ hài lòng nhất định.

Nghiên cứu đề xuất sử dụng phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization – ACO) để giải quyết bài toán q-CaRS, so sánh hiệu quả với thuật giải di truyền (Genetic Algorithm – GA) đã được đề cập trong các nghiên cứu trước. Kết quả thực nghiệm cho thấy phương pháp ACO mang lại hiệu quả cao hơn về cả chất lượng và thời gian giải quyết bài toán.

Luận văn cũng đi sâu vào giới thiệu các phương pháp metaheuristic như thuật giải di truyền và tối ưu hóa đàn kiến, đồng thời trình bày chi tiết về mô hình toán học, các ràng buộc và hàm mục tiêu của bài toán q-CaRS.

Mục lục chi tiết:

  • Chương 1: Bài toán thuê xe du lịch có hạn ngạch
  • Chương 2: Các phương pháp metaheuristic
  • Chương 3: Thuật toán di truyền giải bài toán q-CaRS
  • Chương 4: Thuật toán ACO giải bài toán q-CaRS
  • Phụ lục: Một số module cơ bản trong lập trình thuật toán