陳娟，倪志偉*，李華

（1.合肥工業(yè)大學(xué)管理學(xué)院，安徽 合肥 230009；2.合肥工業(yè)大學(xué)過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009）

0 引言

隨著社會(huì)及交通工具的發(fā)展，各個(gè)地區(qū)的人流量在不斷攀升，加速了傳染病在人群中的傳播。在各種預(yù)防措施中，注射疫苗被認(rèn)為是最有效的方法［1-2］，研究疫苗的車輛路徑優(yōu)化問(wèn)題（VRP）可以降低疫苗運(yùn)輸過(guò)程的成本，具有重要現(xiàn)實(shí)意義。

我國(guó)人口眾多，在傳染病爆發(fā)時(shí)期，對(duì)疫苗的需求量極大，而在爆發(fā)初期，各地疫苗儲(chǔ)量往往難以滿足全部的需求，所以要研究車輛路徑優(yōu)化問(wèn)題，第一步必須先確定各地區(qū)的疫苗實(shí)際配送量，當(dāng)疫苗供小于求時(shí)，疫苗分配常遵循公平公正的原則［3］，本文在對(duì)儲(chǔ)量不足的疫苗進(jìn)行分配時(shí)同樣采取此原則。在得到各地區(qū)的疫苗實(shí)際配送量后，則要面臨如何合理規(guī)劃疫苗分配路徑這一問(wèn)題。在實(shí)際情境中，如果疫苗在規(guī)定的時(shí)間窗內(nèi)未能及時(shí)到達(dá)并接種，隨著到達(dá)時(shí)間的推遲，在相同的時(shí)間內(nèi)，感染傳染病的人數(shù)會(huì)加速增長(zhǎng)［4］。基于此，本文將疫苗延遲到達(dá)產(chǎn)生的時(shí)間窗懲罰函數(shù)設(shè)置為凹函數(shù)以便更貼合實(shí)際情景。因此，在傳染病爆發(fā)初期，面對(duì)疫苗儲(chǔ)量不足的情況，在遵循公平公正原則的前提下先確定各地區(qū)的疫苗實(shí)際配送量，然后在研究車輛路徑優(yōu)化問(wèn)題時(shí)將時(shí)間窗懲罰函數(shù)設(shè)置為凹函數(shù)將使研究更具現(xiàn)實(shí)意義。

疫苗儲(chǔ)存對(duì)于溫度有極高要求，因而疫苗的配送路徑優(yōu)化屬于冷鏈物流車輛路徑優(yōu)化問(wèn)題，屬于VRP 的變體，國(guó)內(nèi)外很多學(xué)者均對(duì)此進(jìn)行了研究。在模型構(gòu)建方面：ZHAO等［5］研究了包括冷鏈配送成本、碳排放和客戶滿意度的多目標(biāo)模型；JI等［6］為順應(yīng)低碳經(jīng)濟(jì)的趨勢(shì)，在研究冷鏈物流車輛路徑優(yōu)化問(wèn)題時(shí)建立了3 個(gè)低碳魯棒優(yōu)化（RO）模型解決具有不確定性的問(wèn)題；DENG等［7］建立了考慮貨損的最小化成本模型；馬成穎等［8］在考慮實(shí)時(shí)路況和客戶隨時(shí)需求的條件下，構(gòu)建了由最小化總成本和最大化滿意度組成的雙目標(biāo)模型；杜琛等［9］在建立模型時(shí)同時(shí)兼顧了客戶滿意度、油耗成本以及易腐壞貨物損耗成本；王勇等［10］構(gòu)建了資源共享以及溫度控制下的最小化總成本的模型。在求解冷鏈物流車輛路徑優(yōu)化問(wèn)題的算法方面，主要研究方向集中在用啟發(fā)式算法解決問(wèn)題，也有少量學(xué)者使用學(xué)習(xí)類的有關(guān)方法解決問(wèn)題：LI等［11］利用了基于智能優(yōu)化算法的改進(jìn)粒子群優(yōu)化算法結(jié)合實(shí)際案例數(shù)據(jù)求解模型；LIU等［12］提出了局部搜索效率較高的模因算法；YU等［13］采用了混合粒子群算法；馬成穎等［8］通過(guò)改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法求解了雙目標(biāo)模型；任騰等［14］利用融入了禁忌搜索算法和動(dòng)態(tài)概率選擇的蟻群算法研究最小化總成本的模型；方文婷等［15］在求解最小化總成本的模型時(shí)，提出了A*算法和蟻群算法相結(jié)合的混合蟻群算法；雷坤等［16］為解決車輛路徑問(wèn)題，提出了端到端的深度強(qiáng)化學(xué)習(xí)框架；WU等［17］設(shè)計(jì)了一個(gè)基于自注意力的深度架構(gòu)求解帶容量約束的車輛路徑優(yōu)化模型；LI等［18］利用了一種集成異構(gòu)注意機(jī)制的新型神經(jīng)網(wǎng)絡(luò)以減少車輛的總運(yùn)行時(shí)間。上述研究所建立的路徑優(yōu)化模型多是針對(duì)生鮮冷鏈物流，并且求解模型的算法存在難以跳出局部最優(yōu)、運(yùn)行若干次后所求的最優(yōu)解的值波動(dòng)較大等問(wèn)題。為了拓寬冷鏈物流的研究視角和改進(jìn)算法缺陷，本文提出使用混合平衡優(yōu)化算法求解疫苗冷鏈物流路徑優(yōu)化模型。

