模糊時間窗下考慮動態需求的生鮮路徑優化

顧艷鑫， 賴紅波

(上海理工大學 管理學院， 上海 200000)

0 引 言

近年來人民生活水平提高、可支配收入形勢向好，對高品質生活的追求愈加強烈，比起常溫長保質期的產品，人們更傾向于選擇冷藏短保的蔬菜、水果、奶制品等產品。然而，由于生鮮購買是高頻次的即時性消費，消費者在生鮮送達的時效性和新鮮度層面對生鮮零售商的物流水平提出高要求。因此，對車輛路徑優化問題的研究具有十分重要的現實意義。

車輛路徑優化問題(Vehicle Routing Problem，VRP)最早由Dantzig等人[1]于1959年提出，自后對于該問題的研究層出不窮，并取得了豐碩的研究成果，研究趨勢給后人提供了參考價值。

在建立車輛路徑優化模型時，要更加貼近現實條件，并考慮多種影響因素進行綜合優化，將VRP問題進行拓展，多級VRP問題就是在客戶與配送中心之間建立一個或多個物流中心。如：Chen等[2]對藥品分配了一種廣義多級優化方法；Dai等[3]繼續開發三級、四級方法，以求在更短時間內得到解。為響應碳中和政策，更多地考慮碳排放因素，Shen等[4]、Qin等[5]通過計算碳排放交易機制量化成本，考慮不同的碳價格和碳配額。近幾年的研究已從靜態考慮多種因素轉變到因素的動態變化上來。一種考慮動態需求的主流求解方法是兩階段模型法。如：張文博[6]將通過兩階段規劃，在初始規劃后將動態需求轉化為多個瞬時靜態子過程；范厚明[7]先使用改進的遺傳算法進行預優化，再綜合考慮客戶需求和路網變化情況對于預優化結果進行動態調整等。

在求解車輛路徑優化模型時算法的不斷改進，采用多種啟發式算法改進的混合算法是常見的改進思路。如：王勇等[8]提出了一種改進的GA-PSO混合算法，綜合了精英保留策略、全局搜索能力較強的遺傳算法和收斂速度較快的粒子群算法，針對逆向物流車輛路徑問題進行優化；滕鑰等[9]為求解危險品運輸風險的多車型車輛路徑問題，在ε-約束法和禁忌搜索相結合的混合算法中嵌入車型匹配策略，對其它領域的多目標多車型物流配送問題的研究具有一定啟發。此外，還有一些學者采用非主流新型算法進行求解。如：王超等[10]提出并設計了回溯搜索優化算法求解VRP問題，在該算法的交叉、變異操作中構造出6種路徑間搜索算子和4種路徑內搜索算子，以提高算法的局部搜索能力；Mokhtarinejad等[11]提出了一種基于機器學習的啟發式方法MLBM，通過雙聚類方法將客戶、制造商和交叉對接中心的位置進行分組。

綜上所述，學者們對于VRP問題的研究或深究其中一方面、或適當綜合考慮多個條件，將會有更貼近現實情況、求解更精確的算法出現。因此，本文進一步綜合考慮動態需求(包括實時路況優化、碳排放量、時間窗等因素)，并且運用改進的遺傳算法對模型進行求解，以期對未來的研究提供一定參考價值。

1 問題描述與模型建立

1.1 問題描述

原本的VRP問題是已知一些基本條件(如：多個配送中心和多個顧客的地理位置、顧客對于產品的需求量等)和約束條件(時間窗限制、運輸車輛載重量限制)的情況下設計車輛路線，使得貨物有序地從多個配送中心到達多個客戶，滿足優化的目標條件；而DVRPTW是VRP問題的一個分支，是指在原有基礎車輛路徑優化問題的基礎上，考慮客戶的動態需求以及時間窗，如圖1所示。本文研究的DVRPTW是考慮配送過程中，客戶的配送需求是動態變化的。例如：臨時取消原有訂單、重新產生新訂單、數量變更等，需要對原配送路徑進行實時重新規劃，最終仍然收斂于一個最優路徑結果。

