海鐵并行聯運戰略投送優化模型與算法

高忠印,王 諾

(大連海事大學交通運輸工程學院,遼寧大連 116026)

1 引 言

所謂戰略投送,通常是指將軍事力量快速投送到戰略前線的一種軍事行動[1].近年來,隨著兩岸統一呼聲的日益高漲,某大國軍艦多次進入臺灣海峽炫耀武力,一小撮臺獨分子也蠢蠢欲動,極力阻撓兩岸統一.在這一形勢下,開展戰略投送方案優化研究,在軍事上進行必要的準備,對于警告外國勢力,震懾臺獨,推動兩岸早日統一意義重大.

目前對戰略投送的研究已有一些成果,如戰略投送過程的常用模式[2,3],我國戰略投送面臨的問題及體系建設[4].在戰略投送的運輸方面,文獻[5–7]提出了增強海上和鐵路遠程運輸能力的有效方法,但這些研究僅僅是對戰略投送能力進行分析并給出相關建議,并沒有從定量的角度進行分析研究.關于戰略投送方案的優化模型,文獻[8,9]構建了應急中心選址及車輛安排的雙目標混合整數規劃模型;文獻[10]提出了情景推演貝葉斯網絡模型;文獻[11]針對災害情景中的應急運輸問題,建立了整數線性規劃模型.

海鐵并行聯運問題屬于多種運輸方式中下水港選擇及路徑尋優, 屬于特殊的選址–路徑優化問題(location-routing problem,LRP).關于LRP 問題的優化,文獻[12,13]針對選址–路徑優化問題的整數規劃模型采用兩階段啟發式算法進行求解;文獻[14]運用魯棒優化方法,將選址–路徑優化模型轉化為易求解的魯棒等價模型;文獻[15]將遺傳算法和局部迭代搜索算法相結合后對選址–路徑問題進行優化;文獻[16,17]提出一種自適應多種群的混合算法進行求解;文獻[18–20]考慮了選址–路徑優化方面的多重約束,先用聚類分析模型解決選址問題,然后設計算法求解;文獻[21]分析了配送中心的配送模式,建立了組合模型,并利用混合算法進行求解;文獻[22,23]介紹了LRP 問題擴展類型及其他優化方法;文獻[24]基于運輸方式的多樣性,建立了選址–多式聯運路徑優化模型,采用Dijkstra 改進算法和O-D 矩陣搜索算法進行求解;文獻[25]以總成本最低為目標,建立了混合整數規劃模型對多種運輸方式之間的選擇進行優化;文獻[26]建立了帶有時間約束的0-1 整數規劃模型來解決戰略投送網絡選址問題.

上述文獻為我國的戰略投送能力建設和方案優化提供解決思路,分析已有成果發現,盡管有關路徑優化的研究較多,但針對海鐵協同并進及聯運的路徑優化問題卻鮮有提及,尤其是在多種運輸方式協同運輸的優化算法上還缺少深入研究.與以往單一或多式聯運的運輸方式相比,本文需要解決的難點在于問題不僅包含有海鐵聯運,還包括海鐵協同并行運輸,變量較多,內容交叉,需綜合考慮各集結地、下水港(即始發港,下同)、上水港(即登陸港或終點港,下同)和終點站之間的相對距離來統籌優化.在投送過程中,海運下水港及海陸運輸路線難以選擇,船舶在港口的等待時間難以確定等,使其優化過程將更為復雜多變.需要優化的內容包括: 運輸方式和下水港的選擇,船舶航次數量、每個航次中的掛靠港以及每個掛靠港裝載人員和裝備數量的決策;鐵路專列班次數量、每個班次的中轉站以及每個中轉站裝載人員和數量的決策等等.針對上述問題,本文面向海鐵并行聯運開展戰略投送方案優化研究,其主要創新點有兩個:1)構建了既有海鐵并行又有聯運的路徑優化模型;2)對求解算法進行組合重構,將改進的禁忌搜索算法(TS)嵌入到遺傳算法(GA)之中,形成內外協同優化的集成算法(GTSA).為驗證所設模型和算法的有效性,以我國各戰區向東海前線投送為例進行分析,得到了較優方案.通過與其他算法進行對比以及敏感性分析,證明了本文算法在解決此類問題上的有效性.

