近年來資訊與通訊科技的快速發展，例如地理資訊系統、全球定位系統以及智慧型運輸系統，可以快速地處理大量的資料，提供即時的資訊，使得營運者能對車隊作即時的控制與管理，在這樣環境背景下，國內外研究逐漸以時間的概念引入傳統的車輛路線問題，試圖找出動態車輛路線問題的解決方法。
傳統的車輛路線問題為一靜態問題，在規劃車輛巡迴路線時，所有需求點、需求量以及路段的旅行時間等輸入資料皆為已知，但是現實狀況下這些輸入資料是未知的，而是會隨著時間持續更新，動態車輛路線問題是處理一連串靜態問題的過程。車輛路線問題已被證實為NP-Hard的問題，傳統的數學規劃難已快速求得最佳解，因此有許多人將數學模式與巨集啟發式演算法做整合，先利用數學模式求得起始解，再利用巨集啟發式演算法找到近似的最佳解，結合兩者之優點以解決車輛路線巡迴問題。
本研究將結合數學模式與巨集啟發式演算法進行求解，首先，路段旅行時間根據旅行時間階段函數的概念，建構依時性動態車輛路線巡迴問題之數學模式，在最小商用車輛旅行成本之下，符合容量限制、時間限制以及子迴路限制，利用CPLEX進行求解獲得較佳之車輛指派起始解，依據所獲得之初始指派結果以禁制搜尋法進行路徑更新。
數值模擬實驗以模擬指派模式DynaTAIWAN進行，實驗路網以50節點虛擬路網為例，觀察不同實驗因子：車流型態、配送需求點、商用車輛數以及即時資訊更新頻率下，對於配送結果所帶來之影響。

Information and communication technologies have been advanced increasingly in recent years, including GIS, GPS and ITS. These technologies can handle vast amount of data and provide real-time information. Fleet dispatchers can control and manage immediately a fleet of vehicles due to availability and quality of information. Most researches in logistic management adopt concept of time in traditional VRP (Vehicle Routing Problems) and attempt to seek a best solution for DVRP (Dynamic Vehicle Routing Problems).
Traditional VRP is a static problem. When it schemes vehicle routing and scheduling, all input data (i.e. demand, travel time, etc. ) is deterministic. However, the input data is unknown in fact and dynamically changed according to time. VRP has been testified as a NP-hard problem. The traditional mathematic programming cannot solve optimal solutions for VRP with large demand nodes, meta-heuristic approaches are applied to find solution quickly.
This research integrates mathematical model and Meta-heuristics to cope with the dynamic VRP. The mathematical model is designed to solve an optimal routing solution for initial routes based on time-dependent travel costs in a traffic network. The travel cost function is assumed to possess the form of step functions, thus could be incorporated with math formulation. Several constraints are considered, such as cost, capacity limitations, time restrictions and sub-tour elimination constrains. The math formulation is solved through CPLEX in order to obtain optimal solution for vehicle routing. The route updating algorithm is designed based on Tabu search, and real-time information is used to update link costs.
Numerical experiments are implemented based on simulation-assignment model, DynaTAIWAN, and different scenarios are developed to illustrate possible advantages of the solution approach. Observations are made based on factors such as traffic flow pattern, demand, number of vehicles, and frequency of the real-time updating.

1. 毛皖亭 (2007)，線上動態車輛巡迴路線演算法之發展：滾動平面法之應用，國立成功大學交通管理科學系碩士論文。
2. 柯景文 (2002)，禁制搜尋法於動態巡迴路線問題之研究，逢甲大學交通工程與管理研究所碩士論文。
3. 胡大瀛等(2004)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統(第一年期)，交通部運輸研究所。
4. 張有恆 (2005)，現代運輸學，華泰文化事業股份有限公司。
5. 梅明德 (1998)，線上型時窗限制車輛路線問題之模式與求解演算法，國立中央大學土木工程研究所博士論文。
6. 郭欣華 (2006)，即時資訊下車隊管理問題之研究，國立成功大學交通管理科學系碩士論文。
7. 陳德政 (2005)，即時資訊下物流配送問題之研究，逢甲大學交通工程與管理研究所碩士論文。
8. 馮正民、邱裕鈞(2004)，研究分析方法，建都文化事業有限公司出版。
9. 蘇義雄 (2005)，物流與運籌管理，華泰文化事業股份有限公司。
10. 運輸研究所(2003)，區域級智慧行運輸系統示範計畫-核心交通分析與預測系統，交通部運輸研究所。
11. Clarke, G. and Wright, J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, pp. 568-581.
12. Chopra, S., and Meindl, P. (2001), “Supply Chain Management,” Prentice-Hall, pp.457.
13. Fisher, M.L., Jaikumar, R. (1981),“A Generalized Assignment Heuristic for Vehicle Routing,” NETWORKS, Vol. 11, pp.109-124.
14. Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R. (2003), “Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies,” European Journal of Operational Research, Vol.151, pp.1-11.
15. Gillett, B. and Miller, L. (1974), “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, Vol. 22, pp. 340-349.
16. Haghani, A. and Jung, S. (2005), “A dynamic vehicle routing problem with time-dependent travel times,” Computer & Operations Research,Vol.32 , pp.2959-2986.
17. Hanshar, F.T and Ombuki-Berman, B.M. (2007), “Dynamic vehicle routing using genetic algorithms,” APPLIED INTELLIGENCE, Vol.27, pp.89-99.
18. Hu, T.Y., Liao, T.Y. and Kuo, H.H. (2007) “Dynamic fleet management under real-time information,” Proceedings of the Eastern Asia Society for Transportation Studies, Vol.6.
19. Ichoua, S., Gendreau, M. and Potvin, J.Y. (2001) “Vehicle dispatching with time-dependent travel times,” European Journal of Operational Research, Vol.144, pp.379-369.
20. Laporte, G. and Osman, I.H. (1995), “Routing problems : A bibliography,” Annals of Operations Research, Vol.61, pp.227-262.
21. Lin, S. (1965), “Computer Solutions of the Traveling Salesman Problem,” The Bell System Technical Journal, Dec., pp. 2245-2269.
22. Malandraki, C. and Daskin, MS. (1992), “Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms,” Transportation Science, Vol. 26, pp.185-199.
23. Osman, I. H. (1993), “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, 41:421–451.
24. Psaraftis, H.N. (1995), “Dynamic vehicle routing: Status and prospect,” Annals of Operations Research, 61, pp.143-164.
25. Renaud, J., Boctor, F.F., and Laporte, G. (1996), “An Improved Petal Heuristic for the Vehicle Routing Problem,” Journal of the Operational Research Society, Vol. 47, pp. 329-336.