一種最小加權延遲問題的整數規劃算法

黃光泉 丁柏圓

摘要：在最小延遲問題的基礎上，對最小加權延遲問題（MWLP）進行了簡要介紹，對已有的算法進行了分析，對使用整數規劃算法解決近似問題的方法進行了研究。在此基礎上，提出了一種解決最小加權延遲問題的整數規劃算法，詳細介紹了該算法的數學模型建模和實現。通過隨機生成的實驗數據對該算法進行了驗證，結果表明，該算法在確保了較高的準確度的前提下，時間效率上相較窮舉法得到了較大的提升，在實際場景中具有應用價值。

關鍵詞：最小延遲問題；最小加權延遲問題；整數規劃

中圖分類號：TP312文獻標志碼：A文章編號：1008-1739（2020）22-71-3

0引言

指揮調度是部隊演習和實戰過程的關鍵點之一，最小加權延遲問題（MWLP）在導彈訓練調度等場景中有著很大的應用前景。作為一個復雜的非確定性問題，由Kousoupias[1]首次提出。此后，吳邦一[2]提出了一種動態規劃算法以解決MWLP問題，但是該方法只適用于部分特殊的場景。Wei等[3]嘗試使用啟發式算法解決MWLP問題，并對比分析了5種常見啟發式算法的效果和效率。Miliotis[4]嘗試使用整數規劃算法解決與MWLP問題近似的旅行商問題（TSP），Gozde等[5]提出了一種新的整數規劃方法解決TSP問題，Francisco等[6]更進一步將整數規劃應用于最小延遲問題（MLP），而MLP問題可被視為各點權值相等的MWLP問題。這些研究通過各種方法解決MWLP問題及相關問題，給后續研究提供了借鑒和啟發。本文在Francisco等[6]工作的基礎上，對其提出的數學模型進行了擴展，從而可以直接使用整數規劃解決MWLP問題，并對該模型和算法進行測試，證實了其在準確度和時間效率上的使用價值。

1 MWLP問題定義

2整數規劃數學模型

一般的線性規劃問題中，最優解可能是整數，也可能不是，但在實際應用中，常常要求變量必須是整數。比如，購買機器的臺數、攜帶物品的件數、車輛調度的車輛數等，這類特殊的線性規劃即是整數規劃。許多組合優化、圖論和計算邏輯問題都可以歸結為整數規劃問題，而MWLP就屬于圖論中的問題。Francisco等[6]提出了使用整數規劃來解決MLP問題，受此啟發，提出了一種解決MWLP問題的整數規劃算法。

2.1 MWLP問題多層網絡表示

MWLP問題可以使用多層網絡表示，如圖2所示，共有+1個節點，+1個層次，層次代表路徑上的先后順序，起點單獨放在第0層，是確定的。對于MWLP問題，優化目標就是從除起點之外的其他層各選一個城市，使得加權延遲之和最小。同時需要保證每層只有一個城市，每個城市只出現在一層。

2.2數學模型

該模型在Francisco等的工作[6]中的數學模型1的基礎上進行了拓展，如式（2）所示，定義代表從頂點到頂點的時間代價，其中，是在頂點處的服務時間，是從頂點到頂點的過程中所用的時間，為頂點的權重，

3實驗和分析

3.1實驗設置

為了驗證上面所提出的整數規劃算法是否可行，本節使用隨機生成的數據對該算法進行測試。為了盡可能模擬實際生活中可能遇到的場景，實驗數據已經被限定需要滿足三角不等式，或者可以認為所有的數據都對應平面上不重復的實際點。各頂點的權值從標準正態分布中隨機采樣獲取，并且滿足每個頂點的權值大于0且小于1。

3.2結果和分析

實驗結果如表1所示。從準確度的角度分析，因為窮舉法是從所有可能的路徑中挑選一條最優的路徑，所以其準確度均為1.0，而整數規劃算法雖然不能達到最優，但是其準確度接近0.85，和窮舉法的結果很接近。并且可以看出，頂點規模對于準確度沒有明顯的影響，這對于實際應用有著重要的參考意義。

使用窮舉法時，頂點規模從7～9變化的過程中，所用時間并沒有呈指數上升，應該是由于頂點規模太小，導致算法運行所消耗的時間同程序自身運行時所消耗的固有時間相比很小，從而導致頂點規模變化對所用時間影響有限。

從所用時間的角度分析，在頂點規模≤9的情況下，窮舉法和整數規劃算法沒有太大差別，這時可以考慮使用窮舉法以得到最優解。但是在規模>9時，如圖3所示，窮舉法所用時間會呈指數上升，而整數規劃算法則大體呈線性上升的趨勢，此時可以考慮使用整數規劃算法在可承受的時間內得到一個較優解。

4結束語

提出了一個整數規劃算法用來解決MWLP問題，使用限定條件的模擬生成的數據進行了實驗，證明了整數規劃算法解決MWLP問題是可行的，在較大規模的問題上，該算法可以在得到一個較高精確度的可行解的前提下，大幅減少所用時間。該算法具有廣泛的實際應用價值，未來可應用于導彈訓練調度等具體的指揮訓練場景，從而節省資源、提高效率。

參考文獻

[1] KOUTSOUPIAS E，PAPADIMITRIOU C，YANNAKAKIS M.Searching a Fixed Graph[J].Lecture Notes in Computer Science，1996：280-289.

[2] WU B Y. Polynomial Time Algorithms for Some Minimum Latency Problems[J].Information Processing Letters，2000，75（5）：225-229.

[3] WEI Z Q，H.MACGREGER M. Heuristic Approaches for Minimum Weighted Latency Problem[C]/International Conference on Machine.Paris：IEEE，2017：552-556.

[4] MILIOTIS P.Integer Programming Approaches to the Travelling Salesman Problem[J].Mathematical Programming， 1976，10（1）：367-378.

[5] ONDER G， KARA I， DERYA T.New Integer Programming Formulation for Multiple Traveling Repairmen Problem[J]. Transportations Research Procedia，2017，22：355-361.

[6] FRANCISCO A B，ADA A，IRMA G.Two Improved Formulations for the Minimum Latency Problem[J].Applied Mathematical Modelling，2013，37（4）：2257-2266.