兩階段啟發式算法在帶時間窗的車輛路徑問題中的應用

[摘要] 對帶時間窗約束的物流配送車輛路徑問題，構造了一種兩階段啟發式算法。算法第一階段采用k-means算法將客戶聚類分群，算法第二階段對每一客戶子類采用禁忌搜索算法優化車輛路徑。仿真實驗結果表明，該算法是有效的。

[關鍵詞] k-均值 禁忌搜索算法 車輛路徑問題

車輛路徑問題（Vehicle Routing Problem， VRP）已被證明是NP-hard問題，隨著客戶數量的增加，可選的車輛路徑方案數量呈指數級增長。隨著生活水平的提高，企業越來越重視客戶對貨物送貨時間的要求，因此必須考慮車輛路徑問題達到配送最快且運輸成本最小的目標，以滿足消費者的需求，研究有時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows， VRPTW）具有十分重要的現實意義。

Solomon和Desrosiers等人（1987）最早對帶時間窗約束的車輛路徑問題進行了研究，Desrochers(1988)進一步對求解帶時間窗的車輛路徑問題的各種優化方法做了總結概括。謝秉磊、李軍研究過有時間窗車輛路徑問題，蔡延光、郎茂祥等曾用禁忌搜索算法求解車輛路徑問題。本文構造了求解有時間窗車輛路徑問題的兩階段啟發式算法，根據客戶分布情況將距離相近的客戶分配在同一輛車中配送，可得到一初始可行解，然后采用禁忌搜索算法優化車輛路徑，進一步求得最佳解。

一、問題描述及模型建立

有時間窗的車輛路徑問題可描述為：從某物流中心用多臺配送車輛向多個客戶送貨，每個客戶的位置和需求量一定，將貨物送到的時間窗一定，每臺配送車輛的載重量一定，其一次配送的最大行駛距離一定，要求合理安排車輛配送路線和行車時間，使目標函數最優。

設物流配送中心有m輛容量為q的車輛，以物流配送中心的位置作為原點0，現有貨物運輸任務，以1，2，…n表示，已知任務i的貨運量為，且，每輛車從物流中心出發，經過一系列客戶點送貨，最終回到物流中心。規定每個客戶點的任務只能由一輛車完成，求以總費用最小化為目標的車輛行駛路線。

車輛優化模型可表述為：

Z為目標函數使總費用最小。約束(1)是車輛的容量限制；約束(2)每個顧客只有一輛車為其服務；約束(3)和(4)表示兩個變量之間的關系；約束(5)和(6)為變量的取值約束。

決策變量表示車輛k是否從需求點（或配送中心）i行駛到點j，若是則為1，否則為0；表示點i的任務是否由車輛k完成，是則為1，否則為0。參數表示為從點i 到點j 的運輸成本，可以是距離、費用、時間等，本文含義為距離。表示車輛到達任務點i的時間，表示在之前到達任務點i的單位時間等待成本，表示在之后到達任務點i的單位時間懲罰成本。

二、VRPTW問題的求解算法

考慮到在安排車輛路徑的時候總是傾向于就近服務的原則，在求解VRP問題時，可先將客戶分群，然后對每個客戶群采用禁忌搜索算法求解。這樣不僅可讓車輛訪問的總距離較小，而且使搜索時間縮短，從而優化目標函數。

1.聚類分析

聚類分析的基本思想是研究樣品或指標（變量）之間存在程度不同的相似性。根據一批樣品的多個觀測指標，具體找出一些能夠度量樣品或指標之間相似程度的統計量，把一些相似程度較大的樣品（或指標）聚合為一類，把另外一些彼此之間相似程度較大的樣品（或指標）又聚合為另一類，直到把所有的樣品（或指標）聚合完畢。

聚類分析中，最基本的方法就是k-均值法。k-均值算法常采用誤差平方和準則函數作為聚類準則函數，誤差平方和準則函數定義為：

其中第k個聚類可以用集合來表示，假設包含個客戶點｛｝，此聚類中心為，其中是屬于第k個聚類的客戶點，E為k個聚類的誤差平方和。

2.禁忌搜索算法

禁忌搜索算法是近年來由局部鄰域搜索擴展而來的一種全局逐步尋優算法， 通過模擬人的記憶過程， 達到整體尋優的效果。通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過特赦準則來赦免一些被禁忌的優良狀態，進行多樣化的有效搜索以最終實現全局優化。

具體實現技術如下：

（1)初始解的構造

