杜小敏,胡遠(yuǎn)新
(陸軍勤務(wù)學(xué)院 軍事設(shè)施系,重慶401331)
近年來(lái)自然災(zāi)害呈現(xiàn)頻發(fā)多發(fā)、范圍大、破壞性強(qiáng)的趨勢(shì),在政府和軍隊(duì)的應(yīng)急處置過(guò)程中,隨著對(duì)受傷人員的救助、應(yīng)急物資的供應(yīng)、災(zāi)后恢復(fù)生產(chǎn)生活秩序等任務(wù)的開(kāi)展,產(chǎn)生了總量較大的、多樣化的應(yīng)急運(yùn)輸需求。應(yīng)急運(yùn)輸是指以滿(mǎn)足自然災(zāi)害、公共事件等突發(fā)事件的運(yùn)輸需求為目的,綜合運(yùn)用軍隊(duì)和社會(huì)的交通運(yùn)輸設(shè)施、設(shè)備、運(yùn)載工具、信息資源,追求時(shí)間效益的最大化和災(zāi)害損失的最小化的一種特殊的運(yùn)輸活動(dòng)。軍隊(duì)平時(shí)的主要任務(wù)是練兵備戰(zhàn),同時(shí)參與搶險(xiǎn)救災(zāi)、應(yīng)急救援等非戰(zhàn)爭(zhēng)軍事行動(dòng),在自然災(zāi)害發(fā)生時(shí),軍隊(duì)?wèi){借組織指揮優(yōu)勢(shì)、快速反應(yīng)能力和機(jī)動(dòng)能力,擔(dān)任了應(yīng)急運(yùn)輸?shù)耐粨絷?duì)和中堅(jiān)力量,在應(yīng)急處置過(guò)程中發(fā)揮了突出作用,同時(shí)也是對(duì)軍隊(duì)?wèi)?yīng)急運(yùn)輸能力的實(shí)戰(zhàn)化檢驗(yàn)。
車(chē)輛調(diào)度問(wèn)題(Vehicle Scheduling Problem,VSP)是指在車(chē)輛數(shù)量一定的情況下,根據(jù)用戶(hù)的需求合理地調(diào)配有限的車(chē)輛資源,在最大限度滿(mǎn)足用戶(hù)需求的前提下使運(yùn)輸成本最低,最后得到最優(yōu)的調(diào)度方案。車(chē)輛調(diào)度方案的決策是應(yīng)急運(yùn)輸?shù)闹匾h(huán)節(jié),對(duì)提高應(yīng)急運(yùn)輸效率、爭(zhēng)取應(yīng)急救援黃金時(shí)間、實(shí)現(xiàn)精準(zhǔn)保障具有重要意義。近年國(guó)內(nèi)外對(duì)應(yīng)急運(yùn)輸車(chē)輛調(diào)度問(wèn)題的研究不斷深入,王偉[2]研究了在通信中斷和運(yùn)輸路網(wǎng)中斷導(dǎo)致物資運(yùn)輸時(shí)間延遲的車(chē)輛調(diào)度問(wèn)題;喻德曠[3]針對(duì)多種運(yùn)輸貨物類(lèi)型和實(shí)時(shí)路況變化構(gòu)建了車(chē)輛調(diào)度模型;楊海強(qiáng)[4]提出了基于需求優(yōu)先權(quán)重和未滿(mǎn)足物資需求量最小的應(yīng)急車(chē)輛調(diào)度模型;陳湉[5]研究了物資需求呈正態(tài)分布條件下物資分配不足或過(guò)量的車(chē)輛調(diào)度問(wèn)題;鄧燁[6]運(yùn)用魯棒優(yōu)化理論將車(chē)輛調(diào)度問(wèn)題中的物資需求等不確定參數(shù)轉(zhuǎn)化為確定性參數(shù)進(jìn)行分析;J.Sch?nberger[7]為解決短期物流設(shè)施抵達(dá)車(chē)輛過(guò)多的問(wèn)題,提出了混合整數(shù)線(xiàn)性問(wèn)題來(lái)表示多周期的運(yùn)輸決策任務(wù),分析了不同請(qǐng)求組合對(duì)總距離最小化的影響;Safaei[8]構(gòu)建了應(yīng)急運(yùn)輸雙層優(yōu)化模型,上層是基于救濟(jì)物資分配地點(diǎn)影響的總成本最低和未滿(mǎn)足需求最少,下層考慮選擇風(fēng)險(xiǎn)較低的供應(yīng)商;?zdamar[9]研究了供給和需求動(dòng)態(tài)時(shí)變條件下的多種物資多階段的的應(yīng)急運(yùn)輸問(wèn)題,以運(yùn)輸總時(shí)間最短為目標(biāo)函數(shù);Korosec[10]研究了具有裝卸作業(yè)頻率高特點(diǎn)的倉(cāng)庫(kù)和港口的運(yùn)輸調(diào)度問(wèn)題,分別采用分組運(yùn)輸和自由運(yùn)輸?shù)姆椒▽?duì)四項(xiàng)運(yùn)輸任務(wù)進(jìn)行優(yōu)化測(cè)試。
在緊急情況下,應(yīng)急運(yùn)輸具有時(shí)效性、弱經(jīng)濟(jì)性的特點(diǎn),因此車(chē)輛調(diào)度對(duì)時(shí)間的要求比較高,對(duì)成本的要求比較低,以最短的時(shí)間完成應(yīng)急運(yùn)輸任務(wù)具有現(xiàn)實(shí)意義;軍隊(duì)參與非戰(zhàn)爭(zhēng)軍事任務(wù)同樣是以完成任務(wù)為第一目標(biāo),經(jīng)濟(jì)成本方面的考慮次之,與應(yīng)急運(yùn)輸?shù)哪繕?biāo)是統(tǒng)一的,因此軍隊(duì)在遂行應(yīng)急運(yùn)輸任務(wù)上天然具有優(yōu)勢(shì)。本文構(gòu)建了基于單邊時(shí)間窗的軍隊(duì)?wèi)?yīng)急運(yùn)輸車(chē)輛調(diào)度模型,只考慮最晚到達(dá)時(shí)間的單邊時(shí)間窗符合應(yīng)急運(yùn)輸目標(biāo)特點(diǎn),計(jì)劃通過(guò)車(chē)輛編組實(shí)施應(yīng)急運(yùn)輸保障,然后設(shè)計(jì)了一種改進(jìn)遺傳算法進(jìn)行求解,對(duì)交叉算子、變異算子和可行化過(guò)程進(jìn)行了改進(jìn)。
根據(jù)近年自然災(zāi)害應(yīng)急運(yùn)輸實(shí)踐,對(duì)災(zāi)時(shí)軍隊(duì)車(chē)輛調(diào)度問(wèn)題描述如下:在自然災(zāi)害發(fā)生后,有多個(gè)受災(zāi)點(diǎn)需要緊急調(diào)撥各類(lèi)物資,受災(zāi)點(diǎn)用i(i=1,2,…,n)表示,受災(zāi)點(diǎn)的物資需求量表示為Gi(g1,g2,…,gn),駐地部隊(duì)某運(yùn)輸旅發(fā)現(xiàn)災(zāi)情后,立即啟動(dòng)應(yīng)急響應(yīng),擬派出k(k=1,2,…,K)個(gè)車(chē)隊(duì)組織進(jìn)行救災(zāi)物資的應(yīng)急運(yùn)輸,每個(gè)車(chē)隊(duì)有L輛車(chē),一個(gè)車(chē)隊(duì)要求統(tǒng)一行動(dòng),先前往物資儲(chǔ)備庫(kù)裝載物資,然后按照計(jì)劃路徑前往受災(zāi)點(diǎn)卸載物資,最后全部返回運(yùn)輸旅。
為便于構(gòu)建模型,作以下假設(shè)和參數(shù)定義:
(1)每個(gè)受災(zāi)點(diǎn)由單個(gè)車(chē)隊(duì)進(jìn)行保障;
(2)每個(gè)車(chē)隊(duì)單次裝載物資或卸載物資的時(shí)間均為T(mén)x;
(3)根據(jù)受災(zāi)程度的不同,受災(zāi)點(diǎn)要求應(yīng)急運(yùn)輸物資的最晚到達(dá)時(shí)間,即考慮單邊時(shí)間窗,表示為[0,LTi];車(chē)隊(duì)預(yù)計(jì)抵達(dá)受災(zāi)點(diǎn)i的時(shí)間為T(mén)i;
(4)車(chē)隊(duì)勻速行駛速度為V;
(5)每輛車(chē)可裝載物資為Q;
(7)dij表示點(diǎn)i與j之間距離,使用決策變量xijk表示車(chē)隊(duì)k從i點(diǎn)出發(fā)到達(dá)j點(diǎn),此處的點(diǎn)i、j包括物資儲(chǔ)備庫(kù)點(diǎn)0和運(yùn)輸旅駐地點(diǎn)n+1;
目標(biāo)函數(shù)表示為帶時(shí)間窗懲罰函數(shù)的總路程最短,如式(1),L代表每個(gè)車(chē)隊(duì)具有相同的車(chē)輛數(shù)目,S是一個(gè)車(chē)輛調(diào)度方案的總路程,P是懲罰函數(shù):
其中:
α和β是懲罰系數(shù),α是車(chē)隊(duì)超時(shí)的時(shí)間之和的懲罰系數(shù),β是超時(shí)的車(chē)隊(duì)數(shù)目的懲罰系數(shù),Viol代表在n個(gè)受災(zāi)點(diǎn)中超過(guò)最晚到達(dá)時(shí)間的個(gè)數(shù)。假使將目標(biāo)函數(shù)中的L替代為L(zhǎng)k,Lk代表車(chē)輛調(diào)度方案中的第k個(gè)車(chē)隊(duì)的車(chē)輛數(shù)目不大于L,那么最終車(chē)輛調(diào)度方案會(huì)使車(chē)輛運(yùn)行的總路徑更小,即代表成本更低,但是配送時(shí)間相對(duì)地會(huì)少許延長(zhǎng)。由于應(yīng)急運(yùn)輸更強(qiáng)調(diào)時(shí)效性,而不強(qiáng)調(diào)經(jīng)濟(jì)性,受災(zāi)民眾仍然希望在滿(mǎn)足時(shí)間窗的前提下盡可能早地收到應(yīng)急物資,因此目標(biāo)函數(shù)仍采用式(1),在計(jì)算出最優(yōu)車(chē)輛調(diào)度方案后,再判斷各個(gè)車(chē)隊(duì)是否存在空載的車(chē)輛,并剔除多余車(chē)輛,以保證以最短時(shí)間完成應(yīng)急運(yùn)輸任務(wù)。
模型約束條件如下:
其中式(4)表示從需求點(diǎn)i出發(fā)的只有一個(gè)車(chē)隊(duì);式(5)表示抵達(dá)需求點(diǎn)j的只有一個(gè)車(chē)隊(duì);式(6)表示車(chē)隊(duì)k經(jīng)過(guò)受災(zāi)點(diǎn)的需求總和不大于載重Q;式(7)表示每個(gè)點(diǎn)都有車(chē)隊(duì)運(yùn)輸滿(mǎn)足其需求。
車(chē)輛調(diào)度優(yōu)化問(wèn)題被證明為NP-Hard問(wèn)題,隨著需求點(diǎn)的增加,問(wèn)題解的組合數(shù)呈爆炸式增長(zhǎng),求解難度大。車(chē)輛調(diào)度優(yōu)化問(wèn)題的求解方法可分為兩大類(lèi),即精確算法和啟發(fā)式算法,精確算法包括分支定界法、列生成法等,對(duì)于規(guī)模較大的車(chē)輛調(diào)度問(wèn)題使用精確算法求解難度較大,目前學(xué)界更多傾向于啟發(fā)式算法研究,有混合蛙跳算法[11]、免疫算法[12]、混合遺傳算法[13]、層次蝙蝠算法[14]、鯨魚(yú)群優(yōu)化算法[15]等。
為對(duì)上述模型求解,設(shè)計(jì)一種改進(jìn)遺傳算法,目的是提高尋優(yōu)效率、避免局部最優(yōu),具體步驟如下:
(1)基因編碼、解碼和種群初始化。遺傳算法中基因指的是問(wèn)題的解,在應(yīng)急運(yùn)輸車(chē)輛調(diào)度問(wèn)題中,所有車(chē)隊(duì)的調(diào)度方案作為一個(gè)染色體,若干的染色體的集合作為一個(gè)種群,編碼指的是從表現(xiàn)型到基因型的映射,基因解碼反之。
該模型的一個(gè)解所對(duì)應(yīng)的染色體分為兩段,DNA_1=[dna1,dna2,…,dnan]是受災(zāi)點(diǎn)的序列號(hào),DNA_2=[dna1,dna2,…,dna(K-1)]是斷點(diǎn)序列號(hào)作為區(qū)分各個(gè)車(chē)隊(duì)負(fù)責(zé)運(yùn)輸路徑,其中物資儲(chǔ)備庫(kù)的序號(hào)為0,運(yùn)輸旅駐地的序號(hào)為n+1。例如根據(jù)上文對(duì)問(wèn)題和模型的描述,車(chē)隊(duì)先從運(yùn)輸旅駐地出發(fā),前往物資儲(chǔ)備庫(kù)裝載物資,到達(dá)受災(zāi)點(diǎn)卸載物資再返回,因此該DNA表示第一車(chē)隊(duì)的運(yùn)輸路徑是10-0-3-2-10,第二車(chē)隊(duì)的運(yùn)輸路徑是10-0-1-6-5-10,第三車(chē)隊(duì)為10-0-4-9-0,第四車(chē)隊(duì)為10-0-8-7-0。
種群是遺傳交叉、變異和自然選擇的基本單位,初始種群采用隨機(jī)產(chǎn)生序列的方式生成,初始種群是稂莠不齊的,種群規(guī)模越大,種群的多樣性越豐富,初始種群中包含優(yōu)質(zhì)個(gè)體的幾率越高,交叉和變異產(chǎn)生的子代個(gè)體也越多,但是相應(yīng)的計(jì)算量呈線(xiàn)性增長(zhǎng),因此適當(dāng)設(shè)定種群規(guī)模有助于提高計(jì)算效率,種群中染色體的數(shù)量一般設(shè)置為染色體長(zhǎng)度的線(xiàn)性級(jí)別倍數(shù)。
(2)交叉算子和變異算子。將種群隨機(jī)分為兩兩一組,根據(jù)交叉算子Pc,產(chǎn)生本輪的隨機(jī)數(shù)Pt,當(dāng)Pt小于交叉算子Pc時(shí),隨機(jī)對(duì)其中某段進(jìn)行交叉操作,產(chǎn)生新的個(gè)體。交叉操作設(shè)計(jì)為兩種,第一種交叉操作采用部分匹配法(Partially Matching Crossover,PMX),第二種是對(duì)交叉段基因交換,移到首部位置后,消除重復(fù)項(xiàng),產(chǎn)生兩個(gè)子代個(gè)體,可稱(chēng)為類(lèi)PMX算子。例如:
第一種交叉:
第二種交叉:
變異操作的步驟是,首先對(duì)種群內(nèi)所有個(gè)體進(jìn)行判斷,當(dāng)隨機(jī)數(shù)Pt小于Pm時(shí),對(duì)該個(gè)體進(jìn)行變異操作,產(chǎn)生新的個(gè)體。變異操作設(shè)計(jì)為,對(duì)染色體受災(zāi)點(diǎn)序列中的一個(gè)片段進(jìn)行倒序逆轉(zhuǎn),同時(shí)讓斷點(diǎn)序列基因中的隨機(jī)項(xiàng)突變?yōu)榱硪粋€(gè)數(shù),并重新排序,獲得子代個(gè)體的DNA序列。例如:
在交叉和變異操作之后,由原種群加上交叉變異產(chǎn)生的子代種群,共同構(gòu)成新的種群,此時(shí)新種群數(shù)量約為原種群的(1+Pm+Pc)倍。交叉操作是為了讓DNA中的優(yōu)秀基因片段充分交換,產(chǎn)生新的優(yōu)質(zhì)個(gè)體,變異操作是為了增強(qiáng)種群的多樣性,避免過(guò)快收斂進(jìn)入局部最優(yōu)。
(3)可行化。滿(mǎn)足約束條件的個(gè)體稱(chēng)之為良種,反之為劣種,可行化指的是將劣種轉(zhuǎn)化為良種的過(guò)程。上述模型的約束條件在此處主要表現(xiàn)為車(chē)隊(duì)的載重約束,對(duì)新的種群進(jìn)行約束條件判斷,對(duì)不可行解逐一進(jìn)行可行化。對(duì)劣種的可行化過(guò)程具有一定必要性,如果不進(jìn)行可行化而是直接刪除劣種,在運(yùn)輸旅的運(yùn)輸力量不太充足的情況下,隨機(jī)產(chǎn)生的初始種群會(huì)包含大量的劣種,將劣種直接從種群中刪除將導(dǎo)致種群數(shù)目急劇下降,導(dǎo)致難以維持預(yù)期的種群規(guī)模,無(wú)法進(jìn)入下一次遺傳迭代??尚谢惴ǖ乃悸窞?,首先根據(jù)不可行解的路徑集合,找出超載最多的車(chē)隊(duì)kmax和載重最小的車(chē)隊(duì)kmin,將車(chē)隊(duì)kmax路徑中的一個(gè)需求點(diǎn)轉(zhuǎn)移至車(chē)隊(duì)kmax的路徑中,當(dāng)循環(huán)7次仍不能滿(mǎn)足載重約束,刪除該個(gè)體。測(cè)試表明當(dāng)不進(jìn)行可行化時(shí),對(duì)初始種群的劣種通常刪除超過(guò)50%,使用該可行化算法后在5 000次迭代中平均每次迭代刪除劣種0.63個(gè)。
(4)自然選擇。對(duì)可行化之后的新種群,逐一計(jì)算適應(yīng)度,擇優(yōu)進(jìn)入下一代,將種群淘汰至初始種群規(guī)模。為確保優(yōu)質(zhì)個(gè)體與劣質(zhì)個(gè)體在自然選擇中的差別,適應(yīng)度函數(shù)表示如下。
自然選擇的方法一般有輪盤(pán)賭選擇法,隨機(jī)遍歷抽樣法,錦標(biāo)賽選擇法,考慮到算法收斂效率采取精英保留策略和輪盤(pán)賭選擇法相結(jié)合的策略,首先按1/4的比例將適應(yīng)度最優(yōu)的個(gè)體直接保留至下一代種群,剩余部分采用輪盤(pán)賭選擇法進(jìn)行選擇,可以在充分保證種群中的優(yōu)秀個(gè)體能夠遺傳到下一代的同時(shí),其余個(gè)體憑借自身適應(yīng)度接受輪盤(pán)賭的隨機(jī)選擇,適應(yīng)度高的個(gè)體自然能夠大概率遺傳下去,減緩種群收斂過(guò)程,充分迭代優(yōu)化更容易尋到全局最優(yōu)。
(5)結(jié)束判斷。當(dāng)?shù)螖?shù)達(dá)到最大設(shè)定值,結(jié)束迭代循環(huán)。
選取Solomon VRSPTW問(wèn)題測(cè)試集的RC208前15個(gè)和后15個(gè)位置數(shù)據(jù)進(jìn)行算例分析,即保證需求點(diǎn)的位置分布包含聚類(lèi)結(jié)構(gòu)和隨機(jī)結(jié)構(gòu),物資儲(chǔ)備庫(kù)坐標(biāo)[40,50],運(yùn)輸旅駐地坐標(biāo)[35,45]。單車(chē)載重Q=6,一個(gè)車(chē)隊(duì)的車(chē)輛數(shù)L=7,車(chē)隊(duì)數(shù)K=8,每次裝載和卸載時(shí)間Tx=0.5,車(chē)隊(duì)速度V=40,物資需求Gi和最晚到達(dá)時(shí)間LTi見(jiàn)表1。
表1 受災(zāi)點(diǎn)物資需求和最晚到達(dá)時(shí)間信息
受災(zāi)點(diǎn)分布如圖1所示。
圖1 受災(zāi)點(diǎn)坐標(biāo)分布
對(duì)該算例使用上述改進(jìn)遺傳算法進(jìn)行測(cè)試分析,機(jī)器配置為i7-2620m,主頻2.70GHz,內(nèi)存8G,軟件Matlab2010a,交叉概率pc=0.8,變異概率pm=0.1,懲罰系數(shù)α=40,β=100,種群規(guī)模為80,最大迭代次數(shù)5 000次,分別進(jìn)行了10次優(yōu)化求解,測(cè)試結(jié)果見(jiàn)表2,最優(yōu)路徑圖示和迭代過(guò)程如圖2、圖3所示。
表2 測(cè)試結(jié)果
圖2 最優(yōu)路徑圖示
計(jì)算結(jié)果表明,10次測(cè)試中每次的最優(yōu)解均沒(méi)有超過(guò)時(shí)間窗,可以滿(mǎn)足應(yīng)急運(yùn)輸?shù)臅r(shí)間要求和受災(zāi)點(diǎn)的物資需求,能夠獲得該車(chē)輛調(diào)度問(wèn)題最優(yōu)路程的近似解,保證以最短時(shí)間完成應(yīng)急運(yùn)輸,提高了應(yīng)急運(yùn)輸?shù)男?;使用的改進(jìn)遺傳算法對(duì)該模型求解有較好的收斂效果,證明了該改進(jìn)遺傳算法在解決軍隊(duì)?wèi)?yīng)急運(yùn)輸車(chē)輛調(diào)度優(yōu)化問(wèn)題的有效性。其中第9次的測(cè)試結(jié)果為最優(yōu),其目標(biāo)函數(shù)Z為4 902.78,總路程為700.40km,車(chē)隊(duì)路徑為:
圖3 迭代過(guò)程
k=1:20-16-27-17,行駛路程98.50km,加物資裝卸時(shí)間共耗時(shí)4.96h,物資裝載率為98%;
k=2:21-22-25-19,行駛路程115.01km,耗時(shí)5.38h,物資裝載率為69%,因此可以在車(chē)隊(duì)中減少2輛運(yùn)輸車(chē);
k=3:2-18-28-29,行駛 路程91.77km,耗 時(shí)4.79h,物資裝載率為87%;
k=4:26-23-24,行駛路程56.78km,耗時(shí)3.42h,物資裝載率為62%,車(chē)隊(duì)可減少2輛運(yùn)輸車(chē);
k=5:12-14-15-13-9,行駛路程86.05km,耗時(shí)5.15h,物資裝載率為95%;
k=6:4-8-7,行駛路程89.18km,耗時(shí)4.23h,物資裝載率為83%,車(chē)隊(duì)可減少1輛運(yùn)輸車(chē);
k=7:10-11,行駛路程68.15km,耗時(shí)3.20h,物資裝載率為83%,車(chē)隊(duì)可減少1輛運(yùn)輸車(chē);
k=8:30-1-3-5-6,行駛路程94.96km,耗時(shí)5.37h,物資裝載率為87%。
實(shí)際上按照該車(chē)輛調(diào)度方案8個(gè)車(chē)隊(duì)50輛運(yùn)輸車(chē)可以完成應(yīng)急運(yùn)輸任務(wù)。
應(yīng)急運(yùn)輸在應(yīng)急管理體系中具有基礎(chǔ)性支撐作用,各項(xiàng)應(yīng)急處置行動(dòng)對(duì)運(yùn)輸?shù)男枨笫瞧毡榈?,無(wú)論是救援行動(dòng)、衛(wèi)生醫(yī)療保障、重要生活物資保障、恢復(fù)生產(chǎn)生活秩序都離不開(kāi)高效的應(yīng)急運(yùn)輸保障。為提高軍隊(duì)完成應(yīng)急運(yùn)輸保障任務(wù)的能力,構(gòu)建了基于單邊時(shí)間窗的軍隊(duì)?wèi)?yīng)急運(yùn)輸車(chē)輛調(diào)度模型,目標(biāo)函數(shù)為帶時(shí)間懲罰函數(shù)的總路程最短,使用改進(jìn)遺傳算法進(jìn)行優(yōu)化求解,主要方法是交叉算子使用PMX算子和類(lèi)PMX算子,變異算子使用受災(zāi)點(diǎn)序列倒序變異結(jié)合斷點(diǎn)序列單點(diǎn)變異的方式,在自然選擇之前通過(guò)可行化算子將種群中的劣種轉(zhuǎn)化為良種。結(jié)果表明,該算法能夠保持優(yōu)良基因,較好地克服早熟收斂的問(wèn)題,得出了更精確、高效的車(chē)輛調(diào)度方案,有效保障了受災(zāi)點(diǎn)需求,能夠發(fā)揮軍隊(duì)組織指揮優(yōu)勢(shì)、快速反應(yīng)能力和運(yùn)輸投送能力,為我軍參與非戰(zhàn)爭(zhēng)軍事行動(dòng)的應(yīng)急運(yùn)輸決策提供了參考。