2 海鐵并行聯運戰略投送優化模型

2.1 基本問題

為進行戰略上的軍事裝備,需要向指定地點緊急運送軍事力量.由于戰略投送的人員和重型裝備(以下簡稱為裝備)在數量上均較大,而鐵路運輸所需的專用車輛數量有限,若全部采用鐵路運輸會受到專用列車數量的限制,導致等待時間增長,所需的運輸時間增加;同樣,全部采取海運也會受到滾裝船數量的限制.因此,考慮到我國北方地區海上運輸較為便利,故采取海鐵協同并進的運輸方式,即有的集結地選擇海鐵聯運方式,有的選擇完全由鐵路運輸,兩種方式的運量相互協調,以達到整體戰略投送時間最短的最佳效果.在具體操作上,若選擇海鐵聯運方式,則需要利用鐵路運輸將該集結地的人員和裝備運輸至指定下水港,同時在下水港附近調用商用客貨滾裝船(以下簡稱船舶).投送時,船舶需要趕到指定的下水港,進行裝載后到達指定地區的登陸港.若選擇完全以鐵路運輸方式,則需征調適宜裝備和人員運輸的專用車輛.投送時,專用車輛需要趕到運輸集結地,裝載后組成專列到達指定地區的鐵路終點站.如此循環往返,直至所有裝備和人員投送至指定地區.

由上述過程可知,本文構建的海鐵協同并進的戰略投送是由不同運輸方式選擇、海上運輸優化和鐵路運輸優化3 部分內容構成.在優化過程中,海上運輸與鐵路運輸是相互影響的兩個方面: 如全部選擇海上運輸,則船舶需多次往返,鐵路運輸能力未充分利用,運輸時間增加;如全部選擇鐵路運輸,則專列需多次往返,海上運力沒有充分利用,運輸時間也將增加,如何在這兩種運輸方式之間優化平衡是需考慮的第1 個問題.對于海上通道的選擇,若各戰區出發時都以距離最近的港口出海,則會導致船舶靠離泊頻繁,海上運輸的時間將隨之延長;而若選擇少數港口出海,則陸上的運輸時間將延長,這是兩難的抉擇,如何選擇并縮減下水港的數量是第2 個問題.另外,對船舶及專列的運輸量、航次或班次數量及航線或路線等如何確定是第3 個問題.綜上所述,如何解決上述3 個問題是本文所要研究的內容.

2.2 符號設定

為了便于描述,現將模型所需參數和變量的符號設定及含義列于表1 和表2 中.

表1 模型參數的符號設定及含義解釋Table 1 Symbol setting and meaning interpretation of model parameters

表2 決策變量的符號設定及含義解釋Table 2 Symbol setting and meaning interpretation of decision variables

2.3 海上運輸時間

由以上分析,設船舶s第n個航次在始發港的離港時刻為

船舶s第n個航次在第1 個下水港的離港時刻為

同理,船舶s第n個航次在第2 個下水港的離港時間為

從而,船舶s第n個航次在第k個下水港的離港時刻為

由此可知,船舶s完成所有投送任務的時間為

其中式(5)表示船舶s完成投送任務的總時間由靠離泊時間、海上航行時間、港口等待時間以及港口裝卸時間4 個部分組成.

2.4 鐵路運輸時間

設專列r第b個班次從始發站離開的時刻為

專列r第b個班次從始發站出發經過第1 個集結地的離站時間為

同理,專列r第b個班次在經過第2 個集結地的離站時間為

從而,專列r第b個班次在經過第x個集結地的離站時間為

由此可知,專列r完成所有投送任務的時間為

其中式(10)表示專列r完成投送任務的總時間由行駛時間以及裝卸時間2 個部分組成.

2.5 海鐵聯運優化模型

根據以上分析,構建海鐵聯運優化模型如下

