雙目標冷鏈物流車輛路徑問題及其遺傳蟻群求解

張 瑾， 畢國通， 戴二壯

(1. 河南大學計算機與信息工程學院，開封 475004；2. 河南大學商學院，開封 475004)

近年來，生鮮食品需求日益增多，實體超市與電商平臺不斷布局生鮮新零售，生鮮產品的易腐性要求對其進行冷鏈運輸。除造成配送成本的增加以外，生鮮產品配送的時效會對其品質造成影響，從而影響消費者的購物體驗。對冷鏈物流車輛路徑問題進行合理優化，在滿足企業市場定位的前提下有效控制配送成本、提高客戶滿意度，是提高企業市場競爭力的有效手段[1]。

冷鏈物流車輛路徑問題是車輛路徑問題(vehicle routing problem，VRP)在冷鏈物流的實際應用，可根據優化目標將相關研究文獻分為單目標和多目標兩種類型，后者相關研究相對較少。單目標相關文獻中，繆小紅等[2]考慮軟時間窗限制，構建了以貨損成本、懲罰成本與運輸成本之和最小為目標的優化模型，利用改進的遺傳算法求解最優配送路線，求解結果優于標準遺傳算法；Zhang等[3]建立了包含運輸、制冷、貨損和懲罰成本在內的總成本最低的優化模型，考慮了時間窗、載重和不同食品單位體積的裝載量約束，采用遺傳算法求解，驗證了該模型的可行性和合理性；楊珍花等[4]構建了冷藏車多車型混合配送優化模型，開發了混合模擬退火算法，并對比分析不同車型組合下配送成本的差異，表明提出的混合配送方案在總成本和碳排放方面具有優勢；葛顯龍等[5]考慮軟時間窗約束，以生鮮配送損耗為可變成本，車輛啟動費用為固定成本，建立了以總成本最小為目標的生鮮配送模型，表明所提模型可以有效縮短里程、節約成本；潘茜茜等[6]構建了運輸成本、懲罰成本、貨損成本、固定成本和碳排放成本最小的冷鏈物流配送路徑優化模型，采用蟻群算法求解模型；錢光宇[7]構建了以碳排放成本和車輛使用成本、運輸成本、制冷成本、貨損成本最小為目標的生鮮農產品冷鏈配送路徑優化模型，表明所建模型能夠有效減少冷鏈配送過程中產生的二氧化碳；樊世清等[8]建立了含固定成本、運輸成本、貨損成本、懲罰成本和能耗成本在內的總成本最小為目標的農產品冷鏈物流車輛配送路徑優化模型，采用改進的蟻群算法驗證了模型的合理性和可行性；盧甲東等[9]考慮客戶地理位置的相鄰性以及交貨時間相似性，構建了基于時空相似度的冷鏈物流分區配送模型，設計了問題求解的遺傳算法。多目標相關文獻中，Amorim等[10]針對易腐食品構建了配送成本最小化與產品新鮮度最大化的雙目標模型，研究配送方案與成本-新鮮度之間的關系，表明這兩個目標不能同時達到最優；Wang等[11]研究了易腐食品多目標帶時間窗車輛路徑問題，以總成本最低和新鮮度最大作為優化目標，提出一種基于Pareto可變鄰域搜索的兩階段啟發式算法，結果表明算法是有效的；梁承姬等[12]建立了包含運輸成本、貨損成本、時間成本等在內的配送成本最小化和客戶滿意度最大化的雙目標冷鏈物流配送優化模型，運用改進的遺傳算法進行求解，表明模型和算法是有效性的；張亞明等[13]建立基于時間和品質因素的顧客滿意度約束的多配送中心冷鏈物流車輛路徑模型，采用重心分區法和改進的精英單親遺傳算法求解，表明該模型更適合冷鏈物流配送最優路徑選擇；王勇等[14]考慮生鮮商品配送的物流成本和價值損失成本，構建使上述損失最小的配送優化模型，設計了基于K-means聚類的遺傳-禁忌搜索算法，分析得到不同生鮮商品在配送過程中的最佳配送溫度和包含不同配送單元的最佳聚類數；張倩等[15]構建了考慮配送成本、產品新鮮度及碳排放和需求不確定因素的配送模型，應用目標法和果蠅算法對問題模型進行求解，驗證了模型及算法的魯棒性。

