基于雙模式更新五行環(huán)算法的多目標(biāo)冷鏈配送

任 靜，項(xiàng) 月，劉漫丹

（華東理工大學(xué)信息科學(xué)與工程學(xué)院, 上海200237）

冷鏈物流作為物流業(yè)的一個(gè)重要分支受到了越來(lái)越多的關(guān)注。我國(guó)在冷鏈物流配送的過(guò)程中，冷鏈產(chǎn)品的損失金額約為1 億人民幣，足以滿足2 億人口的基本需求[1]。近年來(lái)，針對(duì)冷鏈物流配送中的路徑規(guī)劃問(wèn)題，不論是在模型建立還是在算法求解方面都取得了大量的研究成果。

在模型建立方面，Wang 等[2]建立了以配送成本最低為目標(biāo)函數(shù)的模型；Govindan 等[3]建立了以配送成本最小化、環(huán)境影響最小化為目標(biāo)函數(shù)的模型；Caoa等[4]建立了以車輛數(shù)最小化、計(jì)劃距離最小化等為目標(biāo)函數(shù)的模型；Wang 等[5]建立了以交貨成本最小化、生鮮產(chǎn)品新鮮度最大化為目標(biāo)函數(shù)的模型。

在求解算法方面，Gong 等[6]提出了一種改進(jìn)的粒子群優(yōu)化算法來(lái)解決帶時(shí)間窗的路徑規(guī)劃問(wèn)題；Wang 等[7]提出了一種基于時(shí)空的鄰域搜索-遺傳算法的兩階段啟發(fā)式算法來(lái)解決多目標(biāo)路徑問(wèn)題；Zhao 等[8]提出了一種改進(jìn)的蟻群算法來(lái)求解冷鏈物流中的路徑規(guī)劃問(wèn)題；Claudia 等[9]采用兩階段法求解柔性周期車輛路徑問(wèn)題；Chen 等[10]提出了一種自適應(yīng)的大型鄰里搜索算法來(lái)解決具有時(shí)間窗的車輛路徑規(guī)劃問(wèn)題。

五行環(huán)優(yōu)化(FECO)算法[11]是近年來(lái)提出的一種新型的優(yōu)化算法，因其采用元素空間結(jié)構(gòu)，在全局探索和局部探測(cè)方面可實(shí)現(xiàn)較好的平衡性。相比于經(jīng)典的優(yōu)化算法以及一些其他的新型算法，F(xiàn)ECO 算法在解決單目標(biāo)路徑優(yōu)化問(wèn)題中取得了很好的優(yōu)化結(jié)果?；贔ECO 算法，本文提出了一種雙模式更新個(gè)體的五行環(huán)優(yōu)化算法(Five-Elements Cycle Optimization Algorithm of Dual-Mode Updating Individuals, FECODMUI)用于求解多目標(biāo)優(yōu)化模型，并與FECO 算法、NSGA-II 算法[12]、鯨魚(yú)優(yōu)化算法(Whale Optimization Algorithm, WOA)[13]、灰狼優(yōu)化算法(Grey Wolf Optimizer，GWO)[14]進(jìn)行比較，通過(guò)具體實(shí)例驗(yàn)證了FECO-DMUI 算法能夠?yàn)槔滏溛锪髋渌吞峁┛蓪?shí)施的有效方案。

1 相關(guān)背景

1.1 問(wèn)題描述

根據(jù)顧客對(duì)配送時(shí)間的滿意度可以將顧客分為兩類[15]，每類顧客的滿意度情況如圖1 所示，本文的優(yōu)化模型依據(jù)普遍存在的第二類顧客而建立。冷鏈物流配送問(wèn)題可描述為：某區(qū)域設(shè)有一個(gè)冷鏈產(chǎn)品的配送中心，該中心含有G輛車負(fù)責(zé)向N個(gè)客戶點(diǎn)配送，每輛車的起點(diǎn)與終點(diǎn)均為配送中心。根據(jù)圖1分析得：①為最優(yōu)配送時(shí)間范圍；②為可接受配送時(shí)間范圍；③為拒絕配送時(shí)間范圍。

