張恩澤, 高 毅， 張 輝

(1.95486部隊；2.96756部隊；3.火箭軍工程大學(xué) 基礎(chǔ)部，陜西 西安 710025)

1 問題描述與分析

現(xiàn)代大型軍事行動中采取聯(lián)合投送[1-5]的方式進(jìn)行運輸傳送，但由于聯(lián)合投送具有距離遠(yuǎn)、任務(wù)多、道路約束強(qiáng)等特點，在投送方案的選取上具有較大的挑戰(zhàn)性。現(xiàn)考慮通過鐵路和公路兩種方式對多個編組進(jìn)行投送，每個編組由若干梯隊組成。計劃編成若干個梯隊，對梯隊進(jìn)行編組，通過公路、鐵路兩種方式運輸。聯(lián)合投送規(guī)則如下：

1)在運輸?shù)倪^程中，編組不允許在中間路段、節(jié)點停留，同一個編組只能選擇同一條投送線路，如果需要進(jìn)行線路轉(zhuǎn)換，只允許存在鐵路轉(zhuǎn)公路的情況，并且最多轉(zhuǎn)運一次。設(shè)有A、B、C三種編組類型，若目的地相同，規(guī)定必須B型編組全部梯隊都到達(dá)后才允許其他編組進(jìn)入，而對于A型編組而言，優(yōu)先考慮鐵路運輸。

2)一個編組的投送時間應(yīng)當(dāng)保持連續(xù)，如果該編組當(dāng)天未完成投送任務(wù)，則第二天繼續(xù)進(jìn)行該編組的投送，直到該編組投送完畢再進(jìn)行下一編組的投送。

3)每一個路段都有相應(yīng)的最大投送能力，每天通過各節(jié)點進(jìn)入該路段的總梯隊數(shù)不能超過其最大投送能力。一旦超過最大投送能力則立即關(guān)閉，第二天再開啟投送通道。

4)投送起點和終點、從鐵路轉(zhuǎn)運到公路時分別要進(jìn)行裝卸載，整個裝卸載的耗時忽略不計。鐵路上每天的裝、卸載最大梯隊數(shù)為15梯隊，公路為10梯隊。

假設(shè)投送方式的轉(zhuǎn)換只能發(fā)生在節(jié)點，且節(jié)點處的場地、設(shè)施滿足運輸方式轉(zhuǎn)換的要求，不考慮實時路況對聯(lián)合投送過程中的影響，不考慮車輛損壞、交通事故等意外事件的發(fā)生，不考慮惡劣天氣等自然因素對聯(lián)合投送的影響，同時道路負(fù)荷不會引起道路中斷。根據(jù)任務(wù)設(shè)計合理的聯(lián)合投送方案，在設(shè)計投送方案的時候需要考慮到總?cè)蝿?wù)完成時間、各編組投送時間、總投送里程、道路負(fù)荷等因素。

由于作戰(zhàn)物資的投送分為三種編組類型，每種編組類型包含若干出發(fā)節(jié)點和目的節(jié)點不同的編組，而每個編組又包含若干梯隊。由于每個路段的最大投送能力不同，每個節(jié)點裝、卸載梯隊數(shù)也不盡相同，而且每個節(jié)點有多個可供選擇的下一路段，因此總?cè)蝿?wù)完成時間由各編組投送時間決定，總的投送里程由各編組投送里程決定，道路負(fù)荷則受到各編組路徑選擇的影響。需要解決的問題是：綜合考慮總?cè)蝿?wù)完成時間、各編組投送時間、總投送里程以及道路負(fù)荷等因素，給出最優(yōu)的投送方案。

