節(jié)約算法融合遺傳模型在救援工作中的應(yīng)用

劉志華

（山東省青島市消防救援支隊，山東 青島 266000）

在險情救援過程中，不僅要保證救援人員和救援物資順利送達，還要在保證送達的前提下，盡可能減少配送時間[1]。為了縮短配送時間，需要縮短單車配送距離，從而增加配送車輛，增加救援成本。為了降低救援成本，需要減少配送車輛，延長單車配送距離，這可能會導(dǎo)致救援不及時問題[2]。因此，險情救援過程中需要解決的問題是在保證及時救援的同時有效控制救援成本。根據(jù)大量案例可知，救援配送的每個環(huán)節(jié)不僅關(guān)系密切，而且相互間也有復(fù)雜的關(guān)系。必須建立合理的供應(yīng)鏈，建立科學(xué)的定量分析模型，明確救援成本的控制范圍[3]。降低救援配送總成本不能只從一個角度出發(fā)，而是要綜合考慮影響救援配送過程的所有因素，根據(jù)優(yōu)先級順序為每個分項成本設(shè)定合理的權(quán)重，然后根據(jù)一定的相關(guān)性將其納入整體優(yōu)化模型。該文在險情救援的配送路線優(yōu)化過程中將采用節(jié)約算法和遺傳模型相結(jié)合的方法，對原有的救援方案進行更合理地優(yōu)化。

1 救援配送的成本控制模型

常見的配送成本一般包括配送過程中的固定成本、配送過程中運輸成本、配送中的損失成本和配送過程中懲罰成本。在配送過程中的固定成本與配送車輛當(dāng)天任務(wù)的配送距離無關(guān)。只要車輛參與救援配送，就會產(chǎn)生車輛的日常損耗和折舊。這部分的救援成本計算如公式（1）所示。

式中：s（k）為第k量車輛輛車的標(biāo)號。如果第k輛車參與救援配送，那么s（k）=1。相反，s（k）=0。C1為日常損耗成本；L為損耗系數(shù)；m為個數(shù)。

在救援配送過程中的損失成本包括2個部分：1）運輸過程中的顛簸和碰撞造成的損失。2）在裝卸過程中碰撞造成的損失與裝卸數(shù)量有關(guān)，即險情救援地點的總需求量。損失成本如公式（2）所示。

式中：為救援物資的平均價格；yjk為第k輛運輸車是否已到達第j個險情救援點。C3為日常損失成本，m，n為個數(shù)。

2 基于節(jié)約算法和遺傳模型的救援路線優(yōu)化方法

2.1 總體思路

因此，該文的思想是根據(jù)距離為每個救援中心合理分配不同的險情救援點。這樣，一個大的多目標(biāo)多約束求解問題就變成許多小的求解問題。在每個小規(guī)模分布問題中，執(zhí)行遺傳算法來解決優(yōu)化問題。

因此，該文設(shè)計的救援配送路徑集成優(yōu)化方法包括以下3步：第一步，根據(jù)最近距離原則，將救援任務(wù)中不同的險情救援點合理分配到相應(yīng)的救援中心。將原來的大規(guī)模配送成本優(yōu)化問題分解為幾個結(jié)構(gòu)復(fù)雜度降低的優(yōu)化問題。第二步，使用節(jié)省算法在每個小規(guī)模救援網(wǎng)絡(luò)上形成節(jié)點排序和救援方案的初始解。第三步，根據(jù)保存算法得到的初始解，對每個小規(guī)模救援網(wǎng)絡(luò)進行遺傳算法優(yōu)化，得到最優(yōu)解。

2.2 節(jié)約算法確定遺傳模型初始種群