本文在遵循公平公正的原則下確定各地疫苗供小于求時(shí)的實(shí)際配送量，構(gòu)建懲罰函數(shù)為凹函數(shù)以及包含碳排放成本的總成本最小化的模型。在平衡優(yōu)化器中加入模擬退火算法，并且引入可變參數(shù)確定這兩種算法進(jìn)行粒子更新的概率，從而構(gòu)建一個(gè)新的算法進(jìn)行模型的求解。最后，通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證混合平衡優(yōu)化算法在求解本文所提模型上的優(yōu)勢(shì)。

1 模型構(gòu)建

1.1 問(wèn)題描述

本文提出的冷鏈物流車輛路徑優(yōu)化問(wèn)題描述如下：在傳染病爆發(fā)初期，疫苗由一個(gè)配送中心向N個(gè)需求點(diǎn)進(jìn)行配送，但配送中心的疫苗儲(chǔ)量不足以滿足全部需求點(diǎn)的需求，配送中心也僅擁有有限的疫苗冷藏運(yùn)輸車，在對(duì)各需求點(diǎn)進(jìn)行配送時(shí)，不免出現(xiàn)配送延遲的情況。本文研究的目標(biāo)，一是在疫苗儲(chǔ)量不足的情況下，公平公正地為各地分配疫苗，二是求解出包括固定成本、運(yùn)輸成本、制冷成本、碳排放成本和懲罰成本在內(nèi)的最小總成本和最優(yōu)配送路徑。

關(guān)于本文所研究問(wèn)題的假設(shè)如下：

1）所有疫苗冷藏運(yùn)輸車均為一種車型，最大裝載量相同且始點(diǎn)和終點(diǎn)均為配送中心。

2）疫苗在配送途中始終保持活性，呈無(wú)損耗狀態(tài)。

3）車輛始終中速行駛即保持勻速，避免因?yàn)閯×翌嶔ぴ斐梢呙鐡p耗。

4）各需求點(diǎn)位置和需求量已知，且沒(méi)有任何一個(gè)需求點(diǎn)的需求量大于疫苗冷藏運(yùn)輸車的最大裝載量。

5）一個(gè)需求點(diǎn)僅由一輛疫苗冷藏運(yùn)輸車服務(wù)，但一輛疫苗冷藏運(yùn)輸車可服務(wù)多個(gè)需求點(diǎn)。

6）各需求點(diǎn)都要求疫苗盡快送達(dá)，故當(dāng)疫苗在約定的最晚時(shí)間之前到達(dá)時(shí)無(wú)懲罰成本，只有在約定的最晚時(shí)間之后到達(dá)才會(huì)產(chǎn)生與時(shí)間有關(guān)的懲罰成本。

1.2 已知參數(shù)

本文中所使用的參數(shù)及含義如下所示：

N：疫苗配送中心及需求點(diǎn)集合，N={1,2,…,i}；

