單車場大規模車輛路徑問題求解框架

摘 要:針對傳統優化技術在解決單車場大規模車輛路徑問題中存在的缺陷，對該類車輛路徑優化問題進行了描述和特點分析，提出 了一種解決問題的二階段的求解框架:將問題拆分為配送區域劃分和單車線路優化兩個步驟分別進行求解。研究成果能廣泛應用于卷煙、飲料等日用品的配送領域。

關鍵詞:物流配送;單車場大規模車輛路徑問題;旅行商為題;聚類

中圖分類號:U4

文獻標識碼:A

文章編號:1672-3198(2010)17-0365-02

1 提出問題

在許多物流配送系統中，管理者需要采取有效的配送策略以提高服務水平、降低貨運費用，其中車輛路徑問題(Vehicle Routing Problem of Single-depot，VRPOS)是亟待解決的一個重要問題。車輛路徑優化問題是組合優化數學中的一類經典問題，自1956年由Dantzig和Ramser提出以來，已經有大量的學者對該問題進行了深入的研究。目前對于小規模的VRP已經能夠較好的解決，對于100個結點以下的車輛路徑問題(VRP)甚至能夠得到精確解釋。而實際生活中的問題規模往往較大，與人們日常生活息息相關的一些領域，而這種單車場大規模車輛路徑問題(Large Scale VRPOS，LSVRPOS)在垃圾收集、牛奶收集和配送、飲料配送、香煙配送等日用品產業中普遍存在，其客戶規模一般都達到上萬個(客戶數量級為102~104)。在這種情況之下，現有理論、方法難以有效的解決實際問題。

VRP的求解難點體現在問題復雜度隨著問題規模的增大而呈指數增加，已有的各種求解方法的效率也隨著問題規模的增大而迅速降低，因此大幅削減求解問題的狀態空間成為求解LSVRPOS的關鍵。隨著物流的蓬勃發展，大規模的物流配送問題越來越多。這些大規模的物流系統是復雜的大系統，必須采用問題分解求解、然后再綜合的技術路線。因此將配送區域的客戶按照各種屬性進行聚類是降低LSVRPOS求解難度的有效手段。

針對問題的特點和傳統優化技術在此類問題中存在的缺陷，本文提出了一種解決LSVRPOS的一個二階段的求解框架:將問題拆分為配送區域劃分和單車線路優化兩個步驟分別進行求解——首先采用基于道路網絡的聚類方法對客戶進行配送區域的劃分，確定每一輛車的配送路徑;再采用旅行商問題求解方法對區域內車輛路徑進行優化。研究成果能廣泛應用于卷煙、飲料等日用品的配送領域。

2 單車場大規模車輛路徑問題描述

一般的單車場車輛路徑問題描述為:從物流中心用多輛運輸車向多個顧客送貨，車輛從物流配送中心出發，每個顧客的位置和需求量確定，配送車輛的載重量一定，途經所有要貨的網點并進行卸貨服務，最后又回到物流配送中心，要求合理安排車輛配送路線，使車輛行駛總里程最短，并滿足以下約束條件:①每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量;②每個客戶的需求必須滿足，且只能由一輛車送貨。求解VRPOS的算法有精確算法和啟發式算法。由于VRPOS是NP難題，精確算法只能計算規模不大的物流問題(顧客數量一般在50~100以內)。

本文的大規模是指顧客數量比較大，在目前的計算水平下，必須使用啟發式算法的車輛路徑問題。且本文研究的LSVRPOS可以歸納為具有以下特點的VRP:(1)為靜態和確定型問題;(2)單一車型;(3)只有一個中心停車場;(4)客戶規模非常大，一般為102~104數量級，而且分布密集;(5)路線對稱;(6)客戶需求是確定并預先知道的，且不可分割;(7)只進行配送或收集，二者不同時進行;(8)配送物品種類單一，不考慮兼容性;(9)車輛有載重或容積約束;(10)車輛每天的工作時間不超過預定的最長工作時間;(11)路線優化的目標是使總成本最低。另外，大多數配送和收集企業出于增進客戶關系、方便調度以及讓司機更好地熟悉交通線路情況的考慮，一般要求車輛和其路線相對固定，即工作人員總對同一地域的客戶進行服務。

3 求解框架

針對該類問題約束條件的特點，本文總體上借鑒了“先聚類后排序(cluster-first，route-second)”算法。該算法的中心思想是將問題分解成一個分派問題和一個旅行商問題。將客戶分派到每一輛車，分派做出后，每輛車類似旅行商一樣為分派給它的客戶服務，以路線的費用最小化為目標，通過應用一些旅行商問題的啟發式算法或精確優化算法來得到每輛車的行車路線。這種方法恰好可以很好地滿足客戶和車輛具有固定服務關系的要求，分派完成后一輛車可以固定地為其線路上的客戶服務。

因此，本文提出的求解框架如下:首先，為了降低問題規模，借助基于道路網絡的聚類方法對大規模的密集客戶進行了區域劃分;然后通過求解旅行商問題得到問題的近優解。

