［摘 要］根據(jù)裝載地域分配影響因素，建立了裝載地域分配的數(shù)學(xué)模型，并分析了裝載地域分配組合優(yōu)化問(wèn)題的復(fù)雜性，同時(shí)設(shè)計(jì)了遺傳算法對(duì)問(wèn)題進(jìn)行求解。
　�。坳P(guān)鍵詞］ 軍事物流 裝載地域分配 遺傳算法
　　
　　裝載地域保障是部隊(duì)在軍事物流過(guò)程中，以鐵路為主要方式進(jìn)行輸送的重要物質(zhì)和設(shè)備基礎(chǔ)，是編制保障方案的重要內(nèi)容之一。選擇良好的具有保障部隊(duì)不同進(jìn)度條件下實(shí)施鐵路輸送能力的裝載地域，對(duì)于保障部隊(duì)安全、快速、正點(diǎn)地實(shí)施軍事物流具有十分重要的意義。裝載地域各裝載點(diǎn)的優(yōu)化分配方案可以有效地縮短部隊(duì)的整體輸送時(shí)間。長(zhǎng)期以來(lái)，各裝載站分配方案的制定，通常采用人工試探的方法，這種方法不僅費(fèi)時(shí)費(fèi)力，且經(jīng)驗(yàn)型東西太多，具有很大的局限性，很難適應(yīng)未來(lái)戰(zhàn)時(shí)部隊(duì)鐵路輸送的需要。因此，研究部隊(duì)鐵路輸送保障中的裝載地域分配問(wèn)題的數(shù)學(xué)模型和求解算法，并應(yīng)用于相關(guān)鐵路軍事運(yùn)輸輔助決策系統(tǒng)，是未來(lái)非線(xiàn)性戰(zhàn)爭(zhēng)中提高軍交運(yùn)輸指揮效能的客觀要求。
　　本文根據(jù)裝載地域分配使用影響因素，建立了以對(duì)列車(chē)梯隊(duì)分配裝載站的總得分值為依據(jù)的裝載地域分配模型，分析了該問(wèn)題的復(fù)雜性，并設(shè)計(jì)了遺傳算法來(lái)進(jìn)行求解。
　　一、裝載地域分配影響因素分析
　　鐵路軍事運(yùn)輸?shù)难b載需要在技術(shù)設(shè)備條件良好，運(yùn)輸組織方法適合的鐵路車(chē)站上進(jìn)行。在戰(zhàn)役部隊(duì)鐵路輸送時(shí)，由于部隊(duì)駐地和到達(dá)裝載地域的不同，為保證輸送進(jìn)度和序列實(shí)施，就需要選擇多個(gè)鐵路車(chē)站承擔(dān)部隊(duì)輸送的裝載作業(yè)，這些車(chē)站就構(gòu)成了部隊(duì)的裝載地域。影響裝載地域中裝載站分配的因素很多，其中最主要的有以下幾個(gè)：
　　1.裝卸載能力。裝卸載地域的裝卸載能力是由該地域內(nèi)各裝卸載站的裝卸載能力決定的。它的定義是：在一定的固定和活動(dòng)設(shè)備以及裝卸載和行車(chē)組織方法的條件下，一個(gè)裝卸載地域在單位時(shí)間內(nèi)（通常為一晝夜）所能裝卸載的最大列車(chē)數(shù)。裝卸載地域能力的大小，直接影響被運(yùn)部隊(duì)的輸送進(jìn)度和輸送序列。
　　2.部隊(duì)駐地與各裝載站的距離。部隊(duì)駐地距離裝載站越遠(yuǎn)，部隊(duì)的機(jī)動(dòng)距離就越長(zhǎng)，耗費(fèi)也就越大。所以，應(yīng)盡量選擇離部隊(duì)駐地近的裝載站，這樣可以減少部隊(duì)的摩托化或徒步行進(jìn)的距離，便于部隊(duì)組織管理和進(jìn)行各種保障。
　　3.部隊(duì)輸送進(jìn)度。輸送進(jìn)度是指部隊(duì)每晝夜按平均間隔發(fā)出的列車(chē)數(shù)。輸送進(jìn)度必須與裝載地域的裝載能力相匹配。
　　4.部隊(duì)輸送序列。輸送序列是指各被運(yùn)部隊(duì)的開(kāi)進(jìn)順序。
　　二、裝載地域分配模型的建立
　　裝載地域分配問(wèn)題的描述為：在某個(gè)裝載地域有n個(gè)裝載站，待輸送部隊(duì)共有k個(gè)梯隊(duì)，筆耕文化傳播，輸送期限為m天，輸送進(jìn)度為P，問(wèn)如何對(duì)各梯隊(duì)分配裝載站，使得滿(mǎn)足輸送序列和輸送進(jìn)度要求。
　　定義如下變量：
　　si表示第i個(gè)裝載站；tj表示第j個(gè)梯隊(duì)；表示車(chē)站i在第l天輸送的列車(chē)梯隊(duì)數(shù)，列；表示車(chē)站i的裝載能力，列；表示第j個(gè)梯隊(duì)離開(kāi)裝載地域的時(shí)間；P表示部隊(duì)輸送進(jìn)度；表示梯隊(duì)j選擇車(chē)站i的得分值；
　　式(1)是目標(biāo)函數(shù)，表示對(duì)列車(chē)梯隊(duì)分配裝載站的總得分值最大的那種分配方案；式(2)是裝載能力限制，表示各裝載站在任意一天內(nèi)發(fā)出的列車(chē)數(shù)均不超過(guò)該裝載站的裝載能力；式(3)是輸送序列限制，表示各列車(chē)梯隊(duì)必須按輸送序列發(fā)送；式(4)是輸送進(jìn)度限制，表示各裝載站每天的裝載列數(shù)都必須等于輸送進(jìn)度。
　　顯然，所建立的模型是帶有復(fù)雜約束的混合整數(shù)非線(xiàn)性規(guī)劃模型，屬于NP-hard問(wèn)題。對(duì)于這類(lèi)問(wèn)題，傳統(tǒng)的精確算法存在很多的局限性。比如說(shuō)窮舉法，它的時(shí)間復(fù)雜度為O(Nn)，N為問(wèn)題的規(guī)模，n為運(yùn)行次數(shù)。當(dāng)N不斷增大時(shí)，運(yùn)行時(shí)間將迅速增加，如圖所示。如果假設(shè)運(yùn)算每一種分配方案所用時(shí)間為1s，那么計(jì)算3個(gè)裝載站，30個(gè)梯隊(duì)的部隊(duì)輸送裝載站分配問(wèn)題所花費(fèi)的時(shí)間為6528765年。由此可看出大規(guī)模的部隊(duì)輸送裝載站分配問(wèn)題的復(fù)雜性。
　　三、遺傳算法的設(shè)計(jì)
　　遺傳算法起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。它具有實(shí)用、高效、魯棒性強(qiáng)的特點(diǎn)，利用遺傳算法可以得到問(wèn)題的滿(mǎn)意解。
　　1.設(shè)計(jì)染色體結(jié)構(gòu)。為了提高效率，采用自然數(shù)編碼，即序數(shù)編碼。則裝載地域分配的一條可行的染色體結(jié)構(gòu)為（i1, i2,…, it,…, ik），t∈[1, k]且為自然數(shù)，it∈[1, n]且為自然數(shù)。k為待運(yùn)部隊(duì)的梯隊(duì)數(shù)，n為裝載地域內(nèi)的車(chē)站數(shù)，it表示第t個(gè)列車(chē)梯隊(duì)所選定的裝載站。
　　2.確定初始種群。為了保證計(jì)算效率，群體規(guī)模不能太大，也不能太小，在這里規(guī)定群體規(guī)模取值為20到50之間。
　　3.確定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。由于本文的目標(biāo)是求對(duì)列車(chē)梯隊(duì)分配總得分值最大的裝載站，所以設(shè)計(jì)的適應(yīng)度函數(shù)為： Fit(z) = z
　　4.設(shè)計(jì)遺傳算子。對(duì)于選擇算子，采用精英策略和隨機(jī)競(jìng)爭(zhēng)相結(jié)合的方法，在隨機(jī)競(jìng)爭(zhēng)選擇時(shí)，每次按輪盤(pán)賭選擇機(jī)制選取一對(duì)個(gè)體，然后讓這一對(duì)個(gè)體進(jìn)行競(jìng)爭(zhēng)，適應(yīng)度高的個(gè)體被選中，如此反復(fù)，直至選滿(mǎn)為止。對(duì)于交叉算子，可采用兩點(diǎn)交叉運(yùn)算。變異算子采用對(duì)換變異。
　　5.設(shè)定終止條件。由于遺傳算法具有較大的隨機(jī)性，本文設(shè)計(jì)了2個(gè)終止條件：一是若迭代次數(shù)達(dá)到1000代；二是若最佳染色體連續(xù)保持10代。當(dāng)遺傳算法運(yùn)算過(guò)程中滿(mǎn)足任一個(gè)終止條件，就結(jié)束運(yùn)算。
　　6.遺傳算法的步驟
　　Step1：設(shè)置遺傳算法的參數(shù)，即進(jìn)化總迭代次數(shù)maxgen，種群規(guī)模popsize，交叉概率pc，變異概率pm；
　　Step2：進(jìn)化迭代次數(shù)gen=0，隨機(jī)產(chǎn)生popsize條染色體生成初始種群；
　　Step3：計(jì)算種群所有個(gè)體的適應(yīng)度函數(shù)值；
　　Step4：選擇操作，采用精英策略和輪盤(pán)賭的方法從群體中選擇染色體作為父代染色體；
　　Step5：交叉操作，按照交叉概率對(duì)選擇出的染色體進(jìn)行交叉操作；
　　Step6：變異操作，按照變異概率對(duì)染色體進(jìn)行變異操作；
　　Step7：不斷進(jìn)行遺傳操作，直至生成的染色體的個(gè)數(shù)達(dá)到種群規(guī)模popsize，組成下一代群體，gen= gen+1；
　　Step8：如果gen>maxgen，算法結(jié)束，否則轉(zhuǎn)Step3。
　　四、結(jié)束語(yǔ)
　　通過(guò)實(shí)驗(yàn)，對(duì)一個(gè)師規(guī)模部隊(duì)，應(yīng)用遺傳算法在求解部隊(duì)鐵路輸送裝載地域分配問(wèn)題時(shí)，可以在很短的時(shí)間內(nèi)求得一個(gè)比較優(yōu)的解。得到的裝載站的分配使用方案是合理的，不僅滿(mǎn)足裝載地域分配的基本要求，同時(shí)也保證了部隊(duì)的輸送進(jìn)度和輸送序列。本文建立了貼合部隊(duì)鐵路輸送裝載地域分配的數(shù)學(xué)優(yōu)化模型，并應(yīng)用遺傳算法對(duì)問(wèn)題進(jìn)行了求解。部隊(duì)鐵路輸送中裝載地域分配問(wèn)題是典型的NP問(wèn)題，隨著問(wèn)題規(guī)模的增加，優(yōu)化搜索的計(jì)算量迅速增長(zhǎng)，算法效率必然會(huì)下降。因此，在保證算法求解精度的前提下，進(jìn)一步改進(jìn)算法，提高算法的效率，是下一步的研究方向。
　　參考文獻(xiàn):
　　[1]鮑平鑫,徐開(kāi)啟.鐵路軍事運(yùn)輸［M］.北京:解放軍出版社,2006.
　　[2]劉中,周飛飛,李海華.軍運(yùn)梯隊(duì)鐵路裝載組合優(yōu)化問(wèn)題模擬退火算法研究［J］.軍事交通學(xué)院學(xué)報(bào),2010，(2)21-24。
　　[3]吳曉東.大規(guī)模部隊(duì)鐵路輸送研究.北京交通大學(xué)博士論文,2008
　　[4]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.北京:清華大學(xué)出版社,2005.
　　注：本文中所涉及到的
中國(guó)圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文