韓 印，師 攀 （上海理工大學(xué)，上海200093）

HAN Yin, SHI Pan (University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

我國(guó)每年果品腐蝕損壞近1 200 萬(wàn)噸，蔬菜1.3 億噸，經(jīng)濟(jì)損失超過(guò)上千億元。易腐食品特別是初級(jí)農(nóng)產(chǎn)品的大量損耗，尤其在運(yùn)輸過(guò)程中損耗最高，使整個(gè)物流費(fèi)用占到易腐食品成本的70%。因此，迫切需要降低物流成本。

優(yōu)化配送路徑是降低物流成本的重要途徑。早在1959 年，Dantzig 和Ramser 在進(jìn)行一個(gè)配送汽油至加油站的問(wèn)題時(shí)就提出了車(chē)輛路徑問(wèn)題[1]。Clarke 和Wright 在此基礎(chǔ)上提出了一種改進(jìn)的并且較為有效的啟發(fā)式算法，Clarke-Wright 節(jié)約算法[2]。1987年，Solomon 和Desrosiers 等人將時(shí)間窗約束引入到一般的車(chē)輛路徑問(wèn)題中，最早對(duì)時(shí)間窗的車(chē)輛路徑問(wèn)題進(jìn)行了研究[3]。但是，對(duì)冷鏈物流配送路徑優(yōu)化的研究還相對(duì)較少，Tarantilies 和Kiranoudis 等認(rèn)為時(shí)間的有效性是易腐食品配送的關(guān)鍵，提出通過(guò)交換路徑中的節(jié)點(diǎn)或路徑來(lái)進(jìn)行改進(jìn)算法優(yōu)越性的后啟發(fā)式算法，但是沒(méi)有考慮冷藏[4]。Miroslav Verbic 用線(xiàn)性規(guī)劃的方法，從經(jīng)濟(jì)價(jià)值角度給出衡量冷鏈中易腐食品質(zhì)量的主要因素[5]。李宏以傳統(tǒng)時(shí)間窗限制下車(chē)輛路徑問(wèn)題為基礎(chǔ)，考慮了生鮮產(chǎn)品腐壞造成的貨損成本以及違反客戶(hù)需求時(shí)間窗引起的懲罰成本、配送時(shí)冷凍設(shè)備消耗的成本等，建立了冷鏈物流配送路徑的基本模型，最后進(jìn)行了算例分析和主要參數(shù)的敏感度分析[6]。上述文獻(xiàn)都沒(méi)有考慮路況條件，本文在冷鏈物流配送模型的基礎(chǔ)上，考慮路況對(duì)配送路徑的影響，構(gòu)造了一種綜合節(jié)約算法，并對(duì)10 個(gè)客戶(hù)進(jìn)行算例分析，用該算法分別對(duì)考慮路況條件的配送模型與沒(méi)考慮路況條件的配送模型求解，由結(jié)果可知兩個(gè)模型得出的最優(yōu)路徑不同，因此得出結(jié)論，研究考慮路況條件的冷鏈物流配送更具有實(shí)際意義。

1 冷鏈物流配送模型

1.1 問(wèn)題描述

冷鏈物流配送路徑優(yōu)化問(wèn)題可描述為：一個(gè)配送中心擁有多輛汽車(chē)，每輛汽車(chē)從配送中心出發(fā)，為多個(gè)客戶(hù)送貨，配送結(jié)束后配送車(chē)輛返回配送中心。

1.2 模型前提假設(shè)

（1） 配送中心擁有一定數(shù)量的配送車(chē)輛，且每輛車(chē)載重量一定。

（2） 配送中心不存在缺貨，且客戶(hù)的需求量、地理位置、時(shí)間窗約束已知。

（3） 配送車(chē)輛從配送中心出發(fā)，完成配送任務(wù)后必須返回配送中心。

（4） 車(chē)輛一旦離開(kāi)前一個(gè)客戶(hù)點(diǎn)，下一個(gè)客戶(hù)點(diǎn)便已確定，無(wú)中途指派。

（5） 在配送過(guò)程中能保持固定溫度，產(chǎn)品損耗只與配送時(shí)間有關(guān)。

（6） 每條路線(xiàn)上的需求量都小于車(chē)輛的裝載量，且每個(gè)客戶(hù)所需貨物只能由一輛汽車(chē)配送。

（7） 每條配送路徑上的運(yùn)輸長(zhǎng)度不能大于配送車(chē)輛一次配送最大距離。

（8） 每個(gè)客戶(hù)對(duì)早到或晚到的不滿(mǎn)意程度都符合相同的線(xiàn)性函數(shù)關(guān)系。

（9） 每條道路等級(jí)已知。

1.3 冷鏈物流配送模型建立

模型以綜合成本最低作為目標(biāo)函數(shù)。綜合成本包括：配送車(chē)輛的運(yùn)輸成本、貨損成本、能耗成本以及違反時(shí)間窗的懲罰成本。

（1） 配送車(chē)輛運(yùn)輸成本

車(chē)輛的運(yùn)輸成本可表示為：

其中：c為單位里程運(yùn)輸成本，dij為客戶(hù)i到客戶(hù)j之間的距離，xijk為0，1 變量，當(dāng)?shù)趉輛車(chē)經(jīng)過(guò)（pi,pj）路段時(shí)，則xijk為1，否則為0。