在救援成本控制的融合優(yōu)化算法中，節(jié)約算法被用于第二環(huán)節(jié)，以便于為第三環(huán)節(jié)確定相對更準(zhǔn)確的初始種群。為了使節(jié)省算法更適合該文的研究問題，該文在傳統(tǒng)節(jié)省算法的基礎(chǔ)上，考慮單個救援車輛的負載約束，結(jié)合局部搜索算法，提高算法的性能。改進的保存算法的實現(xiàn)過程如下：1）以救援網(wǎng)絡(luò)中的每個救援中心為算法的起點，計算第i個險情節(jié)點和第j個險情節(jié)點在救援距離中的節(jié)省量，并用w（i，j）標(biāo)記。2）將排序后的存儲到數(shù)組中。在持續(xù)更新過程中，如果出現(xiàn)節(jié)省量為0的情況，就可以停止更新。3）找到陣列中最大的節(jié)省量，并研究第i個險情節(jié)點和第j個險情節(jié)點間的位置關(guān)系。如果兩點間的救援路線可以包括在優(yōu)化路線中，則繼續(xù)向下執(zhí)行。相反，更換下一個最大的節(jié)省量，然后重復(fù)該步驟。4）如果確定是2個險情節(jié)點間的有效救援路線，那么檢查車輛負載是否小于最大容量。如果小于最大承載力，那么該路徑有效。否則，返回步驟三并繼續(xù)重復(fù)前面的工作。5）使用局部搜索算法逐一檢查計算的合理救援路線結(jié)果的合理性。6）通過第五步中檢查的救援路徑形成分配方案，該路徑也是遺傳算法優(yōu)化時的初始種群。

2.3 遺傳算法優(yōu)化救援配送路線

適應(yīng)度函數(shù)是種群進化過程中判斷一個較好種群的標(biāo)準(zhǔn)。適應(yīng)度函數(shù)的值越大，這種演化就越合理。該文提出的險情救援配送總成本越低越好。因此，較早建立的目標(biāo)函數(shù)與適應(yīng)度函數(shù)成反比。構(gòu)造的適應(yīng)度函數(shù)如公式（3）所示。

式中：Fit（i）為適應(yīng)度函數(shù)；L為損耗系數(shù)；dij為距離，m，n為個數(shù)；A為距離參數(shù)。

在上述適應(yīng)度函數(shù)下，當(dāng)救援配送的總成本較小時，由于互惠關(guān)系配置，因此遺傳算法的適應(yīng)度函數(shù)值較大。

在形成新的群體后，適應(yīng)度越高，基因被遺傳的概率就越大。換句話說，選擇操作規(guī)則，即那些具有高適應(yīng)度的基因更有可能被選擇。因此，根據(jù)上述構(gòu)建的適應(yīng)度函數(shù)，為險情救援配送成本控制中遺傳算法的選擇操作設(shè)置以下概率，如公式（4）所示。

式中：p（k）為概率；Fit（i）為適應(yīng)度函數(shù)；n為個數(shù)。

從式中可以看出，分母是一個新物種群中所有基因的適應(yīng)度函數(shù)值之和，分子是第k個基因適應(yīng)度函數(shù)的函數(shù)值。交叉運算規(guī)則是從上一代群體的基因中生成下一代基因的最基本運算。第一步，從上一代的基因群體中隨機選擇2條染色體。這2條染色體應(yīng)該是完整的，沒有基因組重復(fù)。第二步，將2條親本染色體中的一條的邊界基因相應(yīng)地排列在下一代染色體的相應(yīng)位置上。第三步，將2條親本染色體中的另一條和除邊界基因外的其余基因相應(yīng)地排列在下一代染色體的相應(yīng)位置上，形成子染色體操作對象。變異是一種不規(guī)則遺傳，屬于基因突變的一種特殊遺傳規(guī)律。因為變異存在，染色體的遺傳避免了太多的相似性，從而不斷出現(xiàn)變異，形成具有不同屬性的新個體。

3 險情救援路徑結(jié)果與分析

為驗證該方法的有效性，設(shè)定一個險情救援的仿真環(huán)境作為研究對象。這一次的險情救援任務(wù)，一共包括27個險情救援點。險情救援中心一共包括3個，加上27個險情救援，形成一個救援配送網(wǎng)絡(luò)。