K：疫苗冷藏運(yùn)輸車集合，K={1,2,…,k}；

ri：第i個(gè)需求點(diǎn)被分配的疫苗量；

qi：第i個(gè)需求點(diǎn)的疫苗需求量；

f：?jiǎn)?dòng)一輛疫苗冷藏運(yùn)輸車所產(chǎn)生的固定成本；

s：整個(gè)配送過(guò)程中所啟動(dòng)的疫苗冷藏運(yùn)輸車的數(shù)量；

Q：疫苗冷藏運(yùn)輸車的最大裝載量；

ti：需求點(diǎn)i接收到疫苗的時(shí)間；

tj：需求點(diǎn)j接收到疫苗的時(shí)間；

tij：疫苗冷藏運(yùn)輸車從需求點(diǎn)i行駛到需求點(diǎn)j所使用的時(shí)間；

r：車輛行駛單位里程所需的油耗量；

dij：疫苗需求點(diǎn)i和j之間的距離；

g：?jiǎn)挝粫r(shí)間內(nèi)制冷所需的油耗量；

e：?jiǎn)挝挥秃漠a(chǎn)生的碳排放量；

c：柴油單價(jià)；

p：碳交易所實(shí)時(shí)碳交易價(jià)格；

li：疫苗配送中心和需求點(diǎn)i約定的最晚到達(dá)時(shí)間。

1.3 各地疫苗實(shí)際配送量的確定

在傳染病爆發(fā)初期，當(dāng)疫苗儲(chǔ)量不足時(shí)，本文為在對(duì)疫苗儲(chǔ)量分配后，得到的各地疫苗分配量遵從公平公正的原則，引入資源滿意度的概念。資源滿意度為各地分配量與需求量的比值［19］，如式（1）所示，其中，Mi表示第i個(gè)疫苗需求點(diǎn)的滿意度，ri代表第i個(gè)需求點(diǎn)被分配的疫苗量，qi代表第i個(gè)需求點(diǎn)的疫苗需求量。由極值思想可知，所有地區(qū)中最大滿意度和最小滿意度的差值可視為衡量公平性的標(biāo)準(zhǔn)，如式（2）所示，當(dāng)差值趨近于0 時(shí)，便代表數(shù)據(jù)處理完成。

1.4 疫苗配送路徑優(yōu)化模型

1.4.1 決策變量分析

本文中疫苗配送中心和疫苗需求點(diǎn)均由i,j表示，其 中，i,j?{0,1,…,n}，僅當(dāng)i,j取0 時(shí)代表配送中心。

決策變量xijk和xik的取值如下所示：

當(dāng)疫苗冷藏運(yùn)輸車經(jīng)過(guò)i，j之間的路徑，從節(jié)點(diǎn)i駛離后的下一個(gè)到達(dá)節(jié)點(diǎn)即為j，此時(shí)xijk取值為1，否則取值為0；若由車輛k向需求點(diǎn)i配送疫苗，那么xik為1，否則為0。

1.4.2 成本函數(shù)

關(guān)于成本函數(shù)的描述如下：

1）固定成本

在啟動(dòng)疫苗冷藏運(yùn)輸車完成配送的過(guò)程中，會(huì)產(chǎn)生僅與啟動(dòng)車輛數(shù)有關(guān)的固定成本，其中包括車輛的折舊費(fèi)、保養(yǎng)費(fèi)以及司機(jī)的工資［20］，啟動(dòng)一輛疫苗冷藏運(yùn)輸車所產(chǎn)生的固定成本為f，那么啟動(dòng)K輛所產(chǎn)生的固定成本C1如式（3）所示。

2）運(yùn)輸成本和制冷成本

疫苗冷藏運(yùn)輸車在配送過(guò)程中行駛和制冷產(chǎn)生的油耗成本分別記為C2和C3，對(duì)應(yīng)運(yùn)輸成本和制冷成本。車輛在需求點(diǎn)i和j之間的運(yùn)輸成本可由行駛單位里程所需的油耗量r與車輛行駛距離dij的乘積得出，總的運(yùn)輸成本計(jì)算如式（4）所示；制冷成本為單位時(shí)間制冷所需的油耗量g與制冷總時(shí)長(zhǎng)的乘積，如式（5）所示。

