考慮客戶滿意度的帶時間窗的多中心半開放式冷鏈物流車輛路徑優化

江雨燕，尹莉，王付宇

考慮客戶滿意度的帶時間窗的多中心半開放式冷鏈物流車輛路徑優化

江雨燕，尹莉，王付宇

（安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243002）

針對帶時間窗的多中心半開放式車輛路徑問題，以總配送成本最小化和客戶滿意度最大化為目標，提出了雙目標冷鏈物流路徑優化模型。針對NSGA-II算法容易陷入局部最優等缺點，結合粒子群算法生成種群方式，設計一種改進的NSGA-II算法。通過仿真對比實驗，結果表明，所提出的算法和模型可有效解決帶時間窗的多中心半開放式冷鏈物流車輛路徑優化問題，且改進算法性能更優，同時分析了總配送成本與客戶滿意度之間的關系，為冷鏈物流企業帶來一定的管理啟示。

冷鏈物流；路徑優化；帶時間窗的多中心半開放式車輛路徑問題；改進的NSGA-II算法

近年來，人們對生鮮品的需求不斷上升，冷鏈物流行業發展較為迅速。同時，廣大居民越來越重視物流服務的質量，比如產品是否損壞，是否按時送達。因此，如何在降低配送成本的同時提高客戶滿意度，這對冷鏈物流配送企業的長遠發展是十分重要的。

國內學者對冷鏈車輛路徑問題做了大量的研究。HSIAO等[1]設計了生鮮產品冷鏈物流配送模型，并采用了遺傳算法對其求解。CHEN等[2]從低碳經濟的角度提出了一個依賴時間的綠色車輛路徑問題以及一種計算制冷成本的新思路。FAN等[3]進行了基于“互聯網+”的農產品冷鏈物流系統規劃，并給出了冷鏈系統優化建議?？祫P等[4]綜合分析了冷鏈物流配送中的各種成本，以配送總成本最小為目標建立了冷鏈物流配送模型。李倩等[5]在冷鏈配送路徑優化模型加入了客戶滿意度函數，并改進了非支配排序遺傳算法（non-dominated sorting genetic algorithm，NSGA-II）。任騰等[6]以碳排放量最小為目標，建立了冷鏈車輛路徑優化模型，并改進了傳統蟻群算法。丁秋雷等[7]在農產品冷鏈物流配送受擾恢復模型中考慮了農產品新鮮度和配送時間。這些文獻研究的冷鏈物流VRP模型主要是一個配送中心，對多配送中心的冷鏈物流車輛路徑優化的研究不足。

目前，大中型城市的物流配送系統中普遍存在多個配送中心，在多配送中心的路徑優化問題（multi-depot vehicle routing problem，MDVRP）研究方面，SALHI等[8]研究了異構車輛的多配送中心路徑問題，并提出了一種有效的可變鄰域搜索實現方法。DIAO等[9]研究了無最大時間窗的模糊時間窗多車場開放式車輛路徑問題，并采用混合遺傳算法求解。帶時間窗的MDVRP（multi-depot vehicle routing problem with time windows，MDVRPTW）是MDVRP的一個拓展問題。浦徐進等[11]針對“同日達”物流配送中的承諾送達機制，建立多目標多配送站“同日達”配送路徑優化模型，并提出一種改進后的人工蜂群算法進行求解。針對車輛路徑是否為閉環，又可分為封閉式車輛路徑問題和開放式車輛路徑問題（open vehicle routing problem，OVRP），在OVRP中，又包含半開放式車輛路徑問題（half open vehicle routing problem，HOVRP），其特點為車輛將貨物送達客戶后可就近駛回任一配送中心，李延輝等[12]在開放式多車場VRP中提出了沿途補貨策略，并設計了蟻群算法求解該模型。范厚明等[13]在多中心開放式車輛路徑問題中考慮了同時配集貨和需求可拆分，創建了以配送成本最小為目標的車輛路徑優化模型。這些文獻主要關注的是閉合式多配送中心車輛路徑問題，而在冷鏈物流車輛路徑問題中考慮半開放式多配送中心的研究成果相對較少。此外，現有研究中采用多目標優化算法求解冷鏈物流車輛路徑問題的文獻較為匱乏。