3.1 區域劃分

本文提出了一種基于網絡邊的聚類:

基于網絡邊的聚類屬于空間聚類算法，它是以道路網絡結點為指引，通過遍歷網絡圖中所有邊實現對象聚類的過程，直至超出聚類限定規模為止。在實際生活當中，客戶網點往往數量巨大且分布密集，因此一般的配送路徑規劃總是先將位置相近的客戶由同一輛車配送，這種配送安排包含了最基本的聚類思想。

基于網絡邊的聚類過程分為三個階段:初始化階段、分裂階段和合并階段。

(1)初始化階段(initiation phase):遍歷網絡圖中所有邊，同一邊上所有對象指定到同一個聚類中，形成初始聚類，而且初始聚類個數等于網絡邊的個數。此步驟能夠過濾掉不必遍歷的網絡邊，減少網絡搜索范圍。 

(2)分裂階段(splitting phase):遍歷各初始聚類，判斷每條網絡邊上相鄰對象間距離是否小于等于閾值 。 若對象間距離大于閾值 ，則在此處將聚類分開，最終將初始聚類劃分成若干聚類塊，并保證每個聚類塊的配送工作量 不超過其配送量尺度 。

(3)合并階段(merging phase):

Step 1:首先遍歷各網絡邊上的聚類塊，計算每個聚類塊的有效結點，然后將聚類塊按照其所屬的有效結點歸類，對每組聚類塊按照其到有效結點的距離遠近程度排序，將距離初始有效結點最近的聚類塊設為初始聚類。

Step 2:按照排序依次遍歷初始有效結點的所有相關聚類塊來擴展初始聚類，當達到預定的工作量時停止擴展。若否，則轉至Step 3。

Step 3:若一個有效結點的所有相關聚類塊全部歸為一類后仍然滿足預定工作量，則聚類向下一個有效結點擴展，直至不滿足預定工作量為止，轉至Step 4。

Step 4:按順序遍歷剩下的有效結點，重復以上三個步驟，直至聚類完成。

3.2 車輛路徑的優化

在客戶進行完區域劃分后，車輛的固定服務區域就確定下來。每個服務區域應該是一些相互臨近的街區，區域內的客戶具有很好的道路連通性和服務連續性。車輛的路線問題就成為一個純粹的旅行商問題(Traveling Salesman Problem，TSP)。TSP是一個NP-Hard問題，由于它在許多領域中都有著廣泛的應用，因而對其研究一直沒有停止，求解算法基本上可以分為精確算法和啟發式算法兩大類。盡管已有一些求TSP精確解的方法，如動態規劃、分支界定法等，但其算法所能求解的TSP問題規模有限，因此在實際應用中主要用啟發式算法來求解TSP問題，啟發式算法被證明是一類用較少計算量可求出較好質量近似解的一類有效方法。其主要算法有遺傳算法、進化算法、模擬退火法，以及為了提高算法的效率，將局部優化方法與傳統算法進行結合的諸如混合進化算法、混合遺傳算法等。

4 結論

針對問題的特點和傳統優化技術在此類問題中存在的缺陷，本文提出了一種解決LSVRPOS的一個二階段的求解框架:將問題拆分為配送區域劃分和單車線路優化兩個步驟分別進行求解——首先采用基于道路網絡的聚類方法對客戶進行配送區域的劃分，確定每一輛車的配送路徑;再采用旅行商問題求解方法對區域內車輛路徑進行優化。研究成果能廣泛應用于卷煙、飲料等日用品的配送領域。

參考文獻

[1]Paolo T，Daniele V.Models relaxations and exact approaches for the capacitated vehicle routing problem [J].Discrete Applied Mathematics，2002，123:487-512.

[2]Paolo T，Daniele V.Models，relaxations and exact approaches for the capacitated vehicle routing problem [J].Discrete Applied Mathematics，2002，123:487-512.

[3]Yiu M L，Mamoulis N.Clustering objects on a spatial network[C].SIGMOD Conference，2004:443-454.

[4]陳繼東，孟小峰，賴彩鳳.基于道路網絡的對象聚類[J].軟件學報，2007，18(2):332-344.

[5]史亞蓉，萬迪昉，李雙燕，等.基于GIS的物流配送線路規劃研究[J].系統工程理論與實踐，2009，29(10):76-84.

[6]郎茂祥.基于遺傳算法的物流配送路徑優化問題研究[J].中國公路學報，2002，15(3):76-79.

[7]Jung S，Moon B R.Toward minimal restriction of genetic coding and crossovers for the 2-D eunclidean TSP [J].IEEE Transaction on Evolutionary Computation，2002，6(6):557-565.

[8]Huai-Kuang Tsai，Jinn-Moon Yang，et al.An evolutionary algorithm for large traveling salesman problems [J].IEEE Transactions on Systems，Man，and Cybernetics，2004，34(4):1718-1729.

[9]Kirkpatrick S，Gelatt CD，Vecchi M P.Optimization by simulated annealing [J] .Science.1983，220(4598):671-680.