3）碳排放成本

在疫苗配送路徑優(yōu)化模型中，碳排放由油耗產(chǎn)生，且碳排放量與油耗量的正相關(guān)系數(shù)已知［21］，在文中設(shè)定為e，那么碳排放量De可由疫苗冷藏運(yùn)輸車所消耗的油耗量確定，如式（6）所示；在引入碳交易價(jià)格p后即可確定碳排放成本C4，如式（7）所示。

4）懲罰成本

根據(jù)文獻(xiàn)［22］得知，如果疫苗冷藏運(yùn)輸車未能在約定的最晚時(shí)間到達(dá)，使得疫苗需求點(diǎn)延遲接種疫苗，那么傳染病會(huì)快速在人群中傳播，并且速度隨時(shí)間不斷增長(zhǎng)，此時(shí)，懲罰函數(shù)為凹函數(shù)更符合實(shí)際。在傳染病爆發(fā)初期，疫苗應(yīng)盡快到達(dá)各需求點(diǎn)以便及時(shí)控制傳染病在人群中的傳播。因此：當(dāng)疫苗冷藏運(yùn)輸車到達(dá)需求點(diǎn)i的時(shí)間ti在約定的最晚時(shí)間點(diǎn)li之前，則符合各需求地訴求，此時(shí)懲罰成本為0；當(dāng)?shù)竭_(dá)時(shí)間在約定的最晚時(shí)間點(diǎn)li之后，懲罰函數(shù)則為凹函數(shù)，如式（8）所示，懲罰成本C5如式（9）所示。

1.4.3 數(shù)學(xué)模型

本文構(gòu)建的是最小化總成本的路徑優(yōu)化模型，總成本包括固定成本C1、運(yùn)輸成本C2、制冷成本C3、碳排放成本C4和懲罰成本C5，目標(biāo)函數(shù)如式（10）所示。

式（10）為目標(biāo)函數(shù)，由所有參加配送的疫苗冷藏運(yùn)輸車的運(yùn)輸總成本構(gòu)成。式（11）～式（18）為約束條件，其中：式（11）表示任何一個(gè)配送路線的總需求量都不大于車輛的滿載量；式（12）表示每個(gè)需求點(diǎn)都只被服務(wù)一次；式（13）表示所有車輛的始點(diǎn)和終點(diǎn)都是配送中心；式（14）和式（15）表示各需求點(diǎn)僅允許車輛出發(fā)到達(dá)一次；式（16）表示車輛k從客戶點(diǎn)i到客戶點(diǎn)j服從0-1 變量；式（17）表示車輛k服務(wù)客戶點(diǎn)i服從0-1 變量；式（18）可保證配送過(guò)程連續(xù)。

2 算法設(shè)計(jì)

2.1 平衡優(yōu)化器算法原理

平衡優(yōu)化器（EO）算法［23］是一種受物理現(xiàn)象啟發(fā)得到的新型優(yōu)化算法，目的是使得容積質(zhì)量動(dòng)態(tài)平衡，求得最優(yōu)的平衡濃度，目前成功應(yīng)用于基準(zhǔn)函數(shù)和工程問(wèn)題［24］。在算法中，每一個(gè)粒子都對(duì)應(yīng)著一個(gè)濃度，不同的粒子構(gòu)成種群，初始種群隨機(jī)產(chǎn)生，由前4 項(xiàng)最優(yōu)解及其平均值構(gòu)成5 個(gè)候選解，形成平衡狀態(tài)池，由于粒子的更新均與候選解有關(guān)，因此該算法容易陷入局部最優(yōu)進(jìn)而處于停滯狀態(tài)。算法的具體步驟如下：

1）初始化種群。在明確優(yōu)化變量的可變化范圍[Cmin，Cmax]后，在該范圍內(nèi)隨機(jī)產(chǎn)生包含N個(gè)粒子的初始種群：

在式（19）中：Cmin和Cmax分別為優(yōu)化變量可變范圍的下界和上界；ri為隨機(jī)向量，維度與種群中的粒子數(shù)量一致，向量中的每個(gè)元素均為［0，1］之間的隨機(jī)數(shù)。

