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

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.
Nội dung trích xuất từ tài liệu:
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 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 procedure, with a Random Neighborhood Ordering (RVND), in the local search phase. Key words: Vehicle routing problem (VRP), Combinatorial Optimization (CO), Iterated Local Search (ILS); Variable Neighborhood Descent with Random neighborhood ordering (RVND). (*) Trường ĐH KTCN LA TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 50 NGHIÊN CỨU - TRAO ĐỔI 1. Mở đầu Bài toán lập lộ trình xe (VRP) được Phương pháp metaheuristic là phần lõi giới thiệu lần đầu tiên bởi Dantzig and trung tâm một số lớn các giải thuật Ramser [1]. Kể từ đó đã có rất nhiều heuristic có kết quả tốt cho các bài toán công trình mở rộng cho dạng bài toán CO, bao gồm cả bài toán VRP. Các VRP và cố gắng nỗ lực giải quyết chúng. phương pháp metaheuristic ngày càng Ngành vận tải hỗ trợ hầu hết các hoạt được chú ý và phát triển mạnh mẽ để cho động kinh tế-xã hội. Chi phí đi lại hàng ra các giải pháp có hiệu quả rất cao. năm ở Hợp chủng quốc Hoa Kỳ xấp xỉ Bài toán VRP là bài toán NP-khó [22] 45 tỉ USD [2] và doanh thu vận tải hàng cho nên việc giải quyết nó là vấn đề hóa ở Châu Âu khoảng 168 tỉ USD mỗi thách thức lớn. Việc giải bài toán VRP năm. Ngành vận tải ở Vương quốc Anh, thông thường được giải tổng quát bằng Pháp và Đan Mạch đóng góp khoảng giải thuật chính xác và giải thuật 15%, 9% và 15% tiêu dùng quốc gia heuristic. Giải thuật chính xác dùng để tương ứng [2]. Ở Việt Nam, theo số liệu tìm ra lời giải tối ưu chính xác đúng. thống kê của Tổng Cục Thống kê thì: Giải thuật heuristic để tìm giải pháp tổng số lượt hành khách vận chuyển cả trong số những cái có thể, nhưng không nước trong năm 2010 là 71.942,90 triệu đảm bảo rằng cái tốt nhất sẽ được tìm lượt người.km; tổng khối lượng hàng hoá thấy, do đó có thể giả định đó là giải luân chuyển cả nước trong năm 2010 là thuật xấp xỉ và không chính xác. 73.572,10 triệu tấn.km. Như nói ở trên, tài toán VRP cho đến VRP và các dạng của nó có ứng dụng nay đã được phát triển thành nhiều dạng và vai trò rất quan trọng trong dây khác nhau và việc giải tất cả các dạng chuyền cung ứng (lĩnh vực quản trị phân bài toán VRP là công việc khó khăn và phối) và liên quan chặt chẽ đến ngành rất phức tạp. Trong khuôn khổ bài báo vận chuyển hàng hóa và con người. Do này chỉ tập trung vào các dạng sau: sự quan trọng trong ứng dụng thực tế nên (i) Capacitated VRP (CVRP). dạng bài toán VRP được nghiên cứu và (ii) VRP with Simultaneous Pickup phát triển rộng rãi. Golden và các cộng and Delivery (VRPSPD). sự [18] đã nghiên cứu và chỉ ra các (iii) VRP with time window (VRPTW). trường hợp ứng dụng bài toán VRP ở (iv) Multi-depot VRP (MDVRP). nhiều lĩnh vực khác nhau: chất thải rắn, (v) Heterogeneous Fleet VRP nước giải khát, thực phẩm, sữa, các (HFVRP) và các dạng mở rộng của nó. ngành công nghiệp báo chí, hệ thống thư Phần còn lại bài báo như sau: phần kế viện … Công trình Toth and Vigo [21] tiếp định nghĩa 5 dạng bài toán VRP đã cho thấy việc sử dụng công cụ tin học đề cập ở trên. Phần 3 rà soát và thống kê hóa trong việc hoạch định phân phối sơ lược các bài báo có phương p ...