有時間窗車輛路徑問題（vehicle routing problems with time windows，VRPTW）車輛路線問題（VRP）最早是由Dantzig和Ramser於1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，並能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。
基本介紹
- 中文名：有時間窗車輛路徑問題
- 外文名：vehicle routing problems with time windows，VRPTW
- 提出時間：1959年
- 提出者：Dantzig和Ramser
- 主要作用：最佳化配送路線
- 目的：路程最短、成本最小、耗費時間少
理論依據,求解方法,分枝界限法,途程建構啟發,途程改善啟發,合成啟發,依據最佳化,通用啟發,
理論依據
由於VRP問題的持續發展，考慮需求點對於車輛到達的時間有所要求之下，在車輛途程問題之中加入時窗的限制，便成為有時間窗車輛路徑問題（VRP with Time Windows, VRPTW）。有時間窗車輛路徑問題（VRPTW）是在VRP上加上了客戶的被訪問的時間窗約束。在VRPTW問題中，除了行駛成本之外, 成本函式還要包括由於早到某個客戶而引起的等待時間和客戶需要的服務時間。
在VRPTW中，車輛除了要滿足VRP問題的限制之外，還必須要滿足需求點的時窗限制，而需求點的時窗限制可以分為兩種，一種是硬時窗（Hard Time Window），硬時窗要求車輛必須要在時窗內到達，早到必須等待，而遲到則拒收；另一種是軟時窗（Soft Time Window），不一定要在時窗內到達，但是在時窗之外到達必須要處罰，以處罰替代等待與拒收是軟時窗與硬時窗最大的不同。
Bodin和Solomon分別對VRP及其變形問題和VRPTW問題作了較詳細的綜述。生產實際中許多問題都可以歸結為VRPTW來處理, 如鋼鐵廠編制熱軋帶鋼軋制計畫問題實際上就是一個VRPTW問題。一些服務性行業中也普遍存在這樣的問題, 如郵政投遞，飛機、火車及公共汽車的調度等。自從Savelsbergh證明了VRPTW是一個NP難問題之後, 對其算法的研究就主要集中到各種啟發式算法上。遺傳算法、禁忌搜尋法和模擬退火法等智慧型化啟發式算法的出現為求解VRPTW問題提供了新的工具。Thangiah和Joe都曾套用遺傳算法求解VRPTW問題, 前者的目標是使總的服務成本最小, 而後者的目標有兩個, 首先是使用最少的車輛, 其次是在使用最少車輛的前提下使總成本最小。
求解方法
含時窗限制之車輛途程問題（VRPTW）相對於車輛途程問題（VRP），必須額外考慮到運送時間與時間視窗，其主要的原因來自顧客有服務時間的最後期限和最早開始服務時間的限制。故在此限制條件之下，原本VRP問題除了空間方面的路徑（Routing）考慮之外，還必須要加上時間上的排程（Scheduling）考慮。同時由於場站也有時間窗的限制，也間接造成路徑長度的限制，由此可知VRPTW的總巡行成本不僅包含運送成本，還需要考慮時間成本，以及未在時間窗限制內送達的處罰成本。因此，若要得到一個好的解答，時間和空間（Temporal andSpatial）問題的探討是非常重要的。
由於VRPTW比VRP問題多考慮了一樣時窗的因素，因此在解法上較VRP問題更為複雜，而根據Taillard（1997）等人的分類，求解VRPTW的方法可以分為六種，分述如下。
分枝界限法
以分枝界限法求算之精確解法（Exact Algorithm Based on Branch-and-BoundTechniques）：Kolen（1987）利用這種方式可以求得精確解，但是只能解決六至十五個節點的問題，因此求解的範圍過小，僅適用於小型問題。
途程建構啟發
途程建構啟發式算法（Route Construction Heuristics）：在一問題中，以某節點選擇原則或是路線安排原則，將需求點一一納入途程路線的解法。如Soloman（1987）的循序建構法（Sequential Insertion Heuristics）。
途程改善啟發
途程改善啟發式算法（Route Improvement Heuristics）：先決定一個可行途程，也就是一個起始解，之後對這個起始解一直做改善，直到不能改善為止。而常見的是節線交換法（Edge Exchange Procedure），如Lin（1965）所提出的K-Optimal，以及Potvin與Rousseau（1993）提出一考慮旅行方向的交換算法。
合成啟發
合成啟發式算法（Composite Heuristics）：此種解法混合了途程建構啟發式算法與途程改善啟發式算法，如Russell（1995）所提出的Hybrid Heuristics便是混合了Potvin與Rousseau（1993）所提出的平行插入法，並在之中加入路線改善法的合成啟發式算法；Roberto(2000)也提出的屬於平行插入法與內部交換改善法的合成啟發式解法來求解VRPTW的問題。
依據最佳化
依據最佳化之啟發式算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整數規劃模組，再透過啟發式算法，將原始問題分解成指派/分群的子問題的一系列的巡行以及排程問題。
通用啟發
通用啟發式算法（Metaheuristics）：傳統區域搜尋方法的最佳解常因起始解的特性或搜尋方法的限制，而只能獲得局部最佳解，為了改善此一缺點，近年來在此領域有重大發展，是新一代的啟發式解法，包含禁忌法（Tabu Search）、模擬退火法（Simulated Annealing）、遺傳算法（Genetic Algorithm）和門坎接受法（Threshold Accepting）等，可以有效解決局部最佳化的困擾。如Potvin（1996）等人、Taillard（1997）等人均利用Tabu Search的方式來求解VRPTW的問題。