2）構(gòu)建平衡狀態(tài)池。初始化種群后，可通過(guò)計(jì)算各粒子的適應(yīng)度值確定前4 項(xiàng)最優(yōu)解，然后通過(guò)計(jì)算這4 個(gè)解的平均值確定構(gòu)成平衡狀態(tài)池的5 個(gè)候選解，進(jìn)行粒子更新時(shí)可從中隨機(jī)選取一個(gè)，每個(gè)候選解被選擇的概率一致，這在一定程度上可避免粒子進(jìn)行低質(zhì)量的更新和緩解算法容易陷入局部最優(yōu)的困境。平衡狀態(tài)池的具體構(gòu)成如下：

3）確定指數(shù)項(xiàng)系數(shù)。指數(shù)項(xiàng)系數(shù)與迭代次數(shù)有關(guān)，通過(guò)設(shè)置不同的參數(shù)可平衡算法全局搜索和局部尋優(yōu)的能力，如式（21）所示。

其中：t可由最大迭代次數(shù)和當(dāng)前迭代次數(shù)計(jì)算得出，具體如式（22）所示。

在式（22）中：a1和a2分別為控制全局搜索能力和局部尋優(yōu)能力的系數(shù)，常取值為2 和1，可根據(jù)問(wèn)題取不 同的值；r和γ是與ri形式相 同的向 量；IIter和IMax_Iter為當(dāng)前迭代次數(shù)和算法設(shè)置的最大迭代次數(shù)。

4）確定質(zhì)量生成速率。為使得算法在局部開采時(shí)得到高質(zhì)量的解，EO 算法引入質(zhì)量生成速率G，可由式（23）計(jì)算得出。

在上式中：Ceq是在平衡狀態(tài)池中隨機(jī)選出的一個(gè)候選解；C為當(dāng)前待更新的解；r1和r2為［0，1］之間的隨機(jī)數(shù)；PGP為生成概率。

5）進(jìn)行解的更新。在經(jīng)過(guò)上述4 個(gè)步驟之后，EO 算法通過(guò)下式對(duì)當(dāng)前解進(jìn)行更新：

其中：V常取值為1。

2.2 混合平衡優(yōu)化算法

由于EO 算法的全局搜索能力較差，而模擬退火（SA）算法擁有較強(qiáng)的全局搜索能力，因此可在EO算法中融入SA 算法，使得改進(jìn)后的EO 算法在保證解的質(zhì)量的前提下，可跳出局部最優(yōu)。SA 算法是依據(jù)固體退火原理提出的一種算法。在該算法中，由于固體初始溫度足夠高，固體中的粒子呈無(wú)序運(yùn)動(dòng)狀態(tài)，后隨著溫度的降低，固體中的粒子逐漸趨于穩(wěn)定，當(dāng)溫度降低至終止溫度Tf時(shí)的固體能量即為最優(yōu)解。在這個(gè)過(guò)程中的每個(gè)溫度下，都要進(jìn)行L次迭代，如果迭代后的能量變小，則直接接受，否則根據(jù)Metropolis 準(zhǔn)則，以可變概率更新固體的能量。

更新概率可由下式計(jì)算得出：

其中：E1為未迭代更新前的能量；E2為迭代更新后的能量；T為當(dāng)前溫度，隨著溫度的降低，接受較高能量的概率也在逐步降低，直至最后不接受較差解。

在EO 算法中融入SA 算法后，為平衡算法的全局搜索能力和局部尋優(yōu)能力，在算法中引入可變參數(shù)R：以概率R選擇SA 算法更新解，進(jìn)行全局搜索；以概率1-R選擇EO 算法更新解，進(jìn)行局部尋優(yōu)。

綜上，混合平衡優(yōu)化算法的具體流程如下：

Step1設(shè)置相關(guān)參數(shù)。

Step2在優(yōu)化變量范圍內(nèi)初始化種群，并將全局最優(yōu)解Mnf設(shè)置為無(wú)窮大。

Step3計(jì)算種群中各粒子的適應(yīng)度值。

Step4確定平衡狀態(tài)池Ceq,pool，并將當(dāng)前最優(yōu)解mnf記為Ceq。