圖1 顧客滿意度分析Fig.1 Customer satisfaction analysis

1.2 問(wèn)題假設(shè)

假設(shè) 1：每輛車的最大載重量已知，并且客戶的需求量不會(huì)超過(guò)車輛的最大載重量。

假設(shè) 2：每個(gè)客戶點(diǎn)之間的距離均預(yù)先可知且每個(gè)客戶點(diǎn)只用一輛車進(jìn)行配送。

假設(shè) 3：每輛車的起點(diǎn)與終點(diǎn)均為配送中心且車輛在整個(gè)運(yùn)輸過(guò)程中以近似恒定的速度行駛。

假設(shè)4：每個(gè)客戶點(diǎn)均有時(shí)間窗限制，如果沒(méi)有按照規(guī)定時(shí)間送達(dá)則產(chǎn)生相應(yīng)的懲罰成本。

2 模型的建立

2.1 參數(shù)及變量設(shè)定

模型參數(shù)的設(shè)定：Q為車輛的最大載重量；h為單位里程的運(yùn)輸成本；e為燃料單價(jià)；μ1為運(yùn)輸中單位時(shí)間內(nèi)制冷設(shè)備的能耗；μ2為裝卸過(guò)程中單位時(shí)間內(nèi)制冷設(shè)備的能耗；s為運(yùn)輸過(guò)程中車輛行駛的恒定速度；p為冷鏈貨物單價(jià)；c1為提前服務(wù)引起的懲罰成本；c2為延遲服務(wù)引起的懲罰成本；α 為裝卸過(guò)程中的貨損率；β 為貨物對(duì)時(shí)間的敏感系數(shù)；[Ei,Li]為客戶i的最優(yōu)時(shí)間窗；[EEi,Ei,Li,LLi] 為客戶i的特定時(shí)間窗；di j為客戶點(diǎn)i與客戶點(diǎn)j之間的距離，i或j為0 時(shí)，代表配送中心，否則代表各客戶點(diǎn)；qi為客戶點(diǎn)i的需求量。

模型變量的設(shè)定：tiv為車輛v到達(dá)客戶點(diǎn)i的時(shí)間；wi jv為車輛v到達(dá)配送點(diǎn)的時(shí)間，當(dāng)車輛v由配送點(diǎn)i行駛到配送點(diǎn)j時(shí)，wijv=1 ，否則為0（wiiv=0 ，i或j為0 時(shí)，代表配送中心，否則代表各客戶點(diǎn)）；yiv表示客戶點(diǎn)i是否由車輛v配送，是，yiv=1 ，否則為0。

2.2 配送成本模型

配送成本f1由運(yùn)輸成本C1、貨損成本C2、制冷成本C3和時(shí)間懲罰成本C4構(gòu)成。

2.2.1運(yùn)輸成本 冷藏車輛產(chǎn)生的運(yùn)輸成本主要包含燃料成本以及車輛的維修成本，具體表達(dá)形式如下：

其中：N為配送點(diǎn)的數(shù)目；G為配送車輛的數(shù)目。

2.2.2貨損成本 相對(duì)于傳統(tǒng)物流，冷鏈物流的關(guān)鍵是保證冷鏈產(chǎn)品的新鮮。在實(shí)際情況中，配送車輛長(zhǎng)時(shí)間行駛使得冷鏈產(chǎn)品腐爛變質(zhì)或品質(zhì)下降；在裝卸貨物過(guò)程中，冷鏈產(chǎn)品與外部熱空氣接觸，溫度升高會(huì)使冷鏈產(chǎn)品的質(zhì)量遭到損壞[16]。本文的貨損成本模型根據(jù)文獻(xiàn)[17]改進(jìn)所得，具體表達(dá)形式如下：