圖1 VRP問題圖示

配送中心車輛的一天工作路網可以體現在一張完備有向圖G(V,E)中，其中V代表所有配送節點，E表示所有邊，0是配送中心。有M輛車從配送中心出發，有序經過各顧客節點，在執行初始配送方案的過程中，實時接收新的訂單動態，并對原有配送路徑進行調整，完成對所有客戶需求的配送服務之后返回到配送中心。

1.2 模型假設和符號說明

為了簡化計算步驟、突出算法原理，使得計算環境更加理想化，對模型作出以下假設：

(1)本文研究的問題是多個配送中心到多個門店的路徑優化問題；

(2)冷鏈配送中心車輛數量充足、車型號相同，能滿足對所有門店的配送；

(3)每輛冷藏車均從配送中心出發，沿著一條路線將貨物分發到門店，完成配送之后返回配送中心；

(4)冷藏車行駛的公路狀況良好，車輛能夠勻速行駛；

(5)配送時間內，外界大氣溫度不隨時間而變動，冷鏈配送車內的溫度保持在恒定水平。

模型中出現的各個符號說明解釋見表1。

表1 符號說明

1.3 考慮實時路況

車輛在行駛過程中常常受到交通擁堵、各種突發狀況等因素的影響，而增加物流配送的成本且影響貨物送達時間。因此，在VRP問題的研究中，動態變化是不可忽視的重要因素之一。

研究發現，誘發交通擁堵的原因諸多，通常分為常發性因素和偶然性因素兩方面。常發性因素是受固定因素影響，是有規律可循的交通擁堵。如：工作日路況擁堵變化程度較大，潮汐現象更為明顯；而休息日人們調整作息時間，早高峰推遲且持續時間增長等。偶然性因素主要是由特殊情況引起。如：受交通事故、大型活動、惡劣天氣的影響，造成臨時性交通流的集中，導致路段偶發擁堵或者擁堵程度加劇。

本文通過高德地圖軟件所提供的城市道路實時路況免費接口，可實時獲取各路段(i,j)的交通擁堵系數rij，以期在對不同擁堵程度路況賦值的基礎上進行計算，量化判斷路況隨時間的變化情況。配送車輛在路段(i,j)的通行時間為

(1)

式中:dij表示i地與j地的距離，v0是配送車輛正常行駛的平均速度。

1.4 考慮碳中和背景

當前碳中和成為各大研究領域的熱點問題，在VRP問題中很多在目標函數中考慮到了碳排放成本，關鍵在于車輛碳排放量如何測度。常見思路是使用碳稅稅率計算碳稅，直接計入成本。但本文認為，簡單地將碳排放轉化為經濟成本明顯忽略了碳排放量最小化的目標，并且現實中車輛行駛過程中的碳排放量會受到包括載重、速度、距離等多種因素在內的影響，計算較為復雜。因此，本文在此處引入一個燃料消耗最優模型并舉例驗證了其有效性。

本文采用燃油消耗模型來刻畫燃油消耗量，即：

(2)

其中，ρ0和ρ*分別為車輛空載和車輛滿載時的燃油消耗率；Q是車輛的最大裝載量；ρ(Qk)是指當車輛裝載量為Qk時的單位行駛里程的燃油消耗量。

為了更加直觀地解釋燃油消耗量與車輛裝載量的關系，假設ρ0=10、Q=400，分別畫出當ρ*=20、25、30時的函數圖像，如圖2所示。

圖2 燃油消耗量與車輛裝載量關系圖

由圖2可知，燃油消耗率和車輛裝載量呈現正比關系，即車輛裝載量越大，燃油消耗量越大，且車輛滿載時的燃油消耗率ρ*越大，行駛相同路徑所消耗的燃油量就越大。因此，對于任意配送路徑段(i,j)，燃油消耗成本為

(3)

其中，c0表示單位燃料成本，dij表示客戶點之間的歐式距離。

由此得到車輛在配送時的燃料消耗成本則為

(4)