通過對近年來冷鏈物流車輛路徑問題相關文獻進行研究，發現綜合考慮總成本和客戶滿意度的多目標優化研究較少，其多目標問題的處理主要通過線性加權、權重迭代、優先級法及約束法等，主要思路是將目標函數轉化為單目標進行求解，但這些方法對于確定參數的大小或優先級具有一定的主觀性，需要決策者本身對每個目標都有比較明確的把握，且研究結果具有特殊性。基于此，將考慮軟時間窗和車輛容量約束，構建以總成本最低和客戶滿意度最高為目標的雙目標冷鏈物流車輛路徑優化模型，采用ε約束法處理多個目標以避免問題處理時的主觀性和特殊性，結合遺傳(genetic algorithm，GA)和蟻群算法(ant colony optimization，ACO)各自優勢，設計了模型求解的遺傳蟻群算法(genetic-ant colony optimization algorithm，GA-ACO)。

1 冷鏈物流車輛路徑問題模型

研究帶容量和軟時間窗約束的雙目標冷鏈物流車輛路徑問題，由一個配送中心服務多個客戶，配送車輛具有容量約束，所有車輛均從配送中心出發，客戶服務完成后返回配送中心，優化目標是在保證完成客戶需求的前提下最小化總成本及最大化客戶滿意度。

1.1 模型假設

所研究問題的前提條件如下：①僅有一個配送中心，所有冷藏車都由配送中心出發并最終返回配送中心；②所有冷藏車都是同質的；③每個客戶點僅有送貨需求，沒有取貨需求；④每個客戶的需求量和位置都是已知和固定的；⑤每個客戶由且僅由一輛車提供服務；⑥每個客戶都有期望時間窗和可接受時間窗；⑦冷藏車在運輸途中勻速行駛，僅在客戶點處停留；⑧僅配送一種生鮮農產品，貨損比例已知；⑨冷藏車運輸過程中車廂內外溫度恒定。

1.2 參數說明

模型中相關重要參數定義如下：K為所需車輛總數；dij為客戶i和客戶j的距離；qi為客戶i的需求量；tj為客戶j卸貨需要的時間；p為單位質量農產品的價格；v為配送車輛行駛速度；Mweight為車輛額定載重；λ為使用每輛冷藏車的固定成本；λ0為冷藏車單位距離運輸成本；λ1為運輸過程單位時間內的制冷成本；λ2為卸貨時單位時間內的制冷成本(通常λ2≥λ1)；λ3為運輸過程單位時間內的貨損率；λ4為卸貨時單位時間內的貨損率(通常λ4≥λ3)；λ5為早到時單位時間懲罰成本；λ6為遲到時單位時間懲罰成本；[ETi,LTi]為客戶i最佳服務時間窗；[AETi,ALTi]為客戶i可接受時間窗；M為無窮大的懲罰成本。

決策變量定義為

(1)

(2)

1.3 模型建立

綜合考慮成本和客戶滿意度兩方面因素，優化目標為

(3)

式(3)中：minC表示最小化總成本C；maxS表示最大化客戶滿意度S。

1.3.1 成本因素分析

總成本主要包括固定成本、運輸成本、制冷成本、貨損成本和懲罰成本。

(1)固定成本：指安排車輛完成客戶需求所產生的固定費用，包括車輛保養、維護、折舊損耗以及員工工資等費用，記為C1，計算公式如式(4)所示：

C1=λK

(4)

(2)運輸成本：指冷藏車完成配送所需的燃油費用，通常與運輸距離成正比，記為C2，計算公式如式(5)所示：

(5)

