淺談物流配送中的車輛路徑問題

[摘 要] 本文通過分析物流在國民經(jīng)濟的重要地位，進而得出優(yōu)化物流的核心是配送中的車輛路徑問題，并對車輛路徑問題進行描述和分類，便于進一步對車輛路徑問題進行研究，從而優(yōu)化物流配送，提高國民經(jīng)濟水平。

[關(guān)鍵詞] 物流配送 車輛路徑問題

一、車輛路徑問題在物流配送中的地位

國民經(jīng)濟是一個不斷生產(chǎn)、消費、連續(xù)不斷的循環(huán)過程。一個企業(yè)的生產(chǎn)要不間斷的進行，一方面，必須按照生產(chǎn)所需的數(shù)量、質(zhì)量、品種、規(guī)格和時間不間斷的供給原材料、燃料、工具和設(shè)備等生產(chǎn)資料;另一方面，又必須把自己生產(chǎn)的產(chǎn)品供應(yīng)給其他企業(yè)。也就是說物流既是保證物質(zhì)資料不間斷的流入生產(chǎn)企業(yè)的條件，又是生產(chǎn)企業(yè)生產(chǎn)的產(chǎn)品不間斷的流向國民經(jīng)濟各部門的保證?？梢院敛豢鋸埖卣f，離開了物流，社會經(jīng)濟將會陷入嚴重癱瘓。

市場經(jīng)濟條件下，用于物流的費用支出已越來越大，越來越成為決定生產(chǎn)成本和流通成本高低的主要因素。一些發(fā)達國家，通過對各種產(chǎn)品物流費用及其在零售價格構(gòu)成中比重的分析，看到了物流中存在的巨大潛力。視為同人力、物力兩個利潤來源并列的“第三大利潤源”，“降低成本的最后邊界”。但是我國物流還是處于初級階段，其中最為突出的問題是物流成本高。據(jù)有關(guān)資料顯示，以商品零售價格為基數(shù)進行計算流通費用所占用的比例達59%。2006年中國物流總費用38414億元，占GDP總量的19.07%。過高的物流成本，制約了國民經(jīng)濟的發(fā)展，消弱了企業(yè)的市場競爭能力。

運輸費用占物流費用的比例超過50%，是影響物流總成本的重要因素，運輸?shù)暮侠斫M織可以歸結(jié)為車輛調(diào)度問題。而車輛調(diào)度問題的核心問題便是車輛路徑問題（Vehicle Routing Problem，簡稱VRP）。如何有效地利用各種運載工具（汽車、輪船、火車、飛機），采用何種線路（公路、水路、鐵路、航空），在滿足各種約束條件的情況下，將貨物及時有效地送達客戶手中便是車輛路徑問題需要研究的重點。

二、車輛路徑問題的描述

車輛路徑問題（Vehicle Routing Problem，簡稱VRP）這一名詞是由著名學(xué)者DANTZIG G和RAMSERJ在1959年發(fā)表的一篇論文中首先提出的。之后便引起運籌學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科技、計算機應(yīng)用等學(xué)科的專家及以運輸計劃制定者和管理者的普遍關(guān)注，并廣泛被借鑒應(yīng)用于生產(chǎn)生活，比如：郵政投遞問題、車輛調(diào)度問題、管道鋪設(shè)問題、計算機網(wǎng)絡(luò)拓撲問題等。

車輛路徑問題的一般描述：對一系列送貨點或取貨點，確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達到一定的目標(biāo)(如路程最短、費用最小、時間盡量少、使用車輛盡量少等)。參見左圖。

三、車輛路徑問題的構(gòu)成要素分析

從車輛路徑問題發(fā)展和研究來看，目前已知的模型中，車輛路徑問題主要是對以下幾個因素的一個或多個組合。

1.道路網(wǎng)。道路網(wǎng)是貨物運輸?shù)幕A(chǔ)，它是構(gòu)成車輛路徑問題的核心的要素之一。通常用從配送中心出發(fā)沿途依次經(jīng)過客戶點，最后返回配送中心所形成的網(wǎng)絡(luò)表示。

2.客戶點?？蛻酎c代表現(xiàn)實當(dāng)中的任意服務(wù)對象，通常具有以下屬性：需運送或收取的貨物量（貨物可能具有不同的種類）；客戶需求服務(wù)的時間段（又稱時間窗），比較典型的是客戶只在特定的時間段內(nèi)營業(yè)；確定性需求或不確定性需求；單需求計劃期或周期需求計劃期；客戶需求的優(yōu)先順序等。

3.配送中心。配送中心是每條車輛路線的起點或終點，車輛從配送中心對客戶點進行貨物配送或者從客戶點收集貨物到配送中心。在車輛路徑問題中，車場有單車場和多車場之分，在某些實際問題中，客戶點被事先按照配送中心進行劃分，此時整個VRP就可以分解為幾個獨立的VRP問題，每個問題都對應(yīng)一個不同的配送中心。

4.車輛。車輛路徑問題中，要完成從配送中心到客戶點的物流配送，離不開重要的交通工具，車輛是個泛稱，在現(xiàn)實生活中，車輛可以指汽車、輪船、火車、飛機等各種交通運輸工具，通常具有以下屬性：車輛的載重，容積限制；單車型或多車型，每型車輛數(shù)目的限制以及運輸范圍的限制，如有的交通網(wǎng)只能采用某種運輸工具；車輛行駛里程（或時間）的限制；車輛成本，如固定成本和可變成本，其中固定成本是車輛的使用年限折舊，可變成本是指單位運距（或時間）的費用。

5.運輸安排要求。在物流配送過程中，車輛行駛路線往往取決于所運送的貨物性質(zhì)、服務(wù)質(zhì)量水平、以及客戶和車輛的特點等，常見的有：客戶只能由一輛車服務(wù)、客戶可由多輛車服務(wù)；車輛須返回車場或不必返回車場；多車場時存在車輛是否返回同一車場的情況；每條線路上，相應(yīng)的車輛的當(dāng)前裝載量不能超過車輛的載重量；客戶只要求送貨，取貨，或送取貨兼有等。

6.目標(biāo)。根據(jù)實際研究的車輛路徑問題屬性特征的不同，從單目標(biāo)和多目標(biāo)分別加以考慮。

單目標(biāo):最小化總運輸費用，其大小取決于服務(wù)所有客戶所需要的車輛數(shù)、以及每輛車的固定成本和可變成本；最小化運輸距離完成任務(wù)所需的車輛最少；空載車總運行時間最少；總運輸時間最短；層次化優(yōu)化目標(biāo)函數(shù)，以車輛數(shù)作為首要的優(yōu)化目標(biāo)，在此基礎(chǔ)上優(yōu)化對應(yīng)的車輛旅行距離。

多目標(biāo):主要是指研究的車輛路徑問題需要同時優(yōu)化多個目標(biāo)函數(shù)，比如需要同時考慮最小化旅行距離、最小化駕駛員薪酬。以及最小化車輛數(shù)。實際配送管理中，許多車輛路徑問題均為多目標(biāo)情況下的決策優(yōu)化問題，將傳統(tǒng)的求解車輛路徑問題的現(xiàn)代啟發(fā)式算法拓展到求解多目標(biāo)車輛路徑問題則具有十分重要的意義。

參考文獻：

[1]Dantzig G，Ramser J.The truck dispatching problem[J].Managment Science，1959(6):80～91

[2]婁山佐:車輛路徑問題的建模及優(yōu)化算法研究[D].西北工業(yè)大學(xué)，2006

[3]李相勇:車輛路徑問題模型及算法研究[D].上海交通大學(xué)，2007