供應(yīng)鏈網(wǎng)絡(luò)物流配送與車輛路徑問題

1、供應(yīng)鏈網(wǎng)絡(luò)物流配送與車輛路徑問題 配送是指對局域范圍內(nèi)的客戶進行多客戶、多品種、按時聯(lián)合送貨活動。 配送活動是指根據(jù)一定區(qū)域范圍內(nèi)各個客戶所需要的各個品種要求， 對配送中心 的庫存物品進行揀選、加工、包裝、分割、組配、分裝上車，并按一定路線循環(huán) 依次送達各個用戶的物流活動。 物流配送是供應(yīng)鏈網(wǎng)絡(luò)中一個重要的直接與消費 者相連的環(huán)節(jié)，是貨物從物流節(jié)點送達收貨人的過程。配送是在集貨、配貨基礎(chǔ) 上，按貨物種類、品種搭配、數(shù)量、時間等要求所進行的運送，是“配”和“送”的 有機結(jié)合。配送的實質(zhì)是現(xiàn)代送貨，是以低成本、優(yōu)質(zhì)服務(wù)為宗旨，是一種先進 的物流形式。 供應(yīng)鏈網(wǎng)絡(luò)的物流配送過程主要包括：從生產(chǎn)工廠進

2、貨并集結(jié)的集貨作業(yè)； 根據(jù)各個用戶的不同需求，在配送中心將所需要的貨物挑選出來的配貨作業(yè)；考 慮配送貨物的質(zhì)量和體積， 充分利用車輛的載重和容積的車載貨物的配裝及路線 的確定。隨著供應(yīng)鏈管理系統(tǒng)的集約化、一體化的發(fā)展，常將配送的各環(huán)節(jié)綜合 起來，核心部分為配送車輛的集貨、貨物裝配及送貨過程。進行配送系統(tǒng)優(yōu)化， 主要是配送車輛優(yōu)化調(diào)度，包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化，以及 集貨、貨物配裝和送貨一體化優(yōu)化。物流配送車輛優(yōu)化調(diào)度，是供應(yīng)鏈系統(tǒng)優(yōu)化 中關(guān)鍵的一環(huán)，也是電子商務(wù)活動不可缺少的內(nèi)容。對配送車輛進行優(yōu)化調(diào)度， 可以提高供應(yīng)鏈管理的經(jīng)濟效益、實現(xiàn)供應(yīng)鏈管理科學(xué)化。 配送車輛優(yōu)化調(diào)度實

3、際上也就是車輛路徑問題 （Vehicle Routing Problem， 簡 稱 VRP） ，是 Dantzig 和 Ramse 80 于 1959 年提出來的，該問題被提出來之后， 很快就引起了運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論、網(wǎng)絡(luò)分析、物流學(xué)、管理學(xué)、 以及計算機科學(xué)等學(xué)科專家和運輸計劃制訂者的極大重視， 成為了運籌學(xué)和組合 優(yōu)化領(lǐng)域的前沿和研究熱點問題。 各學(xué)科專家對該問題進行了大量的理論研究及 實驗分析，取得了很大的進展。 車輛路徑問題是徑旅行商問題（Travel Salesman Problem，簡稱 TSP）衍生 而出的多路 TSP 問題，即為 K-TSP。VRP 的一般定義為

4、81 ：對一系列送貨點和 （或取貨點） ，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約 束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、 時間限制等） ，達到一定的目標(biāo)（如路程最短、費用最少、使用車輛數(shù)最少等） 。 見圖 1。 圖圖 1 1 車車輛輛路路徑徑問問題題示示意意圖圖 物流配送車輛路徑問題可以歸納為一般網(wǎng)絡(luò)模型： 設(shè) G(V,E,A)是一個連通 的混合網(wǎng)絡(luò)，V 是頂點集（表示物流中心、客戶、停車場等） ，E、A 分別為無向 的邊集和有向的弧集，E 中的邊和 A 中的弧均被賦權(quán)（可以表示配送的距離、時 間或費用） ，V1、E1、A1分別為 V 、E、