對于此問題，首先將物資的聯(lián)合投送問題抽象為由節(jié)點以及連接節(jié)點的弧(即節(jié)點之間的路段)構(gòu)成的有向虛擬網(wǎng)絡(luò)圖，該網(wǎng)絡(luò)圖的每條弧上都賦予了非負(fù)的權(quán)值；其次建立路徑優(yōu)化模型，然后將每段路的最大投送能力看作是容量，而得到最優(yōu)投送方案需要考慮的總?cè)蝿?wù)完成時間、各編組投送時間、總投送里程等因素則看作是費用，因此可以采用最小費用最大流算法進(jìn)行求解。當(dāng)不同編組路徑發(fā)生沖突時，則采用排隊論思想或次優(yōu)解的方法進(jìn)行求解，最終將其轉(zhuǎn)化為一個帶有時間約束、里程約束和容量限制的最短路徑優(yōu)化問題。在對不包含負(fù)權(quán)環(huán)路的情況下，可以先構(gòu)造鄰接矩陣，再利用Warshall-Floyd算法[6]求解出單個編組的最優(yōu)解，然后利用自適應(yīng)遺傳算法[6]對所有找到的單個編組的解進(jìn)行優(yōu)化，最終得出綜合所有因素后的全局最優(yōu)解，求解流程圖如圖1所示。

圖1 問題求解流程圖Fig.1 Flow chart of problem solving

2 路徑優(yōu)化設(shè)計模型與算法

由聯(lián)合投送要求及對問題的分析，采用Warshall-Floyd算法和自適應(yīng)遺傳算法對投送方案進(jìn)行求解。要遵循一些原則從而達(dá)到提高聯(lián)合投送的效率、降低投送成本的目的，具體包括充分利用道路資源原則、時間和里程綜合最優(yōu)原則、任務(wù)需要原則等。這是一個多式聯(lián)合投送問題，需考慮運輸方式對最優(yōu)解的影響，如圖2所示。A、B、C三種編組出發(fā)時路徑、投送方式、每天發(fā)出的梯隊數(shù)均可以不同，且起點、終點也可以不同，所以在對其建立模型時要分層次進(jìn)行，用約束條件分別對不同編組進(jìn)行模型建立，然后再綜合優(yōu)化進(jìn)而得出全局最優(yōu)解。

圖2 多式聯(lián)合投送路徑圖Fig.2 Multi-type joint delivery path graph

由于交通信息復(fù)雜，可抽象簡化將投送路線網(wǎng)看作是一個虛擬網(wǎng)絡(luò)，交叉路口、車站或城市看作是節(jié)點得到投送路線網(wǎng)絡(luò)圖，投送過程中每個編組有不同的起點和終點以及中間點。

建立多個編組聯(lián)合投送的數(shù)學(xué)模型要求解的路徑較多，且要綜合考慮到運輸方式的選擇、投送時間及道路負(fù)荷等影響因素，同時不同編組可能在同一路段上發(fā)生沖突，因此在求解過程中要劃分層次，逐個解決。單個編組考慮的最優(yōu)路徑是局部最優(yōu)，但現(xiàn)在需要綜合考慮不同編組路徑的組合是全局最優(yōu)。由于局部最優(yōu)解的線性組合無法代表綜合最優(yōu)解，所以首先得到排名靠前的十組次優(yōu)解，然后利用自適應(yīng)遺傳算法在這些次優(yōu)解中優(yōu)化得出綜合最優(yōu)解。

2.1 A型編組的路徑最優(yōu)模型

單個編組在投送過程中的最優(yōu)方案與路段的最大投送能力、投送時間、投送里程有著密切的關(guān)系。將影響投送的因素作為求解最優(yōu)路徑的權(quán)值賦給每條路段，建立模型

懲罰因子為

若選擇公路，ω將會使得出的解變大，不滿足最優(yōu)的思想，這樣就可以將優(yōu)先走公路的路徑篩除；而選擇鐵路時，不會對求解最優(yōu)路徑造成影響，懲罰因子ω用來保證A型編組優(yōu)先選擇且充分利用鐵路。

根據(jù)實際需要，里程和時間指標(biāo)的重視程度需要進(jìn)行分配，取α=0.45，β=0.55。因為不同權(quán)重的量綱和數(shù)量級有所差異，為屏蔽數(shù)值量綱差異，確保求解結(jié)果的可靠性，需將里程d和時間t進(jìn)行歸一化處理,得模型

約束條件為

