常馨玉，龐知非，劉振國，尚晉平

（1.交通運輸部科學研究院，北京 100029；2.交通運輸部公路科學研究院，北京 100088）

1 引言

隨著經濟的發(fā)展和居民消費水平的提高，我國生鮮農產品的流通量逐年增加，加之電子商務的飛速發(fā)展，各類企業(yè)紛紛涉足生鮮電子商務。由于生鮮農產品本身的特殊性以及在流通過程中對運輸時間有較強的敏感性，要求盡可能的減少運輸過程中所消耗的時間，保證生鮮農產品的新鮮程度。我國的冷鏈干線運輸經過幾十年的發(fā)展，已經能夠滿足人們對于生鮮農產品消費的需求，而從配送中心到客戶手中的“最后一公里”物流配送是電商降低物流成本、提高配送效率、搶奪生鮮配送市場的關鍵所在，也是全面貫徹落實物流業(yè)降本增效的抓手。

2 國內外研究現狀

國外最先開始研究生鮮物流配送問題，PedroAmorim[1]等研究食品配送過程中的配送車輛路徑優(yōu)化過程，但并沒有將食品的損耗考慮在內；Solomon[2]等將客戶點的收貨時間窗約束條件加入到生鮮農產品物流配送問題的模型中，滿足了生鮮物流配送問題的時效性要求；Miroslaw[3]等提出生鮮農產品在配送過程中需要滿足客戶的需求、配送服務時間以及產品的新鮮度等條件，將客戶點的收貨時間窗和配送車輛的控制溫度作為約束條件，構建以配送成本最小化為目標的混合整數規(guī)劃模型；Dabia[4]等提出為了減少配送所需要的時間并降低配送成本，可以在與客戶約定的時間段內提供配送服務。國內一些學者也對生鮮農產品的末端配送展開了研究，并取得了相應的成果，楊芳[5]等構建了基于安全和效率的多目標MAS系統(tǒng)模型，提高了生鮮果蔬的流通效率；龔樹生，梁懷蘭[6]等研究了生鮮食品的冷鏈物流網絡；王紅玲[7]等構建了以生鮮農產品在途時間最短、配送成本最小為優(yōu)化目標的規(guī)劃問題；石兆[8]等通過建立在時變條件下的仿真模型來求解配送網絡的最優(yōu)路徑；楊婷[9]、邵舉平[10]等以客戶的滿意度極大化作為約束條件來優(yōu)化配送路徑。

生鮮農產品的配送問題本質上屬于車輛調度（簡稱VRP問題）問題，是NP-hard問題，因此運用精確算法求解的難度較大，目前對VRP問題的研究大多采用啟發(fā)性算法，并取得了一定的成果。在求解算法方面，Humberto[11]等運用模擬退火算法對帶有時間窗的VRP問題進行求解；Zhang[12]等采用禁忌搜索算法對冷鏈物流配送路徑進行了優(yōu)化研究；Arbelaitz[13]等建立了帶有時間窗的冷鏈配送路徑問題的模型，通過MEAT啟發(fā)式方法和路線規(guī)劃啟發(fā)算法相結合，從而縮小了可行解的搜索范圍；Baker（2003）[14]利用遺傳算法解決了最基本的VRP問題；Blanton和Wainwright（1993）[15]、Potvin（2002）[16]等利用遺傳算法解決了帶時間窗的VRP問題。

本文針對生鮮農產品的最后一公里配送問題的特點，引入了生鮮損耗度系數來反映生鮮農產品隨時間推移而下降的特點，并建立了在滿足客戶點收貨時間窗的基礎上，配送成本最低的混合整數規(guī)劃模型，并采用精確算法本德斯分解法（benders decomposition）來對該模型進行求解。

2.1 問題描述

本文研究的是城市內生鮮農產品的最后一公里配送問題。問題以配送成本最小化為目標，采用同類型電動三輪車實現生鮮農產品的最后一公里配送。

問題的特點如下：

（1）運輸網絡包含兩類節(jié)點：區(qū)域配送中心及該配送中心輻射服務范圍內若干有配送需求的客戶點。其中區(qū)域配送中心是配送車輛的始發(fā)/終到點。

（2）配送車輛的車型相同，且其額定載貨量、實載率、速度、行駛成本等已知。

（3）客戶點的貨物需求已知且不可拆分，每個客戶點的貨物需求量不超過一臺配送車輛的額定載貨量。所有客戶點均有收貨時間窗限制。在配送周期內配送車輛服務全部客戶點，每個客戶點每天只能被服務一次。

