秦詩寒　余小鵬　朱秀迪

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

[關(guān)鍵詞] 時(shí)間約束；生鮮配送路線；優(yōu)化模型；節(jié)約算法

[中圖分類號] F323.7 [文獻(xiàn)標(biāo)識碼] 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

一、前言

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

二、模型提出

（一）問題描述

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

（二）數(shù)學(xué)模型

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

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

其中：C1為運(yùn)輸成本，c為單位里程運(yùn)輸成本，tij為運(yùn)輸車輛從網(wǎng)點(diǎn)Vi到Vj的運(yùn)輸時(shí)間，Xijk為0，1變量，若車輛經(jīng)過網(wǎng)點(diǎn)Vi到Vj，則為1，反之為0。

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

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

3.懲罰成本。首先，每個(gè)網(wǎng)點(diǎn)都有自身的時(shí)間窗約束，車輛未在指點(diǎn)時(shí)間范圍內(nèi)送達(dá)，則會(huì)影響網(wǎng)點(diǎn)日常經(jīng)營情況，需要加入一定的懲罰成本，懲罰成本與貨物量、貨物價(jià)格以及延誤時(shí)間相關(guān)；其次，我們假定了網(wǎng)點(diǎn)可接受的延誤時(shí)間，若超過可接受的延誤時(shí)間，則網(wǎng)點(diǎn)拒絕收貨，公式表示為：endprint

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

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

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

因此，根據(jù)配送總成本最小的思想，建立了如下目標(biāo)函數(shù)：

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

三、算法設(shè)計(jì)

考慮到生鮮品的特點(diǎn)及配送的軟時(shí)間窗約束，同時(shí)認(rèn)識到上文建立的生鮮品配送模型求解問題屬于非線性規(guī)劃問題，我們因故采取啟發(fā)式算法中的節(jié)約算法來進(jìn)行求解。

（一）具體思路

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

其中，Yij為網(wǎng)點(diǎn)Vi到Vj的節(jié)約成本，c為單位運(yùn)輸成本，Wij為網(wǎng)點(diǎn)Vi到Vj的節(jié)約里程，h為變量，C3（tj）為Vj網(wǎng)點(diǎn)的懲罰成本，其他變量在第二章已提及，不再一一介紹。通過上述目標(biāo)函數(shù)，發(fā)現(xiàn)添加新網(wǎng)點(diǎn)時(shí)應(yīng)遵循時(shí)間約束為第一順序（降低懲罰成本），各網(wǎng)點(diǎn)運(yùn)輸里程為第二順序（降低運(yùn)輸成本、貨損成本和能耗成本）。

（二）算法步驟

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

（三）實(shí)例分析

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

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

四、結(jié)論

通過對生鮮品配送特點(diǎn)的認(rèn)識，構(gòu)建了包含運(yùn)輸成本、貨損成本、能耗成本和懲罰成本的線路模型，并采用節(jié)約算法，對該模型進(jìn)行了優(yōu)化，以期在最大化節(jié)約成本和時(shí)間窗約束的條件下，確定合適的配送線路；最終通過相應(yīng)實(shí)例，證明了該配送線路優(yōu)化模型的有效性。

[參 考 文 獻(xiàn)]

[1]國家發(fā)展改革委.國家發(fā)展改革委印發(fā).農(nóng)產(chǎn)品冷鏈物流發(fā)展規(guī)劃[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ìn)遺傳算法的新鮮農(nóng)產(chǎn)品配送路線優(yōu)化研究[J].江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，4（36）：399-402

[責(zé)任編輯：王鳳娟]endprint