5、A 的子集，求滿足約束條件（包括客戶 的貨物需求或供應(yīng)數(shù)量約束、 需求或供應(yīng)時間約束、 配送車輛一次配送的最大行 駛距離約束、車輛的最大載重量約束等） ，并包含 V1、E1、A1的一些巡回路線， 使目標(biāo)函數(shù)取得優(yōu)化， 目標(biāo)函數(shù)可以取配送總里程最短、 配送車輛總噸位公里數(shù) 最少、配送總費用最低、配送時間最少、使用的配送車輛數(shù)最少、配送車輛的滿 載率最高等。 一、車輛路徑問題的分類車輛路徑問題的分類 1.車輛路徑問題的目標(biāo)函數(shù)和約束條件 (1) 目標(biāo)函數(shù) 對配送車輛路徑的問題，可以選用一個目標(biāo)，也可以選用多個目標(biāo)。經(jīng)常選 用的目標(biāo)函數(shù)有： 配送總里程最短 配送里程與配送車輛的耗油量、磨損程度以及司

6、機疲勞程度直接相關(guān)，它直 接決定運輸成本，對配送業(yè)務(wù)的經(jīng)濟效益有很大影響。 配送車輛的噸位公里數(shù)最小 該目標(biāo)將配送距離與車輛的載重量結(jié)合起來考慮， 即以所有配送車輛的噸位 數(shù)（最大載重量）與行駛距離乘積的總和最少為目標(biāo)。 綜合費用最低 降低綜合費用是實現(xiàn)配送業(yè)務(wù)經(jīng)濟效益的基本要求。 在配送中， 與取送貨物 有關(guān)的費用包括：車輛維護和行駛費用、車隊管理費用、貨物裝卸費用、相關(guān)工 作人員工資費用等。 準(zhǔn)時性最高 由于客戶對交貨時間有較嚴(yán)格的要求， 為提高配送服務(wù)質(zhì)量， 有時需要將準(zhǔn) 時性最高的作為確定配送路線的目標(biāo)。 運力利用最合理 該目標(biāo)要求使用較少的車輛完成配送任務(wù)， 并使車輛的滿載率最高，

7、以充分 利用車輛的裝載能力。 勞動消耗最低 即以司機人數(shù)最少，司機工作時間最短為目標(biāo)。 (2) 約束條件 配送車輛路徑問題應(yīng)滿足的約束條件主要包括： 滿足所有客戶對貨物品種、規(guī)格、數(shù)量的要求； 滿足客戶對貨物發(fā)到時間范圍的要求； 在允許通行的時間進行配送（如有時規(guī)定白天不能通行貨車等） ； 車輛在配送過程中的實際載重量不得超過車輛的最大允許載重量； 在配送中心現(xiàn)有運力范圍內(nèi)。 2. 車輛路徑問題的分類 現(xiàn)實中的物流配送車輛路徑問題是一個非常復(fù)雜的問題， 根據(jù)車輛路徑問題 的構(gòu)成要素將車輛路徑問題分為以下幾類 111 ： (1) 按配送中心的數(shù)目分 單配送中心問題，即只有一個配送中心； 多配送中

8、心問題，既有兩個或兩個以上的配送中心。 (2) 按車輛載貨狀況分 滿載問題，即客戶需求或供應(yīng)的貨物大于或等于車輛的載重量，完成一項 配送任務(wù)需要一輛或一輛以上的配送車輛，且配送車輛需要滿載運行； 非滿載問題，即客戶需求或供應(yīng)的貨物小于車輛的載重量，多項配送任務(wù) 可以用一輛配送車輛，且配送車輛常處于非滿載狀態(tài)； 混載問題，即滿載和非滿載混合問題。 (3) 按配送任務(wù)分 純送貨問題，即純卸貨問題，只考慮由配送中心向客戶送貨； 純?nèi)∝泦栴}，即純裝貨問題，只考慮將客戶供應(yīng)的貨物取到配送中心； 取送混合問題，即裝卸混合問題或集貨和送貨一體化問題。 (4) 按客戶對貨物?。ㄋ停r間的要求分 無時限問題，即

9、客戶對貨物的?。ㄋ停┑臅r間無具體要求； 有時限問題，又稱有時間窗問題，即客戶要求在規(guī)定的時間內(nèi)完成交易。 同時有時間窗問題又分為硬時間窗問題和軟時間窗問題， 硬時間窗問題即對客戶 的交易必須在規(guī)定的時間內(nèi)完成； 軟時間窗問題即對客戶的交易盡量在規(guī)定的時 間內(nèi)完成，否則對配送企業(yè)給予一定的懲罰。 (5) 按車輛類型分 單車型問題， 即所有配送車輛的載重量、 最大行駛里程及其他性能均相同； 多車型問題，即配送車輛的載重量、最大行駛里程及其他性能不相同。 (6)按車輛對車場的所屬關(guān)系分 開放式車輛路徑問題，即車輛完成任務(wù)后可以不返回其出發(fā)的車場； 封閉式車輛路徑問題，即車輛完成任務(wù)后必須返回其出發(fā)的