綜上所述，本文以帶時間窗的多中心半開放式車輛路徑問題（multi-depot half open vehicle routing problem with time windows，MDHOVRPTW）為研究對象，在冷鏈物流配送中，建立考慮客戶滿意度的MDHOVRPTW模型，使得冷鏈車輛路徑問題更具有研究意義，并針對該問題模型，采用改進的帶精英策略的非支配排序遺傳算法（Improved non-dominated sorting genetic algorithm，INSGA-II）求出滿足決策者不同要求的配送方案，并通過對比實驗證明改進算法求解模型的有效性。

1 問題描述與模型構建

1.1 問題描述與假設

問題假設：（1）配送中心不存在冷藏車輛不夠使用的情況；（2）已知車輛的最大載重量等信息，且只有一種車型；（3）車輛將貨物送達客戶后可以到最近的配送中心添加貨物，繼續為下一客戶提供配送服務；（4）車輛的行駛速度全程保持不變；（5）配送中心和需求點的信息是提前知道的；（6）每個客戶僅由一輛車配送一次；（7）不考慮配送中心的建設或使用成本；（8）駕駛員24小時內駕駛時間不超過8小時。

1.2 符號定義

相關參數定義如表1所示。

1.3 目標函數設計

（1）假設每輛車的固定成本相同，則固定成本計算如下：

（2）運輸成本計算公式如下：

（3）貨損成本計算如下：

（4）制冷成本是由以下兩種能源消耗成本組成：

表1 變量說明

（5）如果配送時間不能滿足客戶期望的時間窗，則產生的罰款成本計算如下：

圖1 客戶滿意度

1.4 建立模型

通過以上分析，本文構建考慮客戶滿意度的MDHOVRPTW優化模型，其中為了算法在求解過程中計算方向統一，將客戶滿意度取負值變為求最小，因此，數學模型表示如下：

目標函數：

約束條件：

其中，式(14)表示車輛的載重限制；式(15)表示配送中心的車輛總數與該配送中心提供服務的車輛數之間的關系；式(16)和式(17)含義為每個客戶只有一輛車提供配送；式(18)含義為車輛滿載出發，它是式(19),(20)及式(21)的基礎；式(19)表示車輛的載貨量要滿足每個客戶的需求量；式(20)表示車輛通過客戶時運輸量發生變化的關系式；式(21)表示車輛進入配送中心添加貨物量的條件；式(22)是為了防止車輛從一個配送中心到另一個配送中心；式(23)表示車輛完成配送服務后可就近返回任一配送中心；式(24)表明交付過程是連續的。

2 INSGA-II算法設計

算法流程如圖2所示。

圖2 INSGA-II算法流程

2.1 編碼及初始種群的生成

2.2 適應度函數

適應度函數通常是將目標函數做一些數學變換得到，本文將目標函數值的倒數作為適應度函數。

2.3 遺傳操作

（1）選擇算子

為了提高解集的分布性，在選擇操作時引入概率操作。在種群進化前期，以較大概率排除當前選出的最優個體進而選擇其他個體，在種群進化末期，以較小的概率排除當前選出的最優個體。概率操作的計算公式為

（2）交叉算子

交叉算子選擇部分匹配交叉（Partially-matched crossover，PMX），其保證了在一個染色體中沒有重復的基因，PMX示例如圖3所示。

圖3 部分匹配交叉

（3）變異算子

2.4 子代種群生成方式

為了提高NSGA-II進化的方向性和適應性，擴大搜索空間，具體操作如下：在利用NSGA-II算法合并新父種群后，NSGA-II算法經過一系列操作后，生成子代種群1，同時，利用粒子群算法的更新種群方式生成子代種群2，最后將兩個子代種群合并，執行下一步操作。

2.5 算法性能評估

為了評價改進算法的收斂性與多樣性，通過多目標測試函數進行算法對比。如圖4～7所示，在測試函數ZDT1、ZDT2、ZDT3及ZDT4中，INSGA-II的近似解比其他算法更靠近真實的Pareto前沿面，表明改進的NSGA-II算法收斂性較為良好。