2.2.3 制冷成本 由于車輛在運(yùn)輸過(guò)程中維持冷鏈產(chǎn)品的低溫和到達(dá)客戶點(diǎn)進(jìn)行交貨過(guò)程中產(chǎn)生的能耗成本[18]均不可忽視，因此本文的制冷成本模型根據(jù)文獻(xiàn)[18]改進(jìn)所得，具體表達(dá)形式如下：

2.2.4 時(shí)間懲罰成本 不論配送車輛到達(dá)的時(shí)間早于Ei還是晚于Li，均會(huì)增加配送成本。因此，只要車輛在客戶規(guī)定的最優(yōu)時(shí)間窗外到達(dá)，就要產(chǎn)生相應(yīng)的懲罰成本。具體表達(dá)形式如式（4）所示。

2.3 客戶滿意度模型

客戶滿意度f(wàn)2的評(píng)估是基于配送車輛到達(dá)客戶點(diǎn)的時(shí)間建立的。根據(jù)圖1 建立的評(píng)估函數(shù)如式（5）所示：

在該評(píng)估函數(shù)中，當(dāng)tiv位于 [Ei,Li] 時(shí)，客戶的滿意程度為1；當(dāng)tiv位于 [EEi,Ei] 或 [Li,LLi] 時(shí)，滿意程度位于 (0,1) ；當(dāng)tiv位于 (0,EEi] 或 [LLi,∞) 時(shí)，滿意程度為0。因此，最終建立的客戶滿意度模型如式（6）所示。

2.4 冷鏈物流模型

本文建立的是單個(gè)配送中心和多個(gè)客戶點(diǎn)的模型，優(yōu)化目標(biāo)為最小化配送成本f1、最大化客戶滿意度f(wàn)2。目標(biāo)函數(shù)和約束條件的表達(dá)式如下：

其中，目標(biāo)函數(shù)式（7）表示配送成本最小化；式（8）表示客戶滿意度最大化；約束條件式（9）表示保證每個(gè)客戶點(diǎn)都能接受服務(wù)；式（10）、式（11）、式（12）表示每個(gè)客戶點(diǎn)只用一輛車服務(wù)；式（13）表示客戶需求量不超過(guò)車輛的最大裝載量；式（14）表示保證每一輛車的起點(diǎn)和終點(diǎn)都是配送中心。

3 FECO-DMUI 算法的求解

3.1 FECO 算法的原理

Liu[19]提出的FECO 算法利用了五行元素(金、木、水、火、土)相生相克的關(guān)系（圖2），將金、水、木、火、土這5 個(gè)元素分別用序號(hào)1、2、3、4、5 來(lái)表示。假設(shè)在k時(shí)刻，各元素的質(zhì)量為mi(k) ，各元素受到其他4 個(gè)元素所施加的合力為Fi(k) ，其中i=1,2,3,4,5。由F于i(k)是由4 個(gè)元素施加的力組成，并且每個(gè)元素施加的力所產(chǎn)生的作用并非完全相同，定義、wgp、wrp、wgawra分別為上述4 個(gè)元素施加的力的權(quán)重系數(shù)，因此所建立的五行環(huán)模型(Five-ElementsCycleModel,FECM)[12]如下：

圖2 五行元素相生相克關(guān)系Fig.2 Five elements complement each other

在求解優(yōu)化問(wèn)題時(shí)，往往將FECM 中的五行元素拓展為任意元素，并將所有元素劃分為q個(gè)環(huán)，每個(gè)環(huán)包含L個(gè)元素。xij(k) 表示第k時(shí)刻第j個(gè)環(huán)中的第i個(gè)元素，mi j(k) 表示元素xij(k) 的質(zhì)量，F(xiàn)ij(k)表示元素xij(k) 所受第j個(gè)環(huán)中的其他元素的作用合力，F(xiàn)i j(k) 的表達(dá)形式如下：

