帶時(shí)間窗的連鎖超市生鮮品配送車輛路徑優(yōu)化

■ 姚卓順（蘇州工業(yè)職業(yè)技術(shù)學(xué)院經(jīng)貿(mào)管理系 江蘇蘇州 215104）

引言

1959年，Dantzig和Ramser提出了車輛路徑問題（Vehicle Routing Problems，簡稱VRP），VPR問題至今都是解決物流配送問題的核心部分，它以路程最短、成本最小、耗費(fèi)時(shí)間最少等為目的。本文的VRP描述為：在一定約束條件（需求量、車載量、需求時(shí)間、行駛里程、行駛時(shí)間等）下，對一定數(shù)量的門店，選擇適當(dāng)?shù)能囕v配送路徑，使其從配送中心出發(fā)，將貨物有序送至各門店后返回配送中心。

綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics）。

精確算法一般會隨著問題規(guī)模的增大而呈現(xiàn)數(shù)據(jù)量增大的情況，計(jì)算成本比較大，因此很難有效解決大規(guī)模的VRP問題，實(shí)際應(yīng)用范圍有限。

由于VRP是NP-hard問題，這類問題的大型實(shí)例很難以用精確算法求解，多年來很多專家對此類車輛運(yùn)輸問題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法，常見的有構(gòu)造算法、蟻群算法、遺傳算法、節(jié)約里程法。

節(jié)約里程法，是用來解決運(yùn)輸車輛數(shù)目不確定的問題的最有名的啟發(fā)式算法。節(jié)約里程法的核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。根據(jù)節(jié)約法的基本思想，如果一個(gè)配送中心p0分別向m個(gè)客戶配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過的客戶個(gè)數(shù)越多，里程節(jié)約量越大，配送線路越合理。

節(jié)約里程法運(yùn)算速度較快，特別是在小規(guī)模的配送路徑優(yōu)化問題中，節(jié)約里程法的優(yōu)化解與最優(yōu)解更加接近，其在實(shí)際應(yīng)用中也能得到較滿意的結(jié)果，連鎖超市配送規(guī)模較小，所以本文將以節(jié)約里程法對連鎖超市配送車輛路徑進(jìn)行優(yōu)化。

帶時(shí)間窗約束的VRP

時(shí)間約束問題大體分為兩種，一種是“允許延時(shí)”的“軟時(shí)間窗”問題，一種是“不允許延時(shí)”的“硬時(shí)間窗”問題。

“軟時(shí)間窗”問題是指：客戶對配送的時(shí)間要求具有彈性，客戶能夠承受因各種原因?qū)е碌牟荒軠?zhǔn)時(shí)送達(dá)，但要索取因此而帶來的損失。

“硬時(shí)間窗”問題是指：客戶對最長運(yùn)達(dá)時(shí)間具有嚴(yán)格要求，也就是說，在客戶的時(shí)間要求之內(nèi)，配送中心必須將貨物配送到位，否則配送沒有達(dá)到客戶的時(shí)間要求，直接導(dǎo)致了物流流通的障礙和瓶頸。

由于“硬時(shí)間窗”的約束，往往會導(dǎo)致成本激增，因此，相比而言，“軟時(shí)間窗”更具管理柔性，我們可以通過制定懲罰機(jī)制，例如設(shè)定懲罰成本來提高準(zhǔn)點(diǎn)服務(wù)頻率。

在建立懲罰成本模型時(shí)，設(shè)門店a可接受的時(shí)間窗[Ma，Na]，門店要求的時(shí)間窗[ma，na]。根據(jù)配送車輛到達(dá)門店的時(shí)間，可以分三種情況：

一是配送車輛在門店要求的時(shí)間之前到達(dá)。此時(shí)又可分為兩種情況，其一車輛是在門店可接受的時(shí)間到達(dá)，即在[Ma，ma]內(nèi)，車輛到達(dá)后可以交貨，但由于交貨不在門店要求的時(shí)間內(nèi)，需要付出一定懲罰成本，則函數(shù)可以表示為P(Xa)=(ma-Xa)·α；其二是車輛到達(dá)的時(shí)間在門店可接受的時(shí)間之前，即在Ma之前，此時(shí)客戶無法收貨，這時(shí)的懲罰成本無窮大，P(Xa)=∞。

二是配送車輛在門店要求的時(shí)間內(nèi)到達(dá)，即在[ma，na]內(nèi)，此時(shí)不產(chǎn)生懲罰成本，P(Xa)=0。

