軍事物流中鐵路輸送裝載地域分配問題研究

［摘 要］根據(jù)裝載地域分配影響因素，建立了裝載地域分配的數(shù)學(xué)模型，并分析了裝載地域分配組合優(yōu)化問題的復(fù)雜性，同時設(shè)計了遺傳算法對問題進行求解。

［關(guān)鍵詞］ 軍事物流 裝載地域分配 遺傳算法

裝載地域保障是部隊在軍事物流過程中，以鐵路為主要方式進行輸送的重要物質(zhì)和設(shè)備基礎(chǔ)，是編制保障方案的重要內(nèi)容之一。選擇良好的具有保障部隊不同進度條件下實施鐵路輸送能力的裝載地域，對于保障部隊安全、快速、正點地實施軍事物流具有十分重要的意義。裝載地域各裝載點的優(yōu)化分配方案可以有效地縮短部隊的整體輸送時間。長期以來，各裝載站分配方案的制定，通常采用人工試探的方法，這種方法不僅費時費力，且經(jīng)驗型東西太多，具有很大的局限性，很難適應(yīng)未來戰(zhàn)時部隊鐵路輸送的需要。因此，研究部隊鐵路輸送保障中的裝載地域分配問題的數(shù)學(xué)模型和求解算法，并應(yīng)用于相關(guān)鐵路軍事運輸輔助決策系統(tǒng)，是未來非線性戰(zhàn)爭中提高軍交運輸指揮效能的客觀要求。

本文根據(jù)裝載地域分配使用影響因素，建立了以對列車梯隊分配裝載站的總得分值為依據(jù)的裝載地域分配模型，分析了該問題的復(fù)雜性，并設(shè)計了遺傳算法來進行求解。

一、裝載地域分配影響因素分析

鐵路軍事運輸?shù)难b載需要在技術(shù)設(shè)備條件良好，運輸組織方法適合的鐵路車站上進行。在戰(zhàn)役部隊鐵路輸送時，由于部隊駐地和到達裝載地域的不同，為保證輸送進度和序列實施，就需要選擇多個鐵路車站承擔部隊輸送的裝載作業(yè)，這些車站就構(gòu)成了部隊的裝載地域。影響裝載地域中裝載站分配的因素很多，其中最主要的有以下幾個：

1.裝卸載能力。裝卸載地域的裝卸載能力是由該地域內(nèi)各裝卸載站的裝卸載能力決定的。它的定義是：在一定的固定和活動設(shè)備以及裝卸載和行車組織方法的條件下，一個裝卸載地域在單位時間內(nèi)（通常為一晝夜）所能裝卸載的最大列車數(shù)。裝卸載地域能力的大小，直接影響被運部隊的輸送進度和輸送序列。

2.部隊駐地與各裝載站的距離。部隊駐地距離裝載站越遠，部隊的機動距離就越長，耗費也就越大。所以，應(yīng)盡量選擇離部隊駐地近的裝載站，這樣可以減少部隊的摩托化或徒步行進的距離，便于部隊組織管理和進行各種保障。

3.部隊輸送進度。輸送進度是指部隊每晝夜按平均間隔發(fā)出的列車數(shù)。輸送進度必須與裝載地域的裝載能力相匹配。

4.部隊輸送序列。輸送序列是指各被運部隊的開進順序。

二、裝載地域分配模型的建立

裝載地域分配問題的描述為：在某個裝載地域有n個裝載站，待輸送部隊共有k個梯隊，輸送期限為m天，輸送進度為P，問如何對各梯隊分配裝載站，使得滿足輸送序列和輸送進度要求。

定義如下變量：

si表示第i個裝載站；tj表示第j個梯隊；表示車站i在第l天輸送的列車梯隊數(shù)，列；表示車站i的裝載能力，列；表示第j個梯隊離開裝載地域的時間；P表示部隊輸送進度；表示梯隊j選擇車站i的得分值；

式(1)是目標函數(shù)，表示對列車梯隊分配裝載站的總得分值最大的那種分配方案；式(2)是裝載能力限制，表示各裝載站在任意一天內(nèi)發(fā)出的列車數(shù)均不超過該裝載站的裝載能力；式(3)是輸送序列限制，表示各列車梯隊必須按輸送序列發(fā)送；式(4)是輸送進度限制，表示各裝載站每天的裝載列數(shù)都必須等于輸送進度。