（2） 配送過(guò)程中的貨損成本

貨損成本包含運(yùn)輸過(guò)程中的貨損成本和服務(wù)客戶(hù)時(shí)車(chē)門(mén)開(kāi)啟造成的貨損成本。貨損成本可表示為：

其中：p為生鮮產(chǎn)品的單位成本，xjk為0，1 變量，當(dāng)?shù)贙輛車(chē)為j客戶(hù)服務(wù)時(shí)，xjk=1，否則為0。dij為從客戶(hù)i到客戶(hù)j的距離。zij為路況條件轉(zhuǎn)換系數(shù)，θ1為運(yùn)輸過(guò)程中的貨損系數(shù)，θ2為服務(wù)客戶(hù)時(shí)的貨損系數(shù)，qj為到達(dá)客戶(hù)j時(shí)車(chē)上所剩的貨物量。

（3） 配送車(chē)輛制冷的能耗成本

制冷劑消耗量計(jì)算簡(jiǎn)化公式為：

其中：H為制冷劑消耗量，β 為常數(shù)，R為車(chē)廂的熱傳系數(shù)（W/（m2·K），Sb為車(chē)體表面積（m）2，ΔT為車(chē)廂內(nèi)外溫度差（℃）。設(shè)ph為制冷劑價(jià)格，則車(chē)輛行駛過(guò)程中消耗制冷劑成本為：

打開(kāi)車(chē)門(mén)時(shí)消耗的制冷成本為：

其中：fj為車(chē)輛在客戶(hù)j的服務(wù)時(shí)間，S為車(chē)門(mén)面積。

（4） 違反客戶(hù)時(shí)間窗的懲罰成本

假設(shè)客戶(hù)j要求的時(shí)間窗為[ej,lj]，可接受的時(shí)間窗為[Ej,Lj]，tj為配送車(chē)輛到達(dá)客戶(hù)點(diǎn)j的時(shí)間。如果送達(dá)時(shí)間在[Ej,lj]，懲罰成本為0；如果送達(dá)時(shí)間超過(guò)[Ej,Lj]，則懲罰成本為+∞；若在Ej之前則需要等待至Ej，期間貨損系數(shù)為θ1；如在[lj,Lj]之間送達(dá)，懲罰系數(shù)為μ。因此，懲罰成本可表示為：

1.4 冷鏈物流車(chē)輛配送路徑優(yōu)化模型

上述式中式（1） 為目標(biāo)函數(shù)；式（2） 約束配送路徑數(shù)不能超過(guò)配送車(chē)輛總數(shù)；式（3） 約束配送車(chē)輛的出發(fā)點(diǎn)和返回點(diǎn)都為配送中心；式（4）、（5） 約束每個(gè)客戶(hù)只被一輛車(chē)服務(wù)一次；式（6） 約束每條路徑上客戶(hù)需求總量不得超過(guò)配送車(chē)輛的載重量；式（7） 要求車(chē)輛到達(dá)時(shí)間必須在客戶(hù)要求的時(shí)間范圍內(nèi)；式（8）、（9） 保證時(shí)間表的靈活性。

2 基于路況條件下的綜合節(jié)約算法

綜合節(jié)約算法與原有節(jié)約里程法的不同之處是不單純的以距離作為節(jié)約的判斷依據(jù)，而是綜合考慮了道路狀況，將距離節(jié)約轉(zhuǎn)化為綜合節(jié)約。

綜合節(jié)約的基本思想是綜合考慮配送道路通行狀況，并通過(guò)當(dāng)?shù)亟还懿块T(mén)獲取道路狀況系數(shù)zij，通過(guò)道路平均運(yùn)行速度進(jìn)行換算，然后對(duì)運(yùn)輸成本、貨損成本、制冷成本分別節(jié)約，最后對(duì)其進(jìn)行綜合，如表1。其方法如下：

表1 綜合節(jié)約成本

（1） 每一個(gè)節(jié)點(diǎn)pi與配送中心p0連接，產(chǎn)生n條僅含一個(gè)點(diǎn)的路徑p0-p1-p0，根據(jù)節(jié)約算法，連接任意兩點(diǎn)i、j后算出節(jié)約運(yùn)輸成本Δc1=c0i+c0j-cij。然后依次算出節(jié)約貨損成本節(jié)約制冷成本