（4）配送成本主要考慮行駛成本、等待時間懲罰成本和生鮮農產品損耗成本。

2.2 參數及變量

將上述問題定義在有向圖G=(V,A)上，V={0,1,...,n}為點集合，其中，0表示區(qū)域配送中心，V{0}表示配送網絡中等待配送服務的客戶點。具體參數及變量含義見表1。

表1 參數及變量

2.3 建立模型

目標函數：

約束條件

目標函數式（1）表示總配送成本的最小化，由三部分組成：第一部分為配送過程的行駛成本；第二部分為配送過程中配送車輛在客戶點處等待的懲罰成本；第三部分為配送過程中生鮮農產品生鮮度損耗成本。

約束（2）表示配送車輛進出場站的次數為1；約束（3）表示對于任一客戶點來說，只能被一輛配送車輛服務一次；約束（4）表示配送車輛k的進出節(jié)點流平衡，且每輛配送車輛對同一個節(jié)點服務一次；約束（5）確保了每臺配送車輛服務客戶點的貨物需求總量不超過該配送車輛的實際載貨量；約束（6）和（7）表明了配送車輛從區(qū)域配送中心出發(fā)時間與到達第一個客戶點處的到達時間的關系；約束（8）和（9）表明了配送車輛在兩個客戶點的到達時間之間的關系，約束（10）和（11）表示配送車輛要滿足客戶點的取貨時間窗要求；約束（12）-（14）定義變量 dtk、atki、wtki的取值范圍為非負。

3 第一種benders分解策略

benders分解法（簡稱BD）[17]的基本原理是將模型按照變量類型分解為主問題和子問題，其中主問題包含0-1整數變量，子問題包含連續(xù)變量。首先求解主問題獲得0-1變量的初始解，并將初始解作為輸入來求解對偶子問題，若子問題的對偶問題有界，那么通過求解對偶問題可得到benders最優(yōu)割，若子問題無界，則得到benders可行割，將得到的割約束添加到主問題中，重建主問題并求解，如此循環(huán)迭代，直到求解主問題得到的下界值和求解子問題得到的上界值相等或在一定的偏差范圍內，算法停止，得到最優(yōu)解。

按照經典benders分解法的思路對模型進行分解，分解得到的子問題及重建主問題如下：

3.1 子問題及其對偶問題

主問題包含的約束條件為（2）-（5），固定模型中約束條件（6）-（11）中的整數變量xkij來確定子問題。

目標函數：

約束條件：

將約束條件轉化為原問題的標準形式得：

為約束條件（22）-（27）分別設置對偶變量 uki、根據對偶原理得到原問題的對偶問題如下所示：

約束（29）是針對變量dtk得到的對偶問題約束條件，約束（30）是針對子問題中的變量atki,?i∈V{0}的約束條件，而約束（31）為針對原問題中變量atk0的約束，約束（32）是針對變量 wtki,?i∈V{0}的約束。

3.2 重建主問題

引入自由變量θ，將生成的benders割約束加入到主問題中，生成重建主問題：

4 第二種benders分解策略

在第一種分解策略中，主問題中只包含一個變量，子問題中包含三個變量，這種分解方法可能會導致主問題不夠完整，而子問題的規(guī)模偏大，因此在第一種分解策略的基礎上提出了第二種分解策略，這兩種分解策略的區(qū)別在于第二種分解策略將連續(xù)變量atki、dtk作為主問題中的變量，而子問題中只包含連續(xù)變量wtki，這種分解方式可以使得主問題相較于第一種分解策略更加完整，得到的主問題的初始解更合理。

4.1 子問題及其對偶問題

相較于第一種benders分解策略，第二種分解策略中主問題包含的約束條件為（2）-（9），固定模型中約束條件（10）-（11）中 xkij、atki值來確定子問題。

將求解主問題獲得的xkij、atki值作為初始值帶入到子問題中，得到了原問題對應的子問題，子問題中包含連續(xù)變量wtki：

目標函數：

約束條件：

將約束條件轉化為標準形式得：

為約束條件（38）～（41）分別設置對偶變量 wkij、根據對偶原理得到原問題的對偶問題如下所示：

約束（43）針對變量 wtki,?i∈V{0}。

4.2 重建主問題

引入自由變量θ，將生成的benders割約束加入到主問題中，重建主問題：

