Chương 1. Giới thiệu 8 e Trong ngành logistics và vận tai, TTP được sử dụng để tối ưu hóa lộ trình của các phương tiện vận chuyển như xe tải, tàu biển, và máy bay. Điều này giúp giảm thiểu thời gian di chuyển, nhiên liệu tiêu thụ, và chỉ phí vận chuyển. Các công ty vận chuyển và dịch vụ giao hàng thường sử dụng các giải thuật TTP để lên kế hoạch giao hàng một cách hiệu quả.
© Trong quản lý lịch hẹn, TTP có thể được sử dụng để sắp xếp thứ tự các cuộc hẹn sao cho tối ưu hóa thời gian và chỉ phí. Ví dụ, một bác sĩ có thể ứng dung TTP để lên lịch khám bệnh cho các bệnh nhân ở các địa điểm khác nhau, trong khi cân nhắc đến các yêu tố như thời gian di chuyển, thời gian khám, và thu nhập từ mỗi bệnh nhân. e Trong bảo mật, các thuật toán TTP có thể được sử dụng để thiết kế các hệ thống mã hóa và giải mã an toàn. Ví dụ, một hệ thống mã hóa có thể ứng dụng TTP để tạo ra một chuỗi các khóa bí mật, mỗi khóa tương ứng với một thành phố trong bài toán TTP.
Sau đó, hệ thống sẽ mã hóa thông tin bằng cách sử dụng các khóa theo thứ tự được xác định bởi lộ trình của bài toán TSP. Để giải mã, hệ thống cần phải tìm ra lộ trình và các khóa tương ứng. ¢ Bài toán vận tải thùng nước [28}: Bài toán TTP được sử dung để tối ưu hóa việc chuyển các bể nước có kích thước khác nhau từ nhà máy đến các khách hàng. Các bể nước có thể được đóng gói vào nhau để tiết kiệm không gian trên xe tải, nhưng cần phải được tháo ra ở các trạm cơ sở trước khi giao hàng.
Mục tiêu là chọn ra một tập hợp các bể nước và một lộ trình giao hàng sao cho tổng giá trị của việc giao hàng là cao nhất. Tổng giá trị này tỷ lệ với tỉ lệ giữa tổng giá của các bể nước được giao và tổng quãng đường xe tải đi. Bài toán này có ít nhất hai bài toán con là chọn các bể nước để giao và xác định lộ trình giao hàng. Việc giải quyết từng bài toán con riêng biệt không đảm bảo tìm được giải pháp tối ưu cho bài toán toàn cục.
Giới thiệu 9 e Thiết kế mach in: Bài toán TTP được sử dụng để thiết kế các mạch in trong các mạch tích hợp quy mô lớn. Một trong những ứng dụng của bài toán TSP là trong thiết kế mạch in, mục tiêu là nối các chân của các linh kiện điện tử bằng các dây sao cho tổng chiều dài của các dây là nhỏ nhất. Tuy nhiên, đây chỉ là một phần của bài toán. Bài toán hoàn chỉnh bao gồm hai phần là đặt các linh kiện điện tử lên một tắm bảng (phần này gọi là đặt vị trí) và nối các chân của các linh kiện theo một cách nào đó sao cho lượng dây sử dụng là nhỏ nhất (phần này gọi là dây nối).
Trong thiết kế mach in, đôi khi các dây không thể cắt nhau, do đó cần phải sử dụng các lớp khác nhau để đặt các dây. Mục tiêu là tối thiểu hóa số lượng lớp sử dụng. Bài toán này có ít nhất hai bài toán con là đặt vị trí các linh kiện và dây nồi các chân. Việc giải quyết từng bài toán con riêng biệt không đảm bảo tìm được giải pháp tối ưu cho bài toán toàn cục.4 Đóng góp của nhóm Nhóm chúng em đã tiến hành mở rộng nghiên cứu các thuật toán heuristics cho bài toán Traveling Thief Problem: s® Nghiên cứu va thử nghiệm các thuật toán state-of-the-art cho bài toán Traveling Thief Problem.
¢ Dua ra thuật toán SAVI (lay cảm hứng từ thuật toán CS2SA*|29]) và phát triển thêm thuật toán Simulated Anealing với phương pháp Vertex In- sertion tối ưu với Quy Hoạch Động. e Tiến hành thử nghiệm trên tập TTP Benchmark để chứng minh độ hiệu quả của thuật toán.5 Câu trúc của luận văn Cau trúc phan còn lại của bài luận văn nay được trình bày như sau: Chương 1. Giới thiệu 10 se Chương 2 sẽ giới thiệu các thuật toán Local Search, các thuật toán cho 2 bài toán con TSP và KP. Từ đó đưa ra cái nhìn tổng quan để hiểu hơn các thuật toán state-of-the-art đã được đề ra trước đó.
* Chương 3 sẽ giới thiệu chi tiết về thuật toán SAVI, bao gồm cách thức hoạt động, mã giả và các kỹ thuật tăng cường hiệu suất. se Chương 4 sẽ dua ra tập TIP Benmark dùng để đánh giá thuật toán. Thuật toán SAVI sẽ được đánh giá, so sánh với các thuật toán state-of- the-art khác. e Chương 5 tổng kết luận văn và dé ra một số phương án cho các nghiên cứu tương lai.
11 Chương 2 e 2 e Hướng giai pháp hiện nay Như đã trình bày ở mục 1.2 thì bài toán Traveling Thief Problem (TTP) được tạo ra từ sự kết hợp của hai bài toán con là Traveling Saleman Problem (TSP) và Knapsack Problem (KP). Trong mỗi bài toán con thì sẽ có những thuật toán tối ưu riêng. Với mỗi thuật toán tối ưu đó sẽ sử dụng một số thuật toán hoặc thao tác để tối ưu kết quả. Ở trong chương này chúng em sẽ trình bày về các thuật toán sẽ được sử dụng đến trong hướng giải pháp của chúng em của bài luận văn này.
Cụ thể như sau, đầu tiên chúng em sẽ trình bày về các thuật toán local search (thuật dùng để tối ưu kết quả cho các bài toán con), sau đó chúng em sẽ trình bày về các thuật toán dùng để giải quyết hai bài toán con, cuối cùng chúng em sẽ trình bày các thuật toán state-of-the-art hiện nay giải quyết TTP.1 Local search Tìm kiếm cục bộ (Local search) là một thuật toán tìm kiếm thường được sử dụng trong lĩnh vực trí tuệ nhân tạo và các bài toán tối ưu hóa (ví dụ như TSP). Thuật toán này bắt đầu từ một giải pháp ban đầu và sau đó thực hiện các bước thay đổi để cải thiện giải pháp đó. Những thay đổi này thường được thực hiện thông qua các toán tử (operator). Mỗi lần áp dụng toán tử sẽ tạo ra một giải pháp lân cận (neighboring solution), nếu giải pháp lân cận có điểm đánh giá tốt hơn giải pháp ban đầu, thì giải pháp ban đầu sẽ bị thay thế bằng Chương 2.
Hướng giải pháp hiện nay 12 giải pháp lân cận. Nếu một giải pháp không có giải pháp lân cận nào có điểm đánh giá tốt hơn, thì giải pháp đó là một tối ưu cục bộ đối với bài toán đó. Việc liên tục lặp đi lặp lại quá trình thay thế giải pháp hiện tại bởi một giải pháp lân cận tốt hơn được gọi là một thuật toán leo đồi (hill climbing algorithm) (được thể hiện trong thuật toán Ilbên dưới). Algorithm 1 HILL CLIMBING 1: x — một giải pháp ban đầu 2: while chưa gặp điều kiện dừng do 3 x€Cargmax/cw(x) f(x’) > ƒ là hàm đánh giá 4: > N là lân cận của x 5: end while Phương pháp này có ưu điểm là có thể tìm được lời giải chấp nhận được trong thời gian không quá lâu (có thể nhanh với một số trường hợp).
Nhưng nó có nhược điểm đó là có thể bị mắc kẹt ở các điểm tối ưu cục bộ hoặc các điểm dừng, dẫn tới không đảm bảo tìm được lời giải tối ưu toàn cục. Đối với Traveling Thief Problem thì local search được sử dụng để tối ưu kế hoạch chọn các vật phẩm (packing plan) (của bài toán con Knapsack Problem - KP) hoặc là tối ưu chu trình (tour) (của bài toán con Traveling Saleman Problem - TSP) mà tên trộm di chuyển (định nghĩa sơ lược về TSP và KP được chúng em trình bày trong phần 2. Trong phần này, chúng em sẽ trình bày về một số thuật toán local search được sử dụng trong hướng giải pháp của nhóm trong luận văn này.1 2-opt 2-opt là một phương pháp tìm kiếm cục bộ thường được sử dụng chủ yếu trong bài toán người du lịch (Traveling Salesman Problem - TSP), mục tiêu của thuật toán là có gắng cải thiện một chu trình đã có bằng cách thay đổi các cặp cạnh không liên tiếp. Ngoài được sử dụng cho TSP, nó còn có thể được sử dụng cho bắt kỳ bài toán mà kết quả ở dạng hoán vị.
Hướng giải pháp hiện nay 13 @——® “` @—O-O.INN HAAG IIE) HÌNH 2.1: 2-opt (Hình bên trái là chu trình ban đầu, hình bên phải là chu trình sau khi áp dụng 2-opt lên đoạn từ đỉnh thứ 3 tới đỉnh thứ 5 trong đồ thị ban đầu) Ý tưởng của 2-opt khi áp dụng để tối ưu một chu trình như sau. Đầu tiên sẽ chọn một đoạn liên tiếp các đỉnh từ i tới j với 1 <i <j < n (với n6 là số đỉnh trong chu trình). Sau đó dao ngược đoạn được chọn lại thì sẽ được một giải pháp lân cận (Hình 2.1), rồi đánh giá giải pháp lân cận vừa có được. Tiếp đó tiễn hành so sánh với giải pháp hiện có, nêu kết quả đánh giá tốt hơn thì ta thay thế giải pháp hiện có bằng giải pháp lân cận, ngược lại thì ta giữ nguyên giải pháp hiện có.
Quá trình được lặp đi lặp lại đến khi không thể tối ưu được nữa. Thuật toán này có hiệu quả rất tốt trong việc tối ưu kết quả dựa trên một kết quả đã có ban đầu. Dễ dàng nhìn thấy mọi đoạn từ/ tới 7 sao cho 1 <i <j <n thì đều có thể được chọn để thực hiện 2-opt, vì thế có thể chọn tới O(n?) đoạn, tương ứng với O(n) giải pháp lân cận (neighboring solution). Với số lượng giải pháp lân cận lớn như vậy thì khi giải quyết các trường hợp (instances) có kích thước lớn sẽ không hiệu quả.
Trong bài báo dé xuất về thuật toán CS2SA* và CS2SAR của Yafrani và các cộng sự [29], đã dé cập đến việc sử dung Delaunay triangulation [8] như một bộ tạo ứng viên cho thuật toán 2-opt. Delaunay triangulation cũng được sử dụng trong thuật toán memetic ở [21]. Với một giải pháp hiện có, thay vì phải đánh giá hết tất cả O(n) giải pháp lân cận, Chương 2. Hướng giải pháp hiện nay 14 việc sử dụng Delaunay triangulation để tạo ứng viên sẽ giúp giảm bớt độ phức tạp mà không làm giảm chất lượng của các giải pháp đáng kể.
Cụ thể, trong một dé thị Delaunay, trung bình mỗi thành phố chỉ có 6 thành phố xung quanh [29]. Vì thé độ phức tạp của thuật toán 2-OPT sẽ trở thành O(n) thay vi O(n”). Tác giả đã triển khai thuật toán 2-opt sử dụng thuật toán Delaunay triangulation bằng phương pháp chia để trị [11] để giải quyết trường hợp xâu nhất, có độ phức tap thời gian là O(n log n) 2.