約束條件1)～ 3)分別表示網(wǎng)絡(luò)中起點、中間點及終點為滿足得到一條從起點到終點的完整路線；約束條件4)是用來篩選得到的解中滿足只能由鐵路轉(zhuǎn)為公路，且至多轉(zhuǎn)運一次；約束條件5)表示從任意節(jié)點vi出發(fā)只能選擇一種運輸方式，對同一編組只能選擇同一條投送路線進(jìn)行了限制；約束條件6)可以保證單個編組在運輸方式上的連續(xù)性。

2.2 B、C型編組的最優(yōu)路徑

在求解B、C型編組的最優(yōu)路徑中，求解思路與A型編組的方法類似，且同樣要進(jìn)行歸一化處理，但B、C型編組沒有充分利用鐵路的要求，因此對于B、C型編組的求解不需要利用懲罰因子ω對運輸方式篩選，模型為

C型編組在求解過程中的約束條件與A型編組基本一致，故可直接利用上述A型編組的約束條件對B、C型編組進(jìn)行約束，然后根據(jù)模型解得B、C型編組的10組次優(yōu)解。

2.3 綜合優(yōu)化所有次優(yōu)解，得出全局最優(yōu)解

在得出所有次優(yōu)解后，綜合所有編組，考慮到總投送時間要最短，建立如下模型(如圖3)：

滿足的約束條件為

11)∑i,jktsBijvij≤∑i,jktsAijvij；

12)∑ijktsBijvij≤∑ijktsAijvij,

其中決策變量為

約束條件7)～9)保證投送過程中通過起點、終點和轉(zhuǎn)運點的梯隊數(shù)不超過節(jié)點每天允許的裝卸載梯隊數(shù)；約束條件10)保證每天通過節(jié)點進(jìn)入路段的總梯隊數(shù)不超過該路段的最大投送能力；約束條件11)和12)保證多個編組目的地相同時，所有B型編組全部到達(dá)后，其他編組才能進(jìn)入。

圖3 隨機(jī)次優(yōu)解路徑圖Fig.3 Path table of stochastic suboptimal solution

3 模型求解

假設(shè)有29個鐵路節(jié)點和29個公路節(jié)點，共計58個節(jié)點。對于不包含負(fù)權(quán)環(huán)路，先構(gòu)造58×58的鄰接矩陣，再利用Warshall-Floyd算法求解出單個編組的最優(yōu)解，然后利用自適應(yīng)遺傳算法對所有找到的單個編組的解進(jìn)行優(yōu)化，最終得出綜合所有因素后的全局最優(yōu)解。

3.1 Warshall-Floyd算法求解局部最優(yōu)解

對于58×58鄰接矩陣，對于其中實際不存在的節(jié)點，令其與剩余任何節(jié)點的里程距離和時間距離都為無窮大，對于實際存在連接關(guān)系的公路與公路節(jié)點，鐵路與鐵路節(jié)點，它們間的距離和時間按照實際里程距離和實際時間距離構(gòu)造。考慮到公路不能轉(zhuǎn)鐵路而鐵路可以轉(zhuǎn)公路，則令鐵路到公路里程距離和時間距離為0，令公路到鐵路的里程距離和時間距離為無窮大。再根據(jù)帶權(quán)重的時間距離和里程距離，采用Warshall-Floyd算法求解最短路徑，為了避免局部最優(yōu)無法代表全局最優(yōu)，現(xiàn)對每一個編組保留較短的10條路徑，作為后續(xù)算法的輸入?yún)?shù)。

3.2 用自適應(yīng)遺傳算法求解全局最優(yōu)解

現(xiàn)采用自適應(yīng)遺傳算法，以每個編組保留的10條路徑為對象，綜合考慮所有約束條件，對所有編組進(jìn)行全局優(yōu)化，最終得出最優(yōu)解，如圖4～圖7所示。

染色體編碼：每一個染色體作為一個可行解，存儲在一個元胞數(shù)組Chorm中，Chorm{:,1}存儲21個編組的路徑信息，Chorm{:,2}存儲21個編組的投送出發(fā)時間，出發(fā)時間以及每天投送量依據(jù)各段道路的承載能力和各個路段耗時情況，按照避免擁塞和超過載荷的原則，對每天的投送量按短板效應(yīng)原則分配，Chorm{:,3}存儲對應(yīng)21個編組得選擇方案來自于Top_10的索引位置。

