生鮮產品配送中帶時間窗車輛路徑問題研究

摘? 要：文章以生鮮產品配送為背景，分析了近年來生鮮產品配送和帶時間窗車輛路徑問題相關文獻，基于帶時間窗車輛路徑問題構建了最小化車輛行駛成本的數學模型，并使用CPLEX求解器中的分支定界算法求解。將求解結果與已知最優解和其他文獻比較表明，分支定界算法在求解帶時間窗車輛路徑的生鮮產品配送問題時具有可行性和優越性。

關鍵詞：交通工程;帶時間窗車輛路徑問題;生鮮產品;CPLEX;分支定界算法

中圖分類號：TP18? ? ? ?文獻標識碼：A 文章編號：2096-4706（2020）24-0110-04

Research on Vehicle Routing Problem with Time Window in Fresh Product Distribution

LI Jun

（School of Business Administration，Chongqing Technology and Business University，Chongqing? 400067，China）

Abstract：Based on the background of fresh products distribution，this paper analyzes the literature on fresh product distribution and vehicle routing problem with time windows in recent years. Based on the vehicle routing problem with time windows，a mathematical model to minimize the vehicle driving cost is constructed and solved by the branch and bound algorithm in CPLEX solver. Compared with the known optimal solution and other literatures，the results show that the branch and bound algorithm is feasible and superior in solving the fresh product distribution problem with time window vehicle routing.

Keywords：traffic engineering;vehicle routing problem with time window;fresh product;CPLEX;branch and bound algorithms

0? 引? 言

生鮮產品配送具有溫度和新鮮度等限制，產品的配送效率直接影響產品質量，從而影響消費者滿意度。此外由于配送不及時導致的產品損耗直接影響企業成本。本文在生鮮產品配送的帶時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）[1]的研究課題中，發現將生鮮產品在合適的時間內配送給客戶至關重要。目前大部分研究使用啟發式算法求解大規模算例，容易陷入局部最優，且忽略了生鮮產品小批量、多批次等特點[2]。故有本篇研究，使用精確算法求解小規模算例，為的是提高生鮮配送效率、降低生鮮配送成本，為推動生鮮配送行業發展做出貢獻。

VRPTW最早由Savelsbergh提出，是在車輛路徑問題的基礎上增加了顧客接受配送服務的時間窗要求，較VRP更貼近實際生活。VRPTW已被證實是NP-hard問題，主要由啟發式算法或精確算法求解。當問題規模較大時，啟發式算法較易得到滿意解。葉勇等[3]以城市物流配送和交通運輸中的VRPTW為背景，以總運輸成本最小為目標，使用狼群算法求解。當問題規模較小時，精確算法較易得到最優解，但目前國內使用精確算法求解車輛路徑問題的文獻較少。曹平方等[4]建立了一種改進型的單場站和多車輛路徑數學模型，并使用分支界定法求解旅行商問題。以上文獻為研究生鮮產品配送提供了理論支撐。

國內外學者多以啟發式算法求解生鮮配送問題。范立南等[5]以農產品冷鏈總成本最小為目標構建VRPTW模型，并使用改進遺傳算法求解;Priyantha等[6]以總配送費用最小為目標構建易腐品生產和配送協同優化模型，使用進化算法求解;Amorim等[7]研究了不同配送環境與不同產品變質系數條件下生鮮農產品的新鮮度與配送成本，并使用多目標進化算法求解。從已有文獻來看，傳統啟發式算法在求解時容易出現無法收斂和陷入局部最優等不足，因此本文將建立VRPTW的數學模型，使用CPLEX求解器，采用精確算法中的分支定界算法（Branch-and-Bound algorithms，B&B）求解小規模生鮮配送問題。

1? 問題描述與模型構建

VRPTW可以描述為：一個配送中心有一系列勻質車輛，車輛從配送中心出發，依次為顧客提供配送服務，服務完最后一個顧客后返回配送中心。VRPTW須在一定約束條件下（如時間約束和容量約束等），求出最優化函數（如最小化行駛成本和最小化行駛時間）。VRPTW可以用有向圖G=（N，A）來描述，其中N={0，1，1，2，…，n，n+1}為節點集，A={（i，j）|（i，j）∈N，i≠j}為邊集合。N由配送中心“0，n+1”和一組客戶N′=N＼{0，n+1}組成，δ-（i）和δ+（i）分別代表流入和流出i的點集合，S為客戶集的子集。

配送中心有一系列容量為Q的同質車輛K={1，2，…， k}。車輛從配送中心0出發，訪問顧客點i，然后到達顧客點j并離開，為最后一個顧客提供服務后返回配送中心n+1。同一路線上所有產品的總需求不能超過每輛車的容量Q。每個顧客的需求qi是確定的，并且必須在一次配送服務中得到滿足。

對于顧客點i，車輛的到達時間為ai，等待時間為wi，開始接受服務的時間必須在[ei，li]范圍內，其中ei和li分別為顧客點i的最早開始接受服務的時間和最晚開始接受服務的時間。如果車輛在ei之前到達顧客點i，則必須等到ei開始服務。車輛在顧客點i的服務時間為si。在兩個節點i，j之間，車輛的行駛時間為tij，行駛距離與行駛成本cij成正比。定義配送中心0和n+1的需求為q0=qn+1=0，時間窗為[e0，l0]=[en+1，ln+1]，服務時間為s0=sn+1=0，配送中心0和n+1的距離為c0，n+1=t0，n+1=0。研究目的就是在滿足顧客要求的前提下找到一系列行駛路徑使總行駛成本最小。VRPTW的模型構建為：

（1）

（2）

（3）

（4）

（5）

（6）

（7）

ei≤ai+wi≤li，?i∈N′? ? ? ? ? ? ? ? ? ? ? ?（8）

