復康巴士乃針對身心障礙者而設立之及門服務運輸系統；此類服務亦稱之為撥召運輸系統。復康巴士營運至今，規模漸大，而車輛利用率始終偏低。本研究之目的即在於改善現有派車與路徑規劃方式以提升車輛之利用率；由於考量動態需求，因而形成一個動態撥召問題，也增加了求解的複雜性。

　　本研究以0-1整數規劃建模，並以先分群後規劃路徑策略分解原來問題。這樣的策略形成兩階段的求解過程：在第一階段以掃描法分配需求點至各鄰近車輛，第二階段則以最佳化軟體求解各車輛之路徑規劃。藉由多種分群組合的方式反覆找出較佳的解答。

Fukang bus is a door-to-door transportation service system in Taiwan established for the handicapped. Such type of service is also known as dial-a-ride transportation system. Though the scale of the Fukang bus becomes larger and larger, the performance of the system is not satisfactory due to the low utilization of vehicles. The purpose of this study is to improve the dispatch and routing of vehicles to enhance their utilization. This study focuses on the dynamic requests of service and hence makes the route planning a dynamic dial-a-ride problem, which also increases the difficulty in solving the problem.
This study uses 0-1 integer programming to model the dynamic dial-a-ride problem, and adopts the cluster-first-routing-second strategy to solve the problem. Such a strategy divides the solution procedure to two stages. In the first stage, the sweep algorithm is employed to allocate demand nodes to their neighboring vehicles, and thus forming a set of single vehicle routing problems. In the second stage, an optimization solver is used to solve the route planning of each vehicle. By performing the sweep algorithm repeatedly with different stating nodes, we can find different combinations of demand clusters and then obtain different routing plans. A best solution is finally found from all combinations.

中文摘要	I
英文摘要	II
誌謝	III
目錄	IV
圖目錄	VI
表目錄	VII
第一章 緒論	1
1.1 研究動機	1
1.2 研究背景	1
1.3 研究目的	2
1.4 研究範圍	2
1.5 研究流程	3
第二章 文獻探討	4
2.1 復康巴士	4
2.2 撥召服務問題	5
2.2.1 撥召服務	5
2.2.2 撥召問題(Dial-A-Ride Problem,DARP)	6
2.3 啟發式解法	9
2.3.1 掃描法	10
2.3.2 插入法	11
2.3.3 節省法	11
2.4 巨集啟發式解法	12
巨集啟發式解法	12
2.4.1 基因演算法	12
2.4.2 蟻群演算法	13
2.4.3 蜂群演算法	13
第三章 研究方法	15
3.1 問題描述	15
3.2 多車輛數學模型	16
目標式:	17
車輛派遣限制式:	17
流量守恆限制式:	18
時間/順序限制式:	18
車容量限制式:	18
工作時間限制式:	18
定義限制式:	19
3.3 單一車輛數學模型	21
目標式:	22
車輛派遣限制式:	22
流量守恆限制式:	23
時間/順序限制式:	23
車容量限制式:	23
工作時間限制式:	23
定義限制式:	24
第四章 復康巴士路線之規劃	27
4.1 復康巴士路線之動態求解演算法	27
4.2 掃描法分群	29
4.3 測試	34
第五章 例題測試與分析	42
5.1 實驗一	43
5.2 實驗二	48
5.3 小結	48
第六章 結論與建議	50
6.1 結論	50
6.2 建議	50
參考文獻	52
附錄A 測試範例資料	54
附錄B 實驗一求解結果	55
附錄C 實驗二求解結果	58

圖目錄
圖1: 時窗示意	16
圖2: 主要演算法	27
圖3: 掃描法	28
圖4: 三條篩選出來的車班路線	29
圖5: 中心節點群以及待分群需求的分佈位置	30
圖6: 以a為中心的座標圖	31
圖7: 以b為中心的座標圖	32
圖8: 以c為中心的座標圖	33
圖9: 六種不同分群結果	34
圖10: 初始化需求表	35
圖11: 初始化班表	35
圖12: 預約1插入需求表	36
圖13: 預約1插入後班表	37
圖14: 預約2插入後需求表	38
圖15: 預約2插入後班表	38
圖16: 兩種分群結果	39
圖17: 兩種分群結果之旅行時間	40
圖18: 預約3插入後的需求表	40
圖19: 預約3插入後的班表	41
圖20: 亂數產生之新預約需求	43
圖21: 初始化班表1	44
圖22: 更新過後的班表1	45
圖23: 初始化班表2	46
圖24: 更新過後的班表2	46
圖25: 初始化班表3	47
圖26: 更新過後的班表3	47

表目錄
表一:   預約需求1	36
表二:   預約需求2	37
表三:   預約需求3	39
表四:   預約2與預約3之比較	41
表五:   班表1媒合結果	44
表六:   班表2媒合結果	45
表七:   班表3媒合結果	46
表八:   重新安排節點後的班表比較	48

1.	辛孟鑫，「撥召運輸系統路線規劃問題之研究－以台北市復康巴士為例」，碩士論文，國立成功大學交通管理科學研究所，2005。
2.	林奕隆，「應用蜂群最佳化演算法求解撥召問題－以復康巴士為例」，碩士論文，國立中央大學土木工程學研究所，2011。
3.	Attanasio, A. and Cordeau, J.F. and Ghiani, G. and Laporte, G., Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel Computing 30 pp.377–387, 2004.
4.	Bergvinsdottir, K.B., The Genetic Algorithm for solving the Dial-a-Ride Problem, Kgs. Lyngby, 2004.
5.	Bodin, L. and Golden, B.L., and Assad, A. and Ball, M., Routing and Scheduling of Vehicle and Crew: The State of Art, Special Issue of Computers and Operations Research vol. 10:2, pp.63-211, 1983.
6.	Clarke, G. and Wright, J. W., Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research Vol. 12:4,pp.568-581, 1964.
7.	Cordeau, J. F. and Laporte, G., The dial-a-ride Problem (DARP): variants,modeling issues and algorithms, 4OR: A Quarterly Journal of Operations Research, Vol. 1, pp.89–101, 2003.
8.	Dorigo, M. and Maniezzo, V. and Colorny, A., Ant System: An Autocatalytic Optimizing Process, 1991, Technical Report, pp.91-016, Politecnico di Milano, Italy, 1991.
9.	Dorigo, M. and Gambardella, L.M., Ant colonies for the travelling salesman problem, BioSystems, vol.43, pp.73-81, 1997.
10.	Dorigo, M. and Caro, G.D., The Ant Colony Optimization Meta-Heuristic, New Ideas in Optimization, 1999.
11.	Desrosiers, J., Dumas, Y., and Soumis, F., A dynamic programming solution of the large-scale single vehicle dial-a-ride problem with time windows, American Journal of Mathematical and Management Sciences, Vol. 6, pp.301-325, 1986.
12.	Madsen, O. B. G. and Ravn, H. F. and Rygaard, J. M., “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, pp. 193-208, 1995.
13.	Psaraftis, H. N., A dynamic programming approach to the single-vehicle,many-to-many immediate request dial-a-ride problem, Transportation Science, Vol. 14, pp.130-154, 1980.
14.	Samuel, W. L., Autonomous dial-a-ride transit benefit-cost evaluation, Volpe National Transportation Systems Center, August, 1998.
15.	Sexton, T., The single vehicle many-to-many routing and scheduling problem, Ph.D. dissertation, SUNY at Stony Brook, 1979.
16.	Sexton, T. and Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: I. scheduling, Transportation Science, Vol. 19, pp. 378-410, 1985a.
17.	Sexton, T. and Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: II. routing, Transportation Science, Vol. 19, pp. 411-435, 1985b.
18.	Teodorovic, D. and Radivojevic, G., A fuzzy logic approach to dynamic dial-a-ride problem, Fuzzy Sets and Systems 116 pp.23-33, 2000.