Bài báo này đề cập đến các cách tiếp cận chính xác và metaheuristic để giải quyết các dạng khác nhau của VRP, và đã thực hiện một rà soát thống kê rộng rãi. Giải thuật được trình bày trong bài báo được dựa trên giải thuật metaheuristic Iterated Local Search (ILS) với việc sử dụng một thủ tục giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên (Variable Neighborhood Descent with Random neighborhood ordering (RVND)), trong đoạn tìm kiếm địa phương. | NGHIÊN CỨU - TRAO ĐỔI TỔNG QUAN MỘT SỐ DẠNG CỦA BÀI TOÁN LẬP LỘ TRÌNH XE VÀ GIẢI THUẬT METAHEURISTIC ITERATED LOCAL SEARCH CÓ CẢI TIẾN ĐỂ GIẢI QUYẾT MỘT SỐ DẠNG CỦA BÀI TOÁN LẬP LỘ TRÌNH XE ThS. NGUYỄN MINH ĐẾ TÓM TẮT Bài toán lập lộ trình xe Vehicle Routing Problem VRP là dạng bài toán tối ưu rời rạc và được giới thiệu lần đầu tiên trong cuối những năm 1950. Các giải pháp chính xác cho VRP thường tạo nên bùng nổ tổ hợp tính toán phức tạp. Vì tính hiệu quả nên các giải pháp phải dựa vào các phương pháp xấp xỉ và heuristic đã hoạt động tốt trong thực tế. Các nhà nghiên cứu vẫn tiếp tục nỗ lực để thiết kế ra các giải thuật xấp xỉ mà có tỉ lệ tốt hơn các giải thuật xấp xỉ đã có. Bài báo này đề cập đến các cách tiếp cận chính xác và metaheuristic để giải quyết các dạng khác nhau của VRP và đã thực hiện một rà soát thống kê rộng rãi. Giải thuật được trình bày trong bài báo được dựa trên giải thuật metaheuristic Iterated Local Search ILS với việc sử dụng một thủ tục giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên Variable Neighborhood Descent with Random neighborhood ordering RVND trong đoạn tìm kiếm địa phương. Từ khóa lập lộ trình xe tối ưu tổ hợp tìm theo vùng lặp lại giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên. SUMMARY The Vehicle Routing Problem VRP is a discrete optimization problem and first introduced in the late 1950 s. Exact solutions of VRPs are often computationally intensive. For the sake of efficiency one must resort to approximation methods and heuristics which work well in practice. Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing algorithms. This paper mentions about exact and metaheuristic approaches for solving different variants of the VRP and make a survey of extensive literature reviewing. The proposed algorithm is based on the Iterated Local Search ILS metaheuristic which uses a Variable Neighborhood Descent .
