基于道路狀況的冷鏈物流配送路徑優(yōu)化

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

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

0 引 言

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

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

1 冷鏈物流配送模型

1.1 問題描述

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

1.2 模型前提假設(shè)

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

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

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

（4） 車輛一旦離開前一個(gè)客戶點(diǎn)，下一個(gè)客戶點(diǎn)便已確定，無中途指派。

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

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

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

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

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

1.3 冷鏈物流配送模型建立

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

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

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

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

（2） 配送過程中的貨損成本

貨損成本包含運(yùn)輸過程中的貨損成本和服務(wù)客戶時(shí)車門開啟造成的貨損成本。貨損成本可表示為：

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

（3） 配送車輛制冷的能耗成本

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

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

打開車門時(shí)消耗的制冷成本為：

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

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

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

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

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

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

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

綜合節(jié)約的基本思想是綜合考慮配送道路通行狀況，并通過當(dāng)?shù)亟还懿块T獲取道路狀況系數(shù)zij，通過道路平均運(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)，將所有客戶依次排序。

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

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

3 算例分析

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

單位運(yùn)輸成本c=2 元/km，蔬菜單價(jià)為4 000 元/t，運(yùn)輸過程中的貨損系數(shù)θ1為3%，裝卸過程中的貨損系數(shù)θ2為0.2%，車內(nèi)溫度為-20℃，車外溫度為30℃，車輛使用液態(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ì)問題進(jìn)行求解，得到的優(yōu)化結(jié)果為：

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

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

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

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

4 結(jié) 論

本文在一般冷藏配送模型的基礎(chǔ)上，充分考慮了實(shí)際道路狀況，通過將道路狀況進(jìn)行簡單的轉(zhuǎn)化，構(gòu)建了考慮道路狀況的冷藏物流配送路徑優(yōu)化模型。模型以包括制冷成本、運(yùn)輸成本、貨損成本、違反時(shí)間窗的懲罰成本在內(nèi)的總成本最小為目標(biāo)函數(shù)，以車載重量、時(shí)間窗為約束。在算法上，構(gòu)建了基于道路狀況的綜合節(jié)約算法，并用該算法找出一個(gè)10 個(gè)客戶算例最優(yōu)路徑。最后通過比較一般冷藏物流配送模型跟考慮實(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] 李宏. 城市冷鏈物流配送車輛問題的研究[D]. 長沙：長沙理工大學(xué)（碩士學(xué)位論文），2006.