隨著物流業的發展，由於運送成本所佔的比例相當高，所以如何將運送成本降低已成為一種趨勢，因為能夠減少運輸成本便可以減少物流成本，進而降低企業的營運成本，提昇企業的競爭力。又因為科技的進步，智慧型運輸系統的推動，使得業者可透過車輛上的定位系統，並根據即時的交通路網狀況來改善車隊路線的派遣，以降低營運上的成本並提昇顧客貨物運輸的服務水準，所以從傳統的車輛路線巡迴問題演進到可利用即時資訊下的動態車輛路線巡迴問題逐漸受到重視，並有大量的研究投入。
由於車輛路線巡迴問題有NP-Hard的特性，當這些問題的需求點數目愈多時，其複雜度將會急速地增加，因此傳統的數學規劃解法就無法快速解決此類問題。啟發式解法雖不能保證求得最佳解，但其具有求解快速且能求得近似最佳解的優點，所以多以啟發式解法求解此類相關議題。商用車輛在鄰近區域間交換需求點的車輛路線問題可視為由動態車輛路線問題所衍伸的問題，過去的研究上已指出在動態資訊下進行路線更新可以降低旅行成本，能得到比利用靜態指派更好的績效，但若能加上商用車在路線上進行鄰近區域間需求點的交換更新，則更能符合真實的運輸環境，也更符合經濟效益。
本研究利用改良的petal method來構建車輛指派，在鄰近的區域中，利用Swap Exchange節點交換法進行車輛路線間的改善程序，使商用車間可互相支援。並利用禁制搜尋法在提供動態資訊下及利用2-opt產生可行解進行群內路線更新，透過ㄧ交通模擬指派模式(DynaTAIWAN)來結合上述演算法產生即時旅行時間矩陣，進行即時資訊下動態車輛路線問題之評估與分析，希望能透過此一模擬評估架構呈現所能帶來的路線效益。並利用模擬的路網與真實的台中市路網設定不同的情境及透過不同的需求點個數與即時資訊提供的頻率作為設計因子進行實驗，希望能透過此一模擬評估架構比較在不同情況下，呈現本研究所發展的演算法所帶來的效益。

關鍵字：petal method、禁制搜尋法、群間交換、DynaTAIWAN

As the development of logistics, transportation or delivering cost, which accounts for substantial proportion of overall cost, could be reduced to enhance the competitiveness of the enterprise. Thus, the issue of minimizing transportation cost has drawn a lot of attention. Due to the advancement of Intelligent Transportation Systems (ITS), dispatching centers can arrange vehicle routes according to real-time information. The application of ITS technologies can improve deliver/pick-up services; however, the critical question is how to solve the Vehicle Routing Problems (VRP) under real-time information.
The Vehicle Routing Problems, belong to the class of NP-hard problems, cannot not be solved efficiently by mathematical programming techniques. Although the heuristic approaches do not guarantee to obtain the optimal solution, they can solve the VRP problem more efficiently. Under real-time information, the routing solution could be improved through exchanging demands among vehicles.
This research proposes improved petal methods to perform vehicle assignment. During the route updating process, the Swap-exchange and Tabu Search algorithms are deployed to update routes and exchange demand points between commercial vehicles. The algorithm is implemented through C++, an object-oriented language. The proposed approaches are then evaluated in a realistic traffic simulation environment. The traffic simulation-assignment model, DynaTAIWAN is applied to evaluate assigning and routing strategies in a experiment network and a true network. DynaTAIWAN is used to produce time-dependent travel cost matrix, according to different simulation scenario setups.
Numerical experiments, based on different information supply strategies, are conducted to explore the research framework for dynamic fleet management problems under real-time information.
Key words：petal method、Tabu Search algorithm、Swap Exchange、DynaTAIWAN