以上模型中,式(11)為目標函數,表示以最短的時間完成海鐵協同并進的戰略投送任務;約束條件(12)表示每艘船舶各航次途徑下水港所裝載的人員不超過船舶的最大載人量;約束條件(13)表示每艘船舶各航次途徑下水港所裝載的裝備不超過船舶的最大載貨量;約束條件(14)表示每列專列各班次途徑集結地所裝載的人員不超過專列的最大載人量; 約束條件(15)表示每列專列各班次途徑集結地所裝載的裝備不超過專列的最大載貨量; 約束條件(16)表示船舶會服務所有被選為下水港的港口; 約束條件(17)表示每個集結地要么選擇海鐵聯運,要么選擇鐵路專列進行運輸;約束條件(18)表示每一下水港對每艘船舶每個航次僅接受服務1 次; 約束條件(19)表示每1 集結地對每列專列每個班次僅接受服務1 次; 約束條件(20)和約束條件(21)表示所有集結地的人員和裝備必須全部投送至目的地.

3 算法設計

本文所建模型變量數目眾多、各變量之間的關系縱橫交貫,情況復雜,為了快速準確的求解,需針對本文模型的特點構建行之有效的算法.雖然遺傳算法全局尋優能力較強,但在針對復雜問題時存在搜索速度慢、穩定性差及早熟的缺點.禁忌搜索算法采用一種獨特的記憶功能(禁忌表),通過對最近的搜索過程進行記錄來指導下一次搜索的方向,從而避免無效的循環搜索,具有較強的局部搜索能力,但此算法運行機理較為簡單,在求解復雜問題時效率會有所下降.綜上所述,單一智能優化算法雖各有優勢,但在優化海鐵協同并進的戰略投送這種復雜問題時,由于運算量過大,在參數的選擇上要求苛刻,過于依賴初始值,因而在條件不理想時將很難快速獲得全局最優的結果.針對此類問題,本文充分利用遺傳算法較好的全局搜索能力以及禁忌搜索算法較強的局部搜索能力等優勢,并對不足之處進行改進,以期獲得運行速度快、計算準確度高、結果穩定性好的求解算法.

本文的算法設計是,將基于仿真的禁忌搜索算法嵌入到遺傳算法當中,通過內外之間的協同優化,最終得到最優解.具體做法是: 在外層遺傳算法中以染色體表達陸上集結地選擇的運輸方式以及選擇的下水港編號,將外層的染色體信息(包括下水港的編號、集結地的編號)傳至內層,內層的禁忌搜索算法根據傳入的信息對船舶的航次數量、每個航次的掛靠港、每個掛靠港所裝載的人員和裝備數量以及專列的班次數量、每個班次的中轉站、每個中轉站所裝載的人員和裝備數量進行優化,結合海上運輸時間與鐵路運輸時間計算出目標函數值,再將結果傳至外層,利用外層遺傳算法進行優化,直至算法收斂為止,具體算法步驟如下:

步驟1開始;

步驟2初始化種群;

步驟3讀取種群中的染色體,獲取下水港的編號以及集結地編號,并計算各下水港集結人員和裝備的數量;

步驟4獲取下水港的編號以及集結地的編號生成禁忌搜索算法初始解;

步驟5利用仿真計算初始解的運輸時間;

步驟6判斷是否滿足禁忌搜索終止條件,若滿足,則轉向步驟9,否則進行下一步驟;

步驟7在初始解的鄰域中選取滿足禁忌表要求的可行解作為候選集;

步驟8在候選集中選擇一個運輸時間最短的解,并更新禁忌表,返回步驟5;

步驟9計算個體的適應度值;

步驟10判斷遺傳算法的終止條件是否滿足,若滿足則轉向步驟,否則進行下一步驟;

步驟11對種群中個體進行選擇、交叉、變異,產生新一代種群后轉向步驟3;

步驟12輸出最優解;

步驟13結束.

3.1 基于運輸方式選擇的遺傳算法設計

1)染色體

設各集結地待運送的人員和裝備數量數據見表3.

表3 各集結地待運輸的人員和裝備數量Table 3 The number of personnel and equipment to be transported in each staging area

首先,以染色體中基因的索引值表示集結地編號,基因表示運輸方式以及下水港的選擇情況.其次,在生成遺傳算法初始解過程中,由于內陸集結地明顯不宜采用海運,為了縮小算法的搜索空間,可以基于啟發式規則生成初始解.圖1 表示1 條可能的染色體,其含義為1#號和2#號集結地的人員和裝備選擇1#號港口出海,3#號和4#號集結地的人員和裝備選擇2#號港口出海,5#,6#,7#,8#,9#號集結地選擇鐵路專列運輸至目的地.由該染色體表示的各下水港及各集結地的對應的人員和裝備信息如表4 和表5 所示.

