汪琳，何成銘

（陸軍裝甲兵學(xué)院 裝備保障與再制造系，北京 100072）

0 引 言

陸軍平時器材使用通常由現(xiàn)有器材倉庫進行保障，而戰(zhàn)時器材保障不同于平時保障的固定性。戰(zhàn)時，陸軍器材保障是陸軍部隊作戰(zhàn)的重要支撐，對整個戰(zhàn)爭進程有著重要影響。所以，器材倉庫的選址問題就顯得尤為重要。臨時應(yīng)急器材儲備庫的位置選得好，不僅可以降低運輸成本，更重要的是在戰(zhàn)時可以充分發(fā)揮倉庫物資的時效性，使器材倉庫的戰(zhàn)術(shù)作用發(fā)揮更加明顯。

由于野戰(zhàn)地點分布隨機，與現(xiàn)有器材倉庫的距離也并不固定，也就是說，戰(zhàn)時僅靠現(xiàn)有的器材倉庫無法滿足器材保障的需求，必須開設(shè)臨時器材倉庫以實現(xiàn)對戰(zhàn)時某一區(qū)域的戰(zhàn)場器材需求進行及時、準(zhǔn)確、不間斷的保障，確保戰(zhàn)時器材供應(yīng)保障高效準(zhǔn)確、及時穩(wěn)定。因此，在戰(zhàn)時環(huán)境下，臨時器材倉庫選址問題就很有必要進行研究解決。

過去的研究中，關(guān)于倉庫選址問題的解決方法不多。張帥等人依據(jù)微分算法選擇庫區(qū)，引入層次分析法和模糊綜合評判建立選址指標(biāo)體系和建立野戰(zhàn)器材倉庫選址模型，對倉庫位置進行優(yōu)化配置。羅耀波等人利用改進的遺傳算法解決了帶退貨和軟時間窗的地方物流多倉庫路徑-選址問題。苑德春等人運用四元評價（DFGH）理論分析了影響交通戰(zhàn)備器材儲備倉庫選址的主要因素，并建立了相應(yīng)模型。嚴(yán)駿等人提出了一種維修器材倉庫選址模型的魯棒優(yōu)化方法，對定點器材倉庫選址的穩(wěn)定性進行了論證。

在對倉庫選址進行評價方面，彭飛等人通過建立評價體系，進一步利用模糊綜合評價法研究了倉庫選址完成之后的評價問題。邵帥等人還在評價過程中引入了正態(tài)云的概念，對于解決倉庫選址評估問題中的隨機性和模糊性問題發(fā)揮了一定的作用。辛昱等人提出基于AHP和模糊物元分析法（FMEA）對物流中心選址方案進行優(yōu)度評價。

綜合上述研究，不難發(fā)現(xiàn)過去的研究大多數(shù)局限于簡單的定量方法，其中模糊綜合評價法和AHP的使用尤為頻繁，且對于部隊?wèi)?zhàn)時倉庫選址的研究少之又少。本文在對遺傳算法進行改進的基礎(chǔ)上，對戰(zhàn)時器材倉庫選址的定量優(yōu)化進行了有益探索。

1 陸軍戰(zhàn)時裝備器材選址問題

1.1 問題描述

本文通過設(shè)定假定條件，在倉庫選址問題上運用改進遺傳算法在待選戰(zhàn)時倉庫地址中選取最優(yōu)點建立臨時器材倉庫。

器材倉庫選址問題可描述為：已知個作戰(zhàn)點（，，…，B）的地理位置（，），（，），…，（x，y）和個（，，…，W）可供選擇建立臨時倉庫的待選點位置（，），（，），…，（a，b），運輸車從某一倉庫待選點出發(fā)，將所有作戰(zhàn)點遍歷一次，并回到原待選點，如何選點能夠使得所走路徑最短。

為了便于研究，現(xiàn)做出如下假設(shè)：

（1）出于戰(zhàn)時器材倉庫的臨時性，單一倉庫儲存的器材種類可能不能滿足所有戰(zhàn)場需求，需要至少建立2個或以上的臨時器材倉庫，本文假設(shè)從5個待選地點中選擇2個建立倉庫即可滿足需求；且為保障安全性，5個待選位置均處于戰(zhàn)場后方，最終選取的2個器材倉庫必須保持一定距離；

（2）凡是某一器材倉庫中存在某種類型的器材，則該器材必然能滿足所有戰(zhàn)場的某次器材需求；

（3）在選址的條件考慮中，器材通過陸路運輸，僅考慮路途的遠近問題，認(rèn)為各待選點的自然地理條件均無大差別，不考慮選址點的自然環(huán)境；

（4）由于戰(zhàn)時環(huán)境多變，無法隨時保障各個戰(zhàn)場與臨時器材倉庫之間、各器材倉庫互相之間信息通信及時、順暢。因此，假設(shè)每次器材運輸車出發(fā)前往各作戰(zhàn)點時，所承載的器材數(shù)必然能夠滿足所有作戰(zhàn)點的需求，且器材運輸車每次出發(fā)必經(jīng)過所有作戰(zhàn)點。

1.2 建立模型

