Bài viết Một hướng tiếp cận mới giải bài toán cực tiểu độ trễ MLP đi sâu vào nghiên cứu tìm kiếm địa phương trong phương pháp ACO. Thuật toán ACO được Dorigo đề xuất lần đầu tiên là AS (Ant System) đến nay có rất nhiều biến thể như MMSA (Max-Min Ant System), SMMAS (Smooth Min-Max Ant System) do chưa có tìm kiếm địa phương đã bộc lộ nhược điểm. | Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN 978-604-82-2274-1 MỘT HƯỚNG TIẾP CẬN MỚI GIẢI BÀI TOÁN CỰC TIỂU ĐỘ TRỄ MLP Đặng Thị Thu Hiền Trường Đại học Thủy lợi email hiendt@ 1. GIỚI THIỆU CHUNG này đi sâu vào nghiên cứu tìm kiếm địa phương trong phương pháp ACO. Thuật toán Bài toán cực tiểu độ trễ Minimum ACO được Dorigo đề xuất lần đầu tiên là AS Latency Problem - MLP thuộc lớp NP-Khó. Ant System đến nay có rất nhiều biến thể Bài toán luôn nhận được rất nhiều sự quan như MMSA Max-Min Ant System SMMAS tâm nghiên cứu của các học giả. Tác giả Wu Smooth Min-Max Ant System do chưa có et al. đề xuất thuật toán theo hướng quy tìm kiếm địa phương đã bộc lộ nhược điểm. hoạch động với độ phức tạp thời gian hàm số Bài báo này sẽ kết hợp SMMAS và tìm kiếm mũ để giải bài toán MLP. Theo hướng gần địa phương nên đã thể hiện ưu điểm vượt trội đúng cận tỷ lệ có Blum et al. Goemans et al. thông qua kết quả thực nghiệm chạy trên các Arora et al. Gần đây et al. 1 bộ dữ liệu chuẩn TSPLIB 4 . đưa ra thuật toán gần đúng với cận tỷ lệ là đây là cận tỷ lệ nhỏ nhất hiện nay cho 2. PHƯƠNG PHÁP NGHIÊN CỨU bài toán MLP. Hiện nay có hai công trình nghiên cứu theo hướng tiếp cận meta- . Bài toán MLP heuristic giải bài toán MLP đã được công bố. Cho đồ thị đầy đủ Kn với tập đỉnh V Đó là A. Salehipour et al. 2 đề xuất thuật 1 2 n và ma trận chi phí không âm C toán meta-heuristic dựa trên GRASP Greedy cij i j 1 2 n với cij là khoảng cách giữa randomized adaptive search procedure và hai đỉnh i và j. Giả sử T v1 v2 vn là một VNS Variable neighborhood search . Sau hành trình xuất phát từ v1 đường đi xuất phát đó M. Silva et al. 3 cũng đề xuất một thuật từ v1 đi qua mỗi đỉnh của đồ thị đúng một toán meta-heuristic khác dựa trên lược đồ của lần trên Kn. Kí hiệu P v1 vk là đoạn đường GRASP ILS Iterated local search và đi từ v1 đến vk trên hành trình T. Ta gọi độ trễ RVND Random variable neighborhood của đỉnh vk trên hành trình T ký hiệu bởi descend thực nghiệm .