(3)制冷成本：包括運輸途中車廂溫度恒定的制冷成本和卸貨過程中車門開啟產生熱交換的制冷成本，記為C3，計算公式如式(6)所示：

(6)

(4)貨損成本：主要包括運輸途中和卸貨時產生的貨損成本，記為C4，運輸時車廂溫度恒定，卸貨時產生熱交換引起車廂溫度升高，導致運輸和卸貨時貨損率不同，計算公式如式(7)所示：

(7)

式(7)中:ri表示離開客戶i時車廂內貨物重量。

(5)懲罰成本：在配送車輛未在客戶定義的最佳時間窗內到達時產生，將其定義為無窮大的數M。任一客戶i具有一個最佳服務時間窗[ETi,LTi]和可接受時間窗[AETi,ALTi]，若配送車輛在[ETi,LTi]之內到達客戶i，不會產生懲罰成本；若在[ETi,LTi]之外、[AETi,ALTi]之內到達客戶i，會產生一定的懲罰成本；若在[AETi,ALTi]之外到達，客戶i將拒絕接受服務。客戶i的懲罰成本P(ti)與車輛到達時間ti之間的關系如圖1所示，其函數關系定義為

圖1 懲罰成本與車輛到達時間關系Fig.1 Relationship between penalty cost and arrival time

(8)

由此可得所有客戶的總懲罰成本C5，計算公式為

(9)

1.3.2 客戶滿意度分析

客戶滿意度主要依據時間窗進行定義，若在[ETi,LTi]之內到達客戶i，則其滿意度為100%；若在[ETi,LTi]之外，[AETi,ALTi]之內到達客戶i，其滿意度會有一定的降低；若在[AETi,ALTi]之外到達客戶i，其滿意度為0，不再接受服務。客戶i的滿意度S(ti)與車輛到達時間ti之間的關系如圖2所示，函數關系定義為

圖2 客戶滿意度與車輛到達時間關系Fig.2 Relationship between customer satisfaction cost and arrival time

(10)

總體客戶滿意度S依據每個客戶的需求量占整體的比重分配相應的權重：

(11)

1.3.3 模型構建

根據上述分析，構建模型如式(12)～式(21)所示：

minC=C1+C2+C3+C4+C5

(12)

(13)

s.t.

(16)

(17)

(18)

(19)

(20)

AETi≤ti≤ALTi

(21)

式(12)為目標函數，即使綜合成本最低；式(13)為目標函數，即使客戶滿意度最高；式(14)～式(21)為約束條件，其中式(14)、式(15)為決策變量取值約束；式(16)表示為車輛容量約束；式(17)、式(18)保證每個客戶能且僅能被一輛車服務；式(19)表示配送中心共發出K輛冷藏車；式(20)表示每輛車從配送中心出發，最后返回配送中心；式(21)指每輛車都要在可接受時間窗內到達。

2 求解冷鏈物流車輛路徑問題的遺傳蟻群算法

由于所設計模型源于經典的屬于NP(non-deterministic polynomial)難題的VRP問題，傳統算法難以在有限時間內獲得精確解，適宜采用智能算法。考慮蟻群和遺傳算法是當前公認的較為常用且具有良好性能的智能優化算法，蟻群算法具有正反饋機制、局部尋優能力強，但存在搜索時間過長且會因信息素累積而陷入局部最優解；遺傳算法具有較好的全局搜索能力，卻過于依賴初始種群并因缺少反饋機制而存在冗余迭代。結合二者的優缺點，在ACO中引入GA的交叉算子和變異算子，設計遺傳蟻群算法以求解該問題。首先通過ACO生成初始解，然后對其實施交叉操作和變異操作，以增加種群多樣性，從而提高算法收斂速度和解的質量。

2.1 蟻群算法求解初始解

2.1.1 種群初始化

首先利用蟻群算法對種群進行初始化，得到初始種群，過程如下。

Step1將種群中每只螞蟻的起始點設為配送中心并將其編號記為0，對于每只螞蟻，在n個需求點中隨機選取一個地點作為其第一個訪問點，并記錄到路徑禁忌表中。