將一個倉庫待選點和所有作戰(zhàn)點記為頂點集，各頂點間的邊集記為，則和組成圖=(,)。各頂點間的距離(V,V)已知，設(shè)：

其中f表示遍歷一次的總路徑，(V,V)表示從第個作戰(zhàn)點到達第+1個作戰(zhàn)點的距離，表示臨時倉庫。式（1）、式（2）表示對每個點而言，有且僅有一條邊進和一條邊出；式（3）則保證了沒有任何子回路解的產(chǎn)生。

2 利用改進遺傳算法求解戰(zhàn)時倉庫選址問題

2.1 遺傳算法

遺傳算法的基本思想是根據(jù)問題的目標(biāo)函數(shù)構(gòu)造一個適值函數(shù)，對一個由多個解（每個解對應(yīng)一個染色體）構(gòu)成的種群進行評估、選擇、遺傳運算，經(jīng)多代繁殖，獲得適應(yīng)值最好的個體作為問題的最優(yōu)解。其通常包含“產(chǎn)生一個初始種群”“根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適值函數(shù)”“根據(jù)適應(yīng)值的好壞不斷選擇和繁殖”以及“若干代后得到適應(yīng)值最好的個體為最優(yōu)解”這四個大步驟。

2.2 求解思路和流程

本文中求解器材倉庫選址最優(yōu)方案的總體思路是，在計算過程中，針對每一個待選址點，將其等同于各個作戰(zhàn)點，相當(dāng)于從原來的個點轉(zhuǎn)為從+1個點中去尋找最優(yōu)路線，從而將問題簡化為多個TSP問題。利用遺傳算法求解出最優(yōu)路徑，以此作為從該待選址出發(fā)，運輸車走遍所有作戰(zhàn)點，并返回原待選址點的最短路徑；將每個待選址點都求出最短路徑后，對比選出最優(yōu)者和次優(yōu)者作為最終器材倉庫的選址位置。圖1為算法流程圖。

圖1 算法流程圖

算法基本步驟如下：

（1）隨機生成個倉庫待選址點；

（2）生成初始解種群：利用initPop()函數(shù)生成隨機初始種群；

（3）利用適應(yīng)度函數(shù)fitness()計算種群中每個染色體的適應(yīng)度值，并按適應(yīng)度值進行排序，計算每個染色體的累計概率；

（4）根據(jù)累計概率選擇染色體進入新種群；

（5/6）分別按照交叉、變異概率，在新種群中隨機選擇兩個解，進行相應(yīng)操作；并決定是否將交叉、變異產(chǎn)生的新染色體替換入新種群；

（7）在新群體中選擇適應(yīng)度值最低的解進行進化逆轉(zhuǎn)，并決定是否將逆轉(zhuǎn)產(chǎn)生的新染色體替換入新種群；

（8）檢驗是否達到終止條件，若未達到，則轉(zhuǎn)步驟3；否則，得出最優(yōu)解，并從不同待選址點所對應(yīng)的數(shù)個最優(yōu)解中選出最優(yōu)和次優(yōu)所對應(yīng)的待選址點作為最終的選址點。

2.3 算法詳細(xì)設(shè)計

本文編碼方式為順序編碼，即用1到的自然數(shù)來編碼，其中“0”表示臨時器材倉庫的位置；1到則表示可能發(fā)生戰(zhàn)爭的作戰(zhàn)地點。圖2表示了倉庫待選點與作戰(zhàn)點總數(shù)的染色體編碼的一種情況示例。

圖2 染色體編碼示意圖

2.3.2 種群初始化

在完成染色體編碼之后，必須產(chǎn)生一個初始種群作為起始解。本文選擇從含有120個隨機個體的群體中尋找最優(yōu)解進入初始種群，組成含80個染色體的初始解空間。

2.3.3 適應(yīng)度函數(shù)

將適應(yīng)度函數(shù)設(shè)置為自“倉庫”出發(fā)，逐一、無重復(fù)經(jīng)過所有“作戰(zhàn)點”，再回到“倉庫”的總距離的倒數(shù)，即：

其中D表示從“作戰(zhàn)點”k到k的距離，表示“倉庫點”。優(yōu)化的目標(biāo)就是選擇適應(yīng)度函數(shù)值盡可能大的染色體，適應(yīng)值越大的染色體越優(yōu)質(zhì)，反之越劣質(zhì)。給出了染色體適應(yīng)值計算的偽代碼為：

2.3.4 選擇策略

其次，一個場景內(nèi)，需要各式各樣，年代和狀況各有不同的建筑，這對于保證區(qū)域的地價水平有重要作用。區(qū)域內(nèi)需要有大型企業(yè)對產(chǎn)業(yè)起到引領(lǐng)作用，因此需要高端商業(yè)區(qū)域；同時區(qū)域也需要考慮小型企業(yè)、個人工作室的需求，因此需要相對老舊的房屋場所。同樣多樣化的房屋可以保證地租水平的穩(wěn)定，減少居民必要支出，釋放消費潛力。在許多對文化創(chuàng)意產(chǎn)業(yè)的研究中都發(fā)現(xiàn)，地租水平是影響文化創(chuàng)意產(chǎn)業(yè)發(fā)展的重要因素，差異化的地租，對建立多樣化人群的社交網(wǎng)絡(luò)有重要影響。

