Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Công nghệ thông tin Luận văn cntt bài toán thuê xe du lịch có hạn ngạch...

Tài liệu Luận văn cntt bài toán thuê xe du lịch có hạn ngạch

.PDF
71
157
82

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI Đinh Thị Thủy BÀI TOÁN THUÊ XE DU LỊCH CÓ HẠN NGẠCH Ngành: Công nghệ thông tin Chuyên ngành: Khoa học máy tính Mã số: 64080101 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: PGS.TS.Hoàng Xuân Huấn Hà Nội - 2018 LỜI CAM ĐOAN 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ự 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 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. 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ác nguồ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ả được liệt kê tại mục tài liệu tham khảo. Hà Nội, ngày .. tháng .. năm 2018 Học viên Đinh Thị Thủy LỜI CẢM ƠN 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 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ể 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 trong khoa Công nghệ thông tin, Đại học Công Nghệ, Đại Học Quốc Gia Hà Nội đã dạy bả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ực hiện luận văn tốt nghiệp. Hà Nội, ngày .. tháng .. năm 2018 Học viên Đinh Thị Thủy 2 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ACO Phương pháp tối ưu hóa đàn kiến(Ant Colony Optimisation). AS Hệ kiến AS(Ant System). ACS Hệ kiến ACS(Ant Colony System). MMAS Hệ kiến MMAS(Max-Min Ant System). SMMAS Hệ kiến MMAS trơn(Smooth-Max Min Ant System). CaRS Bài toán thuê xe du lịch(Traveling car renter problem). GA Thuật giải di truyền(Genetic Algorithm ). QTSP Quota Traveling Salesman Problem. q-CaRS Bài toán thuê xe du lịch có hạn ngạch(Quota traveling car renter problem) TSP Bài toán người chào hàng(Traveling Salesman Problem). || Số phần tử trong một tập. Mục lục Danh mục kí hiệu và chữ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chương 1. Bài toán thuê xe du lịch có hạn ngạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1. Quy hoạch nguyên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.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 . . . . . . . . . . . . . . . 8 8 9 1.2. Bài toán người chào hàng(Traveling Salesman Problem - TSP). . . . . . . . 11 1.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) . . . . . . . . . . . . . . . . . . . . . . . 13 1.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) . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13 15 Chương 2. Các phương pháp metaheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1. Thuật giải di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 24 25 2.2. Phương pháp tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 29 29 Chương 3. Thuật giải di truyền cho bài toán q-CaRS . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1. Biểu diễn quần thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2. Quá trình tái tạo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3. Thủ tục tìm kiếm địa phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4. Thuật toán MemPlas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5.1. Bộ dữ liệu chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2. Tiến hành chạy thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 44 44 3.5.3. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Chương 4. Thuật toán ACO giải bài toán q-CaRS . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.1. Đồ thị cấu trúc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2. Vết mùi và thông tin heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3. Quy tắc cập nhật mùi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4. Thủ tục tìm kiếm cục bộ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.5. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.6. Kết quả thực nghiệm và đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 LỜI MỞ ĐẦU Trong những năm gần đây, đi cùng với sự bùng nổ mạnh mẽ của công nghệ thông tin và du lịch, các dịch vụ tiện ích phục vụ cho khách du lịch với các ứng dụng di động cũng được phát triển mạnh mẽ. Nhu cầu tìm kiếm các kế hoạch cho chuyến đi với chi phí phù hợp và thuận lợi là một trong những nhu cầu phổ biến. Cụ thể, trong một tour du lịch tham quan các địa điểm của thành phố, tại mỗi địa điểm đều có những sẵn những chiếc xe du lịch với giá thành cụ thể. Vì lý do tài chính cũng như thời gian hành khách có thể sẽ không đi tham quan được hết các địa điểm nhưng họ luôn mong muốn sẽ có một chuyến đi hài lòng nhất với chi phí nhỏ nhất. Đây bài toán thuộc vấn đề tối ưu tổ hợp, thuộc lớp bài toán NP-khó và là bài toán biến thể của bài toán người bán hàng du lịch(TSP) và bài toán thuê xe du lịch(CaRS). Đã có rất nhiều các nghiên cứu đưa ra cho bài toán này như : “Các phương pháp tối ưu cho bài toán người bán hàng du lịch trực tuyến”[46] , “Bảo đảm xấp xỉ cho bài toán người bán hàng có trọng số”[6] , “Thuật toán Memetic cho bài toán thuê xe du lịch”[20]. . . Tuy nhiên các nghiên cứu này không xét đến chi phí di chuyển mà mới chỉ xét đến thời gian di chuyển thành công giữa các địa điểm. Vấn đề được đặt ra trong nghiên cứu này đó là sự tổng quát hóa của thuật toán QTSP với một tập hợp các xe ô tô để người bán hàng có thể thuê để di chuyển. QTSP là một biến thể của TSP với mỗi đỉnh đều có rằng buộc nhất định và mục tiêu là tối thiểu hóa chi phí di chuyển với yêu cầu rằng buộc không nhỏ hơn giá trị định sẵn. Trong nghiên cứu “Thuật toán Memetic cho bài toán thuê xe du lịch”[20] đã đưa ra những kết quả được đánh giá khá cao, tuy nhiên trong nghiên cứu không có ràng buộc nào đối với các địa điểm đến thăm. Bài toán q-CaRS là bài toán tối ưu tổ hợp có nhiều ràng buộc , thuộc lớp bài toán NP khó, chỉ có thể tìm lời giải gần đúng trong thời gian đa thức. Trong nghiên cứu [21] tác giả đã đưa ra thuật giải di truyền để giải bài toán và kết quả thu được là khá tốt. Tuy nhiên trong thời gian gần đây, phương pháp tối ưu hóa đàn kiến giải bài toán tối ưu tổ hợp đang được nổi lên với những thực nghiệm được đánh giá khá cao đặc biệt là thành công trong bài toán người bán hàng với số đỉnh lên đến 2000. Vì vậy luận văn đề xuất thêm phương pháp tổi ưu hóa đàn kiến giải bài toán q-CaRS trên. Kết quả thực nghiệm cho thấy phương pháp tối ưu hóa đàn kiến cho kết quả trong nhiều hợp tốt hơn thuật giải GA về cả chất lượng và thời gian. Trong phương pháp tối ưu hóa đàn kiến, luận văn sử dụng quy tắc cập nhật mùi Maxmin trơn trong nghiên cứu của tác giả Đỗ Đức Đông và các cộng sự [2]. 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 6 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. 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. Do thời gian thực hiện luận văn không nhiều, kiến thức còn hạn chế nên khi làm luận văn không tránh khỏi những hạn chế và sai sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Xin chân thành cảm ơn! Hà Nội, ngày .. tháng .. năm 2018 Học viên Đinh Thị Thủy 7 Chương 1 Bài toán thuê xe du lịch có hạn ngạch 1.1. Quy hoạch nguyên Quy hoạch nguyên (Integer Programming) , viết tắt là IP, là bài toán quy hoạch mà trong đó tất cả hoặc một phần các biến bị ràng buộc chỉ lấy giá trị nguyên. Trường hợp thứ nhất được gọi là quy hoạch nguyên hoàn toàn (Pure Integer Programming – PIP), trường hợp thứ hai được gọi là quy hoạch nguyên bộ phận (Mixed Integer Programming – MIP) 1.1.1. Dạng tổng quát của bài toán Bà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 ≤ b x≥0 x ∈ Zn Bài toán quy hoạch nguyên được gọi là hoàn toàn khi tất cả các biến đều là số nguyên và được gọi là bộ phận khi một số biến không phải là số nguyên. Bài toán quy hoạch nguyên 0-1 là bài toán khi các biến được giới hạn là 0 hoặc 1. 1.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 quy hoạch nguyên hỗn hợp và bài toán quy hoạch nguyên 0-1. 8 Lập kế hoạch sản xuất Quy hoạch nguyên hỗn hợp có nhiều ứng dụng trong sản xuất công nghiệp, bao gồm mô hình hóa việc làm. Một ví dụ quan trọng xảy ra trong quy hoạch sản xuất nông nghiệp bao gồm xác định năng suất sản xuất cho một số loại cây trồng có thể chia sẻ tài nguyên (ví dụ như đất đai, lao động, vốn, hạt giống, phân bón ...). Một mục tiêu có thể là tối đa hóa tổng sản lượng mà không vượt quá các nguồn lực sẵn có. Trong một số trường hợp, điều này có thể được biểu diễn dưới dạng một chương trình tuyến tính, nhưng các biến phải được hạn chế là số nguyên. Bài toán lập lịch Bài toán này liên quan đến dịch vụ và lập lịch trình xe trong mạng lưới vận tải. Ví dụ, bài toán liên quan đến việc chỉ định xe buýt hoặc tàu điện ngầm vào các tuyến đường riêng để có thể đáp ứng được thời gian biểu, và cũng để trang bị cho họ các trình điều khiển. Ở đây các biến quyết định nhị phân cho biết xe buýt hoặc tàu điện ngầm được gán cho tuyến đường và liệu người lái xe có được chỉ định cho một chuyến tàu hoặc tàu điện ngầm hay không. Mạng viễn thông Mục tiêu của những bài toán này là thiết kế một mạng lưới các đường dây cài đặt để đáp ứng các yêu cầu truyền thông được xác định trước và tổng chi phí của mạng là tối thiểu. Điều này đòi hỏi tối ưu hóa cả topo của mạng cùng với việc thiết lập năng suất của các đường khác nhau. Trong nhiều trường hợp, năng suất bị hạn chế là số nguyên. Thông thường, tùy thuộc vào công nghệ được sử dụng, các hạn chế bổ sung có thể được mô hình hóa như là một bất đẳng thức tuyến tính với các biến số nguyên hoặc nhị phân. Mạng di động Nhiệm vụ quy hoạch tần số trong mạng di động GSM bao gồm việc phân phối các tần số sẵn có trên các ăng ten để người dùng có thể được đáp ứng và sự kết hợp được giảm thiểu giữa các ăng-ten. Bài toán này có thể được xây dựng như là một chương trình tuyến tính số nguyên, trong đó các biến nhị phân cho biết tần số được gán cho một ăng-ten. 1.1.3. Các phương pháp tiếp cận giải bài toán quy hoạch nguyên Sử dụng tổng số đơn modulo Nếu bài toán có dạng max (c T x ), Ax = b với A, b, c đều nguyên và A là tổng đơn modulo, khi đó tất cả các phương án đều là số nguyên. Do đó, đáp án trả về bằng thuật toán đơn giản được đảm bảo là nguyên. Để chỉ ra tất các các đáp án đều là nguyên, đặt x là một lời giải của bài toán. Khi đó Ax = b, x0 = [ xn1 , xn2 , ..., xn j ] là các phần tử tương ứng trong cột của x. Theo định nghĩa, có ma trận vuông con B của A sao cho Bx0 = b. 9 Vì các cột của B là độc lập tuyến tính và B là ma trận vuông, theo giả định B là đơn modulo và det( B) = ±1. Vì B là ma trận không suy biến, khả nghịch nên B adj (B adj là ma trận liên hợp của B). Khi đó: x0 = B−1 b. Theo định nghĩa B−1 = det ( B) B−1 = ± B adj là nguyên x0 = B−1 b là nguyên Tất cả các đáp án có thể đều nguyền Thuật toán chính xác Khi ma trận A không hoàn toàn unimodular, có một loạt các thuật toán có thể được sử dụng để giải bài toán quy hoạch nguyên chính xác. Một lớp các thuật toán là các phương pháp cắt mặt phẳng bằng cách giải sự lũy biến của bài toán quy hoạch nguyên và sau đó thêm các ràng buộc tuyến tính đưa ra giải pháp theo hướng nguyên mà không loại bỏ bất kỳ điểm khả thi nào. Một lớp các thuật toán khác là các biến thể của nhánh cận và phương thức giới hạn biên. Ví dụ, phương pháp nhánh cận và cắt kết hợp phương pháp cắt và phương pháp nhánh cận. Một lợi thế là các thuật toán có thể được kết thúc sớm và miễn là có ít nhất một giải pháp tích hợp đã được tìm thấy khả thi, mặc dù không nhất thiết phải tối ưu, giải pháp có thể được trả lại. Hơn nữa, các giải pháp của sự bài toán quy hoạch nguyên lũy biến có thể được sử dụng để ước tính trường hợp xấu nhất từ giải pháp tối ưu được trả lại. Cuối cùng, phương pháp nhánh cận và giới hạn biên có thể được sử dụng để trả về nhiều giải pháp tối ưu. Lenstra năm 1983 cho thấy rằng, khi số lượng các biến được cố định, bài toán quy hoạch nguyên có thể được giải quyết trong thời gian đa thức. Phương pháp Heuristic Vì bài toán quy hoach nguyên là bài toán NP, nên nhiều trường hợp khó giải quyết được và do đó phương pháp heuristic phải được sử dụng thay thế. Ví dụ, tìm kiếm tabu có thể được sử dụng để tìm kiếm lời giải cho bài toán quy hoạch nguyên. Để sử dụng tìm kiếm tabu để giải quyết bài toán quy hoạch nguyên, các chuyển động có thể được định nghĩa là tăng hoặc giảm một số biến ràng buộc nguyên, trong khi tất cả các biến số nguyên ràng buộc khác không đổi. Các biến không bị ràng buộc sau đó được giải. Bộ nhớ ngắn hạn có thể bao gồm các giải pháp đã được thử nghiệm trước đó trong khi bộ nhớ trung hạn có thể bao gồm các giá trị cho các biến số nguyên bị ràng buộc. Cuối cùng, bộ nhớ dài hạn có thể hướng dẫn tìm kiếm theo các giá trị số nguyên mà chưa từng được thử. Một số phương pháp heuristic khác: Hill climbing Simulated annealing Reactive search optimization Ant colony optimization 10 Hopfield neural networks Ngoài ra còn có một loạt các phương pháp heuristic khác đối với các bài toán đặc biệt, chẳng hạn như phương pháp k-opt cho bài toán người chào hàng. 1.2. Bài toán người chào hàng(Traveling Salesman Problem - TSP) Bài toán người bán hàng là một trong những bài toán điển hình của tối ưu tổ hợp được định nghĩa trong thế kỉ 19 bởi nhà toán học Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman. Trò chơi Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình Hamilton. 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ành 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 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 trên) sao cho tổng độ dài các cạnh là nhỏ nhất. Dưới dạng đồ thị bài toán được mô hình hóa như một đồ thị vô hướng có trọng số. Đây chính là bài toán tìm chu trình Hamilton với đồ thị đầy đủ có trọng số G = (V, E), với V là tập các đỉnh với nhãn là các thành phố trong C, E là tập các cạnh nối các thành phố tương ứng, độ dài mỗi cạnh chính là độ dài đường đi giữa hai thành phố tương ứng. Trong trường hợp này, tập S sẽ là tập các chu trình Hamilton trên G, f là độ dài của chu trình, Ω là ràng buộc đòi hỏi chu trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), C là tập thành phố được xét, C0 trùng với C, tập X là vectơ độ dài n: x = { x1 , x2 , ..., xn } vớixi ∈ C ∀i ≤ n, còn X ∗ là các vectơ trong đó xi khác x j đối với mọi cặp (i, j). Do đó, lời giải tối ưu của bài toán TSP là một hoán vị π của tập đỉnh c1 , c2 , ..., cn sao cho hàm độ dài f (π ) là nhỏ nhất, trong đó f (π ) được tính theo công thức sau: n −1 f (π ) = ∑ (d(π (i), π (i + 1))) + d(π (n), π (1)) i =1 Trong bài toán TSP đối xứng, khoảng cách giữa hai thành phố là không đổi dù đi theo chiều nào. Như vậy đồ thị trong bài toán này là đồ thị vô hướng. Việc đối xứng này làm giảm đi một nửa số lời giải có thể. Trong khi đó, với bài toán TSP bất đối xứng thì đường đi giữa hai thành phố có thể chỉ một chiều hoặc có độ dài khác nhau giữa mỗi chiều, tạo nên đồ thị có hướng. TSP là một trong những bài toán được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp 11 tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố. Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch. Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của TSP (cho trước độ dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều tăng theo cấp số nhân với số thành phố. TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó như lập kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian du lịch hay giá thành, hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian thậm chí còn làm cho bài toán trở nên khó hơn. Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài toán TSP thuộc lớp NP-đầy đủ. Vì vậy không có giải thuật hiệu quả nào cho việc giải bài toán TSP. Hay nói cách khác, giống như thời gian chạy xấu nhất cho bất ký giải thuật nào cho bài toán TSP tăng theo hàm mũ với số lượng thành phố, vì vậy thậm chí nhiều trường hợp với vài trăm thành phố cũng đã mất vài năm CPU để giải một cách chính xác. Một số cách tiếp cận bài toán • Thiết kế thuật toán tìm kiếm lời giải tối ưu (thường hoạt động hiệu quả cho những trường hợp nhỏ). • Thiết kế thuật toán heuristic để tìm những lời giải tốt nhưng không nhất thiết tối ưu. • Thiết kế thuật toán xấp xỉ để tìm những lời giải không quá lớn so với lời giải tối ưu.. • Giải quyết các trường hợp đặc biệt. 12 1.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) Bài toán thuê xe du lịch có hạn ngạch được đề xuất bởi Elizabeth F.G. Goldbarg và các cộng sự[22]. Đây là bài toán mở rộng của bài toán người bán hàng có hạn ngạch và bài toán thuê xe du lịch được ứng dụng trong việc chọn tour du lịch. 1.3.1. Bài toán người bán hàng có hạn ngạch(QTSP) Bài toán được giới thiệu trong[21]. Dưới dạng đồ thị đây là bài toán có đồ thị có hướng và có trọng số. Ta có G = {V, A} là một đồ thị đầy đủ, với V = {v1 , v2 , ..., vn } là tập các đỉnh và A = {(vi , v j ), vi , v j ∈ V }. Mỗi đỉnh vi ∈ V đều có một ràng buộc là mức độ hài lòng, tại mỗi cạnh (vi , v j ) ∈ A có một trọng số cij là chi phí thuê xe. Lời giải của bài toán chính là tìm chu trình Hamilton từ tập con V 0 của V với chi phí thấp nhất. Bài toán thuê xe du lịch có hạn ngạch được mở rộng từ bài toán QTSP. 1.3.2. Các bài toán liên quan Hầu hết các nghiên cứu trước đây của vấn đề du lịch là dựa trên các biến thể của vấn đề [23] và chúng không xem xét đến các chi phí vận chuyển. Họ xem xét đến thời gian di chuyển thành công giữa các điểm và giá trị tối đa của tổng các lợi ích liên kết với mỗi điểm. Một số bài bái có xem xét đến thời gian cần thiết để đến thăm các điểm du lịch hấp dẫn. Cho một tập hợp các điểm tương ứng với các đỉnh của 1 đồ thị, mỗi đỉnh có một điểm số tương ứng đại diện cho mức độ hài lòng của điểm đến. Trọng số tương ứng với mỗi cạnh (vi , v j ) ∈ A biểu thị cho thời gian cần thiết để di chuyển giữa vi và v j . Mục tiêu của bài toán là tìm được giá trị lớn nhất của tổng số điểm cho những điểm du lịch đã chọn trong một khoảng thời gian giới hạn nhất định. Một cuộc khảo sát heuristic và metaheuristic để tiếp cận TTDP được giới thiệu trong [15]. Một công cụ hướng dẫn du lịch động ở Goerlitz (Đức) được giới thiệu trong [24, 26] bằng cách dùng thuật toán tham lam để giải quyết các vấn đề tối ưu. Một biến thể của bài toán định hướng đã được dùng trong các bài toán thực tế trong [39], trong đó mỗi đỉnh có một giá trị trọng số tương ứng với thời gian cần thiết để di chuyển tới mỗi vị trí. Điểm số tương ứng với mỗi vị trí được tính toán bằng thông tin thu được từ kĩ thuật tìm kiếm thông tin và tìm kiếm địa phương sẽ được áp dụng cho bài toán. Một hệ thống thực tế được hoàn thành đã được giới thiệu cho thành phố Ghent. Bài báo này được kế thừa từ [38] bằng cách xem xét đến thời tiết, giờ mở cửa, địa điểm đông dân và sở thích cá nhân. Về cơ bản, mô hình cơ sở của nghiên cứu này giống với bài toán định hướng, 13 tuy nhiên nó khác ở điểm là cho một số lượng địa chỉ có thể di chuyển đến nhưng bị giới hạn bởi một thời gian nhất định. Thuật toán tìm kiếm ngẫu nhiên tham lam (GRASP) với phương pháp nối liền (relinking) đã được áp dụng để giải quyết bài toán tối ưu. Phiên bản với 2 tham số của vấn đề này được đề cập trong [39] và cũng được nghiên cứu trong[34], có 2 giá trị lợi ích khác nhau được gán với mỗi thành phố. Thuật toán đàn kiến và thuật toán khu phổ biến(variable neighborhood ) với phương nối liền (path relinking) đã được áp dụng cho nhiều trường hợp với một và 2 tham số. Ngoài ra, để có thể đánh giá các trường hợp, các thuật toán đã được áp dụng cho những trường hợp thực tế với dữ liệu từ Úc và thành phố Padua (Italy). Trong [??], GRASP đã được dùng để phát triển hệ thống chuyên gia du lịch gọi là City Trip Planner. Năm thành phố ở Belgium đã được chọn để kiểm thử. Một phần mở rộng của vấn đề đó là xem xét đến các phương tiện đi lại công cộng được giới thiệu trong [14] và thành phố San Sebastian đã được chọn để kiểm thử. Vấn đề đã được mô hình hóa thành bài toán định hướng phụ thuộc thời gian với các cửa sổ thời gian và đã được giải quyết bằng thuật toán tìm kiếm địa phượng[42] . Hầu hết các nghiên cứu trước đây đều bị giới hạn khu vực, ví dụ như 1 thành phố hoặc các địa điểm lân cận. Tuy nhiên, trong một số trường hợp, khách du lịch hoặc người bán hàng có thể di chuyển qua nhiều thành phố khác nhau bằng cách thuê xe [20] và mục tiêu của vấn đề có thể là việc tối ưu chi phí của tour, bao gồm số tiền bỏ ra để thuê xe. Có nhiều phương tiện và công ty trong mỗi thành phố, phạm vi của các tùy chọn có thể là người dùng chọn phương tiện tốt nhất để sử dụng khi di chuyển trong tour. Nói chung, một tour sẽ bắt đầu và kết thục tại một thành phố. Để chọn được xe nào là tốt nhất cho mỗi phần của tour, khách hàng nên xem xét đến giá tiền thuê xe, các chí phí liên quan đến nhiên liệu tiêu thụ và các chi phí khác (ví dụ như phí cầu đường). Nếu một chiếc xe được thuê ở một thành phố và được trả lại ở một thành phố khác, khách hàng sẽ phải trả thêm lệ phí để đưa chiếc xe trở lại thành phố ban đầu. Trong một công ty, các xe cho thuê được quản lý theo cấu trúc phân cấp đơn giản với các khu vực chung [11]. Theo [11], những công ty này sẽ quản lý khoảng 15 nhóm xe, mỗi nhóm gồm những xe có chất lượng giống nhau và những nhóm khác nhau sẽ có chất lượng và giá tiền để thuê xe khác nhau. Một nghiên cứu về vấn đề định tuyến trong lĩnh vực thuê xe được giới thiệu trong [45]. Một vấn đề chính khác là sự phân phố xe tại mỗi trạm cho thuê, vì khách hàng được phép thuê tại một trạm và trả lại xe tại một trạm khác. Do đó, cần thiết để duy trì số lượng cố định xe tại mỗi trạm vì phương tiện được thuê phải được trả lại. Những hệ thống cho thuê xe và trả lại có thể xảy ra tại những trạm khác nhau và được sử dụng ở nhiều địa điểm khác nhau[16]. Có những cách để giảm tỉ lệ số xe được trả lại ở một trạm khác đó là cung cấp những ưu đãi cho khách hàng. 14 Những trạm có tỉ lệ sử dụng cao có thể được khuyến khích giảm đi lợi nhuận một chút để khách hàng trả xe tại những trạm có tỉ lệ sử dụng thấp hơn 1.3.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 du 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 đị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 chi 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 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 quan và chi phí di chuyển. Yêu cầu được đặt ra là khách tham quan có thể thuê xe để di chuyển giữa các thành phố. Mức giá thuê xe ở mỗi thành phố là khác nhau. Khi khách hàng trả xe lại tại một thành phố không phải là nơi thuê xe thì mất thêm chi phí trả xe để xe đó di chuyền về nơi ban đầu. Các vấn đề liên quan đến bài toán này đã được ứng dụng rất nhiều trong thực tế[14]. 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òn gọ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 TSP Input: -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àng buộ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ề j Các biến số: - 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 nhữ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. 15 - Giá trị nguyên ui định nghĩa vị trí của đỉnh i trong tour. Đỉnh 1 gọi là thành phố 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 ∈V f 1jc = ∑∑ c ∈ C i ∈V f 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 i thì sau đó phải có 1 chiếc xe khác rời khỏi đỉnh i. sumc∈C ∑ f ihc = i ∈V ∑∑ c f hj ≤ 1∀ h ∈ V c ∈ 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) 0 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 thành phố i từ thành phố h.  ! aic = ∑ f ijc ∑0  0 j ∈V ∑ 0 f 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 ijc eic = ∑ ! f ijc  j ∈V  ∑0 0 ∑ 0 f 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 1 c∈C -Mỗi xe chỉ được thuê một lần i ∈V -Nếu xe c được thuê thì sau đó nó sẽ được trả lại. ∑ a1c = ∑ e1c ∀c ∈ C i ∈V i ∈V 16 (1.3.8) -Phải đảm bảo được mức độ hài lòng. ∑ ∑∑ ! ! f ijc qi ≥ω (1.3.9) c ∈ C j ∈V i ∈V -Không có các tour du lịch con 2 ≤ ui ≤ n∀i = 2, ..., n ui − u j + 1 ≤ (n − 1)(1 − ∑ f ic j)∀i, j = 2, ..., n (1.3.10) (1.3.11) c∈C -Các biến đều là nhị phân và biến ui là số nguyên dương. f ijc , ωijc , aijc , eijc ∈ [0, 1] (1.3.12) ui ∈ N (1.3.13) Hàm mục tiêu Chi phí cho chuyến đi đảm bảo là thấp nhất min ∑ ∑ dijc . fijc + ∑ ∑ γijc .ωijc c ∈ C j ∈V c ∈ C j ∈V 17 (1.3.14) Chương 2 Các phương pháp metaheuristic 2.1. Thuật giải di truyền Thuật toán di truyền (Genetic Algorithm viết tắt là GA ), là phương pháp metaheuistic đang được sử dụng rộng rãi. Phương pháp này phỏng theo quá trình tiến hoá tự thích nghi của các quần thể sinh học dựa trên học thuyết Darwin để tìm lời giải các bài toán tối ưu. Trong tự nhiên, mỗi cá thể có một tập các tính chất và đặc điểm riêng biệt được thể hiện ra ngoài môi trường gọi là kiểu hình. Kiểu hình này được quyết định bởi cấu trúc của các gene trong cơ thể, được gọi là kiểu gene. Sự đa dạng về kiểu gene của các cá thể dẫn đến sự đa dạng về kiểu hình của một quần thể sinh học. Quá trính phát triển của mỗi quần thể tuân theo quy luật chọn lọc tự nhiên mà tiến hoá qua các thế hệ kế tiếp nhau. Trong đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trình sinh sản (di truyền và biến dị) cạnh tranh tự nhiên, cá thể nào có kiểu hình (và do đó là kiểu gene) thích nghi cao hơn với môi trường phát triển thì sẽ có khả năng lớn hơn trong tồn tại và sản sinh con cháu, do đó kiểu gene này tiến hoá và hoàn thiện. Quá trình tiến hoá này được lặp đi lặp lại, các cá thể có kiểu gene phù hợp sẽ sống sót và phát triển, các cá thể yếu sẽ bị loại bỏ. Dựa vào tư tưởng trên, để giải bài toán tối ưu người ta mã hoá mỗi lời giải tiềm năng dưới dạng thích hợp gọi là một nhiễm sắc thể. Mỗi nhiễm sắt thể (còn gọi là cá thể) cấu tạo từ các gene,thường dùng nhất là dạng xâu. Trên tập nhiễm sắc thể này, người ta xây dựng các toán từ di truyền (tương giao chéo: crosover, biến dị: mutation) và mô phỏng quá trình chọn lọc tự nhiên trên một quần thể nhiễm sắc thể để tìm lời giải gần đúng của bài toán. Để hiểu rõ GA. , trước hết ta làm quen với GA. cổ điển dùng cho bài toán tối ưu liên tục. 18 2.1.1. Thuật toán di truyền cổ điển GA cổ điển được Holland (1975) giới thiệu để tối ưu hoá bài toán: max { f ( x )/x ∈ M ⊂ Rn } (2.1.1) nhờ biểu diễn gene dạng nhị phân, ở đây M là hình hộp in=1 [ ai , bi ] trong không gian véc tơ thực n chiều Rn , f nhận các giá trị dương trên M. Để thực hiện thủ tục GA, trước hết cần mã hóa các phần tử của tập M. Mỗi x trong M được mã hoá bởi một xâu nhị phân độ dài m z = (z1 , z2 , ..., zm ) gọi là nhiễm sắc thể hay một cá thể, mỗi zi được gọi là một gene. F Phương pháp mã hoá và giải mã Mã hóa Giả sử ta cần tìm cực đại hàm f với sai số mỗi biến xi là 10− p . Ta chia mỗi đoạn [ ai , bi ] thành (bi − ai )10 p đoạn bằng nhau và ký hiệu mi là số tự nhiên nhỏ nhất thoả mãn: (bi − ai )10 p 6 2mi − 1 Khi đó nếu x = ( x1 , ..., xi , ..., xn ) và xi thuộc đoạn thứ k thì xi được mã hoá bởi xâu nhị phân độ dài mi có dạng sao cho sẽ thoã mãn yêu cầu về độ chính xác và x được biễu diễn bởi xâu nhị phân có độ dài . Giải mã Với mỗi đoạn gene (bmi −1 , ..., b0 ) ta xác định ki theo hệ số 10 : m −1 k i = ∑ j=i 0 (b j 2 j )10 ( bi − a i ) 2m i −1 m −1 (b − a ) ai + ∑ j=i 0 (b j 2 j )10 2mi i −i1 . và có xi = ai + k i Hay là xi = Mô tả lược đồ GA Với phương pháp mã hóa và giải mã như trên, để thực hiện GA, ta dựng thủ tục mã hoá , giải mã tương ứng. Tiếp theo, xây dựng thủ tục tính hàm eval trên tập nhiễm sắc thể để đánh giá độ thích nghi của mỗi cá thể: eval (z) = f ( x ), trong đóx là véc tơ tương ứng với z. Sau khi đã có các thủ tục mã hóa-giải mã và tính hàm eval cho các nhiễm sắc thể, thủ tục GA khở tạo ngẫu nhiên quần thể ban đầu P(0) gồm N nhiễm sắc thể và thực hiện lặp quá trình tiến hoá quần thể này cho đến khi dừng nhờ các thử tục 19
- Xem thêm -

Tài liệu liên quan