在FECO 算法中，F(xiàn)i j(k) 的大小反映了元素xij(k)質(zhì)量的優(yōu)劣。當(dāng)Fi j(k)>0 時(shí)，元素xij(k) 的質(zhì)量較優(yōu)。因?yàn)樵谙到y(tǒng)平衡中大的受力會(huì)使元素變得強(qiáng)壯，所以當(dāng)前的xij(k) 被保留到下一代。當(dāng)Fi j(k)<0時(shí)，元素xij(k) 的質(zhì)量較差。Fi j(k) 為負(fù)，說(shuō)明系統(tǒng)期望當(dāng)前元素變得更加衰弱，所以當(dāng)前的xij(k)會(huì)被其他元素替換。重復(fù)此過(guò)程，直至達(dá)到最大迭代次數(shù)，即可獲得所求問(wèn)題的最優(yōu)解。

3.2 FECO-DMUI 算法的適應(yīng)度函數(shù)以及個(gè)體的編碼與解碼

本文模型中初始化種群n=L×q，選取式（7）和式（8）作為評(píng)估函數(shù)。由于需要將客戶點(diǎn)與配送車輛同時(shí)進(jìn)行編碼，所以采用隨機(jī)鍵[20]的方式。若客戶點(diǎn)數(shù)為N，配送車輛數(shù)為G，則個(gè)體xij(k) 的編碼長(zhǎng)度為N+G?1 ，每一位的取值范圍是 [0,1] 之間的小數(shù)。由N+G?1 個(gè) [0,1] 之間的小數(shù)組成一個(gè)個(gè)體xij(k)的過(guò)程即為編碼。解碼時(shí)，首先對(duì)個(gè)xij(體k)中的每一位進(jìn)行大小排序，最小值對(duì)應(yīng)1，次小值對(duì)應(yīng)2，以此類推，通過(guò)這樣的方式將個(gè)N+G?1[0,1]之間的小數(shù)轉(zhuǎn)化為1～N+G?1的自然數(shù)排列。其中1～N表示客戶N+點(diǎn)1N，+G～ ?1表示線路分割符號(hào)，通過(guò)線路分割符號(hào)得到每輛車的配送路線。以圖3 為例，客戶點(diǎn)數(shù)N=10 ，車輛數(shù)G=3 ，則個(gè)體的長(zhǎng)度為12，1～10 表示客戶點(diǎn)，11～12 表示線路分割符，因此每輛車的配送路線為：第1 輛車：1→5；第2 輛車：8→3→2；第3 輛車：10→7→4→6→9。

圖3 編碼與解碼操作Fig.3 Encoding and decoding operations

3.3 FECO-DMUI 算法通過(guò)選擇、交叉和變異產(chǎn)生新個(gè)體

3.3.1 選擇 本文采用的選擇方式為錦標(biāo)賽選擇[21]。每次從種群規(guī)模為n的種群中抽取n/2 的個(gè)體，從已抽取的個(gè)體中選擇目標(biāo)函數(shù)達(dá)到最優(yōu)的一個(gè)進(jìn)入子代種群。重復(fù)上述操作，直到新的種群規(guī)模達(dá)到原來(lái)的種群規(guī)模n。對(duì)于多目標(biāo)優(yōu)化模型來(lái)說(shuō)，目標(biāo)函數(shù)最優(yōu)是指從當(dāng)前Pareto 前沿面上的兩個(gè)端點(diǎn)解以及擁擠距離最大的解中隨機(jī)選擇一個(gè)，這樣既能迭代出最優(yōu)解也能找到更均勻的Pareto 前沿面。

3.3.2 交叉 本文采用的交叉方式為單點(diǎn)交叉，交叉概率為pc，即在當(dāng)前迭代過(guò)程中的個(gè)體xij(k) 中隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)，以該交叉點(diǎn)為基準(zhǔn)相互交換兩個(gè)個(gè)體、的序列，產(chǎn)生新的個(gè)體、，統(tǒng)。交叉過(guò)程如圖4 所示。