三是配送車輛在門店要求的時(shí)間后到達(dá)。此時(shí)也可分為兩種情況，其一車輛是在門店可接受的時(shí)間到達(dá)，即在(na，Na]內(nèi)，車輛到達(dá)后可以交貨，但此時(shí)需要承擔(dān)一定的懲罰成本，則函數(shù)可以表示為P(Xa)=(Xa-na)·β；其二是車輛到達(dá)的時(shí)間在門店可接受的時(shí)間之后，即在Na之后，此時(shí)客戶無法收貨，這時(shí)的懲罰成本無窮大，P(Xa)=∞。

綜上，懲罰成本函數(shù)可以表示為：

式中：Xa是生鮮品送達(dá)門店的時(shí)間；A和β是懲罰系數(shù)；P(Xa)是懲罰成本；P是生鮮單位價(jià)值；qb是每個(gè)門店生鮮需求量。

表1 連鎖超市配送中心與門店之間的距離

表2 門店的貨物需求量及時(shí)間窗要求

連鎖超市生鮮品配送車輛路徑問題模型建立

（一）模型建立的約束條件

門店的數(shù)量固定且位置已知；門店的生鮮品需求量一定；生鮮品送達(dá)時(shí)間窗一定；每輛車的行駛時(shí)間不得超過司機(jī)工作的時(shí)間；每家門店且只能由一輛車一次性完成送貨；每條配送線路各門店的需求量之和不得超過車輛的最大核載量；車輛由配送中心出發(fā)，有序到達(dá)各門店后返回配送中心。

（二）軟時(shí)間窗約束下的模型建立

生鮮品配送中心每天派出n輛車從配送中心出發(fā)，為一家或多家門店送貨，完成任務(wù)后再返回配送中心。生鮮品配送的成本主要包括運(yùn)輸成本、制冷成本以及軟時(shí)窗下的懲罰成本。

1.運(yùn)輸成本。運(yùn)輸成本主要包括車輛的固定成本和變動成本。由于固定成本與車輛運(yùn)輸距離及門店數(shù)量沒有直接聯(lián)系，因此本文不予考慮。變動成本受油耗、車輛磨損、維修等因素的影響，所以他們主要與車輛的運(yùn)輸距離呈正比。計(jì)算公式為：

2.生鮮品的制冷成本。 在配送過程中，生鮮品的制冷成本主要是由于保存環(huán)境和配送時(shí)間而導(dǎo)致的。因此我們在研究時(shí)，忽略其他因素，將生鮮品的制冷成本分為兩個(gè)部分，一是隨著配送時(shí)間的增加制冷成本也隨之上升；二是配送服務(wù)時(shí)，裝卸生鮮品過程中開啟車門，車內(nèi)外冷暖空氣對流導(dǎo)致車內(nèi)溫度上升，從而產(chǎn)生制冷成本。計(jì)算公式為：

3.懲罰成本如式（1）所示。 綜上所述，我們構(gòu)建的生鮮品配送車輛路徑問題的目標(biāo)函數(shù)：

公式中涉及的參數(shù)如下：

m是門店的數(shù)量；n是配送車輛數(shù)；lab是從門店a到門店b的運(yùn)輸距離；tab是從門店a到門店b的運(yùn)輸時(shí)間；tbh是從第h輛車在門店的停留時(shí)間；Cabh是從第h輛車在路段(la，lb)上的運(yùn)輸成本；C表示單位運(yùn)輸成本；Cbh是配送過程的制冷成本；Cz1是由于配送服務(wù)時(shí)間產(chǎn)生的制冷成本；Cz2是門店送貨服務(wù)過程中熱侵入時(shí)產(chǎn)生的制冷成本；ΔT是為冷藏車內(nèi)與外界溫差；q是每個(gè)門店生鮮需求量；xabh是0,1變量，若第第h部車輛經(jīng)過路段(la，lb)，則xabh=1，否則xabh=0；xbh是0,1變量，若第h部車輛為b門店服務(wù)，則xbh=1，否則xbh=0。

連鎖超市生鮮品車輛路徑優(yōu)化算例分析

客戶在蘇州市有1個(gè)配送中心和10家連鎖超市門店，現(xiàn)要求對其生鮮品配送車輛路徑進(jìn)行優(yōu)化。相關(guān)參數(shù)如表1、表2、表3所示。