Step2構建解空間。對每只螞蟻k(k=1,2,…,m)，按照狀態轉移規則選擇每個待訪問的地點，并修改禁忌表，直到全部螞蟻訪問完所有地點。

為了避免算法過早收斂，狀態轉移按照確定性選擇和偽隨機比例選擇相結合的方式進行。確定性選擇規則為

(22)

式(22)中:q0為初始化參數，且q0∈[0,1]；q為[0,1]區間內的隨機數；τij(t)為啟發函數，表示在t時刻的邊(i，j)上的信息素大小；α為信息啟發因子，表示信息素的相對重要性；ηij(t)表示從客戶i到客戶j的啟發程度，且ηij(t)=1/dij；β為期望啟發因子，表示能見度的相對重要性。

當q>q0時，采用偽隨機比例選擇，如式(23)所示：

(23)

式(23)中:Fk(k=1,2,…,m)為螞蟻k待訪問的需求點集合。

2.1.2 種群適應度計算

使用蟻群算法生成初始種群后，需要計算初始種群的適應度，獲得當前最優解。由于研究目標為雙目標，為求得種群的適應度，采用ε約束法處理雙目標函數。ε約束法是一種處理多目標優化問題的有效方法，主要思想是先對其中一個目標函數f1(x) 進行尋優，尋得最優值ε，并將此值作為f1(x)的約束條件，在其不小于ε的條件下，尋找另一目標f2(x)的最優值，獲得一組帕累托解。逐漸增加ε的值，并以此為約束求得f2(x)的最優值，通過多次求解，逐漸求得多組在f1(x)不同值情況下f2(x)的帕累托解。

由于成本受諸多因素影響，較難進行人為控制，而客戶滿意度的大小則可以依據企業的經營目標進行控制，因此將客戶滿意度作為約束。先對客戶滿意度進行尋優，尋得最優值ε，并將此值作為約束條件，在其不小于ε的條件下，尋找總成本的最優值，然后逐漸減小ε的值，并以此為約束求得總成本的最優值，獲得帕累托解。種群適應度計算流程如下。

Step1分配配送路線。

Step2計算每條染色體的適應度。

Step3計算客戶滿意度。

Step4求解給定客戶滿意度情況下當前最優適應度和全局最優適應度，若當前最優適應度大于全局最優適應度，則將當前最優適應度作為全局最優適應度，并記錄當前編碼方式和路線分配方式。

2.2 遺傳算法優化

2.2.1 交叉操作

染色體按照概率Pc(0≤Pc≤1)進行交叉，交叉方式采用部分映射交叉。將父代染色體兩兩分組，每組按照如下方式進行交叉。

Step1判斷是否進行交叉操作。生成一個隨機數，若隨機數小于Pc，則該組染色體進行交叉操作，否則重新生成隨機數，并判斷下一組染色體。

Step2若進行交叉操作，則生成小于染色體長度的兩個隨機整數r1和r2，對應兩個進行交叉操作的位置，對之間的染色體進行交叉。

Step3消除染色體沖突。由于交叉后可能存在重復標號和有的位置被覆蓋，因此需要消除染色體沖突。采用部分映射的方法消除沖突，通過尋找沖突位置原始染色體對應的編號以取代被替換掉的編號。

Step4驗證交叉后染色體是否符合要求，若符合則作為新的染色體進行下一步操作，否則舍去。

2.2.2 變異操作

染色體按照概率Pm(0≤Pm≤1)進行變異操作，變異方式采用以下策略。

Step1遍歷每條染色體，每次生成一個隨機數，若隨機數小于Pm，則該染色體進行變異操作，否則判斷下一條染色體是否進行變異操作。

Step2若進行變異操作，則隨機選取該染色體的兩個點，并將其對換位置，產生新的染色體。

Step3驗證變異后染色體是否符合要求，若符合則作為新的染色體進行下一步操作，否則舍去。

2.3 更新信息素

