Tóm tắt 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

Luận văn trình bày về bài toán thuê xe có hạn ngach q-CaRS, sau đó là giới thiệu chung về hai phương pháp metaheuristic là thuật giải di truyền và phương pháp tối ưu hóa đàn kiến giải bài toán toán tối ưu tổ hợp. Tiếp theo luận văn trình bày cụ thể về hai phương pháp trên giải bài toán q-CaRS và chương trình thực nghiệm.
Nội dung trích xuất từ tài liệu:
Tóm tắt 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ố: 64080101TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TINHà Nội - 2018Chương 1Bài toán thuê xe du lịch có hạn ngạch1.1.Quy hoạch nguyên1.1.1.Dạng tổng quát của bài toánBài toán quy hoạch nguyên tổng quát được biểu diễn dưới dạng:f ( x ) = c T x → min(max )với các điều kiện:Ax ≤ bx≥0x ∈ Zn1.1.2.Ứng dụng của bài toánỨng dụng của bài toán được phát triển dựa vào các biến thể là bài toán quyhoạch nguyên hỗn hợp và bài toán quy hoạch nguyên 0-1.Lập kế hoạch sản xuấtBài toán lập lịchMạng di động1.1.3.Các phương pháp tiếp cận giải bài toán quy hoạch nguyênSử dụng tổng số đơn moduloThuật toán chính xácPhương pháp Heuristic21.2.Bài toán người chào hàng(Traveling Salesman Problem - TSP)Bài toán được phát biểu như sau:Có một người giao hàng cần đi giao hàng tại n thành phố(hoặc điểm tiêu thụ) C ={c1 , c2 , ..., cn } độ dài đường đi trực tiếp từ ci đến c j là dij . Anh ta xuất phát từ một thànhphố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu, mỗi thànhphố chỉ đến một lần. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiệntrên) sao cho tổng độ dài các cạnh là nhỏ nhất.1.3.Bài toán thuê xe du lịch có hạn ngạch(q-CaRS)Bài toán xuất phát từ những nhu cầu thực tiễn của người du lịch. Khi người dulịch đi tham quan một khu vực, họ thường đặt ra các mục tiêu về sự hấp dẫn củađịa điểm. Tuy nhiên vì một số lý do tài chính và thời gian họ không thể tham quanđược tất cả. Do đó mục tiêu đặt ra là thỏa mãn về mức độ hài lòng đồng thời chiphí tiết kiệm nhất. Bài toán được đặt ra trong nghiên cứu này không đề cập đếnthời gian di chuyển mà tập trung vào mức độ hấp dẫn của những địa điểm thamquan và chi phí di chuyển.Bài toán có một số ràng buộc sau:-Một chiếc xe không thể bị thuê nhiều hơn 1 lần.-Một ràng buộc được gán với mỗi thành phố được gọi là mức độ hấp dẫn.-Tour du lịch bắt đàu và kết thúc trong thành phố với nơi đầu tiên bắt đầu, còngọi là cơ sở.Mô hình toán học của bài toán:Đây là một bài toán biến thể của bài toán TSPInput:-C: tập các xe để cho thuê-V: tập các các thành phố-A: tập các cạnh (đường đi nối giữa hai thành phố))- Một ràng buộc qi , i = 1, ..., n, được gán với thành phố i ∈ V và ω là tổng ràngbuộc tối thiểu cần thiết thu được trong suốt tour du lịch.-Giá để thuê c ∈ C trên canh (i, j) ∈ A là dijc-Số tiền bổ sung γijc phải được trả nếu c được thuê tại thành phố j và di chuyểnđến thành phố i với i 6= j, giá trị này tương ứng với thuế phải trả để chuyển c về jCác biến số:3- f ijc có giá trị 1 khi xe c di chuyển trên cạnh (i, j) từ i tới j và có giá trị 0 trongnhững trường hợp khác.-wijc có giá trị 1 khi xe c được thuê ở j và được chuyển tới i.-aic nhận giá trị 1 khi c được thuê ở i.-eic có giá trị 1 khi xe c được chuyển tới i.- Giá trị nguyên ui định nghĩa vị trí của đỉnh i trong tour. Đỉnh 1 gọi là thànhphố cơ sở.Các ràng buộc:-Tour bắt đầu và kết thúc tại thành phố 1∑∑c ∈ C j ∈Vf 1jc =∑∑c ∈ C i ∈Vf 1jc = 1(1.3.1)-Mỗi đỉnh chỉ được đến thăm một lần duy nhất và nếu một chiếc xe đến đỉnh ithì sau đó phải có 1 chiếc xe khác rời khỏi đỉnh i.sumc∈C∑f ihc =i ∈V∑∑c≤ 1∀ h ∈ Vf hjc ∈ C j ∈V(1.3.2)-Các cặp biến aic và f ijc biểu diễn rằng nếu xe c được thuê ở thành phố i, (i 6= j)0thì xe c sẽ được sử dụng để di chuyển từ i đến thành phố j và sẽ có xe c đi đếnthành phố i từ thành phố h.!aic =∑f ijc∑0j ∈V0∑0f hic ∀c ∈ C, i ∈ V, i > 1(1.3.3)c ∈C,c 6=C h∈V-Tương tự điều kiện [1.3.3], các biến eic và f ijceic =∑!f ijc j ∈V∑00∑0f ihc ∀c ∈ C, i ∈ V, i > 1(1.3.4)c ∈C,c 6=C h∈V- Các cặp biến wijc , aic , eic .omegaijc = acj .eic ∀c ∈ C, ∀i, j ∈ V(1.3.5)∑ a1c = 1(1.3.6)∑ a1c ≤ 1∀c ∈ C(1.3.7)-Có 1 xe thuê ở đỉnh 1c∈C-Mỗi xe chỉ được thuê một lầni ∈V4 ...