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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

5
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ột TÓ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ất sẽ 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 đều dà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ắ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. 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ìm nghiệ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ực tế. 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ời gian, 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án nà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ại phá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ồm có 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ông bao 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ứa tấ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ân cấ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ổng quát là bài toán thuộc lớp NP-Hard [8]. Năm 1980, Handler và đồng nghiệp đã đề xuất thuật toá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 Lagrangian ralaxation để 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àng buộc kiểu Knapsack [9]. Năm 1988, Desrochers và đồng nghiệp đề xuất thuật toán dựa trên gán nhãn cho tài nguyên và sử dụng luật Dominace cho những nhãn ứng viên [10][11] – được xem như 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ải quyế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ơn mộ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à đồng nghiệ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 Time Windows [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-robustness và đư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ủa Gabrel 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ải quyế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ày mộ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án tì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ày trong 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ần IV 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ẤT PHƯƠNG PHÁP NGHIÊN CỨU Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Cho trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v' thuộcV sao cho ∑ 𝑓(𝑝) (1) 𝑝∈𝑃 là nhỏ nhất trong tất cả các đường nối từ v tới v' . Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh v và v' . Mô hình hóa bài toán đường đi ngắn nhất dưới dang qui hoạch nguyên như sau: ▪ Giả sử cho đồ thị G(V, E, c) là đồ thị có trọng số không âm, trên mỗi cạnh (i,j) gán một số nguyên không âm c(i, j). Nhãn c(i,j) biểu diễn “chi phí” thực tế qua cạnh này. ▪ Trọng số trên đồ thị của bài toán này sẽ xoay quanh các yếu tố ảnh hưởng như quãng đường, vận tốc tối đa cho phép xe di chuyển, mật độ xe trong các khung giờ trong ngày, số lượng đèn đỏ trên đoạn đường cần di chuyển, … Trong khuôn khổ báo cáo này chúng tôi chỉ quan tâm đến thời gian di chuyển trên đoạn đường là bao nhiều và cần tìm ra đoạn đường có thời gian di chuyển thấp nhất. Do vậy, chúng tôi biểu diễn trọng số thời gian cho cạnh của đồ thị theo công thức sau: 𝑠 𝑖𝑗 𝑐 𝑖𝑗 = 𝛼 𝑖𝑗 (2) 𝑣 𝑖𝑗 trong đó 𝑐 𝑖𝑗 trọng số đại diện cho thời gian xe di chuyển từ i đến j; 𝑠 𝑖𝑗 là quãng đường từ từ đỉnh i đến đỉnh j; 𝑣 𝑖𝑗 là vận tối tối đa cho phép xe di chuyển trên đoạn đường i đến j; 𝛼 𝑖𝑗 ∈ [1; 2] là 498
hệ số đại diện cho đại lượng lưu lượng xe vào các khung giờ trong ngày, vào giờ cao điểm lưu lượng xe nhiều thì 𝛼 càng lớn ngược lại lưu lượng xe ít thì 𝛼 nhỏ. Các khung giờ trong ngày sẽ được chi làm 5 mức độ khác nhau của tình trạng lưu thông xe, với 𝛼 được chọn như sau: 2 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑟ấ𝑡 𝑛ℎ𝑖ề𝑢 𝑥𝑒 1.7 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑛ℎ𝑖ề𝑢 𝑥𝑒 𝛼 𝑖𝑗 = 1.5 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑏ì𝑛ℎ 𝑡ℎườ𝑛𝑔 (3) 1.3 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 í𝑡 𝑥𝑒 { 1 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑟ấ𝑡 í𝑡 𝑥𝑒 Gọi v là đỉnh nguồn, v’ là đỉnh đích. Tìm đường đi ngắn nhất (nếu có) từ đỉnh v tới v’ trong đồ thị G được mô hình hóa như sau: 𝑚𝑖𝑛 ∑ 𝑐 𝑖𝑗 ∗ 𝑥 𝑖𝑗 , (1) 𝑖𝑗 ∈ 𝐸 (4) 1 𝑛ế𝑢 𝑐ạ𝑛ℎ (𝑖, 𝑗) ∈ 𝑃 𝑥 𝑖𝑗 = { 0 𝑛𝑔ượ𝑐 𝑙ạ𝑖 trong đó c(i,j) là trọng số chi phí, xij là biến quyết định nhị phân bằng 1 nếu cạnh (i,j) thuộc đường đi ngắn nhất P và ngược lại bằng 0. Nếu một đỉnh được chọn cho đường đi ngắn nhất thì tổng số cạnh đi vào đỉnh đó bằng tổng số bằng tổng số lượng cạnh đi ra khỏi đỉnh đó và bằng 1. Gọi m là đỉnh trên đường đi từ v đến v’, K’ là tập đỉnh có cạnh đi tới m và T’ là tập đỉnh có cạnh đi từ m tới. ∑ 𝑥 𝑘𝑚 = ∑ 𝑥 𝑚𝑡 =1 (5) 𝑘 ∈𝐾′ 𝑡 ∈𝑇 ′ Đặt v là đỉnh nguồn, K là tập các đỉnh kề với đỉnh nguồn có nghĩa là từ đỉnh nguồn sẽ có cạnh nối tới các đỉnh trong tập K. Trong tập các cạnh từ đỉnh nguồn đến các đỉnh kề trong K – gọi là cạnh ra khỏi đỉnh nguồn sẽ có một cạnh được chọn, nên ta có: ∑ 𝑥 𝑖𝑗 − 1 = 0 𝑣ớ𝑖 𝑖 ≡ 𝑣 𝑣à 𝑗 ∈ 𝐾 (6) 𝑗∈ 𝐾 Đặt v’ là đỉnh đích, T là tập các đỉnh kề với đỉnh đích có nghĩa là từ đỉnh đích có cạnh nối tới các đỉnh trong tập T. Trong tập các cạnh từ đỉnh trong tập T đến đỉnh đích – gọi là cạnh vào đỉnh đích sẽ có 1 cạnh được chọn, nên ta có: 1 − ∑ 𝑥 𝑖𝑗 = 0 𝑣ớ𝑖 𝑗 ≡ 𝑣 ′ 𝑣à 𝑖 ∈ 𝑇 (4) (7) 𝑖∈ 𝑇 Mô hình Bài toàn đường đi ngắn nhất cơ bản được áp dụng công thức (1) đến (4), thêm vào đó để giải quyết bài toán đường đi ngắn nhất có ràng buộc chúng ta cần mô hình hóa các ràng buộc đi kèm. Chúng tôi chia các ràng buộc thành các dạng: ràng buộc trên cạnh của đồ thị, ràng buộc trên đỉnh của đồ thị, ràng buộc đường trên đồ thị. Bài toán tìm đường đi ngắn nhất từ v đến v' trong đồ thị G nhưng buộc đi qua/không đi qua một hay một số cạnh cho trước. Đối với loại ràng buộc này ta cần thiết lập biến quyết định (1’) 1 𝑛ế𝑢 𝑐ạ𝑛ℎ (𝑖, 𝑗) ∈ 𝑃 𝑥 𝑖𝑗 = { (8) 0 𝑛𝑔ượ𝑐 𝑙ạ𝑖 499
Bài toán tìm đường đi ngắn nhất từ v đến v' trong đồ thị G nhưng buộc đi qua/không đi qua một hay một số đỉnh cho trước. Đối với loại ràng buộc này ta áp dụng theo công thức (2) 1 𝑛ế𝑢 đỉ𝑛ℎ 𝑚 ∈ 𝑃 ∑ 𝑥 𝑘𝑚 = ∑ 𝑥 𝑚𝑡 = { (9) 0 𝑛𝑔ượ𝑐 𝑙ạ𝑖 𝑘 ∈𝐾′ 𝑡 ∈𝑇 ′ Theo [4] trên đường đi ngắn nhất từ v đến v’ ràng buộc đường cấm có hai trường hợp: • Cấm tất cả các đường từ đỉnh y đến đỉnh k, hay nói cách khác trên đường đi ngắn nhất từ v đến v’ sẽ không đi qua hai đỉnh y và k. Do đó, chỉ cần áp dụng công thức (6) cho hai đỉnh y và k để mô hình ràng buộc này. ∑ 𝑥 𝑘𝑚 = ∑ 𝑥 𝑚𝑡 =0 (10) 𝑘 ∈𝐾′ 𝑡 ∈𝑇 ′ Với m là đỉnh y và đỉnh k. • Trường hợp từ k đến y có nhiều đường đi nhưng chỉ cấm một/một vài đường đi từ đỉnh k đến đỉnh y. Hay nói cách khác tổng các cạnh trên đường cấm nhỏ hơn tổng số đỉnh thuộc đường cấm trừ 1, mô hình ràng buộc như sau: ∑ 𝑥 𝑖𝑗 < 𝑆 − 1 (11) 𝑖𝑗 ∈ 𝐸 • Đồ thị có đường đi từ đỉnh k đến đỉnh y thì tổng số cạnh được chọn cho đường đi lớn hơn hoặc bằng tổng số đỉnh của đường đi trừ một, được mô hình như sau: ∑ 𝑥 𝑖𝑗 ≥ 𝑆 − 1 (12) 𝑖𝑗 ∈ 𝐸 trong đó S là tổng số đỉnh thuộc đường đi P. 3. THỰC NGHIỆM Trong phần này, chúng tôi trình bày các thực nghiệm xung quanh các ràng buộc được trình bày trong phần III. Bên cạnh đó, để giải mô hình qui hoạch nguyên chúng tôi sử dụng công cụ LP Solve IDE để tìm nghiệm cho bài toán. Thực tế áp dụng, chỉ cần định nghĩa mô hình của bài toán và áp dụng công cụ Solver để tìm nghiệm sẽ giúp người sử dụng không cần lập trình cũng có thể giải được bài toán. Cho đồ thị như hình sau: Hình 1. Đồ thị thực nghiệm. 500
Thực nghiệm 1 (TN1): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8. Thực nghiệm 2 (TN2): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không qua nút 5. Thực nghiệm 3 (TN3): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 phải qua nút 4. Thực nghiệm 4 (TN4): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và nếu đi qua nút 7 phải qua nút 3. Thực nghiệm 5 (TN5): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi qua tất cả các đường từ 3 tới 7. Thực nghiệm 6 (TN6): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi đường từ 3 tới 5 tới 7. Thực nghiệm 7 (TN7): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và phải đi qua đường từ 3 tới 5 tới 7. Biến quyết định: xij: xác định có hay không một liên kết từ nút i đến nút j. Hàm mục tiêu: 100x12 + 151x13 + 150x26 + 75x25 + 42x35 + 67x34 + 22x45 + 11x57 + 25x67 + 71x68 + 52x78 → Min (cực tiểu chi phí đường đi) Các ràng buộc cho đồ thị: xij  [0,1] x12 + x13 − 1 = 0 x25 + x26 − x12 = 0 x34 + x35 − x13 = 0 x45 + x47 − x34 = 0 x57 − x25 − x35 − x45 = 0 x67 + x68 − x26 = 0 x78 − x47 − x57 − x67 = 0 { 1 − x68 − x78 = 0 Bên cạnh đó, để thõa ràng buộc của các thực nghiệm 2, 3, 4, 5, 6, 7 thêm ràng buộc sau : • Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không qua nút 5 : x25 = x35 = x45 = x57 = 0 • Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 phải qua nút 4: x45 + x47 = 1 • Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và nếu đi qua nút 7 phải qua nút 3. x25 + x26 - x78 ≥ 0 • Ràng buộc không đi qua tất cả các đường từ đỉnh 3 tới đỉnh 7 x13=x35=x34=x57=x47=x78=0 • Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi đường từ 3 tới 5 tới 7 x35+x57 < 2 • Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và phải đi qua đường từ 3 tới 5 tới 7. x35+x57 >= 2 501
Giải bài toán trên bằng phần mềm LP Solve IDE thu được kết quả như sau : Biến TN1 TN2 TN3 TN4 TN5 TN6 TN7 x12 1 0 0 0 1 1 0 x13 0 1 1 1 0 0 1 x25 1 0 0 0 0 1 0 x26 0 0 0 0 1 0 0 x34 0 1 1 0 0 0 0 x35 0 0 0 1 0 0 1 x45 0 0 0 0 0 0 0 x47 0 1 1 0 0 0 0 x57 1 0 0 1 0 1 1 x67 0 0 0 0 0 0 0 x68 0 0 0 0 1 0 0 x78 1 1 1 1 0 1 1 Chi phí 238 270 270 256 321 238 256 Theo Bảng 1, kết quả được diễn giải như sau: • Thực nghiệm 1: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 là đường từ 1 ➔ 2 ➔ 5 ➔ 7 ➔ 8 với tổng chi phí là 238. • Thực nghiệm 2: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không qua nút 5 là đường từ 1➔ 3 ➔ 4 ➔ 7 ➔ 8 với tổng chi phí 270. • Thực nghiệm 3: tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 phải qua nút 4 là đường từ 1➔ 3 ➔ 4 ➔ 7 ➔ 8 với tổng chi phí 270. • Thực nghiệm 4: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và nếu đi qua nút 7 phải qua nút 3 là đường 1 ➔ 3 ➔ 5 ➔ 7 ➔ 8 với tổng chi phí 256. • Thực nghiệm 5: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi qua tất cả các đường từ 3 tới 7 là đường 1➔2➔6➔8 với tổng chi phí là 321. • Thực nghiệm 6 (TN6): đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi đường từ 3 tới 5 tới 7 là đường 1➔ 2➔5➔7➔8 với tổng chi phí là 238. • Thực nghiệm 7 (TN7): đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và phải đi qua đường từ 3 tới 5 tới 7 là đường 1 ➔ 3 ➔ 5 ➔ 7 ➔ 8 với tổng chi phí 256. 4. KẾT LUẬN Bài báo này đã đưa ra mô hình quy hoạch tuyến tính cho bài toán đường đi ngắn nhất có ràng buộc – cSPP, có thể thêm ràng buộc một cách linh hoạt, tùy biến. Bài toán đường đi ngắn nhất có ràng buộc thuộc lớp NP-Hard nên độ phức tạp là đa thức do đó việc mô hình hóa bài toán bằng quy hoạch tuyến tính sẽ không giúp giảm độ phức tạp tính toán của thuật toán tìm nghiệm nhưng với các công cụ nguồn mở có sẵn sẽ giúp tìm nghiệm tối ưu dễ dàng. Điều này sẽ hiệu quả khi bài toán có số lượng biến khoảng vài nghìn và có thể giúp cho tổ chức cần giải quyết nhanh bài toán với số biến không nhiều. Hướng nghiên cứu sắp tới, chúng tôi thực nghiệm trên bài toán có số biến lớn, lượng đỉnh lớn, ràng buộc nhiều. 502
TÀI LIỆU THAM KHẢO 1. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische mathematik 1, 269- 271 (1959) 2. Fu, L., Sun, D., Rilett, L.R.: Heuristic shortest path algorithms for transportation applications: state of the art. Computers & Operations Research 33, 3324-3343 (2006) 3. Deo, N., Pang, C.Y.: Shortest‐path algorithms: Taxonomy and annotation. Networks 14, 275-323 (1984) 4. Villeneuve, D., Desaulniers, G.: The shortest path problem with forbidden paths. European Journal of Operational Research 165, 97-107 (2005) 5. Di Puglia Pugliese, L., Guerriero, F.: Dynamic programming approaches to solve the shortest path problem with forbidden paths. Optimization Methods and Software 28, 221-255 (2013) 6. Current, J., Pirkul, H., Rolland, E.: Efficient algorithms for solving the shortest covering path problem. Transportation Science 28, 317-327 (1994) 7. Current, J., ReVelle, C., Cohon, J.: The shortest covering path problem-an application of locational constraints to network design. Journal of Regional Science 24, 161-183 (1984) 8. Michael, R.G., David, S.J.: Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co., San Fr (1979) 9. Handler, G.Y., Zang, I.: A dual algorithm for the constrained shortest path problem. Networks 10, 293-309 (1980) 10. Desrochers, M., décisions, É.d.h.é.c.G.d.é.e.d.r.e.a.d.: An algorithm for the shortest path problem with resource constraints. Montréal: École des hautes études commerciales (1988) 11. Desrochers, M., Soumis, F.: A generalized permanent labeling algorithm for the shortest-path problem with time windows. Infor 26, 191-212 (1988) 12. Jaumard, B., Semet, F., Vovor, T.: A two-phase resource constrained shortest path algorithm for acyclic graphs. Cahiers du GERAD (1996) 13. Santos, L., Coutinho-Rodrigues, J., Current, J.R.: An improved solution algorithm for the constrained shortest path problem. Transportation Research Part B: Methodological 41, 756-771 (2007) 14. Feillet, D., Dejax, P., Gendreau, M., Gueguen, C.: An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44, 216-229 (2004) 15. Gabrel, V., Murat, C., Wu, L.: New models for the robust shortest path problem: complexity, resolution and generalization. Annals of Operations Research 207, 97-120 (2013) 503