對于染色體，設(shè)其適應(yīng)值為F，種群規(guī)模為NP，則該染色體的選擇概率P可表示為

2.3.5 改進遺傳算子

對于交叉算子，創(chuàng)新性的提出了同基因交換方式進行交叉。對于兩個選定的染色體和，隨機選取兩個切點和（＞0，＜），逐個比較兩切點之間的子串，進行同基因交換。以為例，若其子串第一個位置的基因在的子串中能找到相同基因且處于r（r＜）位置，則改變中該基因的位置為r，并將原先處于r位置的基因調(diào)整至子串的第一個位置；若無法找到相同基因，則不改變該基因的位置。同樣的，將與未進行交叉操作前的進行同基因交換。若產(chǎn)生的新染色體優(yōu)于父輩，則將其替換入新種群。圖3為染色體交叉示例，經(jīng)過同基因交換后的染色體不會產(chǎn)生不合法編碼。

圖3 同基因交換示意圖

下文給出了改進遺傳算法交叉策略與變異策略的偽代碼：

%對染色體B進行交叉，操作同上。

變異策略采取隨機選取某一染色體的兩個位置和，將兩位置上的值進行互換：

2.3.6 進化逆轉(zhuǎn)操作

為改善遺傳算法的局部搜索能力，在選擇、交叉、變異之后引進連續(xù)多次的進化逆轉(zhuǎn)操作。

在串中隨機選擇兩點（兩點之間稱為逆轉(zhuǎn)區(qū)域），再將逆轉(zhuǎn)區(qū)域內(nèi)的子串按反序插入原位置中。如圖4所示，若新生成的染色體適應(yīng)度優(yōu)于原染色體，則進行逆轉(zhuǎn)操作（即進化），否則，不進行逆轉(zhuǎn)。

圖4 進化逆轉(zhuǎn)示意圖（r1=2，r2=6）

進化逆轉(zhuǎn)操作的偽代碼為：

2.3.7 停止準(zhǔn)則

當(dāng)尋優(yōu)迭代次數(shù)達到最大遺傳代數(shù)MAXGEN時，尋優(yōu)結(jié)束。

當(dāng)整個算法循環(huán)次數(shù)達到總的待選倉庫點數(shù)時，算法結(jié)束并輸出最優(yōu)和次優(yōu)倉庫位置。

3 實例分析

某戰(zhàn)區(qū)東南沿海多點同時發(fā)生敵方入侵事件，多地局部小規(guī)模戰(zhàn)爭一觸即發(fā)。臨時器材倉庫選址建設(shè)問題迫在眉睫。

目前，已初步統(tǒng)計出戰(zhàn)斗極有可能發(fā)生的14處位置坐標(biāo)，如表1所示。根據(jù)前期偵查，發(fā)現(xiàn)后方有5處位置可供建設(shè)臨時器材倉庫，如表2所示。目前需要以最快的速度確定2個倉庫待建點，以進行臨時器材倉庫的搭建。

表1 可能的作戰(zhàn)地點位置坐標(biāo)

表2 臨時倉庫待選點位置坐標(biāo)

染色體編碼為從0-14-0的順序編碼（0表示倉庫點），表示器材保障路徑為從倉庫點出發(fā)，遍歷所有作戰(zhàn)點后返回倉庫。

3.1 參數(shù)設(shè)置

由于在不同種群大小、尋優(yōu)代數(shù)以及交叉變異概率下，改進遺傳算法的計算速率有所不同，甚至在待選倉庫點較多的情況下，不合適的計算參數(shù)為得到最優(yōu)解可能累積產(chǎn)生極大計算負(fù)擔(dān)。因此，本文為改進遺傳算法設(shè)置可能的參數(shù)取值如表3所示，以便從中選出可能的最優(yōu)參數(shù)選擇。

表3 算法參數(shù)取值

3.2 算法可行性分析

在表3給出的具體算法參數(shù)下，可利用改進遺傳算法得到器材倉庫選址的最優(yōu)點和次優(yōu)點，結(jié)果如表4所示。結(jié)果顯示，采取基于同基因交叉的改進遺傳算法時，在合適的參數(shù)取值下收斂速度能夠明顯優(yōu)于傳統(tǒng)遺傳算法。并且，當(dāng)參數(shù)取值為第2組時，結(jié)果最優(yōu)。

表4 倉庫選址結(jié)果

4 結(jié) 論

戰(zhàn)時器材倉庫選址問題面臨作戰(zhàn)任務(wù)的重要性和器材供應(yīng)的緊迫性，在通過以定性為主的方法（如模糊綜合評價法）得出幾個待選址點后，需要快速進行更準(zhǔn)確的選擇。本文通過改進遺傳算法，對交叉算子提出了同基因交叉的改進思路，給出了戰(zhàn)時倉庫精確選址的一種解法，為未來戰(zhàn)場應(yīng)急倉庫選址提供可行途徑，為提升戰(zhàn)場器材保障效率提供了參考依據(jù)。