5 算例生成

5.1 方法

為了檢驗模型的合理性以及算法的有效性，本文結合城市物流配送實際并利用Matlab生成一系列隨機算例，算例相應變量見表1。

（1）網絡節(jié)點坐標以及距離矩陣dij。城市生鮮“最后一公里”配送的運載工具以電動三輪車為主。以1km為單位建立坐標系。在配送過程中，考慮到電動三輪車一次充電后的續(xù)航里程以及一輛車配送的范圍，可設定其最大行駛距離Dmax=15km。由此可以確定客戶點均應位于以(7.5,7.5)為圓心、7.5km為半徑的圓內。在該圓內隨機生成若干個客戶點坐標，利用各節(jié)點的坐標空間分布來計算兩節(jié)點之間的歐氏距離dij。

（2）客戶點的訂單量qi?？紤]到電動三輪車的最大載重量為600kg左右，以一天送50單貨物可知，貨物重量范圍為（1kg,12kg），隨機生成該范圍內客戶點的訂單量。

（3）客戶點取貨時間窗[ ]ei,li。在本文研究中，生鮮農產品的配送需要考慮到時效問題，在配送過程中需要滿足客戶點取貨時間窗的要求，因此本文借鑒Solomn[2]（1987）中的方法生成客戶點的時間窗，假設配送服務從時間t開始。

假設客戶點i為區(qū)域配送中心輻射服務區(qū)域內的客戶點，配送車輛在客戶點i處的服務時間為si；t1=ei+dij/v為配送卡車在i點無需等待時的時間窗下限的最大值；t2=li-dij/v-si為配送卡車剛好能夠完成配送活動的時間窗上限值。隨機生成[t1,t2]范圍內的數t3作為時間窗中心，并且利用正態(tài)隨機分布生成時間窗半徑t4，則客戶點i處的時間窗下限為ei=max(t,t3-t4)，時間窗上限為li=min(t2,t3+t4)。

（4）客戶點處的派件服務時間。按照實際經驗取5min-20min內的隨機數即可。

5.2 參數設置

隨機算例的參數設置見表2。

表2 隨機算例的參數設置

5.3 算例計算結果

本文運用CPLEX 12.4軟件結合VS 2010軟件編程實現兩種benders分解法，并對隨機算例求解，計算結果見表3，其中第一列表示算例編號，算例編號“mn”表示包含m個客戶點的第n個算例，如算例“5-1”表示包含5個客戶點的第1個算例；第三列表示該模型的目標函數，即車輛的配送成本；第四、五列表示所需要的配送車數量以及相應的配送路徑；第六列表示不同分解方式所需要的計算時間；第七列表示benders分解過程中上界值和下界值之間的偏差。

表3 算例計算結果

從算例計算結果來看，兩種分解策略得到的目標函數值和配送車輛的路徑是一致的，表明這兩種分解策略均能在一定時間內給出算例的最優(yōu)路徑，同時也表明模型的準確性及算法的有效性；從計算時間看，70%算例的第二種分解策略的計算時間優(yōu)于第一種分解策略；從算法計算的收斂情況看，70%的算例第二種分解策略的收斂效果優(yōu)于第一種分解策略。結合這兩方面來看，第二種分解策略的計算效果要優(yōu)于第一種分解法。從benders算法的基本原理來看，本文所討論的問題本質上為路徑優(yōu)化問題，每次迭代過程中模型的完整度對解的質量有很大的影響，第二種分解策略在每次迭代的過程中，主問題所包含的變量和約束條件比第一種分解策略更多，主問題的完整度相較于第一種分解策略更高，主問題越完整，每次求解主問題獲得的初始解就會更加合理，那么初始解帶入子問題后求解子問題得到的割約束的約束力會更強，在求解重建主問題時算法會收斂的更快，體現在算例計算結果中，70%的算例運用第二種分解策略的求解速度更快。

6 結語

本文研究了時間窗約束下的生鮮農產品最后一公里配送問題，建立了車輛調度的混合整數規(guī)劃模型，利用兩種不同的benders分解策略對隨機生成的算例精確求解，對生成的配送路徑進行了優(yōu)化實證，驗證了模型的準確性和算法的有效性，得到了不同客戶點規(guī)模下的最優(yōu)配送方案，計算結果證明第二種benders分解策略能夠在較短的時間內給出隨機算例的最優(yōu)路徑方案，為城市配送車輛調度問題的求解提供了一種新的方法。