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

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

[關鍵詞] 物流配送 車輛路徑問題

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

國民經濟是一個不斷生產、消費、連續不斷的循環過程。一個企業的生產要不間斷的進行，一方面，必須按照生產所需的數量、質量、品種、規格和時間不間斷的供給原材料、燃料、工具和設備等生產資料;另一方面，又必須把自己生產的產品供應給其他企業。也就是說物流既是保證物質資料不間斷的流入生產企業的條件，又是生產企業生產的產品不間斷的流向國民經濟各部門的保證。可以毫不夸張地說，離開了物流，社會經濟將會陷入嚴重癱瘓。

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

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

二、車輛路徑問題的描述

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

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

三、車輛路徑問題的構成要素分析

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

1.道路網。道路網是貨物運輸的基礎，它是構成車輛路徑問題的核心的要素之一。通常用從配送中心出發沿途依次經過客戶點，最后返回配送中心所形成的網絡表示。

2.客戶點。客戶點代表現實當中的任意服務對象，通常具有以下屬性：需運送或收取的貨物量（貨物可能具有不同的種類）；客戶需求服務的時間段（又稱時間窗），比較典型的是客戶只在特定的時間段內營業；確定性需求或不確定性需求；單需求計劃期或周期需求計劃期；客戶需求的優先順序等。

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

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

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

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

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

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

參考文獻：

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

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

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