圖1 染色體表達式Fig.1 Chromosome expression

表4 各下水港的人員和裝備數量Table 4 The number of personnel and equipment in each launching port

表5 各集結地的人員和裝備數量Table 5 The number of personnel and equipment in each staging area

2)適值函數

對于遺傳算法得到的每條染色體,其適值函數定義為

其中Cmax是一個較大的正數,它保證適應度非負;適應度越大,其保留下來的概率就越高.

3)交叉和變異

在交叉操作中,首先對父代的染色體進行兩兩配對,然后通過計算機隨機產生交叉位進行交叉,得到新的染色體,如圖2 所示.在變異操作中,采用換位變異的方法,即通過計算機隨機產生兩個基因索引值,然后互換這兩個索引值位置上的基因,如圖3 所示.

圖2 染色體交叉Fig.2 Chromosome crossing

圖3 染色體變異Fig.3 Chromosomal variation

3.2 基于路徑優化的禁忌搜索算法設計

根據上文分析, 海上運輸和鐵路運輸的優化包括船舶(專列)的航(班)次數量、各航(班)次路線、各航(班)次承載的人數和裝備數量等多項內容,解空間十分復雜.本文采取在得到禁忌搜索算法的1 個解時,利用仿真過程來計算該解所對應的海上運輸及鐵路運輸的時間,將其作為禁忌搜索算法中解的評價標準.

使用遺傳算法得到的染色體中選擇的下水港編號及使用專列運輸的集結地編號作為禁忌搜索算法的初始解,為區分下水港和集結地,在該染色體中間添加0 以表示分割.圖1 中染色體表示的禁忌搜索算法的初始解如圖4 所示,該染色體表示海上運輸過程中選擇下水港的優先級排序為1>2,鐵路運輸過程中選擇集結地的優先級為5>6>7>8>9.

圖4 初始解Fig.4 Initial solution

由于傳統的禁忌搜索算法難以滿足本文的模型,因此需要對算法嵌入計算運輸時間的仿真過程,更改傳統的鄰域操作為分隔鄰域操作等幾個方面進行改進,具體如下.

1)仿真過程

根據解的表示信息以及約束條件(12)至約束條件(21),對船舶各航次的掛靠港、掛靠順序、裝船量以及專列各班量以及專列各班次經過的集結地、行駛路線和裝車量等進行仿真,得出該解所對應的運輸時間,具體過程為:

(a)按照當前解所表達的優先級,對有關船舶(專列)先選擇優先級較高的下水港(集結地);

(b)在不超過船舶和鐵路專列最大裝載量的前提下盡可能滿載,但如果人員和裝備中的有一項達到滿載,則船舶和鐵路專列則應出發進入啟運.

計算運行時,需要對解不斷進行評價,以便在迭代過程中不斷獲得質量更優的解.具體做法是隨時判斷所尋求的運輸路徑方案是否滿足問題的約束條件,同時計算出該方案的運輸時間,在滿足問題約束條件的前提下得到的運輸時間越短,解的質量越高.

2)分隔鄰域操作

由于本文設計的內層禁忌搜索算法的初始解與外層遺傳算法所傳入的染色體有關,而傳統的鄰域操作方式會將解中的下水港和集結地之間進行交換,有可能改變解的信息結構,因此需將傳統的鄰域操作方法改成分隔鄰域操作,使得下水港之間以及集結地之間的交換相互獨立.例如,對于S=12056789 的解,隨機產生的結果為第1 位基因與第2 位基因進行交換和第5 位基因與第7 位基因進行交換,實施交換后可得到原解的一個“鄰居”S′=21058769,具體步驟見圖5

圖5 分隔鄰域操作Fig.5 Separate neighborhood operation

3.3 計算步驟

步驟1根據遺傳算法染色體所表達的信息,生成禁忌搜索算法的初始可行解x0;

步驟2選取初始可行解x0和禁忌表H,記當前最優解為xbest=x0;

步驟3根據得到的可行解,按照仿真原則和約束條件對船舶的航次數量、各航次掛靠港、掛靠順序、裝船量等信息及專列的班次數量、各班次中轉站、各班次行駛路線和裝車量等信息進行仿真計算;