由于ρij受到裝載量序列的影響，可以通過設計合理的配送路線，從而達到既減少燃油消耗量、響應國家碳中和政策，又節約了配送成本的目標。

1.5 考慮軟時間窗

現如今各大生鮮電商在“前置倉”的模式下紛紛推出 “一小時達”等業務，同時制定了承諾送達機制。如果晚于規定時間送達，則會支付一定的懲罰費用。這表明電商進階的新門檻在于爭分奪秒的時間戰，因此本文考慮時間窗，將時間窗作為約束條件之一。

通常情況下，客戶對于生鮮農產品的滿意程度與產品的新鮮程度相關，而產品的新鮮程度則與生鮮農產品在運輸途中花費的時間有關。如果配送商在規定時間內將產品送到，顧客的滿意度最高，否則就會降低。具體情況如圖3所示。

由圖3可知，在配送時間早于或者晚于送達配送門店的顧客滿意度值為0，在時間段[Ei,ETi]中，顧客滿意度逐漸提高，在[ETi,LTi]中顧客滿意度達到最高水平，值為1，而后在[LTi,Li]時間段中，顧客的滿意度又逐漸下降趨于0。

圖3 客戶滿意度變化規律圖示

為了方便計算，量化顧客滿意度，使得滿意度與時間呈線性相關關系，定義顧客滿意度函數如下：

(5)

其中，[ETi,LTi]是指令顧客滿意的時間窗，[Ei,Li]指的是顧客可以接受的時間窗。

1.6 模型建立

基于上述對影響配送成本因素的分析，構建生鮮配送成本函數模型。

目標函數：

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

其中，目標函數是生鮮冷鏈配送全程成本的最小化，其中包括固定成本、變動成本、貨損成本、懲罰成本和碳排放成本。

約束條件中，式(7)指每輛冷鏈配送車的載重量不超過額定載重量；式(8)指配送中心進行配送服務的車輛總數不超過配送中心所擁有的車輛數；式(9)、式(10)指每個超市門店只由一輛冷鏈配送車對其進行服務，并且只服務一次；式(11)指每輛冷鏈配送車從配送中心出發到超市門店完成配送任務之后必須返回到配送中心；式(12)指硬時間窗約束，必須在規定時間內到達；式(13)、式(14)是指配送變量的0～1約束；式(15)是客戶滿意度約束。

2 算法設計及實現

本文選用遺傳算法對該模型進行求解，并針對遺傳算法的一些缺點進行了相應的改進。具體操作包括在選擇算子中引入歐式距離、交叉算子時引入自適應交叉算子等，以期增強局部搜索能力、提高解集質量。

2.1 算法原理步驟

遺傳算法的主體部分包括選擇、交叉和變異算子，改進后的遺傳算法流程如圖4所示，其主要實現步驟如下：

(1)對染色體進行編碼，并且確定初始種群；

(2)對初始種群進行選擇、自適應交叉、自適應變異運算；

(3)如果進化代數達到最大，則算法停止并輸出解，流程結束；否則返回到自適應交叉算子。

圖4 改進的遺傳算法流程圖

2.2 編碼及算子設計

2.2.1 整數編碼

在對優化模型采用改進的遺傳算法進行求解時，需要先通過一定的編碼方式將問題的解集合轉化成按照一定次序排列的基因串結構組成的解集合。考慮到二進制編碼的一些缺點(如染色體較長時使得算法搜索范圍迅速膨脹等)，本文采用自然編碼方法對染色體進行編碼。

2.2.2 選擇算子

選擇運算就是在對染色體適應度大小進行評估之后，根據特定方法從父代種群中選擇適應度值高的遺傳到下一代種群。常見的選擇方法包括賭輪選擇方法、排擠方法等。本文引入歐式距離，對選擇操作進行改進為

(16)

其中，ηi是個體η的第i個基因；θi是個體θ的第i個基因；n是基因個數。

若歐式距離越大，則表明兩個個體之間的相似度越小。選擇操作步驟如下：

