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

姚卓順

內(nèi)容摘要：生鮮品是人們生活的必需品。近年來，隨著城市化的發(fā)展，連鎖超市已作為人們?nèi)粘Ｉr獲取的主要途徑之一，而生鮮品配送問題成為利潤最大化目標的關鍵之一。本文在考慮時間窗約束的基礎上，分析連鎖超市生鮮品配送過程中的各項成本，建立配送總成本最小化模型，并利用節(jié)約里程法對配送車輛路徑進行優(yōu)化。最后，本文通過算例分析驗證了所建模型的合理性和有效性。

關鍵詞：時間窗 連鎖超市 生鮮品 配送車輛路徑 節(jié)約里程法

引言

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

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

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

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

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

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

帶時間窗約束的VRP

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

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

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

由于“硬時間窗”的約束，往往會導致成本激增，因此，相比而言，“軟時間窗”更具管理柔性，我們可以通過制定懲罰機制，例如設定懲罰成本來提高準點服務頻率。

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

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

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

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

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

（1）

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

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

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

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

（二）軟時間窗約束下的模型建立

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

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

（2）

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

（3）

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

（4）

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

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

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

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

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

（5）

（6）

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

（7）

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

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

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

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

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

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

結(jié)論

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

參考文獻：

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

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

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

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

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

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

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

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

（3）

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

（4）

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

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

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

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

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

（5）

（6）

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

（7）

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

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

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

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

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

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

結(jié)論

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

參考文獻：

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

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

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

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

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

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

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

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

（3）

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

（4）

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

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

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

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

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

（5）

（6）

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

（7）

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

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

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

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

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

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

結(jié)論

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

參考文獻：

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

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

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

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

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

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

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

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