時間約束下生鮮配送線路優化研究

秦詩寒　余小鵬　朱秀迪

[摘 要] 我國冷鏈物流起步較晚，導致生鮮品在配送、裝卸、儲存等環節的損失率較高，建立完善的冷鏈物流配送體系意義重大。根據生鮮品的特點，構建了包含運輸成本、貨損成本、能耗成本和懲罰成本的線路模型，并采用節約算法，對該模型進行了優化，以期在最大化節約成本和時間窗約束的條件下，確定合適的配送線路，最終通過相應實例，證明了該配送線路優化模型的有效性。

[關鍵詞] 時間約束；生鮮配送路線；優化模型；節約算法

[中圖分類號] F323.7 [文獻標識碼] A

Abstract： The cold chain logistics in China starts late， As a result， the distribution， loading and unloading， and storage of fresh food has high loss rate， so it is significant to establish perfect cold chain logistics distribution system.According to the characteristics of fresh food， the study build a line model in terms of transportation， cost of damage， energy consumption and penalty cost and optimized this model by means of saving algorithm， so as to determine appropriate distribution lines to maximize cost savings and time window constraints.Finally， this model is effective proved by the corresponding instance.

Key words： time constraint， fresh distri bution route，optimization models， saving algorithm

一、前言

發改委于2010年7月出臺了首部《農產品冷鏈物流發展規劃》，該規劃提出到2015年，建成一批效率高、規模大、技術新的跨區域冷鏈物流配送中心，使流通環節產品腐損率分別降至15%、8%、10%以下[1]。為了完成該發展規劃，需要整個冷鏈物流體系合理運作，以提升整體效益。而生鮮配送作為冷鏈物流系統中最重要的環節之一，對該環節中路徑的優化不僅能提高配送的時效性，還能有效降低物流成本。目前，國內外關于配送線路優化問題的研究大多歸為車輛路徑問題（VRP），而VRP問題又可細分為帶載重約束VRP問題、帶時間窗VRP問題、帶回程載貨VRP問題等；而早在1959年，Dantzig和Ramser就首次提出了相應的VRP規劃模型和求解算法，以解決需求已知情況下，不同種類的車輛的組成和配送線路，達到運輸費用最少的目的[2]。在2012年Jun等人提出了改進后的經典啟發式算法，通過路線構造、改造、干擾三階段得出最優解[3]；同一年，莊景明等基于改進的遺傳算法對車輛運行路線進行了優化[4]。在本文中，我們對具有時間約束的冷鏈車輛配送線路優化展開了相應研究。

二、模型提出

（一）問題描述

時間約束下生鮮品配送線路優化問題可描述如下：生鮮品配送中心VO接到各網點（Vi=1，2，···n）訂單后，根據各網點訂單量（Qi=1，2···n）和時間窗要求，安排冷鏈配送車輛依次進行貨物配送。其中各配送點Vi與配送中心的距離（di=1，2···n）以及配送量（qi=1，2···n）已知，冷鏈配送車輛具有相同的載重量Q0；各網點都有配送時間約束，超過網點規定時間窗送達則需要承擔延誤成本，該成本與相應生鮮品的價格、數量以及延遲時間相關。本文的目的是在各網點時間約束的條件下，確定合理的配送路線、配送順序、配送車輛數，從而有效降低配送總成本。

（二）數學模型

為了簡化配送條件，以優化生鮮品的配送線路，我們做了如下假設：一是配送中心車輛能夠滿足配送需求；二是單一網點生鮮品需求量不超過每輛車的運載量；三是每個網點生鮮品由一輛車一次送達；四是各網點間以及各網點與配送中心距離已知；五是各網點生鮮品需求量已知；六是各網點間路況相同，配送車輛勻速行駛；七是各網點時間窗、可接受時間窗以及延誤的懲罰系數已知。本文的目標是確定合理的生鮮配送路線、配送順序以及配送車輛數，從而有效降低配送總成本；在本文中，配送總成本主要包括運輸成本、貨損成本、延誤所致的懲罰成本以及車輛能耗成本。

1.運輸成本。由于冷鏈配送車輛相同，因此運輸成本主要與運輸里程相關，用公式可表示為：

其中：C1為運輸成本，c為單位里程運輸成本，tij為運輸車輛從網點Vi到Vj的運輸時間，Xijk為0，1變量，若車輛經過網點Vi到Vj，則為1，反之為0。

2.貨損成本。由于生鮮品具有易損、易腐特點，加上運輸途中擠壓、新陳代謝等問題，會造成生鮮品損耗；我們假定全程路況一致，則貨損成本與車輛的運送時間相關，公式可表示為（假設車輛先到達Vi網點再到Vj網點）：

其中：C2為貨損成本，α為貨損系數，Pj為網點Vj貨物的價格，ΔQjk為K車輛在Vi點卸貨后車輛的剩余載貨；Xijk同上，Si為配送中到Vi網點的距離，Sj為配送中心到Vj網點的距離，h為變量。

3.懲罰成本。首先，每個網點都有自身的時間窗約束，車輛未在指點時間范圍內送達，則會影響網點日常經營情況，需要加入一定的懲罰成本，懲罰成本與貨物量、貨物價格以及延誤時間相關；其次，我們假定了網點可接受的延誤時間，若超過可接受的延誤時間，則網點拒絕收貨，公式表示為：endprint