Step5比較全局最優(yōu)解Mnf和當(dāng)前最優(yōu)解Ceq(1)的大小，若Ceq(1)＜Mnf，則將Ceq(1)的值賦給Mnf，否則Mnf不變。

Step6判斷是否滿足終止條件，是則輸出最優(yōu)解，流程結(jié)束，否則轉(zhuǎn)至Step7。

Step7通過(guò)rand(0,1)函數(shù)生成隨機(jī)數(shù)a，若a＞R，則根據(jù)EO 算法中的平衡候選解更新粒子，否則根據(jù)SA 算法更新粒子。

Step8判斷種群中的粒子是否更新完畢，是則轉(zhuǎn)至Step3，否則轉(zhuǎn)至Step7。

以上流程對(duì)應(yīng)的流程圖如圖1 所示。

圖1 混合平衡優(yōu)化算法流程圖Fig.1 Flowchart of hybrid equilibrium optimization algorithm

3 實(shí)例求解及分析

本文實(shí)驗(yàn)在Matlab 2019b 上進(jìn)行編碼，在Windows 10 系統(tǒng)下操作完成?；旌掀胶鈨?yōu)化算法的初始種群設(shè)置為100，迭代總次數(shù)設(shè)置為200 次，生成概率取值為0.5，SA 算法中初始溫度設(shè)置為3 000，降溫系數(shù)設(shè)置為0.997。實(shí)例中疫苗需求點(diǎn)的坐標(biāo)采用各地實(shí)際經(jīng)緯度表示，兩地距離通過(guò)Haversine法計(jì)算得出。

為了驗(yàn)證算法的性能以及其在不同規(guī)模算例下的有效性，本文在2 種規(guī)模算例下分別進(jìn)行20 次實(shí)驗(yàn)：以安徽省內(nèi)由合肥市向各市配送疫苗作為小規(guī)模算例，其中包括1 個(gè)配送中心（合肥市）、15 個(gè)疫苗需求點(diǎn)；以廣東省內(nèi)由廣州市向各市配送疫苗作為大規(guī)模算例，其中包括1 個(gè)配送中心（廣州市）、20 個(gè)疫苗需求點(diǎn)。現(xiàn)設(shè)置小規(guī)模算例中的配送中心（合肥市）擁有疫苗150 萬(wàn)劑，大規(guī)模算例中的配送中心（廣州市）擁有疫苗200 萬(wàn)劑，除此之外，2 種算例中參數(shù)的設(shè)置均保持一致，即疫苗冷藏運(yùn)輸車行駛速度為60 km/h，啟動(dòng)一輛疫苗冷藏運(yùn)輸車所產(chǎn)生的固定成本為200 元，車輛行駛單位路程油耗費(fèi)用為1.5元/km，單位時(shí)間的制冷成本為0.5元/h，柴油單價(jià)為8.18元/L，單位油耗產(chǎn)生的碳排放量為0.002 7 t/L，碳交易所實(shí)時(shí)碳交易價(jià)格為80 元/t，懲罰函數(shù)系數(shù)設(shè)置為150 元/h，本文用最多載重30 萬(wàn)劑疫苗的疫苗冷藏運(yùn)輸車?？紤]到篇幅限制，本文僅展示小規(guī)模算例的基本信息，如表1 所示。

表1 小規(guī)模算例的基本信息Table 1 Basic information of small-scale examples

3.1 各地疫苗實(shí)際配送量的獲取

在兩種算例中各疫苗需求點(diǎn)的需求總和均大于配送中心的儲(chǔ)量，此時(shí)按照公平分配原則確定的各疫苗需求點(diǎn)的配送量如表2 所示。由表2 可知，安徽省內(nèi)各地區(qū)最大資源滿意度和最小資源滿意度的差值為0.000 031 231，廣東省內(nèi)各地區(qū)最大資源滿意度和最小資源滿意度的差值為0.000 033 566，差值極小，已達(dá)到公平分配。

表2 各地區(qū)實(shí)際疫苗配送量Table 2 Actual vaccine distribution by region 單位：劑

3.2 消融實(shí)驗(yàn)