此外，4種算法分別在迭代次數為50和100時獨立運行20次，將超體積指標HV以及反轉世代距離IGD的結果值進行平均，從表2中可以看出，INSGA-II算法的HV指標基本高于MOEAD、NSGA-II以及MOPSO，表明INSGA-II求解得到的Pareto解集能夠較好地收斂到理想的Pareto前沿面。同時，從表3中可以看出，改進后的NSGA-II算法的IGD指標低于其他算法，表明INSGA-II算法的收斂性與多樣性較為良好。

圖4 4種算法在ZDT1測試函數的Pareto前沿

圖5 4種算法在ZDT2測試函數的Pareto前沿

圖6 4種算法在ZDT3測試函數的Pareto前沿

圖7 4種算法在ZDT4測試函數的Pareto前沿

表2 HV對比結果

表3 IGD性能對比結果

3 算例驗證及分析

3.1 算例設計

表4 配送中心信息

表5 客戶相關信息

表6 模型相關參數信息

3.2 算例結果

程序使用MATLAB R2016b編寫，并在Intel(R) Core(TM) i5-7200U CPU 2.50GHz的DELL 筆記本電腦（4核，8GB內存）上運行?；谇拔钠髽I案例數據，并采用INSGA-II算法求解模型，獨立運行50次，INSGA-II算法參數設置如表7所示。

表7 INSGA-II算法參數設置表

圖8是INSGA-II求解考慮客戶滿意度的MDHOVRPTW模型初始迭代收斂結果，圖8中五角星表示當前搜索的最優解，空心圓表示新生成的解。為了更好地觀察非支配解的分布，繪制Pareto最優解集的圖像，如圖9所示，可以看出當其中一個解變好時，另一個解會變差，這說明解集中的所有解互不支配，設計的算法求解得出的最優解是可靠的。

圖8 初始迭代Pareto解集

圖9 最終Pareto解集

經過迭代，算法得到的Pareto解集中的每個解沒有好壞之分，決策者可以根據實際情況或偏好選擇不同側重的解作為最終的配送方案。本文從帕累托最優解集中選擇5個方案，各個方案的目標值如表8所示，其中方案一為隨機方案，方案二為配送成本最低方案，方案三為滿意度最高方案，方案四為模糊方案（折中解）。僅選擇方案三的Pareto解進行展示。圖10為方案三的配送路徑，表9為方案三的車輛配送客戶行駛路徑順序，共有9輛車輛，對應9條行駛路徑的甘特圖如圖11所示，企業可根據甘特圖進行調度和配送。同時，實驗結果也說明了本文所設計的INSGA-II算法能夠解決MDHOVRPTW，并且取得較好的結果。

表8 各方案目標值

圖10 方案三配送路徑

表9 方案三車輛行駛路徑

圖11 甘特圖

3.3 對比分析

一方面，隨著人民日益增長的美好生活需要，消費者更加注重物流配送的時間要求和產品質量體驗。另一方面，物流行業競爭日益激烈，生鮮冷鏈企業在貨物配送過程中所關心的不僅是怎樣的車輛行駛路徑使得配送成本最低，更為重要的是提高客戶對配送服務的滿意度。

為驗證本文算法求解模型的有效性，分別采用MOPSO、NSGA-II、MOEAD和INSGA-II算法求解了客戶規模不同下的配送方案。4種算法優化的帕累托解集分別如圖12～15所示，在4種客戶規模下，INSGA-II形成的Pareto前沿面較為明顯，說明改進的算法（INSGA-II）具有較好的收斂性，能夠有效求解考慮客戶滿意度的MDHOVRPTW模型。

