戰(zhàn)時維修力量最大覆蓋選址問題

李 明，曲長征， 張 波，高 飛 （軍械工程學院，河北 石家莊 050003）

0 引 言

選址問題在生產(chǎn)、生活、物流、軍事中都有非常廣泛的應用，因而，從上世紀六七十年代起，該問題就已開始被較系統(tǒng)地研究[1]。Brandeau等在對選址問題的綜述中將選址問題歸納為50多類，并指出了各類問題相互之間的關(guān)系[2]。選址研究中的一些典型問題，如Weber問題、p－中值問題、覆蓋問題、p－中心問題、多目標選址、競爭選址、不受歡迎的設施選址、選址—分配、選址—路線等，都是引起廣泛關(guān)注和深入研究的熱點課題[3]。覆蓋問題主要有兩類基本模型：集合覆蓋模型 （the Set Covering Location Problem，SCLP）和最大覆蓋模型 （the Maximal Covering Location Problem，MCLP）。最初的MCLP問題是由Church和ReVelle提出的，即先固定設施數(shù)目，再確定它們的位置使得其覆蓋盡可能多的需求點或需求量[4]。維修力量的配置包括維修機構(gòu)的配置和維修人員的配備。維修機構(gòu)配置位置的合理與否直接關(guān)系著維修系統(tǒng)能否在可用的時間范圍內(nèi)為作戰(zhàn)單位提供維修服務、所提供服務的效率高低、以及設施建設和運行成本等一系列問題，直接影響著系統(tǒng)對維修需求的反應能力[5]。本文嘗試用最大覆蓋選址模型解決該問題。

由于任務的緊急程度、作戰(zhàn)要求各不相同，各個作戰(zhàn)區(qū)域內(nèi)作戰(zhàn)單位對接受維修服務的優(yōu)先程度也各不一樣，而傳統(tǒng)的MCLP模型并沒有充分考慮這一因素對選址的影響。本文主要針對維修機構(gòu)的選址問題進行研究，建立了以作戰(zhàn)區(qū)域內(nèi)所有需求點優(yōu)先度和值最大為目標的有限服務臺優(yōu)化模型。

該模型是在傳統(tǒng)網(wǎng)絡覆蓋問題的基礎(chǔ)上，借鑒 “部分覆蓋”[6]的思想，建立的一種適用于軍隊戰(zhàn)時的覆蓋問題模型，擴展了覆蓋問題的應用范圍。

1 模型的建立

1.1 優(yōu)先度函數(shù)

高技術(shù)條件下作戰(zhàn)，裝備保障必須堅持 “一切為了前線，一切為了勝利”的總方針，而 “統(tǒng)籌兼顧，保障重點”是戰(zhàn)時裝備保障必須遵循的基本原則之一。裝備保障的重點通常是指，影響合成指揮員決定實現(xiàn)，與戰(zhàn)斗全局勝負相關(guān)的戰(zhàn)斗行動和單位[7]。

設 ci、 ri分別是第 i（ i=1,2,…,n ）個需求點的優(yōu)先權(quán)和需求量，lij為需求點i到備選服務臺j（ j=1,2,…,m ）的最短距離， 同時引入相對距離的概念，記為我們將需求點的優(yōu)先權(quán)從高到低依次劃分為一、二、三三個等級，其對應的ci則分別被賦以5、3、1三個值。ki為需求點i的時間敏感性參數(shù)，用以表示需求點i對保障時間的敏感程度，0＜ki≤1。f（ci, ri,lij）為第j個備選服務臺對第i個需求點的優(yōu)先度函數(shù)。

基于以上各因子，第j個備選服務臺對第i 個需求點的優(yōu)先度函數(shù)可表示為：

1.2 基于需求點優(yōu)先度的最大覆蓋模型

其中優(yōu)先度函數(shù)f（ ci, ri,lij）可由式 （1）給出；Xj取值為1時表示在候選點j處設立服務臺，否則取值為0；Yij取值為1時表示需求點i的顧客接受設在j處服務臺的服務，否則取值為0。

該模型的目標函數(shù)式 （2）表示是總的優(yōu)先度最大；約束式 （3）是保證每個需求點只被一個服務臺 （對該需求點優(yōu)先度最大的服務臺）服務；約束式 （4）是保證建立的服務臺數(shù)量為p個；約束式 （5）是根據(jù)某備選址點是否設立服務臺而對需求點優(yōu)先度的限制，如果某服務臺沒有設立，則所有接受該服務臺服務的需求點的優(yōu)先度都將變成0；約束式 （6）、 （7）是對所有決策變量的0、1約束。

在上述模型中，還有一個假設的前提，即所有的需求點都被覆蓋，只不過被覆蓋的程度按需求點的優(yōu)先度來區(qū)分。

