帶時間窗車輛路徑問題的最優解

[摘要] 帶時間窗的車輛調度問題是物流配送系統的關鍵之關鍵，對它的研究越來越重視。本文將建立物流管理中的帶時間窗車輛路徑問題的模型，并得到此模型的最優解，有一定的實用意義。

[關鍵詞] 帶時間窗車輛路徑問題物流管理組合優化

一、提出問題

在許多物流配送系統中，管理者需要采取有效的配送策略以提高服務水平、降低貨運費用。其中車輛路徑問題是亟待解決的一個重要問題，此問題可描述如下：有一個貨物需求點（或稱顧客），已知每個需求點的需求量及地理位置，至多用K輛汽車從中心倉庫（或配送中心）到達這批需求點，每輛汽車載重量一定，安排汽車路線使運輸距離最短并且滿足每條線路不超過汽車載重量和每個需求點的需求量且必須只能用一輛汽車來滿足。帶時間窗車輛路徑問題（VRPTW， vehicle routing problem with time windows）是在車輛路徑問題中加入了客戶要求訪問的時間窗口，由于在現實生活中許多問題都可以歸結為VRPTW來處理，但處理的好壞將直接影響到一個企業的效益和顧客的服務質量，所以對它的研究越來越受到人們的重視，目前對它的求解主要集中在啟發式算法上。

20世紀90年代后，遺傳算法、禁忌搜索算法、模擬退火算法、人工神經網絡算法和動態蟻群算法等啟發式算法的出現，為求解VRPTW提供了新的工具。但是，遺傳算法存在“早熟性收斂”問題，禁忌搜索算法、人工神經網絡算法也存在一些不盡人意的地方，如何針對VRPTW的特點，構造簡單、尋優性能優異的啟發式算法，這不僅對于物流配送系統而且對于許多可轉化為VRPTW求解的優化組合問題均具有十分重要的意義。實際數據表明動態蟻群算法行之有效，不失為一種求解VRPTW的性能優越的啟發式算法。

二、問題描述

VRPTW可以描述如下：給定車輛集合V，需求點集合C和有向圖 G。此有向圖有|C|+2個頂點，頂點1，2，K，n表示需求點，頂點0表示離開時的中心倉庫，頂點n+1表示返回時的中心倉庫，把頂點0，1，2，3，K，n+1記作集合N。需求點之間及需求點與中心倉庫之間的弧記作集合A，并且沒有弧開始于n+1點，也沒有弧中止于0頂點，每條弧(i，j)對應一個物耗值cij和一個時間值tij。每輛車有一個載貨量q，每個需求點有一個需求dj和一個時間窗口[ai，bi]，這個時間窗口說明車輛必須在bi之前到達需求點i，在ai之前車輛雖然可以到達需求點i，但是車輛必須等待而不可以馬上為需求點提供服務。中心倉庫也有一個時間窗口[a0，b0]，這個時間窗口說明車輛在a0之前不能離開中心倉庫，并且在b0或之前返回中心倉庫。在這里，假設q、ai、bi、di和cij均為非負整數，tij是正整數。

對于每條弧(i，j)(i≠j，i≠n+1，j≠0)和車輛k定義變量xijk:如果車輛k沒有從節點i到達節點j，則xijk=0;如果車輛k從節點 i到達節點j，則xijk=1。

對于每個需求點i和車輛k定義變量sik，它表示車輛k在sik開始對需求點i進行訪問，如果車輛k不訪問需求點i，則sik不表示任何意義。假設a0=0，這樣對于所有的車輛k，s0k=0。對于每輛車，設計一條費用最小的路徑，此路徑開始于頂點0，終止于頂點 n+1，同時還要保證每個需求點僅被訪問一次，但是不能違背各時間窗口和車輛的載貨量的限制。

三、建立模型

根據上述描述，VRPTW的數學模型可以表示為：

在上述表達式中，約束條件式（2）表達了每個需求點僅能被訪問一次;約束條件式（3）表達了被調用的車輛都滿足能力約束條件;約束條件式(4）和約束條件式(5)保證了每輛汽車始于中心倉庫，訪問需求點后，最終回到中心倉庫;約束條件式(7)表達了車輛k在從i需求點向j需求點行駛的過程中，在sij+tij之前不能到達需求點j，其中k是一個比較大的標量;約束條件式(8)表達了在車輛的行駛過程中，要滿足時間窗的約束;約束條件式(9)是整數化的約束。

這個模型的通用性很強，經過參數的不同設定，可以將其轉換為其他組合優化問題的數學模型。如果設 ai=0，bi=M(M是一個很大的數），則可以把時間約束式(7)去掉，這樣，VRPTW模型就轉化為普通的車輛路徑問題模型；如果僅有一輛車被利用，則該問題轉化為了旅行商問題；如果有多輛車被利用，并且附加條件c0j=1，j∈C和cij=0，就得到了裝箱問題的數學模型。如果去掉約束條件式（2），則該模型變成了基本的有時間窗和能力約束的最短路徑問題，由于所有的車輛均相同，所以每輛車的最短路徑也是相同的。

四、 數值計算結果

有8個分店和一個配送中心，各分店的需求量為dij(i=1，2，K，8)(t)裝貨(卸貨)時間Ti(h)以及分店要求的服務時間范圍[ai，bi]由(表1)給出。這些分店由容量為8t的車輛完成配送，配送中心與各分店的距離(km)由(表2)給出。要求合理安排車輛的行駛路線，使總的運距最短。

計算結果見(表3)，可見，運用動態蟻群算法求解的結果優于節約算法、分派算法和遺傳算法，不失為一個較優化的滿意解。

五、結束語

車輛路徑問題已經被廣泛的應用到生產、生活的各個方面，如報紙投遞及線路的優化及線路設計、垃圾車的線路優化及垃圾站選址優化等等。目前，研究水平已有很大發展，其理論成果除在汽車運輸領域外，在水運、航運、電力、工業管理也有一定的應用，還用于輪船公司運送貨物經過港口與貨物安排的優化設計、交通車路線安排、多種組合優化問題中。車輛路徑問題是物流配送優化中關鍵的一環，也是電子商務活動中不可缺少的內容。對貨運車輛進行優化調度，可以提高物流經濟效益、實現物流科學化。對貨運車輛優化調度理論與方法進行系統研究是物流集約化發展、建立現代調度指揮系統、發展智能交通運輸系統和開展電子商務的基礎。