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

劉志華

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

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

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

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

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

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

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

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

2.1 總體思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 各險(xiǎn)情救援點(diǎn)的時(shí)間窗口

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

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

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

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

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

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

4 結(jié)論

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