2 算 法

最大覆蓋選址問題是NP困難問題，目前關(guān)于解決此類問題的算法已經(jīng)很多，常用的有貪婪算法、禁忌搜索算法、模擬退火算法、拉格朗日松弛算法、蟻群算法等。本文嘗試用拉格朗日松弛算法解決該問題。拉格朗日算法的基本原理是，將造成問題難的約束吸收到目標函數(shù)中去，并使得目標函數(shù)仍保持線性，通過對松弛過程的控制，可以得到問題的最優(yōu)解或知道所得到的解距離最優(yōu)解的最大差距是多少[8-9]。

對于P1問題，首先將約束式（3）松弛到目標函數(shù)（2）中去，并規(guī)定對應于約束式（3）的拉格朗日乘子λi≥0 i∈（）I。由此得到本文模型的拉格朗日松弛問題 （記為P2）

式 （8）中λi為拉格朗日乘子，對于固定的λi，式 （8）中后半部即為常量，因此，為使問題P2的目標函數(shù)式 （8）最大化，我們將 （8）最大化，我們將Yij進一步定義為：

對于確定的拉格朗日乘子來說，Vj的值也是確定的，因此可以通過尋找p個最大的Vj的辦法求得問題P3的最優(yōu)解，并將相應的Xj設為1，其余的Xj設為0，再由式 （14）求出Yij的值，進而得到問題P2的最優(yōu)解，記為ZU。

由于沒有考慮到原模型中約束式 （3）的限制，此時問題P2的最優(yōu)解并不一定是原問題的解。但是就任一需求點i而言，可以在P3最優(yōu)解確定的選址點中找到一個使其優(yōu)先度最大的服務臺，得出原問題的一組可行解。該可行解為原問題求解提供了目標函數(shù)的下限ZL：

通過調(diào)整拉格朗日乘子，可以使問題目標函數(shù)的上下限不斷逼近求解該問題。本文利用次梯度算法來逼近最優(yōu)解[8]。若用k表示迭代次數(shù)，則第k次迭代的最優(yōu)值上下限分別表示為和，相應的拉格朗日乘子為，拉格朗日松弛問題P2的最優(yōu)解為和用tk表示第k步的步長，ZLB為第k次迭代為止最大的下限值，αk是第k次迭代步長參數(shù)（0＜αk≤2 ）。

再設ZUB為第k次迭代為止最小的上限值。則基于拉格朗日松弛算法的步驟如下：

第一步： 初始化模型參數(shù)， 令ZLB=－∞，ZUB=+∞，k=0，=0（?i∈I ）， αk=2；

第四步：更新原問題的上下限。若

第七步：更新拉格朗日乘子，轉(zhuǎn)到第二步。

3 結(jié) 論

在戰(zhàn)時，保障系統(tǒng)的快速反應能力對戰(zhàn)爭的勝負起著至關(guān)重要的作用，而保障設施的選址對保障系統(tǒng)的快速反應能力具有根本性的影響。本文以需求點優(yōu)先度函數(shù)作為目標函數(shù)，并基于拉格朗日松弛算法給出了該模型的啟發(fā)式求解方法。該模型可用于戰(zhàn)時定點維修機構(gòu)的選址決策。保障設施選址問題還有很多方面值得進一步研究，如隨機需求的選址問題、多階段任務條件下的動態(tài)設施選址問題等，將是以后研究的重點。

第五步：檢驗步長更新條件，更新步長參數(shù)αk。若上限ZUB在連續(xù)4次迭代都沒有變化，則令αk=αk/2；

第六步：檢驗迭代結(jié)束條件，如果以下條件中任何一個滿足，終止迭代求解過程：

[1] Marianov V,Re Velle C.Siting emergency services.In:Drezner Z,editor.Facility location[M].Berlin:Springer,1995:199－223.

[2] Brandeau ML,Chui SS.An overview of representative problems in location research[J].Management Science,1989,35(6):645－674.

[3] 卜月華.圖論及其應用[M].南京：東南大學出版社，2000.

[4] Church RL,Re Velle C.The maximal covering location problem[J].Papers of Regional Science Association,1974,32:101－118.

[5] 龔延成.戰(zhàn)時軍事物流系統(tǒng)決策理論與方法研究[D].西安：長安大學 （博士學位論文），2004.

[6] Berman O.The p maximal cover－p partial center problem on the networks[J].European Journal of Operation Research,1994,72:432－442.

[7] 孔令茂,等.戰(zhàn)術(shù)裝備保障學[M].北京：國防大學出版社，2002.

[8] 刑文訓，謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學出版社，2005.

[9] 王文峰.裝備保障網(wǎng)絡優(yōu)化設計問題研究[D].北京：國防科技大學 （博士學位論文），2008.