wi=max{ei-ai，0}，?i∈N′? ? ? ? ? ? ? ? ? ? （9）

（10）

∈{0，1}，?i，j∈N，k∈K? ? ? ? ? ? ? ? （11）

式（1）為目標函數，使行駛成本最小化。式（2）至式（5）為車輛路徑優化問題的傳統約束條件，其中式（2）表示每個客戶只能被一輛車服務一次，式（3）表示車輛必須從配送中心0出發，式（4）強調路線的連續性，式（5）消除子路徑。式（6）的約束條件是指車輛在完成任務后必須返回配送中心n+1。式（7）至式（9）的約束條件表示車輛開始服務的時間限制。式（10）的約束條件保證了同一路線上所有產品的總需求量不超過車輛的容量，式（11）的約束條件定義決策變量。

2? 實驗結果與分析

為測試CPLEX求解VRPTW的求解性能，需利用相應算例進行實驗分析。在此共采用四組算例：2.1中，采用25個點顧客點的Solomon標準測試算例;2.2采用文獻[3]算例;2.3采用文獻[5]算例。實驗采用CPLEX Studio IDE編程，在Windows10 X64操作系統、i5 7200U CPU、2.50 GHz、12 GB內存環境下運行。

2.1? 與已知最優解對比

由于Solomon基準測試數據在研究VRPTW時具有權威性，為驗證本文數學模型的可行性與有效性，將采用CPLEX求解Solomon 25個點中C1類，并與已知最優解進行對比，求解結果如表1所示。

結果表明，CPLEX求解結果和Solomon算例已知最優解完全一致，這既驗證了本文VRPTW模型的可行性和有效性，也驗證了分支定界算法的高效性和優越性。

2.2? 算例1結果對比

CPLEX與文獻[8]和[9]中所提算法的求解結果如表2所示。設置CPLEX求解時間為56.46 s（其他7種算法平均求解時間），運行10次，得到最優路徑長度為1 004.32 km，車輛數為6輛。CPLEX的最優結果比其他7種算法的結果分別優化了16.44%，13.23%，15.56%，22.18%，11.64%，9.19%，7.88%，可見CPLEX求解結果的優越性。

文獻[8]中單點單親遺傳混合蟻群算法求解最優路徑圖如圖1所示。CPLEX在56.46 s內求解的最優路徑為0→ 7→5→14→0;0→1→16→8→0;0→4→15→9→

0、0→18→11→3→0;0→12→19→6→13→0;0→10→20→17→2→0，其中0代表配送中心，1～20代表顧客點，路徑圖如圖2所示。

2.3? 算例2結果對比

CPLEX與文獻[3]中所提算法的求解結果如表3所示。在對比結果中，CPLEX求出的最優解為522.34，均低于其他3種算法的最小費用。CPLEX得到的最優結果比文獻[10]中的結果優化了10.80%，比文獻[11]中的結果優化了7.90%，比文獻[3]中的結果優化了7.10%。

CPLEX求解的收斂圖如圖3所示，其在26秒完全收斂，得到全局最優解，這說明CPLEX求解能力較強。

3? 結? 論

本文以生鮮產品配送為背景，針對VRPTW建立了以行駛成本最小為優化目標的數學模型，并使用CPLEX中的分支定界算法求解。在與Solomon標準算例和其他文獻結果對比時，CPLEX求解小規模算例時結果較優，求解時間較短，求解優勢明顯;但在求解大規模算例時效率較低。因此，使用CPLEX中的分支定界算法求解小規模生鮮產品配送問題具有可行性。未來研究中將繼續考慮溫度、新鮮度等因素的影響，使問題更貼近現實生活，并研究更高效的算法求解大規模生鮮產品配送問題。

參考文獻：

[1] 劉長石，周鮮成，盛虎宜，等.生鮮電商配送的TDVRPTW研究：基于經濟成本與環境成本兼顧的視角 [J].控制與決策，2020，35（5）：1273-1280.

[2] 方文婷，艾時鐘，王晴，等.基于混合蟻群算法的冷鏈物流配送路徑優化研究 [J].中國管理科學，2019，27（11）：107-115.

[3] 葉勇，張惠珍.求解帶時間窗車輛路徑問題的狼群算法 [J].公路交通科技，2017，34（10）：100-107.

[4] 曹平方，李靈，李詩珍.基于分枝界定的VRP模型精確算法研究及應用 [J].包裝工程，2014，35（17）：97-101.

[5] 范立南，董冬艷，李佳洋，等.基于生鮮農產品的冷鏈物流配送路徑優化 [J].沈陽大學學報（自然科學版），2017，29（2）：125-131.

[6] DEVAPRIYA P，FERRELL W，GEISMAR N. Integrated production and distribution scheduling with a perishable product [J].European Journal of Operational Research，2016，259（3）：906-916.

[7] AMORIM P，ALMADA-LOBO B. The impact of food perishability issues in the vehicle routing problem [J].Computers & Industrial Engineering，2014，67：223-233.

[8] 劉云，張惠珍.多目標帶時間窗的車輛路徑問題的單親遺傳混合蟻群算法 [J].公路交通科技，2016，33（6）：95-100+106.

[9] 殷亞，張惠珍.求解帶硬時間窗的多目標車輛路徑問題的多種混合蝙蝠算法 [J].計算機應用研究，2017，34（12）：3632-3636.

[10] 鐘石泉，賀國光.有時間窗約束車輛調度優化的一種禁忌算法 [J].系統工程理論方法應用，2005（6）：522-526.

[11] 李琳，劉士新，唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題 [J].控制與決策，2010，25（9）：1379-1383.

作者簡介：李俊（1998—），男，漢族，江西九江人，碩士研究生在讀，研究方向：智能算法。