該文通過融合算法對這個險情救援任務(wù)的救援配送進行重新規(guī)劃，目的是在確保每個險情點救援的同時，盡可能地降低救援總成本，涉及的主要參數(shù)如下：1）超過最佳救援時間窗口，但是在最大極限救援時間窗口內(nèi)，罰款單價為20元/小時。2）一輛救援車輛的運輸成本為4.5元/km，不考慮超速或擁堵等特殊情況。3）救援車輛的固定成本消耗為80元/輛。4）救援車輛的最大承載能力為2.0t/輛。5）每個險情點的救援時間范圍為凌晨4：00—8：00。6）在運輸過程中的損失率為0.08%。7）在裝卸過程中的損失率為0.16%。8）救援車輛等待成本為10元/小時。進一步了解每個險情救援點交付救援物資的時間窗口以及可能允許的時間窗口，見表1。

表1 各險情救援點的時間窗口

根據(jù)提出的融合優(yōu)化算法的實現(xiàn)過程，首先需要做的工作是將整個救援任務(wù)劃分為新的子任務(wù)。即根據(jù)最近距離原則，將不同的救援節(jié)點合理分配到相應(yīng)的救援中心，降低了原有救援網(wǎng)絡(luò)的復(fù)雜度。在距離最近的原則下，還應(yīng)考慮3個配送中心對應(yīng)的救援節(jié)點數(shù)量的相對平衡。該救援節(jié)點對應(yīng)的救援中心的配送表見表2。

表2 救援節(jié)點分配方案

通過改進節(jié)約算法可知，該初始分配方案的總救援成本為1286.15元。與未經(jīng)優(yōu)化的救援方案的1457.22成本相比，盡管其成本大幅降低，但是這不是最好的結(jié)果。進一步將節(jié)約算法獲得的險情救援方案的初始解代入該文提出的遺傳算法中，該算法在200次迭代后收斂，結(jié)果被視為最佳救援方案。最佳救援方案與原始救援方案間的路線對比如圖1、圖2所示。

圖1 原始救援節(jié)點分配

圖2 該文方法優(yōu)化后的救援方案

根據(jù)圖1、圖2兩種方案的比較結(jié)果可知，在集成優(yōu)化算法得到的救援方案中，救援車輛數(shù)量從9輛減少到8輛，總救援距離從129.36km減少到88.85km，運輸成本從582.12元減少到399.83元。同時，最佳救援方案的平均通過率從原方案的81.41%升至91.75%，提高車輛運輸效率。運輸效率的提高和總運輸距離的縮短也降低罰款成本，從原方案的155.10元降至51.45元，從而提高救援效果。

4 結(jié)論

以救援成本控制為目標(biāo)，對救援配送路徑的優(yōu)化進行研究。通過固定成本、運輸成本、損失成本和懲罰成本的分項設(shè)計，構(gòu)建救援成本控制的總體模型和目標(biāo)函數(shù)。在該基礎(chǔ)上，將節(jié)約算法和遺傳模型相結(jié)合，構(gòu)建一種新的險情救援路徑優(yōu)化方法。首先，對整個救援網(wǎng)絡(luò)進行合理劃分，其次，用改進的節(jié)約算法形成初始解，最后，用遺傳算法優(yōu)化救援方案。在方法描述的過程中，進行遺傳模型的種群初始化、適應(yīng)度函數(shù)和3個遺傳規(guī)則的詳細設(shè)計。在進行具體試驗研究的基礎(chǔ)上，構(gòu)建救援模型，并進行優(yōu)化，得到新的救援方案。試驗結(jié)果表明，該文提出的融合算法獲得了更合理的險情救援方案，救援路徑由原來的129.36km減少到88.85km，救援成本由582.12元減少到399.83元。采用這種新的救援方案，有效降低救援成本，運輸效率顯著提高。