生鮮產(chǎn)品配送中帶時間窗車輛路徑問題研究

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

關(guān)鍵詞：交通工程;帶時間窗車輛路徑問題;生鮮產(chǎn)品;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? 引? 言

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

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

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

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

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

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

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

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

2? 實驗結(jié)果與分析

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

2.1? 與已知最優(yōu)解對比

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

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

2.2? 算例1結(jié)果對比

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

文獻[8]中單點單親遺傳混合蟻群算法求解最優(yōu)路徑圖如圖1所示。CPLEX在56.46 s內(nèi)求解的最優(yōu)路徑為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結(jié)果對比

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

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

3? 結(jié)? 論

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

參考文獻：

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

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

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

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

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

[6] DEVAPRIYA P，F(xiàn)ERRELL 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].計算機應(yīng)用研究，2017，34（12）：3632-3636.

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

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

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