圖4 交叉操作Fig.4 Cross operation

3.3.3變異 本文采用的變異方式為單點(diǎn)變異與高斯變異各占一半的混合變異方式，即每個(gè)個(gè)體以0.5 的概率選擇單點(diǎn)變異或高斯變異，變異概率為pm。采用單點(diǎn)變異時(shí)，隨機(jī)產(chǎn)生一個(gè)變異點(diǎn)，用新生成的[0,1]之間的小數(shù)替換初始變異點(diǎn)上的數(shù)。采用高斯變異時(shí)，隨機(jī)產(chǎn)生一個(gè)變異點(diǎn)，用一個(gè)均值為μ、方差為 σ2的正態(tài)分布的隨機(jī)數(shù)替換初始變異點(diǎn)上的數(shù)。通過(guò)變異產(chǎn)生的新個(gè)體記為。變異過(guò)程如圖5 所示。

圖5 變異操作Fig.5 Mutation operation

3.4 FECO-DMUI 算法通過(guò)對(duì)受力大小的判斷產(chǎn)生新個(gè)體

本文中，個(gè)體xij(k)代表冷鏈物流優(yōu)化模型的一個(gè)解，f1(xij(k))、f2(xij(k))為其目標(biāo)函數(shù)的值，mi j(k)表示元xi素j(k)的質(zhì)量。由于本文建立的模型為多目標(biāo)優(yōu)化模型，所以將個(gè)體xij(k)的非支配等級(jí)賦值給。mi j(k)是Fi衡j(k)量個(gè)體xij(k)質(zhì)量?jī)?yōu)劣的變量，因此，通過(guò)對(duì)受力大小的判斷來(lái)產(chǎn)生新個(gè)體的方式就是根據(jù)的Fi j(值k)來(lái)更新個(gè)xi體j(k)，得到的新個(gè)體記為。根據(jù)式（17）計(jì)算Fi j(k) 的值。若Fi j(k)>0 ，說(shuō)明當(dāng)前個(gè)體xij(k) 的質(zhì)量較優(yōu)，則保留當(dāng)前個(gè)體，即=xi j(k)。若Fi j(k)≤0 ，說(shuō)明當(dāng)前個(gè)體xij(k) 的質(zhì)量較差，則根據(jù)式（18）更新當(dāng)前個(gè)體。

式中：rs、rm分別取 [0,1] 區(qū)間的隨機(jī)數(shù)；ps表示尺度因子；pn表示給定的概率；xrank1?(k) 表示在Pareto 排序?yàn)? 的個(gè)體中隨機(jī)選取的某個(gè)個(gè)體；xbest(k)表示種群中的全局最優(yōu)個(gè)體。

3.5 個(gè)體的修復(fù)

在更新過(guò)程中還需要判斷更新后的個(gè)體是否存在線路分割符相鄰或處于首末位的情況。若存在，就會(huì)有車輛閑置，此時(shí)修復(fù)的方法為：將包含客戶點(diǎn)最多的配送路線中的第1 個(gè)客戶點(diǎn)分配給閑置的車輛。以圖4 為例，此時(shí)的個(gè)體出現(xiàn)了車輛閑置的情況，修復(fù)結(jié)果如圖6 所示。修復(fù)前的路線為：第1 輛車：5→1→10→8→2→3，第2 輛車：7→4→6→9，第3 輛車閑置；修復(fù)后的路線為：第1 輛車：1→10→8→2→3，第2 輛車：7→4→6→9，第3 輛車：5。

圖6 個(gè)體的修復(fù)Fig.6 Individual repair

3.6 非支配排序與擁擠度計(jì)算