所有螞蟻完成一次路徑分配后，按照式(24)、式(25)對路徑上的信息素進行更新。

τij(t+1)=(1-ρ)τij(t)+Δτij

(24)

(25)

(26)

式(26)中：Lk為第k只螞蟻經過路徑的長度；Q表示螞蟻循環一次所釋放的信息素總量。Q過大時，會使信息素過于集中在某一路徑，從而使算法早熟；Q過小時，路徑上信息素濃度增長緩慢，從而使算法收斂速度慢。因此，對信息素總量Q采用分段函數進行優化：

(27)

式(27)中：ite為當前迭代次數；ite1、ite2、ite3為設定的一定迭代臨界值。

算法偽代碼如下。

Begin

Step1：初始化參數；

Step2：按照轉移概率選擇下一地點；

Step3：修改禁忌表；

If遍歷完所有螞蟻

計算適應度，更新已知最優解；

Else

選擇下一只螞蟻，跳轉至Step2；

Step4：更新已知最優解；

Step5：進行交叉操作；

Step6：進行變異操作；

Step7：計算適應度，更新已知最優解；

If滿足循環結束條件

輸出最優解；

Else

更新信息素和迭代次數，清空路徑記錄表，跳轉至Step2；

End

3 算例分析

以文獻[6]中配送案例作為算例，研究單配送中心和20個門店的生鮮物流配送優化問題。實驗設備采用聯想PC機，操作系統為Windows 7 64位旗艦版，Intel i5 2450M CPU，2.5 GHz頻率，6 GB內存，采用MATLAB R2014a作為仿真平臺，分別采用遺傳算法、蟻群算法和遺傳蟻群算法進行求解，通過對比分析驗證模型及算法的有效性。

3.1 算例描述

假設各配送點之間的距離均為歐氏距離，配送中心位置、各門店位置、客戶時間窗、客戶需求量和服務時間等詳細信息如表1所示，所用參數值如表2 所示。

表1 某生鮮農產品配送中心配送數據Table 1 Data of a fresh agricultural products distribution center

表2 所需參數值Table 2 Parameter values

3.2 算法迭代次數分析

為了確定算法的最佳迭代次數，驗證算法的穩定性，設置不同的迭代次數以求解在不同客戶滿意度情況下三種算法的最低成本。由于企業大都追求較高的客戶滿意度，分別選取100%、90%和80%三個較有代表性的滿意度，并求解相應總成本。

在客戶滿意度為100%的情況下，三種算法不同迭代次數的求解結果如表3所示。

表3 客戶滿意度為100%時三種算法不同迭代次數最優解Table 3 Optimal results of three algorithms and iterations when customer satisfaction is 100%

客戶滿意度為100%時三種算法求解結果與迭代次數關系如圖3所示。

圖3 客戶滿意度為100%時三種算法求解結果與迭代次數關系Fig.3 Results of three algorithms and iterations when customer satisfaction is 100%

在客戶滿意度為90%的情況下，三種算法不同迭代次數的求解結果如表4所示。

表4 客戶滿意度為90%時三種算法不同迭代次數最優解Table 4 Optimal results of three algorithms and iterations when customer satisfaction is 90%

客戶滿意度為90%時三種算法求解結果與迭代次數關系如圖4所示。

圖4 客戶滿意度為90%時三種算法求解結果與迭代次數關系Fig.4 Results of three algorithms and iterations when customer satisfaction is 90%

在客戶滿意度為80%的情況下，三種算法不同迭代次數的求解結果如表5所示。

表5 客戶滿意度為80%時三種算法不同迭代次數最優解Table 5 Optimal results of three algorithms and iterations when customer satisfaction is 80%

客戶滿意度為80%時三種算法求解結果與迭代次數關系如圖5所示。

圖5 客戶滿意度為80%時三種算法求解結果與迭代次數關系Fig.5 Results of three algorithms and iterations when customer satisfaction is 80%

通過GA、ACO和GA-ACO三種算法在不同客戶滿意度下求得的最低成本進行對比后得到以下結果。

