黃光泉 丁柏圓

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

關(guān)鍵詞：最小延遲問題；最小加權(quán)延遲問題；整數(shù)規(guī)劃

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

0引言

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

1 MWLP問題定義

2整數(shù)規(guī)劃數(shù)學(xué)模型

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

2.1 MWLP問題多層網(wǎng)絡(luò)表示

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

2.2數(shù)學(xué)模型

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

3實驗和分析

3.1實驗設(shè)置

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

3.2結(jié)果和分析

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

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

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

4結(jié)束語

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

參考文獻

[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.