對(duì)于多目標(biāo)優(yōu)化問(wèn)題而言，非支配排序和擁擠度計(jì)算是求取Pareto 最優(yōu)解集的關(guān)鍵。在FECODMUI 算法中，經(jīng)過(guò)選擇、交叉和變異產(chǎn)生的新個(gè)體為，形成的種群規(guī)模為n；通過(guò)對(duì)受力大小的判斷產(chǎn)生的新個(gè)體為，形成的種群規(guī)模也為n。將兩種方式產(chǎn)生的新個(gè)體合并后，通過(guò)非支配排序與擁擠度計(jì)算篩選出n個(gè)個(gè)體形成新的種群，并使其進(jìn)入下一次迭代。

3.7 FECO-DMUI 算法流程

FECO-DMUI 算法流程如圖7 所示。首先，初始化種群xij(0)，mi j(0) 和Fi j(0) ；其次，對(duì)初始化種群進(jìn)行非支配排序與擁擠度計(jì)算，并將每個(gè)個(gè)體的非支配等級(jí)賦值給mi j(k) ；然后，在每一次的迭代過(guò)程中，通過(guò)兩種方式產(chǎn)生新的個(gè)體；最后，將兩種方式產(chǎn)生的個(gè)體合并形成規(guī)模為 2n的種群，重新計(jì)算合并后種群的非支配排序與擁擠度，通過(guò)每個(gè)個(gè)體的非支配等級(jí)與擁擠度選出新的較優(yōu)個(gè)體組成新的規(guī)模為n的種群，進(jìn)入下一次迭代。當(dāng)?shù)螖?shù)達(dá)到最大時(shí)，算法結(jié)束并得到最終的Pareto 最優(yōu)解集。

圖7 FECO-DMUI 算法流程圖Fig.7 Algorithm flowchart of FECO-DMUI

4 算例分析

4.1 相關(guān)數(shù)據(jù)

為了驗(yàn)證本文模型與算法的有效性，借鑒了文獻(xiàn)[22]中客戶點(diǎn)和配送中心的相關(guān)數(shù)據(jù)來(lái)實(shí)現(xiàn)本文模型。客戶點(diǎn)信息如表1 所示，其中0 代表配送中心，1～25 代表客戶點(diǎn)。為了更清晰地了解配送中心與客戶點(diǎn)的位置，圖8 示出了具體的分布圖，橫、縱坐標(biāo)分別代表客戶點(diǎn)與配送中心在平面圖中的x軸與y軸。

圖8 客戶點(diǎn)分布圖Fig.8 Distribution map of customer point

表1 客戶點(diǎn)信息Table 1 Customer point information

算例設(shè)置如下：1 個(gè)配送中心，由4 輛車向25 個(gè)客戶點(diǎn)進(jìn)行配送。優(yōu)化模型中涉及的參數(shù)取值如表2所示。實(shí)驗(yàn)平臺(tái)為MATLAB R2019b 版本。

表2 優(yōu)化模型參數(shù)取值Table 2 Parameter values of optimize model

4.2 算法參數(shù)分析

經(jīng)過(guò)反復(fù)測(cè)試得出，當(dāng)最大迭代次數(shù) (kmax) 為2 000、環(huán)的個(gè)數(shù) (q) 為40 以及每個(gè)環(huán)中包含的元素個(gè)數(shù)(L)為5 時(shí)，F(xiàn)ECO-DMU 算法處于收斂狀態(tài)且算法性能最優(yōu)。當(dāng)權(quán)重系數(shù)取值為1 時(shí)，算法性能達(dá)到最佳[11]。對(duì)于其他參數(shù)，通過(guò)對(duì)FECO-DMUI 算法進(jìn)行多組比較實(shí)驗(yàn)來(lái)選取合適的取值。選取的一組基本參數(shù)值為：交叉概率（pc）為0.4，變異概率（pm）為0.2，尺度因子（ps）為1，給定的概率（pn）為0.9，當(dāng)對(duì)一個(gè)參數(shù)進(jìn)行比較時(shí), 其他參數(shù)均選取上述基本值。表3～表6分別給出了每個(gè)參數(shù)的實(shí)驗(yàn)比較結(jié)果，均為算法運(yùn)行10 次所取得的平均值。