根據(jù)前面所建立的軟時(shí)間窗約束下生鮮品配送車輛路徑問題的模型式（4），其相關(guān)因素包括運(yùn)輸成本、制冷成本和懲罰成本，其目標(biāo)函數(shù)為總成本最小。本文利用節(jié)約里程法對連鎖超市生鮮品車輛配送路徑進(jìn)行優(yōu)化時(shí)，其涉及的相關(guān)因素包括節(jié)約的運(yùn)輸成本、節(jié)約的制冷成本和懲罰成本，所以我們的目標(biāo)是使節(jié)約總成本最大的門店插入配送路徑中，直至完成所有門店的配送任務(wù)，具體的計(jì)算公式如下：

P(Xa)如式（1）所示。

公式中：yab是節(jié)約里程數(shù)；Pr是節(jié)約的運(yùn)輸成本；Pd是節(jié)約的制冷成本；Pz是節(jié)約的總成本；v表示運(yùn)輸速度。

利用節(jié)約里程法結(jié)合時(shí)間窗約束，我們將帶有時(shí)間窗約束的連鎖超市VRP求解步驟歸納如下：

第一步，將門店按時(shí)間窗先后順序排序；第二步，計(jì)算配送中心到各門店的節(jié)約里程數(shù)；第三步，從配送中心發(fā)車，首先將時(shí)間窗要求最早的門店作為第一個(gè)配送對象，然后將節(jié)約總成本最大的門店加入路線，成為第二個(gè)配送對象；第四步，重復(fù)第三步，直至所有的門店都被排入路線內(nèi)。

根據(jù)以上步驟求解，最終的配送路線為P0配送中心—I鳳凰街店—A東大街店—C養(yǎng)育巷店—E竹輝路店—B南園路店—G桃花塢店—J中街路店—F觀前街店—D皮市街店—H相王路店—P0配送中心。

按當(dāng)前連鎖超市配送車輛路徑規(guī)劃的原則，即以最為靠近配送中心的門店開始送貨，以下一門店距離上一門店最近來進(jìn)行下一門店的送貨，直至送完為止回到配送中心，這10家店目前的配送路線為：P0配送中心—B南園路店—E竹輝路店—H相王路店—I鳳凰街店—C東大街店—A養(yǎng)育巷店—F觀前街店—D皮市街店—J中街路店—G桃花塢店—P0配送中心。

因此，與連鎖超市當(dāng)前的配送路線相比較（表4），配送總成本節(jié)約了138-98.4=39.6元。

表3 相關(guān)參數(shù)值

表4 配送路徑優(yōu)化前后數(shù)值比較

結(jié)論

本文利用節(jié)約里程法結(jié)合門店時(shí)間窗的要求，進(jìn)行了生鮮配送車輛路徑規(guī)劃，在滿足連鎖超市各門店生鮮收貨時(shí)間需求的同時(shí)，選擇較優(yōu)的路徑進(jìn)行配送，這樣提高了配送車輛生鮮送貨服務(wù)質(zhì)量，節(jié)省了車輛在各門店的卸貨等待時(shí)間，同時(shí)也保證了生鮮及時(shí)進(jìn)入各門店上貨架。

1.朱金峰.冷鏈物流車輛路徑模型優(yōu)化研究[D].山東師范大學(xué)，2009

2.朱曉峰，蔡延光.物流配送的優(yōu)化模型及算法在連鎖企業(yè)中應(yīng)用[J].順德職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2011（1）

3.胡運(yùn)權(quán).運(yùn)籌學(xué)（第5版）[M].高等教育出版社，2008

4.付麗茹，解進(jìn)強(qiáng)，羅松濤.運(yùn)輸配送路線優(yōu)化（第1版）[M].清華大學(xué)出版社，2011

5.董立娟.帶時(shí)間窗維束的冷鮮肉制品配送路徑優(yōu)化[D].中南大學(xué)，2011

6.陳曉偉，張悟移，耿繼武.節(jié)約法在配送路線選擇中的應(yīng)用[J].昆明理工大學(xué)學(xué)報(bào)，2003（8）

7.中國物流技術(shù)協(xié)會.中國冷鏈物流發(fā)展報(bào)告[R].2010

8.繆小紅.基于GIS的生鮮食品冷鏈物流配送路徑優(yōu)化研究[D].福建農(nóng)林大學(xué)，2010