每種客戶規模下的4種算法優化的折中解如表10所示。由表10可知，與MOPSO相比，用INSGA-II算法不僅計算得到的配送成本基本不高于MOPSO求解結果，而且客戶滿意度也幾乎不低于MOPSO求解結果，當客戶規模為60時求解質量較高；與NSGA-II相比，當客戶規模較小時，用INSGA-II計算得到的配送成本和客戶滿意度均優于NSGA-II計算得到的結果，但當客戶規模較大時，NSGA-II求解質量較高；與MOEAD相比，在客戶規模為45時，用INSGA-II計算得到的配送成本略高于MOEAD計算的配送成本，但INSGA-II客戶滿意度73%明顯高于MOEAD求解的客戶滿意度62%，其他規模下配送成本和客戶滿意度均優于MOEAD計算得到的結果。綜合上述分析，INSGA-II算法能夠較好的求解本文模型。

圖12 客戶數量30時的4種算法的帕累托解集

圖13 客戶數量45時的4種算法的帕累托解集

圖14 客戶數量60時的4種算法的帕累托解集

圖15 客戶數量90時的4種算法的帕累托解集

表10 不同案例規模下4種算法對比

為了探索模型的適用性，將本文提出的考慮客戶滿意度的MDHOVRPTW模型與不考慮客戶滿意度的MDHOVRPTW模型在不同客戶規模下的較優解對比，采用INSGA-II算法對考慮客戶滿意度的MDHOVRPTW模型進行求解，利用傳統遺傳算法對不考慮客戶滿意度的MDHOVRPTW模型進行求解，結果如表11所示。

表11 兩種模型結果對比

由表11可得出結論：（1）在4組對比數據中，與不考慮客戶滿意度的MDHOVRPTW配送方案相比，在客戶規模為30時，考慮客戶滿意度的MDHOVRPTW配送方案的優化效果有待提高；但在其他規模下，雖然考慮客戶滿意度的MDHOVRPTW方案的配送成本略高，這是因為車輛為了滿足客戶時間窗，可能會繞過距離較近的客戶而選擇優先配送距離稍遠的客戶，這就導致總配送成本增加，但考慮客戶滿意度的MDHOVRPTW方案的客戶滿意度較高，這說明在成本可以接受的前提下，冷鏈物流企業采用考慮客戶滿意度的MDHOVRPTW方案可以提高服務質量，有利于企業長期良好發展。（2）在客戶規模為45、60、90時，客戶滿意度的MDHOVRPTW策略的配送成本比不考慮客戶滿意度的MDHOVRPTW策略分別高于10.92%、2.55%、2.15%，但是客戶滿意度分別高于7.4%、6.35%、5.08%，在客戶規模為45時，客戶滿意度的優化效果最好。（3）在不考慮客戶滿意度的MDHOVRPTW策略中，隨著客戶規模的增加，客戶滿意度越來越低，這是由于不考慮客戶滿意度層面，導致車輛沒有在客戶期待的時間窗內將貨物送達。因此，冷鏈配送公司不僅要注重配送成本的降低，也要著力于提高客戶滿意度，只有這樣，企業才能在激烈的市場競爭中穩步發展。

4 結束語

隨著物流行業競爭的日益激烈，冷鏈物流企業越來越重視客戶對配送服務的滿意度。本文在冷鏈物流配送中建立了考慮客戶滿意度和配送成本的MDHOVRPTW模型，并設計了INSGA-II算法，最后通過仿真實驗對比分析，驗證了模型和算法的有效性，同時提出生鮮配送企業在成本可接受的前提下，考慮客戶滿意度有利于企業長期發展的結論。該研究可為生鮮冷鏈配送提供重要的決策參考價值。

本文建立的冷鏈配送模型中，雖然考慮了多配送中心以及半開放式的配送特點，但仍然忽略了在實際配送過程中，生鮮企業可能會派出不同類型的冷藏配送車輛，因此未來研究工作可以在本研究提出的模型基礎上，考慮異型車輛，使研究的問題更符合實際。此外，本文對NSGA-II算法做了改進，雖然在實驗結果上比其他算法有著優異的表現，但是忽略了算法的運行速度，在下一步研究中，設計出更加高效的啟發式算法，提高算法運行速度。

[1] HSIAO Y H, CHEN M C, CHIN C L. Distribution planning for perishable foods in cold chains with quality concerns: formulation and solution procedure[J]. Trends in Food Science & Technology, 2017, 61: 80-93.