超體積指標(biāo)(Hyper Volume，HV)[23]是評(píng)價(jià)多目標(biāo)優(yōu)化算法綜合性能的指標(biāo)，HV 值越大，說(shuō)明算法的綜合性能越好。在計(jì)算HV 時(shí)，選取的參考點(diǎn)由顧客滿意度和配送成本組成，針對(duì)本文提出的多目標(biāo)優(yōu)化模型，參考點(diǎn)的具體取值為(58 810，0.5895)，不同的多目標(biāo)優(yōu)化模型需根據(jù)實(shí)際情況選取參考點(diǎn)。

由表3 可知，當(dāng)pc=0.4 時(shí)，HV 值最大，說(shuō)明此時(shí)FECO-DMUI 算法的綜合性能最佳。由表4 可知，當(dāng)pm=0.2 時(shí)，HV 值最大，說(shuō)明此時(shí)FECO-DMUI 算法的綜合性能最佳。由表5 可知，當(dāng)ps=1.0 時(shí)，HV 值最大，說(shuō)明此時(shí)FECO-DMUI 算法的綜合性能最佳。由表6 可知，當(dāng)pn=0.9 時(shí)，HV 值最大，說(shuō)明此時(shí)FECO-DMUI 算法的綜合性能最佳。

表3 交叉概率比較實(shí)驗(yàn)Table 3 Crossover probability comparison experiment

表4 變異概率比較實(shí)驗(yàn)Table 4 Mutation probability comparison experiment

表5 尺度因子比較實(shí)驗(yàn)Table 5 Scale factor comparison experiment

表6 給定概率比較實(shí)驗(yàn)Table 6 Comparison experiment with given probability

4.3 算法結(jié)果分析

利用FECO- DMUI 算法解決多目標(biāo)冷鏈物流配送路徑優(yōu)化問(wèn)題，得到每輛車的配送路徑如圖9 所示，其中：橙色代表車輛1，紫色代表車輛2，綠色代表車輛3，藍(lán)色代表車輛4。

圖9 中的方案分別對(duì)應(yīng)Pareto 解集中的兩個(gè)端點(diǎn)解以及相對(duì)居中的一個(gè)解。方案1 為配送成本最小化，此時(shí)配送成本為39 861 元，顧客滿意度為0.645 4；方案2 為顧客滿意度最大化，此時(shí)配送成本為57 149元，顧客滿意度為0.944 6；方案3 為配送成本與顧客滿意度均取折中，此時(shí)配送成本為47 646 元，顧客滿意度為0.871 9。

圖9 路徑規(guī)劃圖Fig.9 Path planning diagrams

本文優(yōu)化方案比單純的多回路運(yùn)輸問(wèn)題(Vehicle Routing Problem, VRP)復(fù)雜，原因如下：對(duì)于方案3 中的第1 輛車，它經(jīng)過(guò)客戶點(diǎn)2 后，直接到達(dá)了客戶點(diǎn)20，若按最短路徑的原則行駛，經(jīng)過(guò)客戶點(diǎn)2 后要先到達(dá)同一路線上的客戶點(diǎn)25，之所以以這樣的方式行駛，是因?yàn)榭蛻酎c(diǎn)20 的時(shí)間窗為(11,89,200,290)，客戶點(diǎn)25 的時(shí)間窗為(72,190,300,382)，先去客戶點(diǎn)25 很有可能錯(cuò)過(guò)客戶點(diǎn)20 的最優(yōu)時(shí)間窗，甚至錯(cuò)過(guò)配送的整個(gè)時(shí)間窗，所以選擇先到達(dá)客戶點(diǎn)20，其他類似的情況同理。

4.4 算法對(duì)比分析