（2） 將三個(gè)節(jié)約成本進(jìn)行綜合得到總節(jié)約成本Δc=Δc1+Δc2+Δc3。

（3） 以時(shí)間窗為標(biāo)準(zhǔn)，將所有客戶(hù)依次排序。

（4） 以配送中心為起點(diǎn)，將時(shí)間窗最靠前的客戶(hù)作為第一條路線(xiàn)上的第一個(gè)客戶(hù)，并在Δc表格中找出總節(jié)約成本最大的客戶(hù)。依此類(lèi)推，直到達(dá)到時(shí)間窗或者車(chē)容量限制，這作為第一條路線(xiàn)。

（5） 刪掉第一條線(xiàn)路上的客戶(hù)，重復(fù)步驟4，直到所有客戶(hù)都在線(xiàn)路上。

3 算例分析

本文給出10 個(gè)客戶(hù)數(shù)算例驗(yàn)證上述算法，具體描述如下：某配送中心向10 個(gè)客戶(hù)配送某種蔬菜，客戶(hù)i的需求量為Qi，配送中心到各配送點(diǎn)的需求量和配送距離由表2 給出，在i的服務(wù)時(shí)間為fi以及客戶(hù)要求到達(dá)的時(shí)間范圍[ej,lj]由表3 給出，采用小型貨車(chē)的載重量為4t，且配送過(guò)程中平均行使速度為30km/h，最后返回配送中心。

單位運(yùn)輸成本c=2 元/km，蔬菜單價(jià)為4 000 元/t，運(yùn)輸過(guò)程中的貨損系數(shù)θ1為3%，裝卸過(guò)程中的貨損系數(shù)θ2為0.2%，車(chē)內(nèi)溫度為-20℃，車(chē)外溫度為30℃，車(chē)輛使用液態(tài)氮為制冷劑，每千克制冷劑價(jià)格為4.5 元，β=0.19,ph=4.5，R=0.4,sb=16, Δt=50。

結(jié)果分析：

根據(jù)產(chǎn)品配送的具體要求，運(yùn)用改進(jìn)后的節(jié)約算法對(duì)問(wèn)題進(jìn)行求解，得到的優(yōu)化結(jié)果為：

表2 配送距離及各配送點(diǎn)的需求量

表3 各配送點(diǎn)的時(shí)間窗及服務(wù)時(shí)間

下面根據(jù)沒(méi)有考慮路況條件的車(chē)輛配送模型，利用上述算法求出最優(yōu)路徑，并把所得路徑給出以供比較。

比較上述路徑可知：兩個(gè)模型所得路徑完全不同，考慮道路狀況的模型將實(shí)際配送的道路狀況考慮在內(nèi)，更加具有實(shí)際意義。

4 結(jié) 論

本文在一般冷藏配送模型的基礎(chǔ)上，充分考慮了實(shí)際道路狀況，通過(guò)將道路狀況進(jìn)行簡(jiǎn)單的轉(zhuǎn)化，構(gòu)建了考慮道路狀況的冷藏物流配送路徑優(yōu)化模型。模型以包括制冷成本、運(yùn)輸成本、貨損成本、違反時(shí)間窗的懲罰成本在內(nèi)的總成本最小為目標(biāo)函數(shù)，以車(chē)載重量、時(shí)間窗為約束。在算法上，構(gòu)建了基于道路狀況的綜合節(jié)約算法，并用該算法找出一個(gè)10 個(gè)客戶(hù)算例最優(yōu)路徑。最后通過(guò)比較一般冷藏物流配送模型跟考慮實(shí)際道路狀況的路徑優(yōu)化模型所得到的最優(yōu)路徑進(jìn)行比較，可知兩個(gè)模型求出的最優(yōu)路徑是不相同的，從而得出建立考慮道路狀況的冷藏物流配送模型更加具有實(shí)際意義。

[1] Dant Zig G, Ramser J. Theruek dispatehing problem[J]. Management Seienee, 1959(6):80-91.

[2] Clark G, Wright J. Seheduling of vehieles from aeentral depotto anumber of delivery Points[J]. OPens, Researeh, 1964(4):15-18.

[3] Solomon, M. M.. Algorithm for the Vehiele Routing and Seheduling Problems with Time—Windows Constraints[J]. OPerationsreseareh, 1987(2):254-265.

[4] Tarantilis C D, Kirannoudis C T. Ameta-heuristic algorithm for the efficient distribution of perishable foods[J]. Joumal of Food Engingeering, 2001,50:1-9.

[5] Miroslav Verbic. Discussing the parameter of preservation of perishable goods in a cold logistic chain model[J]. Applied Economics, 2006,38:137-147.

[6] 李宏. 城市冷鏈物流配送車(chē)輛問(wèn)題的研究[D]. 長(zhǎng)沙：長(zhǎng)沙理工大學(xué)（碩士學(xué)位論文），2006.