步驟4根據仿真結果,計算船舶運輸時間和專列運輸時間;

步驟5若此時已滿足禁忌搜索算法終止條件,停止計算,輸出最優解所對應的船舶航次數量、各航次掛靠港、掛靠順序、裝船量及專列的班次數量、各班次行駛路線和裝車量,進入下一步.否則,在xbest的鄰域N(xbest)中選取滿足禁忌表要求的可行解作為候選集N′(xbest),在候選集N′(xbest)中選擇一個總運輸時間最短的解x1,令xbest=x1,更新禁忌表H,返回步驟3;

步驟6將計算得到的船舶運輸時間和鐵路專列運輸時間中的最大值作為當前解的適應值返回給遺傳算法框架;

步驟7若此時已滿足遺傳算法終止條件,停止計算,進入下一步.否則,重新進行選擇、交叉、變異生成新一代種群,然后返回步驟1;

步驟8結束.

4 實例分析

4.1 背景及數據

現以從我國北部、中部和東部戰區各集結地利用海鐵協同并進的運輸方式向東海前線的寧波市進行戰略投送為例,其集結地為長春等9 個地區,根據上級要求,需投送的人員和裝備的數量見表6.

表6 各集結地待運輸的人員和裝備數量Table 6 The number of personnel and equipment to be transported in each staging area