[2] CHEN J, LIAO W, YU C. Route optimization for cold chain logistics of front warehouses based on traffic congestion and carbon emission[J]. Computers & Industrial Engineering, 2021, 161(1): 1-16.

[3] FAN Y, LI H. Research on cold chain logistics operation mode under internet technology[J]. Journal of Physics: Conference Series, 2021, 1972(1): 1-8.

[4] 康凱，韓杰，普瑋，等. 生鮮農產品冷鏈物流低碳配送路徑優化研究[J]. 計算機工程與應用，2019, 55(02): 259-265.

[5] 李倩，蔣麗，梁昌勇. 基于模糊時間窗的多目標冷鏈配送優化[J]. 計算機工程與應用，2021, 57(23): 255-262.

[6] 任騰，陳玥，向迎春，等. 考慮客戶滿意度的低碳冷鏈車輛路徑優化[J]. 計算機集成制造系統，2020, 26(04): 1108-1117.

[7] 丁秋雷，胡祥培，姜洋，等. 考慮新鮮度的農產品冷鏈物流配送受擾恢復模型[J]. 系統工程理論與實踐，2021, 41(03): 667-677.

[8] SALHI S, IMRAN A, WASSAN N A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation[J]. Computers & Operations Research, 2014, 52(PB): 315-325.

[9] DIAO X , FAN H , REN X , et al. Multi-depot open vehicle routing problem with fuzzy time windows[J]. Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, 2021(1): 40.

[10] SINGH V, GANAPATHY L, PUNDIR A K. An improved genetic algorithm for solving multi depot vehicle routing problems[M]. International Journal of Information Systems and Supply Chain Management (IJISSCM), 2019, 12(4): 1-26.

[11] 浦徐進，李秀峰，付亞平. 基于電商承諾送達機制的低碳“同日達”配送路徑規劃[J]. 系統工程，2018, 36(12): 47-57.

[12] 李延暉，劉向. 沿途補貨的多車場開放式車輛路徑問題及蟻群算法[J]. 計算機集成制造系統，2008, 14(03): 557-562.

[13] 范厚明，張軒，任曉雪，等. 多中心開放且需求可拆分的VRPSDP問題優化[J]. 系統工程理論與實踐，2021, 41(06):1521-1534.

[14] 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標模糊車輛優化調度問題研究[J]. 鐵道學報，2003(02): 15-17.

[15] LIU G, HU J, YANG Y, et al. Vehicle routing problem in cold chain logistics: a joint distribution model with carbon trading mechanisms[J]. Resources Conservation and Recycling, 2020, 156: 1-13.

[16] 范厚明，楊翔，李蕩，等. 基于生鮮品多中心聯合配送的半開放式車輛路徑問題[J]. 計算機集成制造系統，2019, 25(01): 256-266.

Multi-depot half-open cold chain logistics vehicle routing optimization with time window considering customer satisfaction

JIANG Yu-yan，YIN Li，WANG Fu-yu

(School of Management Science and Engineering, Anhui University of Technology, Anhui Maanshan 243002, China)

Aiming at the multi-depot half-open vehicle routing problem with time window, a dual-objective cold chain logistics routing optimization model was proposed to minimize the total distribution cost and maximize customer satisfaction. Aiming at the shortcoming that NSGA-II algorithm is easy to fall into local optimum, an improved NSGA-II algorithm is designed by combining the population generation method of particle swarm optimization algorithm. Through simulation experiments, the results show that the proposed algorithm and the model can effectively solve the multicenter ajar cold-chain logistics with time windows vehicle routing optimization problem, and the improved algorithm has better performance, at the same time analyzed the total distribution cost and the relationship between customer satisfaction, for the cold chain logistics enterprise management implications.

cold chain logistics；path optimization；multi-depot half-open vehicle routing problem with time window；improved NSGA-II algorithm

U116.2

A

1007-984X(2023)03-0074-12

2022-09-07

國家自然科學基金“基于行為運籌的災后傷員救援車輛及手術調度優化研究”（71872002）

江雨燕（1966-），女，安徽宣城人，教授，主要從事智能計算研究，jyy@ahut.edu.cn。