圖4 最優(yōu)解示意圖Fig.4 Schematic chart of optimal solution

圖5 優(yōu)化過程1Fig.5 Optimization process 1

圖6 優(yōu)化過程2Fig.6 Optimization process 1

圖7 各個路段利用甘特圖Fig.7 Gantt table of each section used

優(yōu)先級計算：考慮到目的地相同的有四組，其中每組中都有一個B型編組，并且當(dāng)多個編組的目的地相同時B優(yōu)先級最高，然后根據(jù)沖突數(shù)量衡量編組優(yōu)先級，沖突多的為了不影響其他編組的投送，故沖突多的優(yōu)先級高。所以先給B進(jìn)行優(yōu)先級排序，對每一個染色體的21個編組進(jìn)行沖突預(yù)運算，計算每一個編組中所有路段在其他的重復(fù)情況，并以重復(fù)量作為編組出發(fā)順序的依據(jù)。

適應(yīng)度計算：建立一個118×N的路段容量記錄器，按照計算的優(yōu)先級順序投送編組，并實時更新路段容量記錄器的容量，在投送下一個編組時，也按照前段投送原則，如果路段擁堵不能投送，則推遲發(fā)送時間，當(dāng)超過預(yù)設(shè)的時間后則不再投送，按優(yōu)先級順次到鄰近編組進(jìn)行投送，并將二者優(yōu)先級對調(diào)，每執(zhí)行完一次投送都要清空編隊未投送標(biāo)志。當(dāng)所有標(biāo)志位都清空時，此時的所得值就是最終的投送時間消耗量，該時間消耗量就可以代表適應(yīng)度。

交叉操作：獲取Chorm{:,3}的所有編組代號，根據(jù)編組適應(yīng)度值自動選取合適的交叉概率Pc對相鄰的兩個染色體相同位置的編組號進(jìn)行交叉，交叉長度隨機(jī)生成。

變異操作：根據(jù)編組適應(yīng)度值自動選取合適變異概率Pm對每一個染色體編碼隨機(jī)選擇位置進(jìn)行變異操作。

選擇操作：按照設(shè)定的代溝GGap將新產(chǎn)生的個體和原種群中適應(yīng)度高的插入到原種群中得到新的種群。

最后根據(jù)上述算法，利用MATLAB編程求得A、B、C型編組的最優(yōu)路徑設(shè)計方案，如表1所示。

表1 聯(lián)合投送最優(yōu)路徑設(shè)計求解結(jié)果

4 小結(jié)

本文研究了聯(lián)合投送最優(yōu)聯(lián)合投送路徑規(guī)劃方案問題，提出基于協(xié)同進(jìn)化的自適應(yīng)遺傳算法進(jìn)行模型求解，較好地解決了易陷入局部最優(yōu)解、收斂速度慢的問題。對整個聯(lián)合投送作戰(zhàn)地域進(jìn)行劃分，充分考慮總?cè)蝿?wù)完成時間、各編組投送時間、總投送里程、道路負(fù)荷等因素，引入帶有混合時間窗的懲罰函數(shù)，建立聯(lián)合投送路線管理模型，優(yōu)化聯(lián)合投送路徑安排，逐步優(yōu)化了聯(lián)合投送路徑?？紤]到任務(wù)需要，指揮員可能對時間或?qū)囕v行駛里程重視程度不同，故用相對權(quán)重α和β對其進(jìn)行了分配，可以靈活地改變它們的取值來對投送方案進(jìn)行重新制訂，具有較強(qiáng)的戰(zhàn)場適應(yīng)能力。事實上，該問題也可應(yīng)用于運輸網(wǎng)絡(luò)等諸多領(lǐng)域，如民用海港口集裝箱航線運輸?shù)?，進(jìn)一步研究可用于未來戰(zhàn)場中“陸—海—空”聯(lián)合作戰(zhàn)的物資投送，提高模型的精確程度后可為我國國防領(lǐng)域提供理論支撐與技術(shù)支持，具有較強(qiáng)的理論價值與現(xiàn)實意義。