有時間窗車輛路徑問題
出自 MBA智库百科(https://wiki.mbalib.com/)
有時間窗車輛路徑問題（vehicle routing problems with time windows，VRPTW）
目錄 |
車輛路線問題（VRP）最早是由Dantzig和Ramser於1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，並能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的[1]。
由於VRP問題的持續發展，考慮需求點對於車輛到達的時間有所要求之下，在車輛途程問題之中加入時窗的限制，便成為有時間窗車輛路徑問題（VRP with Time Windows, VRPTW）[2]。有時間窗車輛路徑問題（VRPTW）是在VRP上加上了客戶的被訪問的時間窗約束。在VRPTW問題中，除了行駛成本之外, 成本函數還要包括由於早到某個客戶而引起的等待時間和客戶需要的服務時間[3]。
在VRPTW中，車輛除了要滿足VRP問題的限制之外，還必須要滿足需求點的時窗限制，而需求點的時窗限制可以分為兩種，一種是硬時窗（Hard Time Window），硬時窗要求車輛必須要在時窗內到達，早到必須等待，而遲到則拒收；另一種是軟時窗（Soft Time Window），不一定要在時窗內到達，但是在時窗之外到達必須要處罰，以處罰替代等待與拒收是軟時窗與硬時窗最大的不同[2]。
Bodin[4]和Solomon[5]分別對VRP及其變形問題和VRPTW問題作了較詳細的綜述。生產實際中許多問題都可以歸結為VRPTW來處理, 如鋼鐵廠編製熱軋帶鋼軋制計劃問題實際上就是一個VRPTW問題。一些服務性行業中也普遍存在這樣的問題, 如郵政投遞，飛機、火車及公車的調度等。自從Savelsbergh[6]證明瞭VRPTW是一個NP難問題之後, 對其演算法的研究就主要集中到各種啟髮式演算法上。遺傳演算法、禁忌搜索法和模擬退火法等智能化啟髮式演算法的出現為求解VRPTW問題提供了新的工具。Thangiah[7]和Joe[8]都曾應用遺傳演算法求解VRPTW問題, 前者的目標是使總的服務成本最小, 而後者的目標有兩個, 首先是使用最少的車輛, 其次是在使用最少車輛的前提下使總成本最小[3]。
時間窗車輛路徑問題的求解方法[2]
含時窗限制之車輛途程問題（VRPTW）相對於車輛途程問題（VRP），必須額外考慮到運送時間與時間視窗，其主要的原因來自顧客有服務時間的最後期限和最早開始服務時間的限制。故在此限制條件之下，原本VRP問題除了空間方面的路徑（Routing）考慮之外，還必須要加上時間上的排程（Scheduling）考慮，同時由於場站也有時間窗的限制，也間接造成路徑長度的限制，由此可知VRPTW的總巡行成本不僅包含運送成本，還需要考慮時間成本，以及未在時間窗限制內送達的處罰成本。因此，若要得到一個好的解答，時間和空間（Temporal andSpatial）問題的探討是非常重要的。
由於VRPTW比VRP問題多考慮了一樣時窗的因素，因此在解法上較VRP問題更為複雜，而根據Taillard（1997）等人的分類，求解VRPTW的方法可以分為六種，分述如下。
1、以分枝界限法求算之精確解法（Exact Algorithm Based on Branch-and-BoundTechniques）：Kolen（1987）利用這種方式可以求得精確解，但是只能解決六至十五個節點的問題，因此求解的範圍過小，僅適用於小型問題。
2、途程建構啟髮式演算法（Route Construction Heuristics）：在一問題中，以某節點選擇原則或是路線安排原則，將需求點一一納入途程路線的解法。如Soloman（1987）的循序建構法（Sequential Insertion Heuristics）。
3、途程改善啟髮式演算法（Route Improvement Heuristics）：先決定一個可行途程，也就是一個起始解，之後對這個起始解一直做改善，直到不能改善為止。而常見的是節線交換法（Edge Exchange Procedure），如Lin（1965）所提出的K-Optimal，以及Potvin與Rousseau（1993）提出一考慮旅行方向的交換演算法。
4、合成啟髮式演算法（Composite Heuristics）：此種解法混合了途程建構啟髮式演算法與途程改善啟髮式演算法，如Russell（1995）所提出的Hybrid Heuristics便是混合了Potvin與Rousseau（1993）所提出的平行插入法，併在之中加入路線改善法的合成啟髮式演算法；Roberto(2000)也提出的屬於平行插入法與內部交換改善法的合成啟髮式解法來求解VRPTW的問題。
5、依據最佳化之啟髮式演算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整數規劃模塊，再透過啟髮式演算法，將原始問題分解成指派/分群的子問題的一系列的巡行以及排程問題。
6、通用啟髮式演算法（Metaheuristics）：傳統區域搜尋方法的最佳解常因起始解的特性或搜尋方法的限制，而只能獲得局部最佳解，為了改善此一缺點，近年來在此領域有重大發展，是新一代的啟髮式解法，包含禁忌法（Tabu Search）、模擬退火法（Simulated Annealing）、遺傳演算法（Genetic Algorithm）和門坎接受法（Threshold Accepting）等，可以有效解決局部最佳化的困擾。如Potvin（1996）等人、Taillard（1997）等人均利用Tabu Search的方式來求解VRPTW的問題。
- ↑ Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Industrial and Applied Mathematics philadephia.2002
- ↑ 2.0 2.1 2.2 鄧宇佑(碩士).求解醫院運輸部門運輸中心個數最佳化之研究(D).成功大學工業管理研究所碩士論文，1991年
- ↑ 3.0 3.1 李大衛,王莉,王夢光.遺傳演算法在有時間窗車輛路徑問題上的應用[J].系統工程理論與實踐,1999,(8):65～69
- ↑ Bodin L, Golden B,A ssad A and Ball M. Routing and Scheduling of Vehicles and Crews: The State of the Arts. Computers & Operations Research, 1983, 10: 62～ 212
- ↑ Solomon M , Desrosiers J. Time Window Constrained Routing and Scheduling Problems :A Survey. Trans sportation Science, 1988, 22 (1): 1～11
- ↑ Savelsbergh M. Local Search for Routing Problems with Time Windows. Annals of Operations Research ,1985, 4: 285～305
- ↑ Thangiah S,Nygard K and Juell P. Gideon. A Genetic Algorithm System for Vehicle Routing with Time Windows. Proceedings of the Seventh Conference on Artificial Intelligence Applications ,Miami, Florida, 1991: 322～325
- ↑ Joe L.and Roger L. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms. Proceedings of the Fifth International Conference on Genetic Algorithms,1993,452～459
