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Ộ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 /> TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> Hà Nội - 2018<br /> <br /> Chương 1<br /> Bài toán thuê xe du lịch có hạn ngạch<br /> 1.1.<br /> <br /> Quy hoạch nguyên<br /> <br /> 1.1.1.<br /> <br /> Dạng tổng quát của bài toán<br /> <br /> Bài toán quy hoạch nguyên tổng quát được biểu diễn dưới dạng:<br /> f ( x ) = c T x → min(max )<br /> với các điều kiện:<br /> Ax ≤ b<br /> x≥0<br /> x ∈ Zn<br /> <br /> 1.1.2.<br /> <br /> Ứng dụng của bài toán<br /> <br /> Ứ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 quy<br /> hoạch nguyên hỗn hợp và bài toán quy hoạch nguyên 0-1.<br /> Lập kế hoạch sản xuất<br /> Bài toán lập lịch<br /> Mạng di động<br /> <br /> 1.1.3.<br /> <br /> Các phương pháp tiếp cận giải bài toán quy hoạch nguyên<br /> <br /> Sử dụng tổng số đơn modulo<br /> Thuật toán chính xác<br /> Phương pháp Heuristic<br /> <br /> 2<br /> <br /> 1.2.<br /> <br /> Bài toán người chào hàng(Traveling Salesman Problem - TSP)<br /> <br /> Bài toán được phát biểu như sau:<br /> 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 =<br /> {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ành<br /> phố 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ành<br /> phố 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ện<br /> trên) sao cho tổng độ dài các cạnh là nhỏ nhất.<br /> <br /> 1.3.<br /> <br /> Bài toán thuê xe du lịch có hạn ngạch(q-CaRS)<br /> <br /> 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 du<br /> lị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<br /> đị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<br /> đượ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 chi<br /> phí tiết kiệm nhất. Bài toán được đặt ra trong nghiên cứu này không đề cập đến<br /> thời gian di chuyển mà tập trung vào mức độ hấp dẫn của những địa điểm tham<br /> quan và chi phí di chuyển.<br /> Bài toán có một số ràng buộc sau:<br /> -Một chiếc xe không thể bị thuê nhiều hơn 1 lần.<br /> -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.<br /> -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òn<br /> gọi là cơ sở.<br /> Mô hình toán học của bài toán:<br /> Đây là một bài toán biến thể của bài toán TSP<br /> Input:<br /> -C: tập các xe để cho thuê<br /> -V: tập các các thành phố<br /> -A: tập các cạnh (đường đi nối giữa hai thành phố))<br /> - 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àng<br /> buộc tối thiểu cần thiết thu được trong suốt tour du lịch.<br /> -Giá để thuê c ∈ C trên canh (i, j) ∈ A là dijc<br /> -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<br /> đế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ề j<br /> Các biến số:<br /> 3<br /> <br /> - 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 trong<br /> những trường hợp khác.<br /> -wijc có giá trị 1 khi xe c được thuê ở j và được chuyển tới i.<br /> -aic nhận giá trị 1 khi c được thuê ở i.<br /> -eic có giá trị 1 khi xe c được chuyển tới i.<br /> - Giá trị nguyên ui định nghĩa vị trí của đỉnh i trong tour. Đỉnh 1 gọi là thành<br /> phố cơ sở.<br /> Các ràng buộc:<br /> -Tour bắt đầu và kết thúc tại thành phố 1<br /> <br /> ∑∑<br /> <br /> c ∈ C j ∈V<br /> <br /> f 1jc =<br /> <br /> ∑∑<br /> <br /> c ∈ C i ∈V<br /> <br /> f 1jc = 1<br /> <br /> (1.3.1)<br /> <br /> -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 i<br /> thì sau đó phải có 1 chiếc xe khác rời khỏi đỉnh i.<br /> sumc∈C<br /> <br /> ∑<br /> <br /> f ihc =<br /> <br /> i ∈V<br /> <br /> ∑∑<br /> <br /> c<br /> ≤ 1∀ h ∈ V<br /> f hj<br /> <br /> c ∈ C j ∈V<br /> <br /> (1.3.2)<br /> <br /> -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)<br /> 0<br /> <br /> thì xe c sẽ được sử dụng để di chuyển từ i đến thành phố j và sẽ có xe c đi đến<br /> thành phố i từ thành phố h.<br /> <br /> !<br /> aic =<br /> <br /> ∑<br /> <br /> f ijc<br /> <br /> ∑0<br /> <br /> <br /> <br /> j ∈V<br /> <br /> 0<br /> <br /> ∑<br /> <br /> 0<br /> <br /> f hic ∀c ∈ C, i ∈ V, i > 1<br /> <br /> (1.3.3)<br /> <br /> c ∈C,c 6=C h∈V<br /> <br /> -Tương tự điều kiện [1.3.3], các biến eic và f ijc<br /> eic =<br /> <br /> ∑<br /> <br /> !<br /> f ijc <br /> <br /> j ∈V<br /> <br /> <br /> <br /> ∑0<br /> <br /> 0<br /> <br /> ∑<br /> <br /> 0<br /> <br /> f ihc ∀c ∈ C, i ∈ V, i > 1<br /> <br /> (1.3.4)<br /> <br /> c ∈C,c 6=C h∈V<br /> <br /> - Các cặp biến wijc , aic , eic .<br /> omegaijc = acj .eic ∀c ∈ C, ∀i, j ∈ V<br /> <br /> (1.3.5)<br /> <br /> ∑ a1c = 1<br /> <br /> (1.3.6)<br /> <br /> ∑ a1c ≤ 1∀c ∈ C<br /> <br /> (1.3.7)<br /> <br /> -Có 1 xe thuê ở đỉnh 1<br /> <br /> c∈C<br /> <br /> -Mỗi xe chỉ được thuê một lần<br /> <br /> i ∈V<br /> <br /> 4<br /> <br />