(1)在收斂速度方面，當客戶滿意度分別為100%和90%時，GA和ACO在迭代進行到500次時收斂，GA-ACO在迭代進行到400代時即收斂；當客戶滿意度為80%時，三種算法均在500代時收斂至最小值。表明GA-ACO收斂速度快于GA和ACO，能夠在迭代次數較少時收斂，獲得最優值。

(2)在求解結果方面，在相同迭代次數下，GA-ACO求解結果均優于GA和ACO；在求解精度方面，GA-ACO最終求得的最優解優于GA和ACO求得的最優解。

由于市場競爭激烈，客戶滿意度是企業競爭的關鍵因素，大都追求較高的客戶滿意度，因此，為提高求解效率和求解精度，設置GA-ACO的最大迭代次數Max_iter=400，GA和ACO最大迭代次數Max_iter=500。

3.3 算例求解

為了獲得帕累托解，首先將客戶滿意度的初始值設為100%，并依次遞減5%，分別用三種算法求解不同滿意度下的最低成本，每種算法分別運行20次，取最優結果作為該算法求得的最終結果。三種算法求得的解如表6所示。

表6 GA、ACO和GA-ACO求解結果Table 6 Solution results of GA, ACO and GA-ACO

三種算法在不同客戶滿意度下求得結果的對比圖如圖6所示。

圖6 GA、ACO和GA-ACO求解結果Fig.6 Solution results of GA, ACO and GA-ACO

通過對三種算法求解結果(表6、圖6)對比發現，GA-ACO算法求解結果較GA和ACO更加優秀，在相同客戶滿意度條件下求得的總成本最低，表明設計的GA-ACO算法在相關問題求解上是有效的，并且優于GA和ACO。

對表6中數據進行分析表明，在客戶滿意度為100%時，總成本最高；當客戶滿意度降低至95%時，GA求得總成本降低8.9%，ACO求得總成本降低14.4%，GA-ACO求得總成本降低13%，降幅均較大；當客戶滿意度為80%，同客戶滿意度為95%時相比，GA求得總成本降低6.3%，ACO求得總成本降低1.2%，GA-ACO求得總成本降低2.2%，表明客戶滿意度在由95%降至80%時，總成本降幅較小；而當客戶滿意度低于80%時，總成本基本保持穩定，不再降低。這是由于客戶滿意度降低時雖然運輸成本會降低，但是違反時間窗約束的懲罰成本會增加，當客戶滿意度低于一定值時，懲罰成本會很高，減少的運輸成本并不能抵消增加的懲罰成本，因此總成本并不會降低。前述數據分析結果也進一步表明，對于逐步關注客戶滿意度的市場經營環境來說，由于100%的客戶滿意度要求過高，80%～95%的客戶滿意度在企業制定營銷戰略時是較好的選擇。

4 結論

研究了帶容量和軟時間窗約束的雙目標生鮮農產品冷鏈物流車輛路徑問題，構建了以總成本最小和客戶滿意度最高為優化目標的雙目標優化模型，采用ε約束法求解雙目標函數，結合遺傳算法和蟻群算法各自的優點，在蟻群算法中引入遺傳算法的交叉和變異算子，設計了遺傳蟻群算法。為驗證模型與算法的有效性，對實際算例進行求解，并將其結果與遺傳算法、蟻群算法求得結果進行對比。結果表明本文模型符合實際需求，所設計的遺傳蟻群算法收斂速度和求解結果均優于遺傳算法和蟻群算法。

但假設較為理想，如僅配送一種生鮮農產品、需求點之間距離為歐氏距離、車廂內外溫度恒定、車輛勻速行駛等，與實際中的情況還存在一定的差異。在將來的研究中，可以考慮配送多種生鮮農產品、各需求點之間的實際距離、客戶需求量不定、車廂外溫度變化及道路交通情況和車輛拋錨等對車輛行駛造成的影響等實際因素，從而使研究內容更加符合現實中冷鏈物流企業的需要。