參考文獻
1. 王中武 (2002)，台灣地區運用商車營運系統 (ITS/CVO) 於海運貨櫃進出口貨物自動追蹤之可行性研究，高雄第一科技大學運輸與倉儲營運系碩士班碩士論文。
2. 柯景文 (2002)，禁制搜尋法於動態巡迴路線問題之研究，逢甲大學交通工程與管理學系碩士班碩士論文。
3. 胡大瀛、陳麗雯、陳一昌、黃運貴、蔣敏玲 (2005)，“DynaTAIWAN 模擬指派模式之建立與應用”，中華民國運輸學會第20屆論文研討會。
4. 敖君瑋 (1998)，禁忌搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所碩士論文。
5. 陳勝男 (1996)，禁忌搜尋法應用於車輛路線問題之研究，大葉大學工業工程研究所碩士論文。
6. 陳德政 (2005)，即時資訊下物流配送問題之研究，逢甲大學交通工程與管理學系碩士班碩士論文。
7. 黃冠雄 (2001)，時效導向的娃娃車接送之車輛途程問題—以禁忌搜尋法求解，國立中正大學數學研究所碩士論文。
8. 廖亮富 (1997)，含時窗限制多部車輛途程問題解算之研究，元智大學工業工程研究所碩士論文。
9. 運輸研究所(2004)，台灣地區智慧型運輸系統綱要計畫，交通部運輸研究所。
10. 運輸研究所(2005)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統(第2年期)，交通部運輸研究所。
11. Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G. and Prutzman, P. J (1983)., Improving the distribution of industrial gases with and on-line computerized routing and scheduling optimizer, Interfaces, Vol. 13, pp. 4-23.
12. Boctor, F. F., Renaud, J. and Laporte, G. (1996), An improved petal heuristic for the vehicle routing problem, Journal of the Operational Research Society, Vol. 47, pp. 329-336.
13. Bodin, L., Golden, B., Assad, A. and Ball, M. (1983), Routing and scheduling of vehicles and crews: the state of the art, Computers & Operations Research, Vol. 10, pp. 63-211.
14. 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.
15. David, M. R., Hjorring, C. and Glover, F. (1993), Extensions of the Petal Method for Vehicle Routing, J. Opl Res. Soc, Vol. 44, No, 3, pp. 109-124.
16. Fisher, M. L. and Jaikumar, R. (1981), A generalize assignment heuristic for vehicle routing, Networks, Vol. 11, pp. 109-124.
17. Gendreau, M., Hertz, A. and Laporte, G. (1992), New Insertion and Postoptimizatioin Procedures for the Traveling Salesman Problem, Operations Research, Vol. 40, No.6, pp.1086-1094.
18. Gendreau, M., Laporte, G., Musaraganyi, C. and Taillard, E. (1999), A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem, Computers & Operations Research, Vol. 26, pp. 1153-1173.
19. 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, pp. 151,1-11.
20. Gillett, B. and Miller, L. (1974), A heuristic algorithm for the vehicle dispatch problem, Operations Research, Vol. 22, pp. 340-349.
21. Glover, F. (1986), Future Paths for Integer Programming and Links to Artificial Intelligence, Computers & Operations Research, Vol. 13, pp. 533-549.
22. Golden, B., Bodin, L., Doyle, T. and Stewart, W. (1980), Approximate Traveling Salesman Algorithms, Operations Research, Vol. 28, No. 3, pp. 694-711.
23. Hansen, P. (1986), The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming, Proceedings of Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.
24. Kalakota, R. and Whinston, A. B. (1996), Frontier of Electronic Commerce, Addison-Wesley, Reading, MA.
25. Kotlor, P. (2003), Principles of Marketing, Gary Armstrong, Englewood Cliffs, N. J. ; Prentice Hall, 10th ed.
26. Lin, S. (1965), Computer Solutions of the Traveling Salesman Problem, The Bell System Technical Journal, Dec., pp. 2245-2269.
27. Lin, S. and Kernighan, B.W. (1973), An Effective Heuristic Algorithm for the Traveling Salesman Problem, Operations Research, Vol.21, pp. 498-516.
28. Osman, I. H. (1991), Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problem, Ph.D. Dissertation, The Management School, Imperial Collage, London.
29. Osman, I. H. (1993), Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem, Annals of Operations Research, Vol. 41, pp. 421-451.
30. Potvin, J. Y., Kervahut, T., Garcia, B. L. and Rousseau, J. M. (1992), A tabu search heuristic for the vehicle routing problem with time windows, Technical Report CRT-855, Universite de Montreal, Quebec, Canada.
31. Powell, W. B., Snow, W. and Cheung, R. (2000), Adaptive labeling algorithms for the dynamic assignment problem, Transportation Science, Vol. 34, No. 1, pp. 67-85.
32. Powell, W. B. and Spivey, M. Z. (2004), The Dynamic Assignment Problem, Transportation Science, Vol. 38, No. 4, pp. 399-419.
33. Psaraftis H.N. (1995), “Dynamic vehicle routing: Status and prospect,” Annals of Operations Research, Vol 61, pp.143-164.
34. Reinelt, G. (1991), TSPLIB-A Traveling salesman problem library, ORSA Journal on computing, Vol. 3, pp. 376-384.
35. 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.
36. Rosenkrantz, D., Sterns, R.and Lewis, P. (1977), An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal of Computing, Vol. 6, pp. 563-581.
37. Ryan, D. M., Hjorring, C. and Glover, F. (1993), Glover Extensions of the Petal Method for Vehicle Routing, Journal of the Operational Research Society, Vol. 44, pp. 289-296.
38. Taillard, É., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J. (1997), A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science, Vol. 31, No. 2, pp. 170-185.