假設集結人員和裝備的時間為3 d,陸上行進的速度平均為60 km/h;大連港、天津港和青島港可作為下水港供方案優化時選擇;已調集3 艘船舶(以下簡記為船舶1#、船舶2#和船舶3#)及三列專列(以下簡記專列1#、專列2#和專列3#).船舶的出發地均為大連港,船舶承載能力為人員1 400 人,裝備200 臺,人員上下船的速度為1 min/人,裝備裝卸的速度為10 min/臺; 考慮到天氣的影響,船舶的平均航速設為16 節,如遇到不利天氣耽擱,可適當提高船舶航行速度以滿足計劃船期;船舶航行前的安全檢查需2 小時,靠離泊作業各需1 h.專列的承載能力為人員500 人, 裝備80 臺, 人員上下車的速度為10 s/人, 裝備裝卸的速度為10 min/臺,平均速度60 km/h;專列出行前的安全檢查需1 h,其他有關計算的參數如表7 至表9.

表7 陸上各集結地至下水港之間的距離/kmTable 7 The distance between land staging areas and launching ports/km

表8 各港口之間的海上距離/n mileTable 8 Maritime distance between ports/n mile

表9 各城市之間的陸上距離/kmTable 9 Land distance between cities/km

4.2 計算結果及分析

本文使用Python 語言編程,選用處理器為inter(R)i7-8750H,內存為8G 的計算機計算.遺傳算法種群規模選為100,交叉概率0.7,變異概率0.02;禁忌搜索算法迭代次數為10 次,候選集個數為5,禁忌表長度為5.經計算得到完成全部投送任務共需24.14 d,運輸方案為從長春和沈陽出發的選擇由大連港出海;從天津和石家莊出發的由天津港出海;從濟南和徐州出發的由青島港出海;從鄭州、太原和合肥出發的選擇由鐵路專列運輸.

海上船舶運輸的方案優化為:編號為1#船舶在第1 個航次從大連港承載1 400 人和200 臺裝備運到寧波港;其第2 個航次返回青島港承載1 400 人和200 臺裝備再運到寧波港;編號為2#船舶在第1 個航次先從大連港承載700 人和100 臺裝備,然后再從天津港承載700 人和100 臺裝備運抵目的地寧波港;此后的第2 個航次則從青島港承載700 人和100 臺裝備再運抵寧波港;編號為3#船舶從大連港空載出發到天津港承載1400 人和200 臺裝備后再運到寧波港(表10 和表11).

表10 下水港選擇方案Table 10 Launching port selection plan

表11 鐵路運輸方案Table 11 Railway transportation plan

專列的運輸方案為:專列1#的第1 個班次從太原承載500 人和80 臺裝備后行駛至寧波;第2 個班次從鄭州承載500 人和80 臺裝備后行駛至寧波;第3 個班次從鄭州承載150 人,中轉合肥承載350 人和80 臺裝備后行駛至寧波;專列2#的第1 個班次從太原承載500 人和80 臺裝備后行駛至寧波;第2 個班次從鄭州承載500 人和80 臺裝備后行駛至寧波;第3 個班次從合肥承載350 人和20 臺裝備后行駛至寧波;專列3#第1 個班次從太原承載400 人和40 臺裝備,中轉鄭州承載100 人和40 臺裝備后行駛至寧波;第2 個班次從鄭州承載500 人和50 臺裝備后行駛至寧波(表10 和表12),運輸路線如圖6 所示,計算收斂過程如圖7 所示.

圖7 本文算法運行過程性態示意圖Fig.7 Schematic diagram of the running process of the algorithm

表12 海上運輸方案Table 12 Maritime transportation plan

圖6 東海戰略投送運輸圖Fig.6 Strategic delivery map for the East China Sea

4.3 算法比較

本文用模擬退火算法(SA)及遺傳算法(GA)的計算結果與本文算法(GTSA)進行對比, 其中模擬退火算法初始溫度為1 000 度,蒙特卡洛內部循環為50 次; 遺傳算法種群規模為100,交叉概率為0.7,變異概率為0.02.另外,為了進行敏感性分析,本文采用四個不同的算例規模分別計算10 次,設N=1 即為4.1 節的基本數據,N=2 時,將人員和裝備數量均增加至2 倍,以此類推.測試環境均在處理器為inter(R)i7-8750H,內存為8G 的計算機上進行.結果顯示, 在4 組算例中, 本文算法相對于模擬退火算法和遺傳算法在運行時間上分別減少了4.96%～16.44% 和12.31%～20.39%; 在優化結果上分別改善了7.65%～10.48%和1.44%～6.14%;在算法穩定性上分別提高了50.74%～95.94 ˙%和5.33%～89.07%.在不同計算規模上,本文算法在計算時間、優化結果和計算穩定性等各方面均優于模擬退火算法和遺傳算法.算法對比結果列于表13,其中不同規模下GTSA 與GA 的收斂曲線見圖8.

表13 不同算法結果對比Table 13 Comparison of different algorithms

圖8 不同規模下GA 與GTSA 收斂對比圖Fig.8 Comparison of GA and GTSA convergence at different scales

此外,為進一步驗證本文算法的有效性,將文中實例的數據帶入CPLEX 軟件進行求解.結果顯示,當集結地及下水港的數量不變,僅增加投送規模時,本文算法求解的精度略低于CPLEX 的結果,但求解速度遠快于上述軟件(表14).進一步地,當集結地及下水港的數量增多時,上述軟件的運行便發生困難,以至于難以求出最優解,而本文算法則仍可以在較短的時間內完成計算.

表14 本文算法與CPLEX對比結果Table 14 Comparison of the algorithm and CPLEX

續表13Table 13 Cotinues

5 結束語

與傳統的LRP 問題相比,海鐵協同并進的戰略投送需解決運輸方式和下水港的選擇、船舶運輸路線優化和專列運輸路線優化等問題,其中混合著船舶的裝船量、專列的裝車量等約束條件,因而使得海鐵協同并進的求解更為復雜.

為更有效地求解上述問題,本文以遺傳算法解決運輸方式和下水港選擇問題;以禁忌搜索算法優化船舶和鐵路專列的運輸路線問題;利用仿真分別計算海上運輸時間和陸上運輸時間,通過內外層之間的協同優化,最終求得優化后的方案.最后,以我國向東海地區戰略投送為例,得到運輸時間最短的運輸方案,說明以本文模型和算法求解此類問題是合理且有效的.通過與其他算法進行對比以及靈敏度分析,顯示出本文算法在不同規模中均能在更短的時間內得到更優質的解,且具有更好的穩定.

需要指出的是,本文模型主要解決在正常約束條件下的戰略投送問題,而在緊急情況下,由于軍情是壓倒一切的,實際中如需要可對部分道路、橋梁、車站、碼頭等交通設施實施軍事管制,此時已有的常規性交通法規等約束將暫時失效,船舶和專列的調用將大大加快,相應的優化模型也將調整,如何解決此類問題是下一步的研究內容.