本文引入了一種自然數編碼的解的表示方法，即0表示車場，其余的自然數來表示各個送貨點，這樣就可以得到一串自然數編碼，這串自然數編碼代表了送貨的路徑。例如0-4-5-2-0-1-3-0，表示第一條路徑是從車場出發，到4、5、2送貨后返回車場；第二條路徑是從車場出發，到1、3送貨后返回車場。

由于禁忌搜索算法對初始解有較強的依賴性，好的初始解可使禁忌搜索算法在解空間中搜索到好的解，而較差的初始解則會降低禁忌搜索的收斂速度，因此本文采用了將聚類結果作為禁忌搜索算法的初始解。

（2）鄰域的搜索

鄰域搜索采用2交換（2-opt）產生，每變換一次，重新根據容量約束分配車場。例如路徑0-4-5-2-0-1-3-0，如果選擇5和1進行變換，則變換后的路徑為：0-4-1-2-0-5-3-0，如果1送貨點的貨物比較多，根據容量約束條件分配車場后路線最終變為:0-4-1-0-2-5-3-0。所以路徑的產生需要根據車輛容量的限制進行調整，同時還需要根據車輛的容量限制調整車輛的運行和配車的數目。

（3）禁忌表的處理

針對當前解，每搜索完一次鄰域，都要對鄰域解進行禁忌表處理，在當前解的鄰域中確定若干路徑，按路徑總路程從小到大依次排列于一個數組中。若最優候選解對應的目標值優于當前路徑的最佳狀態，則忽視其禁忌特性，用其替代當前解和最優解，并將這條路徑加入禁忌表，同時把禁忌對象的任期都加1；若不存在優于最佳當前路徑的解，則在候選解中選擇非禁忌的最佳狀態為新的當前解。

（4）其他參數設置

本文采用目標函數值作為適配值函數，迭代指定步數為終止準則。

3.算法具體流程

Step1：讀入車輛調度問題的原始數據：客戶節點數目N、各節點的貨運量，輸入客戶X、Y坐標值。

Step2：計算此問題至少需要的車輛數m，m等于所有客戶的需求量之和除以車容量（取整）。

Step3：分群，直到所有客戶點被分完為止。

Step4：檢查各客戶群內總需求量是否超出車容量限制。若是，執行Step5；否則執行Step9。

Step5：將最晚服務的客戶剔除，直到符合容量限制。

Step6：檢查是否有其他客戶群有多余的車容量。若是，執行Step7，否則，執行Step8。

Step7：將剔除的用戶加入距離最近且加入后不違反車容量限制的客戶群，并執行Step9。

Step8：加派一輛車服務（m=m+1），回到Step3。

Step9：分群完成，得到一串自然數編碼，將其作為禁忌搜索算法的初始解。

Step10:令最優解xbest=x，其中x是通過聚類算法得到的初始解。

Step11:構造鄰域結構，得到鄰域中的最優解y。

Step12:判斷目標函數F(y)和F(x)的關系，若F(y)

Step13:若F(y)

Step14:判斷是否滿足終止條件，若滿足則結束，輸出結果；若不滿足，重新更新禁忌表并返回step11，重新循環。

三、仿真實例分析

本文采用Solomon提供的標準測試問題進行計算結果驗證。因為Solomon算例中C101中的送貨點具有較好的聚類特性，所以選擇在C101送貨點上進行一次聚類算法的實驗。

輸入客戶在坐標平面上所在的位置坐標及客戶需求量，分群數以問題中客戶需求量之和與單車最大容量的商取整值，得到最佳分群數為10。實驗得到分群結果如圖所示。具體每次分類包含的客戶點，見表1。

C101類點聚類成10個客戶群的情形圖

表1 分類結果包含的客戶點情況

分群后，發現每群客戶無時間沖突。利用上述分群結果在每個群內隨機產生一串自然數編碼，然后在這10個群上進行禁忌搜索。對這10個群進行禁忌搜索時設迭代步數為50，禁忌表長度為5。通過20次隨機實驗，最后得到實驗結果：車輛數為10，總里程828.94。經過實驗計算的路線，見表2。

表2 實驗結果

四、結語

本文構造的由聚類算法與禁忌搜索算法相結合的算法，是一種兩階段的啟發式算法結構。相比隨機產生初始解，利用聚類算法產生的初始解能較好的利用送貨點分布信息，在此基礎上利用禁忌搜索算法能有效地提高搜索效率，同時聚類可將原先規模比較大的VRP問題分解成一個相對小規模的VRP問題，降低了算法的復雜性。但是當客戶點地理位置較分散時，如何將客戶點的其他約束信息，如時間窗等應用到聚類中來，提前處理某些約束，將是一個值得進一步探討的問題。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。