intTypePromotion=1

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

Chia sẻ: Nguyễn Văn H | Ngày: | Loại File: PDF | Số trang:24

0
22
lượt xem
0
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2