其中，C3為懲罰成本，β為懲罰系數，Pj為Vj網點所需生鮮品的價格，Qj為Vj網點所需生鮮品的需求量，tjk為K車運送至Vj網點的時間，[tj～td]為Vj網點時間窗，[Ti～Tj]為Vj網點可接受的時間窗（包含了延誤時間）。

4.能耗成本。冷鏈車輛相較于普通運輸車輛而言，需要消耗更多的能源以保證生鮮品溫度的要求；因此生鮮品配送過程中能耗與載貨量、配送里程有關，可用公式表示如下：

其中：C4為能耗成本，γ為耗能系數，Pj為網點Vj貨物的價格，ΔQjk為K車輛在Vi點卸貨后車輛的剩余載貨量，Xijk同上，Si為配送中到Vi網點的距離，Sj為配送中心到Vj網點的距離，h為變量。

因此，根據配送總成本最小的思想，建立了如下目標函數：

在該約束條件中，（1）表明每個網點僅配送一次貨物；（2）表明每個網點都在配送范圍內，不存在遺漏；（3）表明配送中心的冷鏈配送車輛均被利用，不存在閑置車輛；（4）表明每個網點的需求量小于每輛配送車輛的最大載重量；（5）表明每個網點的配送完成時間需在該網點可接受時間范圍內。

三、算法設計

考慮到生鮮品的特點及配送的軟時間窗約束，同時認識到上文建立的生鮮品配送模型求解問題屬于非線性規劃問題，我們因故采取啟發式算法中的節約算法來進行求解。

（一）具體思路

當配送車輛由配送中心發出時，尋找“最鄰近的網點”作為第一條配送線路上的第一個被服務的客戶；隨后，選擇尚未被加入任何線路中的網點加入當前線路中；而且，在加入當前線路的網點選擇中要遵守“綜合成本最低”的原則。其次，運用節約算法求解時，需將可行的網點加入現有回路中，并計算相應的節約值，從而將節約值最多的網點加入到回路中，并不斷重復這一過程直到所有網點納入相應回路。因此，通過對第二節的模型進行優化，可以得到節約值最大化的配送線路模型，其目標函數如下：

其中，Yij為網點Vi到Vj的節約成本，c為單位運輸成本，Wij為網點Vi到Vj的節約里程，h為變量，C3（tj）為Vj網點的懲罰成本，其他變量在第二章已提及，不再一一介紹。通過上述目標函數，發現添加新網點時應遵循時間約束為第一順序（降低懲罰成本），各網點運輸里程為第二順序（降低運輸成本、貨損成本和能耗成本）。

（二）算法步驟

根據節約算法的思想和節約值最大化的配送線路模型，我們認為具體算法步驟包括：（1）按各網點時間窗約束進行排序；（2）計算各網點間的節約里程；（3）按節約算法中“最鄰近網點”思想，在配送中心選擇步驟1排序后網點中的“最鄰近網點”為第一位配送網點；（4）按步驟3的思想逐個將滿足條件的網點納入當前線路，當超過可接受時間窗約束或達到車輛最大載貨量時，則不再加入新的網點；（5）排除已選網點后，重復步驟3和4，直到所有網點均被納入相應配送線路。

（三）實例分析

設某配送中心在約定時間范圍內要向10個生鮮網點配送一批新鮮蘋果，配送中心編號為V0，各網點編號為Vi=1，2···n；配送車輛運行速度為30km/h，載重量Q0為15噸，蘋果的價格P為5000元/噸，生鮮品貨損系數α為0.01%，超過時間窗的懲罰系數β為0.2%，車輛能耗系數γ為0.2%，單位運輸成本c=1元/噸公里，各網點平均卸貨時間為10分鐘/網點。各網點貨物需求量以及時間窗約束見表1，配送中心及各網點間距離見表2。

按照算法步驟對以上實例進行計算：首先，計算出每個網點的時間窗約束先后順序以及各網點間的節約里程；隨后得出第一條配送線路中的第一個網點P1；其次，對剩余網點的節約里程、節約運輸成本、節約貨損成本、節約能耗成本、懲罰成本進行計算，得出各個網點的總節約成本；因此，得到的第一條配送線路為P0-P1-P10-P2-P5-P0，其中載貨量為14.5噸，小于最大載貨量Q0。隨后按以上步驟，計算出第二條配送線路為P0-P3-P4-P6-P0，載貨量為13.5噸；第三條配送線路為P0-P7-P8-P9-P0，載貨量為9.5噸。至此，所有的網點均被納入相應線路。

四、結論

通過對生鮮品配送特點的認識，構建了包含運輸成本、貨損成本、能耗成本和懲罰成本的線路模型，并采用節約算法，對該模型進行了優化，以期在最大化節約成本和時間窗約束的條件下，確定合適的配送線路；最終通過相應實例，證明了該配送線路優化模型的有效性。

[參 考 文 獻]

[1]國家發展改革委.國家發展改革委印發.農產品冷鏈物流發展規劃[EB/OL]. http： // zys. ndrc. gov. cn / xwfb / 201007 / t20100728_363173.html.2010-7-28

[2] Dantzig G.B， Ramser J.H. The truck dispatching problem[J]. Management Science， 1959-6：80-91

[3] Jun Y， Kim B I. New best solutions to VRPSPD benchmark problems by a perturbation based algorithm[J]. Expert Systems with Applications，2012，39（5）： 5641-5648

[4]莊景明，彭昕昀.基于改進遺傳算法的新鮮農產品配送路線優化研究[J].江西師范大學學報（自然科學版），2012，4（36）：399-402

[責任編輯：王鳳娟]endprint