10、車場。 (7) 按優(yōu)化目標(biāo)分 單目標(biāo)問題，即僅考慮一個配送目標(biāo)； 多目標(biāo)問題，即同時考慮多個配送目標(biāo)。 二、車輛路徑問題的數(shù)學(xué)模型二、車輛路徑問題的數(shù)學(xué)模型 N i N j K k ijkijx c 111 min Z (3) s.t Qyq ki N i i 1 (, 2 , 1Kk) (4) 1 1 K k ki y (Ni, 2 , 1) (5) kj N i ijk yx 1 (kNj;, 2 , 1) (6) ki N j ijk yx 1 (kNi;, 2 , 1) (7) hk SiSj ijk yx ( kShVS,0) (8) 1 , 0 ijk x (kNji;, 2 ,

11、1,) (9) 1 , 0 ki y (kNi;, 2 , 1) (10) 式（1） 、 （2）表示變量約束；式（3）表示目標(biāo)函數(shù)為車輛行駛的最短距離 和； 式(4)表示分配給每一輛車的客戶需求量之和不大于車輛的最大裝載量； 式(5) 表示每個客戶只能由一輛車配送；式（6） 、 （7）表示兩個變量之間的約束關(guān)系； 式（8）表示為保證車輛 k 的行駛路線的連通性，避免出現(xiàn)與配送中心分離的路 線，它可以用支路消去約束代替，即 Sx SiSj ijk kNSNS; 12 , 2 , 1 多車場車輛路徑問題（MultiplyDepot Vehicle Routing Problem，簡稱 MDVRP）

12、是基本車輛路徑問題（Vehicle Routing Problem, 簡稱 VRP）的推廣， 指的是有多個車場同時對多個客戶送貨， 各客戶有一定的貨物需求， 每個車場都 可提供貨物， 并且由車隊負(fù)責(zé)執(zhí)行運輸任務(wù)， 要求對各客戶的車輛和行駛路線進 行適當(dāng)?shù)陌才牛诒ＷC滿足各客戶需求的前提下，使總的運輸成本最低。 多車場車輛路徑問題比單車場車輛路徑問題更具有一般性， 更接近于現(xiàn)實生 活，具有更廣泛的應(yīng)用背景。隨著現(xiàn)代商業(yè)的發(fā)展，許多大型的企業(yè)均建立了多 配送中心。 因此， 研究多車場車輛路徑問題對促進現(xiàn)代商業(yè)的發(fā)展有重要的意義。 多車場車輛路徑問題可描述為：有M個車場，各自擁有容量為Q的車 ),

13、2 , 1(MmKm輛，負(fù)責(zé)對N個客戶進行貨物分送工作；客戶i的貨物需求量 為 i q ，Qqi，客戶i和客戶 j 之間的運輸成本為), 2 , 1,(Njidij，每個客戶 可以由任意一個車場的車輛服務(wù)， 但只能由一輛車服務(wù)一次，每輛車完成任務(wù)后 必須返回原車場， 要求一合適的車輛調(diào)度方案， 使各車場的車輛能滿足所有客戶 的要求，并使車輛的總運輸成本最低。 設(shè)客戶的編碼為N, 2 , 1，車場編碼為MNNN, 2, 1，定義變量 0 1 mk ij x 否則 行駛到客戶從客戶的車輛車場jikm (11) 則多車場車輛路徑問題的數(shù)學(xué)模型為： mk ij MN i MN j M m K k ijx dZ m 1111 min (12) s.t m N j K k mk ij Kx m 11 MNNNmi, 2, 1, (13) 1 11 N j mk ji N j mk ij xx MNNNmi, 2, 1, m Kk, 2 , 1 (14) 1 111 MN j M m K k mk ij m x Ni, 2 , 1 (15) 1 111 MN i M m K k mk ij m x Nj, 2 , 1 (16) Qxq mk ij N i MN j i 11 MNNNm, 2, 1 m Kk, 2 , 1 (17) 0 11 MN Nj m