Luận văn Thạc sĩ Công nghệ thông tin: Bài toán thuê xe du lịch có hạn ngạch

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI<br /> <br /> Đinh Thị Thủy<br /> <br /> BÀI TOÁN THUÊ XE DU LỊCH CÓ HẠN NGẠCH<br /> <br /> Ngành: Công nghệ thông tin<br /> Chuyên ngành: Khoa học máy tính<br /> Mã số: 64080101<br /> <br /> LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> Người hướng dẫn khoa học: PGS.TS.Hoàng Xuân Huấn<br /> <br /> Hà Nội - 2018<br /> <br /> LỜI CAM ĐOAN<br /> Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới sự<br /> hướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn. Các kết quả được viết chung<br /> với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn.<br /> Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là<br /> những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các<br /> nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.<br /> Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được<br /> liệt kê tại mục tài liệu tham khảo.<br /> Hà Nội, ngày .. tháng .. năm 2018<br /> Học viên<br /> <br /> Đinh Thị Thủy<br /> <br /> LỜI CẢM ƠN<br /> Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng biết ơn<br /> sâu sắc tới PGS.TS.Hoàng Xuân Huấn người đã tận tình hướng dẫn để em có thể<br /> hoàn thành khóa luận này.<br /> Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong<br /> khoa Công nghệ thông tin, Đại học Công Nghệ, Đại Học Quốc Gia Hà Nội đã dạy<br /> bảo em tận tình trong suốt quá trình học tập.<br /> Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè<br /> đã luôn bên em, cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực<br /> hiện luận văn tốt nghiệp.<br /> Hà Nội, ngày .. tháng .. năm 2018<br /> Học viên<br /> <br /> Đinh Thị Thủy<br /> <br /> 2<br /> <br /> DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT<br /> <br /> ACO<br /> Phương pháp tối ưu hóa đàn kiến(Ant Colony Optimisation).<br /> AS<br /> Hệ kiến AS(Ant System).<br /> ACS<br /> Hệ kiến ACS(Ant Colony System).<br /> MMAS<br /> Hệ kiến MMAS(Max-Min Ant System).<br /> SMMAS Hệ kiến MMAS trơn(Smooth-Max Min Ant System).<br /> CaRS<br /> Bài toán thuê xe du lịch(Traveling car renter problem).<br /> GA<br /> Thuật giải di truyền(Genetic Algorithm ).<br /> QTSP<br /> Quota Traveling Salesman Problem.<br /> q-CaRS Bài toán thuê xe du lịch có hạn ngạch(Quota traveling car renter problem)<br /> TSP<br /> Bài toán người chào hàng(Traveling Salesman Problem).<br /> ||<br /> Số phần tử trong một tập.<br /> <br /> Mục lục<br /> Danh mục kí hiệu và chữ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 3<br /> <br /> Chương 1. Bài toán thuê xe du lịch có hạn ngạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 8<br /> <br /> 1.1. Quy hoạch nguyên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 8<br /> <br /> 1.1.1. Dạng tổng quát của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 1.1.2. Ứng dụng của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 1.1.3. Các phương pháp tiếp cận giải bài toán quy hoạch nguyên . . . . . . . . . . . . . . .<br /> <br /> 8<br /> 8<br /> 9<br /> <br /> 1.2. Bài toán người chào hàng(Traveling Salesman Problem - TSP). . . . . . . .<br /> <br /> 11<br /> <br /> 1.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 13<br /> <br /> 1.3.1. Bài toán người bán hàng có hạn ngạch(QTSP) . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 1.3.2. Các bài toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 1.3.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 13<br /> 13<br /> 15<br /> <br /> Chương 2. Các phương pháp metaheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 18<br /> <br /> 2.1. Thuật giải di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 18<br /> <br /> 2.1.1. Thuật toán di truyền cổ điển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 2.1.2. Biễu diễn bằng véc tơ số thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 2.1.3. GA trong tối ưu tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 19<br /> 24<br /> 25<br /> <br /> 2.2. Phương pháp tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 28<br /> <br /> 2.2.1. Cách tìm đường đi của kiến tự nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 2.2.2. Kiến nhân tạo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 2.2.3. Phương pháp ACO tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 28<br /> 29<br /> 29<br /> <br /> Chương 3. Thuật giải di truyền cho bài toán q-CaRS . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 35<br /> <br /> 3.1. Biểu diễn quần thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 36<br /> <br /> 3.2. Quá trình tái tạo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 37<br /> <br /> 3.3. Thủ tục tìm kiếm địa phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 38<br /> <br /> 3.4. Thuật toán MemPlas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 42<br /> <br /> 3.5. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 44<br /> <br /> 3.5.1. Bộ dữ liệu chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> 3.5.2. Tiến hành chạy thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br /> <br /> 4<br /> <br /> 44<br /> 44<br /> <br />