(1)計算種群平均適應度值及每個個體的適應度值，紀錄最高適應度值個體；

(2)逐個判斷種群個體的適應度值是否小于平均值，若小于，則轉到步驟(3)，否則保存個體，直至整個種群判斷完成；

(3)隨機產生個體，分別計算這個個體的適應度值與原種群中最高適應度值個體之間的歐式距離，選擇適應度值與歐式距離之和最大的個體作為新的個體，取代種群中原有個體。

2.2.3 交叉算子

交叉操作是用自適應較差概率，根據當代種群中的最大適應度值fitmax和平均適應度值fitavg對交叉概率Pc進行自適應調整:

其中，fit是進行交叉運算的兩個染色體中適應度較高的，Pc1的取值在0.6～1之間。

交叉運算過程如圖5所示，其具體步驟如下：

(1)根據公式選擇將要進行交叉運算的染色體FA和FB；

(2)在冷鏈配送車形成的子路徑中隨機選擇兩個交叉基因段；

(3)將父代FA中的基因段置于FB基因段前，形成子代；

(4)刪去子代中的重復基因點，并更新零點；

(5)形成新的子代FA’和FB’。

圖5 交叉算子運算原理圖示

2.2.4 變異算子

變異運算是模擬基因突變的過程，其本質就是對多目標優化問題的可行解路徑進行局部交換，從而使局部搜索優化能力得到增強。本文依然采用自適應調整概率的方法進行，即:

其中，fit′是指被隨機選中進行變異運算的基因。由于基因突變現象在自然界中屬于小概率事件，因此Pm1的取值在0.001～0.1之間。

具體操作過程：先計算出變異概率Pm；然后根據Pm選中子代染色體上幾個位置的等位基因；隨機交換這些位置的基因節點。

圖6 變異算子運算原理圖示

3 實例驗證

3.1 算例描述及參數設定

某零售企業在城市內有3家配送中心，為該市范圍內的客戶提供配送服務。配送前一天企業收到了100個客戶的配送訂單，這些客戶分布在城市的不同位置，而且每個客戶的貨物需求量和要求進行配送的時間窗不同，具體信息見表2、表3。

表2 配送中心信息表

表3 部分客戶信息表

另外，對模型中其余參數的設定，見表4。

表4 算例參數設計

3.2 實驗結果與分析

本文算例中所用的改進遺傳算法參數設置包括：種群規模100個，最大迭代次數500，競賽規模50個，交叉概率0.8，變異概率0.1。使用Python3.9.5編程；運行程序的計算機CPU型號為Apple M1，內存16 GB。

改進算法求解結果如圖7、圖8所示。此外，為了驗證算法的有效性，將改進的算法結果與原遺傳算法(圖9)進行比較。其結果顯示，未改進的遺傳算法收斂速度較慢，且目標函數成本較高。

圖7 改進的遺傳算法路徑優化結果圖

圖8 改進的遺傳算法迭代結果圖

圖9 未改進的遺傳算法迭代結果圖

由表5可知，若使用改進遺傳算法求解得出成本為1 969元，而未經改進的遺傳算法求解得出的成本約為2 134元，經改進成本降低約7.73%，對于降低配送總成本有一定的效果。如果將其方法應用于大規模大范圍的路徑優化，則經濟效益將更為突出。

表5 算法結果對比

4 結束語

本文在疫情期間生鮮電商線上需求量劇增的背景下，針對多配送站的車輛路徑優化問題，考慮了包括實時路況、碳排放、時間窗等因素在內的動態因素，并將其轉化為靜態車輛路徑問題進行求解。建立了以求最小總配送成本和最大客戶滿意度的多目標優化模型，并采用改進的遺傳算法求解，最后通過案例進行了仿真實驗。實驗結果表明：改進的遺傳算法比未改進的遺傳算法成本提高了7.73%。因此，在動態車輛路徑問題中使用本文提出的改進算法，能夠有效降低配送成本，更加具有現實意義。在后續的研究中，可將動態需求的考慮轉化為靜態需求，轉而分解為兩階段方法。