為了進(jìn)一步驗(yàn)證本文算法的有效性，基于相同的數(shù)據(jù)集和編碼方式，采用NSGA-II 算法、FECO 算法、WOA 算法以及GWO 算法分別對(duì)模型求解，將得到的結(jié)果與FECO-DMUI 算法進(jìn)行對(duì)比，進(jìn)一步驗(yàn)證本文算法的有效性。

FECO-DMUI 算法采用的算法參數(shù)和最大迭代次數(shù)與4.2 節(jié)、4.3 節(jié)相同。NSGA-II 算法的n=200，kmax=4 000，p且c=交0.叉4方式均為單點(diǎn)交叉，pm=0.2且變異方式均為混合變異，選擇方式依然為錦標(biāo)賽選擇。FECO 算法的n=200 ，kmax=4 000，ps=1 ，pn=0.9以及權(quán)wgp=重wrp=系wga=w數(shù)ra=1。WOA算法的，n=2，00k系max=數(shù)4 000 和r1r2為[0,1]之間的隨機(jī)數(shù)，系數(shù)l為[?1,1]內(nèi)的隨機(jī)數(shù)，定義螺線的形狀系數(shù)b=1。GWO 算法的n=200 ，kmax=4 000 ，r1，r2的取值與WOA 算法取值相同。

將5 種算法分別對(duì)優(yōu)化模型進(jìn)行求解，得到Pareto 最優(yōu)解集分布如圖10 所示，對(duì)比結(jié)果如表7所示。

從圖10 可以看出，F(xiàn)ECO-DMUI 算法求解所得的Pareto 最優(yōu)解集明顯優(yōu)于其他算法，同時(shí)，F(xiàn)ECODMUI 算法得到的可行解的數(shù)量多于其他算法。

圖10 最優(yōu)解集分布圖Fig.10 Optimal solution set distribution graph

表7 中HV 是算法運(yùn)行10 次所取的平均值。可以看出FECO-DMUI 算法所得HV 明顯大于其他算法，證明了算法的綜合性能好。選取10 次運(yùn)行結(jié)果中HV 居中的一次，將該次運(yùn)行結(jié)果中各算法獲得的Pareto 最優(yōu)解集中的邊界解作為表7 中的“最小配送成本”和“最大顧客滿意度”兩列。此時(shí)，F(xiàn)ECODMUI 算法在配送成本的求解上雖不是最優(yōu)的，但與最優(yōu)解相差不大，而在顧客滿意度的求解上，結(jié)果明顯優(yōu)于其他算法。表7 中“平均最小配送成本”與“平均最大顧客滿意度”是算法運(yùn)行10 次取所有最小配送成本和最大顧客滿意度的平均值。通過(guò)5 種算法的對(duì)比可以看出，F(xiàn)ECO-DMUI 算法不論是在配送成本的求解上還是在顧客滿意度的求解上均最優(yōu)，充分證明了FECO-DMUI 算法的有效性。

表7 5 種算法的對(duì)比結(jié)果Table 7 Comparison results of five algorithms

5 結(jié) 論

本文基于冷鏈物流的實(shí)際情況建立了以配送成本最小化、顧客滿意度最大化為優(yōu)化函數(shù)的多目標(biāo)數(shù)學(xué)模型，其中配送成本包含運(yùn)輸成本、貨損成本、制冷成本以及時(shí)間懲罰成本。在考慮配送成本的同時(shí)，通過(guò)顧客的特定時(shí)間窗和配送車輛到達(dá)客戶點(diǎn)的時(shí)間點(diǎn)來(lái)反映顧客滿意度，從而達(dá)到成本最小化和顧客滿意度最大化的優(yōu)化效果。實(shí)例驗(yàn)證表明，F(xiàn)ECO-DMUI 算法在求解冷鏈物流配送的問(wèn)題中能夠得到更優(yōu)的配送方案，證明了FECO-DMUI 算法的有效性與實(shí)用性。