顯然，所建立的模型是帶有復(fù)雜約束的混合整數(shù)非線性規(guī)劃模型，屬于NP-hard問題。對于這類問題，傳統(tǒng)的精確算法存在很多的局限性。比如說窮舉法，它的時間復(fù)雜度為O(Nn)，N為問題的規(guī)模，n為運行次數(shù)。當N不斷增大時，運行時間將迅速增加，如圖所示。如果假設(shè)運算每一種分配方案所用時間為1s，那么計算3個裝載站，30個梯隊的部隊輸送裝載站分配問題所花費的時間為6528765年。由此可看出大規(guī)模的部隊輸送裝載站分配問題的復(fù)雜性。

三、遺傳算法的設(shè)計

遺傳算法起源于對生物系統(tǒng)所進行的計算機模擬研究。它具有實用、高效、魯棒性強的特點，利用遺傳算法可以得到問題的滿意解。

1.設(shè)計染色體結(jié)構(gòu)。為了提高效率，采用自然數(shù)編碼，即序數(shù)編碼。則裝載地域分配的一條可行的染色體結(jié)構(gòu)為（i1， i2，…， it，…， ik），t∈[1， k]且為自然數(shù)，it∈[1， n]且為自然數(shù)。k為待運部隊的梯隊數(shù)，n為裝載地域內(nèi)的車站數(shù)，it表示第t個列車梯隊所選定的裝載站。

2.確定初始種群。為了保證計算效率，群體規(guī)模不能太大，也不能太小，在這里規(guī)定群體規(guī)模取值為20到50之間。

3.確定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是由目標函數(shù)變換而成的。由于本文的目標是求對列車梯隊分配總得分值最大的裝載站，所以設(shè)計的適應(yīng)度函數(shù)為： Fit(z) = z

4.設(shè)計遺傳算子。對于選擇算子，采用精英策略和隨機競爭相結(jié)合的方法，在隨機競爭選擇時，每次按輪盤賭選擇機制選取一對個體，然后讓這一對個體進行競爭，適應(yīng)度高的個體被選中，如此反復(fù)，直至選滿為止。對于交叉算子，可采用兩點交叉運算。變異算子采用對換變異。

5.設(shè)定終止條件。由于遺傳算法具有較大的隨機性，本文設(shè)計了2個終止條件：一是若迭代次數(shù)達到1000代；二是若最佳染色體連續(xù)保持10代。當遺傳算法運算過程中滿足任一個終止條件，就結(jié)束運算。

6.遺傳算法的步驟

Step1：設(shè)置遺傳算法的參數(shù)，即進化總迭代次數(shù)maxgen，種群規(guī)模popsize，交叉概率pc，變異概率pm；

Step2：進化迭代次數(shù)gen=0，隨機產(chǎn)生popsize條染色體生成初始種群；

Step3：計算種群所有個體的適應(yīng)度函數(shù)值；

Step4：選擇操作，采用精英策略和輪盤賭的方法從群體中選擇染色體作為父代染色體；

Step5：交叉操作，按照交叉概率對選擇出的染色體進行交叉操作；

Step6：變異操作，按照變異概率對染色體進行變異操作；

Step7：不斷進行遺傳操作，直至生成的染色體的個數(shù)達到種群規(guī)模popsize，組成下一代群體，gen= gen+1；

Step8：如果gen>maxgen，算法結(jié)束，否則轉(zhuǎn)Step3。

四、結(jié)束語

通過實驗，對一個師規(guī)模部隊，應(yīng)用遺傳算法在求解部隊鐵路輸送裝載地域分配問題時，可以在很短的時間內(nèi)求得一個比較優(yōu)的解。得到的裝載站的分配使用方案是合理的，不僅滿足裝載地域分配的基本要求，同時也保證了部隊的輸送進度和輸送序列。本文建立了貼合部隊鐵路輸送裝載地域分配的數(shù)學(xué)優(yōu)化模型，并應(yīng)用遺傳算法對問題進行了求解。部隊鐵路輸送中裝載地域分配問題是典型的NP問題，隨著問題規(guī)模的增加，優(yōu)化搜索的計算量迅速增長，算法效率必然會下降。因此，在保證算法求解精度的前提下，進一步改進算法，提高算法的效率，是下一步的研究方向。

參考文獻:

[1]鮑平鑫，徐開啟.鐵路軍事運輸［M］.北京:解放軍出版社，2006.

[2]劉中，周飛飛，李海華.軍運梯隊鐵路裝載組合優(yōu)化問題模擬退火算法研究［J］.軍事交通學(xué)院學(xué)報，2010，(2)21-24。

[3]吳曉東.大規(guī)模部隊鐵路輸送研究.北京交通大學(xué)博士論文，2008

[4]邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京:清華大學(xué)出版社，2005.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文