Mô hình qui hoạch tuyến tính cho bài toán đường đi ngắn nhất có ràng buộc

Trong bài báo này, tác giả trình bày phương pháp mô hình hóa bài toán đường đi ngắn nhất có ràng buộc dựa trên mô hình qui hoạch tuyến tính. Theo đó, việc thêm ràng buộc cho bài toán sẽ đơn giản và linh hoạt có thể đáp ứng việc tìm đường đi ngắn nhất thỏa các ràng buộc như bắt buộc đi qua một số đỉnh trong đồ thị hoặc bắt buộc không đi qua một số đỉnh trong đồ thị hoặc ràng buộc đường đi ngắn nhất bao gồm/không bao gồm một đường con cho trước.
Nội dung trích xuất từ tài liệu:
Mô hình qui hoạch tuyến tính cho bài toán đường đi ngắn nhất có ràng buộc MÔ HÌNH QUI HOẠCH TUYẾN TÍNH CHO BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT CÓ RÀNG BUỘC Bùi Thanh Khiết 1 1. Ban Đề án Chuyển đổi số, Trường Đại học Thủ Dầu MộtTÓM TẮT Bài toán đường đi ngắn nhất được nghiên cứu và áp dụng rộng rãi từ khi nó được ra đời.Cho tới nay có nhiều biến thể từ bài toán đường đi ngắn nhất gốc, đa phần đường đi ngắn nhấtsẽ có thêm nhiều ràng buộc làm cho bài toán trở nên phức tạp. Để giải quyết bài toán đườngđi ngắn nhất có ràng buộc đã có nhiều đề xuất thuật toán để giải quyết nhưng đa phần đềudành riêng cho từng ràng buộc cụ thể. Trong bài báo này, chúng tôi trình bày phương pháp môhình hóa bài toán đường đi ngắn nhất có ràng buộc dựa trên mô hình qui hoạch tuyến tính.Theo đó, việc thêm ràng buộc cho bài toán sẽ đơn giản và linh hoạt có thể đáp ứng việc tìmđường đi ngắn nhất thõa các ràng buộc như bắt buộc đi qua một số đỉnh trong đồ thị hoặc bắtbuộc không đi qua một số đỉnh trong đồ thị hoặc ràng buộc đường đi ngắn nhất bao gồm/khôngbao gồm một đường con cho trước. Chúng tôi đã cài đặt thực nghiệm trên công cụ nguồn mởLP Solve IDE, kết quả cho thấy các ràng buộc cho bài toán được xây dựng tùy biến để tìmnghiệm của bài toán. Từ khoá: đường đi ngắn nhất, quy hoạch tuyến tính.1. GIỚI THIỆU Bài toán đường đi ngắn nhất (shortest path problem – viết tắt SPP) từ một đỉnh đến tất cảcác đỉnh là một trong số những bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thựctế. Giải quyết bài toán này giúp chúng ta tìm kiếm phương án tiết kiệm nhất về chi phí, thờigian, quãng đường có thể áp dụng trong giao thông, lập lịch thi công, … Để giải quyết bài toánnày nhà khoa học máy tính người Hà Lan Edsger Dijkstra đã đề xuất thuật toán Dijkstra[1].Thuật toán có độ phức tạp là O(n2). Tuy nhiên trong thực tế, bài toán đường đi ngắn nhất lạiphát sinh thêm nhiều nhu cầu từ người dùng, họ cần nhiều lựa chọn hơn cho đường đi. Đã cónhiều nghiên cứu mở rộng bài toán SPP gốc, các biến thể của bài toán SPP gốc đa số được mởrộng bằng cách thêm vào ràng buộc (gọi tắt là cSPP) [2]. Ví dụ trên đường đi cần phải bao gồmcó một số nút được chỉ định trước hoặc chỉ định trước số lượng nút [3] hoặc đường đi khôngbao gồm những đường bị cấm cho trước [4, 5] hoặc đường đi từ hai đỉnh cho trước phải chứatất cả các đỉnh của đồ thi (bài toán phủ đỉnh) – bài toán phủ đỉnh có ý nghĩa trong vấn đề phâncấp mạng, định tuyến [6, 7]. Bài toán đường đi ngắn nhất có ràng buộc trong trường hợp tổngquát là bài toán thuộc lớp NP-Hard [8]. Năm 1980, Handler và đồng nghiệp đã đề xuất thuậttoán cho bài toán đường đi có ràng buộc, theo đó thuật toán được phát triển dựa trên Lagrangianralaxation để tìm hai tìm đường đi ngắn nhất giữa hai nút trong mạng đồng thời thõa mãn ràngbuộc kiểu Knapsack [9]. Năm 1988, Desrochers và đồng nghiệp đề xuất thuật toán dựa trên gánnhãn cho tài nguyên và sử dụng luật Dominace cho những nhãn ứng viên [10][11] – được xemnhư mở rộng của thuật toán Bellman–Ford. Năm 1996, Jaumard đề xuất mô hình quy hoạchđộng cho vấn đề đường đi ngắn nhất ràng buộc tài nguyên hai pha trong đồ thị phi chu trình 497[12]. Năm 2007, Santos và đồng nghiệp đề xuất dùng giải pháp k đường đi ngắn nhất để giảiquyết bài toán đường đi ngắn nhất có ràng buộc[13]. Bài toán đường đi ngắn nhất có nhiều hơnmột ràng buộc được diễn tả như bài toán đường đi ngắn nhất có có tài nguyên ràng buộc –Elementary Shortest Path Problem with Resource Constraints (ESPPRC), Feillet và đồngnghiệp đề xuất mở rộng thuật toán đánh nhãn truyền thống cho phiên bản đường không phảiđường chính (nonelementary) và được thực nghiệm cho vấn đề định hướng xe với TimeWindows [14]. Năm 2013 Gabrel và đồng nghiệp [15] đã đưa ra mô hình mới cho bài toánđường đi ngắn nhất theo đó đưa ra tiêu chí đánh giá cho mô hình mới được gọi là bw-robustnessvà đưa ra mô hình tối ưu tổng quát cho bài toán tìm đường đi ngắn nhất. Tuy nhiên, nhóm củaGabrel chỉ tập trung việc đo tính hiểu quả của của các giải thuật giải quyết bài toán nhưng chưađưa ra mô hình chi tiết, cách xây dựng ràng buộc phức tạp cho bài toán tìm đường đi ngắn nhất.Để giải quyết bài toán đường đi ngắn nhất có ràng buộc đã có nhiều đề xuất thuật toán để giảiquyết nhưng đa phần đều dành riêng cho từng ràng buộc cụ thể. Trong bài báo này trình bàymột cách tiếp cận theo mô hình qui hoạch tuyến tính cụ thể là quy hoạch nguyên cho bài toántìm đường đi ngắn nhất theo đó có thể thêm ràng buộc một cách tổng quát. Phần còn lại, mô hình qui hoạch nguyên cho bài toán đường đi ngắn nhất được trình bàytrong phần II. Ràng buộc cho bài toán đường đi ngắn nhất được trình bày trong phần III. PhầnIV trình bày thực nghiệm. Kết luận được trình bày trong phần V.2. MÔ HÌNH QUI HOẠCH NGUYÊN CHO BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤTPHƯƠNG ...