智慧型運輸系統(Intelligent Transportation Systems)的發展與應用已被世界各國視為減輕交通擁擠之主要策略；其中商用車輛營運操作 (Commercial Vehicle Operations, CVO) 一直是 ITS 發展以來重要的子計畫，主要的著眼點在於利用具全球定位系統 (Global Positioning System, GPS) 車輛位置資訊以期減少巡迴、載貨、送貨所需的時間，進而減少商用車輛之旅行成本或減輕車流干擾之情形。重要的關鍵為車輛路線（Vehicle Routing Problem，VRP）的設計，車輛路線問題在國內外一直有許多相關的文獻在探討，然而這些現有的路線規劃模式多假設靜態旅行成本下計算最佳路線，無法反映道路的即時車流狀況，如天氣、道路突發狀況。因此為了更符合實際的道路狀況，本研究針對行車時間不確定的情況下之隨機車輛路線問題（Stochastic Vehicle Routing Problem，SVRP）作一探討。
通常VRP路線的演算法考慮兩個層面：起始路線的產生與路線修正。起始路線的產生根據自由車流（Free Flow）的旅行時間而來，但交通流量的改變會造成旅行時間的改變，車輛之行駛時間會隨流量變化而改變，原有VRP的假設行駛時間將由固定之時間矩陣轉為隨機之旅行時間矩陣，其平均旅行時間也隨之改變，本研究即希望藉由機會限制模式（Chance-Constrained Programming）技巧來求解此一SVRP問題，在動態旅行時間的條件下，藉由SVRP演算法去計算出最佳的巡迴路線，並將所得之結果回饋給車輛駕駛改善路線，達到即時派遣之目標。
為測試經由此一演算法所求得之解確實能有效改善行車路線之效率及達到即時性的路線修正目標，本研究提出一交通模擬架構用於未來路線的評估、產生、與動態資訊的產生與研擬，此一架構結合SVRP的演算法與動態模擬指派模式進行動態路線之評估與分析，希望藉此來反應真實的交通特性。在未來ITS的環境中，此一架構可評估即時性或動態性資訊的產生與研擬，交通管理系統之效率等相關策略之分析與評估，而模擬所產生的路線效益與評估之結果並可提供即時性路徑演算參考與修正之管道。

第一章 緒論………………………………………………………………1
1.1 研究背景……………………………………………………………1
1.2 研究動機與目的……………………………………………………2
1.3 研究範圍……………………………………………………………2
1.4 研究方法與步驟……………………………………………………3
1.5 章節簡述……………………………………………………………6
第二章 文獻回顧……………………………………………………………7
2.1 即時性交通管理之研究方向……………………………………7
2.2 車輛路線問題……………………………………………………8
2.2 隨機車輛路線問題……………………………………………15
2.2.1 動態車輛路線問題…………………………………………………15
2.2.2 隨機車輛路線問題…………………………………………………18
2.3 評估模式DYNASMART…………………………………………23
第三章 即時資訊下車輛巡迴路線架構……………………………………26
3.1 即時資訊下車輛路線問題之交通模擬架構………………………26
3.2 隨機車輛路線問題之數學模式及演算……………………………28
3.2.1 機會限制模式與規劃求解…………………………………………28
3.2.2 隨機車輛路線問題模式之構建…………………………………28
3.3 演算流程………………………………………………………………32
3.3.1 最佳化求解工具：CPLEX之應用……………………………………32
3.3.2 演算過程說明………………………………………………………33
第四章 數值實驗………………………………………………………40
4.1 台中市路網資料……………………………………………………40
4.2 實驗設計……………………………………………………………41
4.3 結果分析……………………………………………………………45
第五章 結論與建議………………………………………………………59
5.1 結論…………………………………………………………………59
5.2 建議…………………………………………………………………60
參考文獻……………………………………………………………………61
附錄1 隨機車輛路線問題求解程式……………………………………66

一、 中文部分
1.易德華（1998），「軟時窗車輛巡迴問題之研究」，中央大學土木工程研究所碩士論文。
2.卓裕仁（2001），「 以巨集啟發式解法求解多車種與週期性車輛路線問題之研究」，交通大學運輸工程與管理研究所博士論文。
3.胡大瀛（1996），「DYNASMART在動態交通指派模式中之應用」，中華民國運輸學會第11屆研討會論文集，頁873-883。
4.胡大瀛、陳克宇、陳建緯、洪百賢（1999），「VRP之交通模擬評估架構」，中華民國第四屆運輸網路研討會論文集，民國88年10月，頁62-71。
5.林修竹（1999），「包容性啟發式解法在VRPTW問題上之應用」，交通大學，運輸工程與管理研究所碩士論文。
6.林明俊（1998），「隨機環境下多車種派車問題之研究」，中原大學工業工程研究所碩士論文。
7.洪仲林（2001），「含時窗限制之動態需求車輛途程規劃問題」，中華大學經營管理研究所碩士論文。
8.白俊偉（1999），「隨機型區位-路線問題解法之研究」，大葉大學工業工程研究所碩士論文。
9.陳正元（1992），「節省法與路線間交換改善法在車輛路線問題上之應用」，國立交通大學土木工程研究所碩士論文。
10.陳建緯（1999），「即時資訊下動態派遣策略之研擬」，逢甲大學交通工程與管理學系國科會大專學生參與專題計畫研究成果報告。
11.韓復華、卓裕仁（1996），「門檻接受法在TSP問題上之應用」，運輸計畫季刊第25卷第2期，頁163-188。
12.韓復華、卓裕仁（1996），「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊第9卷第3期，頁113-144。
13.韓復華、楊智凱、卓裕仁（1997），「應用門檻接受法求解車輛路線問題之研究」,運輸計劃季刊第26卷第2期,頁253-280。
14.韓復華、陳正元（1992），「車輛路線問題啟發式解法在PC上直行績效之研究」，中華民國運輸學會第七屆研討會論文集，第四冊，頁649-662。
15.黃金智（1999），「隨機型車輛路線問題解法之研究」，大葉大學工業工程研究所碩士論文。
二、 英文部分
1.Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. （1994）, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, pp. 846.
2.Bartholdi , J. J., and L.K.Platzman, （1988）“Heuristics based on spacefilling curves for combinatorial problems in Euclidean space,” Management Science, 34, 291-305。
3.Bertsiman, D.J. and van Ryzin, G. （1991） “A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane,” Operations Research, Vol. 39, No. 4, pp. 601-615.
4.Bertsimas ,D.J. , （1992）,”A vehicle routing problem with stochastic demand”, Operations Research , 40,574-585。
5.Bertsiman, D.J. and Van Ryzin, G. （1993） “Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles,” Operations Research, Vol. 41, No. 1, pp. 60-76
6.Bodin, L. ,D. B. L. Golden ,A.A.Assad and M.O. Ball （1983）,“Routing and scheduling of vehicles and crews. The state of the art”, Computers and Operational Research ,10,69-211。
7.Brandao, J. ,A. Mercer, （1997）“A tabu search algorithm for the multi-trip vehicle routing and scheduling problem,” European Journal of Operational Research ,100,180-191。
8.Chao, I. M. , B. L. Golden, and E. Wasil, （1993）“A new heuristic for the multi-depot vehicle routing problem that improves upon best-know solutions,” Am. J. Math. Mgmt Dci. ,13, 371-406。
9.Clarke,G. and J. W.Wright, （1964）“Scheduling of vehicles from a central depot to a number of delivery points,” Ops Res,12,568-581。
10.Dammeyer, F. and V. Stefan, （1993）“Dynamic tabu list management using the reverse elimination method,” Annals of Operation Research ,41 ,31-46。
11.Dantzig, G. and J. H. Ramser,“The truck dispathing problem, （1959）” Management
science, 6, 80-91。
12.Duhamel, C.,J.-Y. Potvin and J.-M. Rousseau, （1997）“A tabu search heuristic for the vehicle routing problem with backhauls and time windows,” Transportation Science ,31,49-59。
13.FHWA, （1998）, 1998 FHWA to Beta Test GPS Travel Time Software, ITE Journal, October, p10.
14.Fisher, M. L. and R. Jaikumar, （1981） “A generalized assignment heuristic for vehicle routing problems,” Networks, 11,109-124。
15.Gendreau, M., G. Laporte and R. Seguin, （1995）, “An exact algorithm for the vehicle routing problem with stochastic demands and customers,” Transportation Science ,29,143-155。
16.Gendreau, M., G. Laporte and R. Seguin, （1996） ,“A tabu search heuristic for the vehicle routing problem with stochastic demands and customers,” Operations Research , 44,469-477。
17.Gendreau ,M., G. Laporte and R. Seguin, （1996） ,“Stochastic vehicle routing,”European Journal of Operational Research ,88,3-12。
18.Gillett, B. and Miller, L. （1974） “A Heuristic Algorithm for the Vehicle Dispatch Problem.” Operations Research, Vol. 22, pp. 340-349
19.Golden, B.L. et al. （1977） “Implement Vehicle Routing Algorithms,” Networks, Vol. 7, pp. 113-148.
20.Golden, B., A. Assad, L. Levy and F. Gheysens, （1984）“The Fleet Size and Mix
Vehicle Routing Problem,” Comput & Ops Res. ,11,49-66。
21.Held, M. and R. Karp （1971） “The Travelling Salesman Problem and Minimum Spanning Trees Part Ⅱ,” Mathematical Programming, Vol. 1, pp.6-25.
22.Hiller, F. and Liberman. G.(1995) “Introduction To Mathematical Programming,” pp.368-374.
23.Hu, T.Y. （1995） “Dynamic Analysis of Network Flows Under Advanced Information and Control Systems”, Ph.D. Dissertation, The University of Texas at Austin.
24.Jaillet, P., and Odoni, A. R. , （1988）”The probabilistic vehicle routing problem,” in: B.L. Golden and A.A. Assad （eds.）,Vehicle Routing: Method and Studies, North-Holland, Amsterdam.
25.Lambert, V., G. Laporte and F. Louveaux, （1993）, “Designing collection routes through bank branches,” Computers Ops Res.,20,783-791。
26.Laporte, G. , F. Louveaux and H. Mercure, （1989） ,“Models and exact solutions for a class of stochastic location-routing problems,”European Journal of Operational Research ,39 ,71-78。
27.Laporte, G. , F. Louveaux and H. Mercure, （1992） ,“The vehicle routing problem with stochastic travel times,” Transportation Science, 26,161-170。
28.Lin, S. and Kernighan, B. （1973） “An Effective Heuristics Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516
29.Little , J. D. C, K.G. Murty, D.W. Sweeney and C. Karel, （1963）“Alghorithm for the traveling salesman problem,” Ops. Res. ,11, 979。
30.Miller, C.E. （1960） “Integer Programming Formulation of Traveling Salesman Problem,” Journal of Association for Computing Machinery, Vol. 7, pp. 326-329.
31.Papastavrou, J.D. （1996） “A Stochastic and Dynamic Routing Policy Using Branching-Processes with State-Dependent Immigration,” European Journal of Operational Research, Vol. 95, Iss. 1, pp. 167-177.
32.Psaraftis, H.N. （1983） “An Exact Algorithm for the Single Vehicle Many-to-Many Dial-a-Ride Problem with Time Windows,” Transportation Science, Vol. 14, pp. 130-154
33.Psaraftis, H.N. （1998） “Dynamic Vehicle Routing Problem,” In Vehicle Routing: Methods and Studies （B.L. Golden and A. A. Assad, eds.）, North Holland, Amsterdam, pp. 223-248
34.Powell, W.B., Jaillet, P. and Odoni, A. （1995） “Stochastic and Dynamic Networks and Routing,” Handbooks in OR & MS, Vol. 8, Network Routing, Elsevier Science B.V., The Netherlands, pp. 141-295.
35.Osman, I. H., （1993）“Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research ,41,421-451。
36.Renaud,J., G. Laporte and F. F.Boctor, （1996）“A tabu search heuristic for the multi-depot vehicle routing problem,” Computers Ops Res.,23,229-235。
37.Solomon, M. M.,“Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research,35,254-265 （1987）。
38.Taillard,E., P. Badeau, M. Genderau, F. Guertin and J.-Y. Potvin, （1997）“A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, 31,170-186。
39.Tillman, F. A., （1996）, “The multiple Terminal Delivery problem with probabilistic demands,” Transportation Science ,3,192-204。
40.Waters, C. D. J, （1989） ,“Vehicle-scheduling problem with uncertainty and omitted customer,”Journal of the Operational Research Society 40,1099-1108
41.Ziliaskopoulos, A. （1994）, Optimum Path Algorithm on Multidimensional Networks: Analysis, Design, Implementation and Computational Experience, Ph.D. Dissertation, The University of Texas at Austin