在確定各個(gè)地區(qū)的實(shí)際疫苗配送量后，即可進(jìn)行車輛路徑優(yōu)化實(shí)驗(yàn)，在此之前，為了驗(yàn)證本文所提的兩處算法改進(jìn)點(diǎn)的有效性，使用上述兩種規(guī)模的算例分別進(jìn)行20 次實(shí)驗(yàn)，以配送成本的最優(yōu)值、均值和標(biāo)準(zhǔn)差，以及實(shí)驗(yàn)運(yùn)行的平均時(shí)間作為衡量標(biāo)準(zhǔn)，比較EO 算法、在EO 算法中融入SA 算法得到的改進(jìn)平衡優(yōu)化算法和在改進(jìn)平衡優(yōu)化算法中加入可變參數(shù)得到的混合平衡優(yōu)化算法的性能，最終的實(shí)驗(yàn)結(jié)果如表3 和表4 所示。

表3 配送成本的對(duì)比結(jié)果Table 3 Comparative results on delivery costs 單位：元

表4 平均運(yùn)行時(shí)間的對(duì)比結(jié)果Table 4 Comparison results on average running time 單位：s

由表3 可知，以小規(guī)模算例為例，改進(jìn)平衡優(yōu)化算法相較于基本的EO 算法在配送成本的最優(yōu)值、平均值和標(biāo)準(zhǔn)差上分別降低了62.9%、56.0%和53.2%，同時(shí)，混合平衡優(yōu)化算法相較于改進(jìn)平衡優(yōu)化算法在配送成本的最優(yōu)值、平均值和標(biāo)準(zhǔn)差上又分別降低了10.1%、29.2%和28.3%。由表4 可知，改進(jìn)平衡優(yōu)化算法相較于基本的EO 算法并沒(méi)有因?yàn)榧尤肓薙A 算法使得算法的復(fù)雜度增加而造成實(shí)驗(yàn)運(yùn)行時(shí)間增加的情況，混合平衡優(yōu)化算法相較于改進(jìn)平衡優(yōu)化算法也沒(méi)有出現(xiàn)實(shí)驗(yàn)運(yùn)行時(shí)間增加的情況，相反，實(shí)驗(yàn)的運(yùn)行時(shí)間還有所減少。由此可知，本文所提的兩處算法改進(jìn)點(diǎn)均能在不延長(zhǎng)實(shí)驗(yàn)運(yùn)行時(shí)間，甚至是在減少實(shí)驗(yàn)運(yùn)行時(shí)間的情況下有效提升算法的性能，提高算法的尋優(yōu)能力，使得算法能夠穩(wěn)定求出更高質(zhì)量的解。

EO 算法、改進(jìn)平衡優(yōu)化算法和混合平衡優(yōu)化算法針對(duì)小規(guī)模和大規(guī)模算例計(jì)算出的最優(yōu)路徑對(duì)應(yīng)的迭代過(guò)程如圖2 和圖3 所示。

圖2 迭代過(guò)程（小規(guī)模算例）Fig.2 Iterative proces（ssmall-cale example）

圖3 迭代過(guò)程（大規(guī)模算例）Fig.3 Iterative proces（slarge-scale example）

由圖2 和圖3 可知，無(wú)論是針對(duì)何種規(guī)模的算例，在基礎(chǔ)的EO 算法中依次加入兩處改進(jìn)點(diǎn)后，不僅算法的收斂速度在逐漸提高，算法跳出局部最優(yōu)的能力也在逐漸提高，這更加證明了本文所提兩處改進(jìn)點(diǎn)的有效性，證明了混合平衡優(yōu)化算法的有效性。

綜上，采用本文所提的兩處改進(jìn)點(diǎn)改進(jìn)EO 算法后得到的混合平衡優(yōu)化算法具有較好的性能，并且能夠更快收斂到一個(gè)較優(yōu)值。

3.3 對(duì)比實(shí)驗(yàn)及結(jié)果分析

3.3.1 混合平衡優(yōu)化算法與Cplex求解器的對(duì)比實(shí)驗(yàn)

將混合平衡優(yōu)化算法與Cplex 求解器針對(duì)同一算例進(jìn)行對(duì)比實(shí)驗(yàn)，算例的基本信息如表5 所示，對(duì)比實(shí)驗(yàn)的結(jié)果如表6 所示，表6 中使用混合平衡優(yōu)化算法求得的配送成本為算法運(yùn)行20 次后得到的平均配送成本。

