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

Bố cục của luận văn bao gồm 4 chương: Chương 1) Bài toán thuê xe 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 trình bày một số module cơ bản trong lập trình thuật toán.
Nội dung trích xuất từ tài liệu:
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ỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘIĐinh Thị ThủyBÀI TOÁN THUÊ XE DU LỊCH CÓ HẠN NGẠCHNgành: Công nghệ thông tinChuyên ngành: Khoa học máy tínhMã số: 64080101LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TINNgười hướng dẫn khoa học: PGS.TS.Hoàng Xuân HuấnHà Nội - 2018LỜI CAM ĐOANTô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ựhướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn. Các kết quả được viết chungvớ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.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à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ácnguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.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ả đượcliệt kê tại mục tài liệu tham khảo.Hà Nội, ngày .. tháng .. năm 2018Học viênĐinh Thị ThủyLỜI CẢM ƠNTrướ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 ơnsâ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ểhoàn thành khóa luận này.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 trongkhoa Công nghệ thông tin, Đại học Công Nghệ, Đại Học Quốc Gia Hà Nội đã dạybảo em tận tình trong suốt quá trình học tập.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èđã 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ựchiện luận văn tốt nghiệp.Hà Nội, ngày .. tháng .. năm 2018Học viênĐinh Thị Thủy2DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮTACOPhương pháp tối ưu hóa đàn kiến(Ant Colony Optimisation).ASHệ kiến AS(Ant System).ACSHệ kiến ACS(Ant Colony System).MMASHệ kiến MMAS(Max-Min Ant System).SMMAS Hệ kiến MMAS trơn(Smooth-Max Min Ant System).CaRSBài toán thuê xe du lịch(Traveling car renter problem).GAThuật giải di truyền(Genetic Algorithm ).QTSPQuota Traveling Salesman Problem.q-CaRS Bài toán thuê xe du lịch có hạn ngạch(Quota traveling car renter problem)TSPBài toán người chào hàng(Traveling Salesman Problem).||Số phần tử trong một tập.Mục lụcDanh mục kí hiệu và chữ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Chương 1. Bài toán thuê xe du lịch có hạn ngạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.1. Quy hoạch nguyên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.1.1. Dạng tổng quát của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2. Ứng dụng của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.3. Các phương pháp tiếp cận giải bài toán quy hoạch nguyên . . . . . . . . . . . . . . .8891.2. Bài toán người chào hàng(Traveling Salesman Problem - TSP). . . . . . . .111.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) . . . . . . . . . . . . . . . . . . . . . . .131.3.1. Bài toán người bán hàng có hạn ngạch(QTSP) . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.2. Các bài toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) . . . . . . . . . . . . . . . . . . . . . . . . . .131315Chương 2. Các phương pháp metaheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.1. Thuật giải di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.1.1. Thuật toán di truyền cổ điển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.2. Biễu diễn bằng véc tơ số thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.3. GA trong tối ưu tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1924252.2. Phương pháp tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .282.2.1. Cách tìm đường đi của kiến tự nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.2. Kiến nhân tạo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.3. Phương pháp ACO tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .282929Chương 3. Thuật giải di truyền cho bài toán q-CaRS . . . . . . . . . . . . . . . . . . . . . . . .353.1. Biểu diễn quần thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .363.2. Quá trình tái tạo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .373.3. Thủ tục tìm kiếm địa phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383.4. Thuật toán MemPlas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423.5. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .443.5.1. Bộ dữ liệu chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.2. Tiến hành chạy thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44444 ...