基于自適應(yīng)遺傳算法的聯(lián)合投送路徑優(yōu)化設(shè)計(jì)研究

張恩澤, 高 毅， 張 輝

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

1 問(wèn)題描述與分析

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

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

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

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

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

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

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

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

圖1 問(wèn)題求解流程圖Fig.1 Flow chart of problem solving

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

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

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

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

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

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

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

懲罰因子為

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

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

約束條件為

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

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

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

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

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

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

滿(mǎn)足的約束條件為

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

12)∑ijktsBijvij≤∑ijktsAijvij,

其中決策變量為

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

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

3 模型求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

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