表5 需求點(diǎn)及各配送點(diǎn)的基本信息Table 5 Basic information of demand points and various delivery points

表6 針對(duì)同一算例的對(duì)比實(shí)驗(yàn)結(jié)果Table 6 Results of comparative experiment for one example 單位：元

由表6 可知，混合平衡優(yōu)化算法所求得的配送成本相較于Cplex 求解器求得的配送成本減少了17.5%，證明了混合平衡優(yōu)化算法所求解的質(zhì)量高于Cplex 求解器求得的精確解的質(zhì)量。

3.3.2 混合平衡優(yōu)化算法與其他5種算法的對(duì)比實(shí)驗(yàn)

針對(duì)上文所提的兩個(gè)規(guī)模的算例，將混合平衡優(yōu)化算法與并行平衡優(yōu)化算法［24］、知識(shí)型蟻群算法［14］、混合變鄰域搜索算法［25］、改進(jìn)混合粒子群算法［26］和基本的平衡優(yōu)化器算法在每個(gè)算例上分別運(yùn)行20 次進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表7 和表8 所示，表7 中數(shù)據(jù)表示最小配送成本。

表7 針對(duì)不同規(guī)模算例的對(duì)比實(shí)驗(yàn)結(jié)果Table 7 Results of comparative experiment for different scale examples 單位：元

表8 不同算例規(guī)模下的平均運(yùn)行時(shí)間Table 8 Average running time at different example scales 單位：s

由表7 可知，無(wú)論是針對(duì)小規(guī)模算例還是大規(guī)模算例，利用本文所提出的混合平衡優(yōu)化算法求得的最小配送成本都明顯小于利用其他5 種算法求得的最小配送成本。以小規(guī)模算例為例，混合平衡優(yōu)化算法求得的最小配送成本分別為其他5 種算法的73.5%、53.9%、69.1%、64.1%和33.4%，混合平衡優(yōu)化算法在20 次實(shí)驗(yàn)中求得的配送成本的均值和標(biāo)準(zhǔn)差也是6 種算法中最小的。由此可知，混合平衡優(yōu)化算法不僅在不同規(guī)模的算例上具有有效性，其所求解的穩(wěn)定性和質(zhì)量也明顯優(yōu)于一些改進(jìn)后的算法和基礎(chǔ)算法。

由表8 可知，無(wú)論針對(duì)何種規(guī)模的算例，混合平衡優(yōu)化算法的平均運(yùn)行時(shí)間總是最小的，這表明混合平衡優(yōu)化算法的計(jì)算效率更高、計(jì)算速度更快。

綜上，混合平衡優(yōu)化器算法不僅所求解的質(zhì)量較高，其在求解時(shí)還具有較好的穩(wěn)定性和較高的計(jì)算效率，因此該算法可用于求解疫苗配送車輛路徑優(yōu)化問(wèn)題并且具有一定優(yōu)勢(shì)。

在本文實(shí)驗(yàn)中，以小規(guī)模算例和混合平衡優(yōu)化算法為例，其求得的最優(yōu)配送路徑如圖4 所示(彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版)。

圖4 最優(yōu)配送路徑Fig.4 Optimal delivery route

4 結(jié)束語(yǔ)

針對(duì)當(dāng)前冷鏈物流車輛路徑優(yōu)化問(wèn)題的研究多以研究生鮮配送為主。本文提出了包含碳排放成本在內(nèi)的配送總成本最小化的疫苗配送路徑優(yōu)化模型。針對(duì)平衡優(yōu)化器算法容易陷入局部最優(yōu)的缺點(diǎn)，本文在平衡優(yōu)化器算法中融入模擬退火算法，并引入起平衡作用的可變參數(shù)求解模型，得到疫苗最優(yōu)配送路徑。最后通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證了混合平衡優(yōu)化算法在求解本文所提模型上的優(yōu)勢(shì)，利用該算法求解可以較大程度地降低疫苗配送成本。下一步擬研究多配送中心和多車型情況下的疫苗配送路徑優(yōu)化問(wèn)題，并將持續(xù)改進(jìn)平衡優(yōu)化器算法，提高算法的求解性能和穩(wěn)定性。