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

江雨燕，尹莉，王付宇

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

江雨燕，尹莉，王付宇

（安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243002）

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

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

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

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

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

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

1 問題描述與模型構(gòu)建

1.1 問題描述與假設(shè)

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

1.2 符號定義

相關(guān)參數(shù)定義如表1所示。

1.3 目標(biāo)函數(shù)設(shè)計

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

（2）運(yùn)輸成本計算公式如下：

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

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

表1 變量說明

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

圖1 客戶滿意度

1.4 建立模型

通過以上分析，本文構(gòu)建考慮客戶滿意度的MDHOVRPTW優(yōu)化模型，其中為了算法在求解過程中計算方向統(tǒng)一，將客戶滿意度取負(fù)值變?yōu)榍笞钚?，因此，?shù)學(xué)模型表示如下：

目標(biāo)函數(shù)：

約束條件：

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

2 INSGA-II算法設(shè)計

算法流程如圖2所示。

圖2 INSGA-II算法流程

2.1 編碼及初始種群的生成

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)通常是將目標(biāo)函數(shù)做一些數(shù)學(xué)變換得到，本文將目標(biāo)函數(shù)值的倒數(shù)作為適應(yīng)度函數(shù)。

2.3 遺傳操作

（1）選擇算子

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

（2）交叉算子

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

圖3 部分匹配交叉

（3）變異算子

2.4 子代種群生成方式

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

2.5 算法性能評估

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

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

圖4 4種算法在ZDT1測試函數(shù)的Pareto前沿

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

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

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

表2 HV對比結(jié)果

表3 IGD性能對比結(jié)果

3 算例驗證及分析

3.1 算例設(shè)計

表4 配送中心信息

表5 客戶相關(guān)信息

表6 模型相關(guān)參數(shù)信息

3.2 算例結(jié)果

程序使用MATLAB R2016b編寫，并在Intel(R) Core(TM) i5-7200U CPU 2.50GHz的DELL 筆記本電腦（4核，8GB內(nèi)存）上運(yùn)行。基于前文企業(yè)案例數(shù)據(jù)，并采用INSGA-II算法求解模型，獨(dú)立運(yùn)行50次，INSGA-II算法參數(shù)設(shè)置如表7所示。

表7 INSGA-II算法參數(shù)設(shè)置表

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

圖8 初始迭代Pareto解集

圖9 最終Pareto解集

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

表8 各方案目標(biāo)值

圖10 方案三配送路徑

表9 方案三車輛行駛路徑

圖11 甘特圖

3.3 對比分析

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

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

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

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

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

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

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

表10 不同案例規(guī)模下4種算法對比

為了探索模型的適用性，將本文提出的考慮客戶滿意度的MDHOVRPTW模型與不考慮客戶滿意度的MDHOVRPTW模型在不同客戶規(guī)模下的較優(yōu)解對比，采用INSGA-II算法對考慮客戶滿意度的MDHOVRPTW模型進(jìn)行求解，利用傳統(tǒng)遺傳算法對不考慮客戶滿意度的MDHOVRPTW模型進(jìn)行求解，結(jié)果如表11所示。

表11 兩種模型結(jié)果對比

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

4 結(jié)束語

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

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

[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] 康凱，韓杰，普瑋，等. 生鮮農(nóng)產(chǎn)品冷鏈物流低碳配送路徑優(yōu)化研究[J]. 計算機(jī)工程與應(yīng)用，2019, 55(02): 259-265.

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

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

[7] 丁秋雷，胡祥培，姜洋，等. 考慮新鮮度的農(nóng)產(chǎn)品冷鏈物流配送受擾恢復(fù)模型[J]. 系統(tǒng)工程理論與實(shí)踐，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ìn)，李秀峰，付亞平. 基于電商承諾送達(dá)機(jī)制的低碳“同日達(dá)”配送路徑規(guī)劃[J]. 系統(tǒng)工程，2018, 36(12): 47-57.

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

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

[14] 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標(biāo)模糊車輛優(yōu)化調(diào)度問題研究[J]. 鐵道學(xué)報，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] 范厚明，楊翔，李蕩，等. 基于生鮮品多中心聯(lián)合配送的半開放式車輛路徑問題[J]. 計算機(jī)集成制造系統(tǒng)，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

國家自然科學(xué)基金“基于行為運(yùn)籌的災(zāi)后傷員救援車輛及手術(shù)調(diào)度優(yōu)化研究”（71872002）

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