社會保障一詞源於Social Security，其保障制度起源於十九世紀末的歐洲工業社會，社會福利制度即是社會保障制度的內容之一，近年來，身心障礙者的人口數持續攀升，其中現今又以新北市為全台擁有最多的身心障礙者之縣市，而一個制度完善的復康巴士服務將有助於社會福祉之提升。
根據102年度新北市復康巴士營運服務評鑑計畫調查顯示，目前共乘辦理的部分，仍多以調度員來進行人工排班之方式，惟藉由人工排程之車輛路徑多以經驗法則來安排，且不見得為具有效率之路線，故本研究針對新北市復康巴士問題之特性探討出一合適的復康巴士撥召系統模型，以減少營運單位的不必要開銷，並合理地依據乘客之時窗、方向性、需求點間之距離來判斷共乘服務，而非將空駛里程成本轉嫁給需求者的共乘費用來負擔，增進其營運效能。
本研究採用兩階段的方式建構路線，第一階段為採用插入法建構初始路徑解後，再藉由第二階段的類電磁演算法之吸引與排斥機制，進行初始路徑之改善，最終採以Microsoft Visual C#開發環境來撰寫程式，並針對郭耀煌(2001)、Christofides等人(1979)之公開標準例題與同為復康巴士背景之魏健宏等人(2007)研究進行範例測試與比較，其結果顯示本研究除將共乘合理化之外，車輛行駛距離反而將因同性質乘客的媒合共乘下，進而較僅考慮排程重疊的方式有所改善。

The Social security system was originated from Europe in the nineteenth century, and the social welfare system is a part of the system.  In recent years, the number of handicapped population continues to rise in New Taipei City, which has the largest number of handicapped population in Taiwan.  A well design handicapped bus service is a crucial component of the social welfare system for the City agencies. 
Based on the Operational Services Evaluation Report of New Taipei city’s Handicap Service bus in 2013, the carpool service of the handicapped bus is scheduled by the dispatchers based on their previous experience, which is inefficient and ineffective.  The purpose of this study is to develop a suitable model for the efficient design of the handicapped bus servicer with minimum total empty-loaded mileage.  By allocate the passenger into carpool service based on service time window, travel direction and inter-passenger distance of the handicapped passengers, the proposed model can provide more effective carpool handicapped service, which will reduce the passenger cost and empty-loaded mileage. 
A two-phase algorithm was proposed to construct the routes for the problem dealt in this study.  In the first phase, the initial path of each vehicle was determined by the Insertion heuristics method.  The Electromagnetism-like algorithm was then used to improve the initial paths in the second phase.  A series of case studies were derived from the previous VRP and handicapped service studies to test the validation of the proposed two-phase algorithm.  Based on the results of these case studies problem, the proposed algorithm can provide valid and solid solution for these problem.

目錄
第一章	緒論	1
1.1	研究動機	1
1.2	研究目的	4
1.3	研究範圍	4
1.4	研究架構	6
第二章	文獻回顧與復康巴士營運概況	8
2.1	TSP與VRP相關文獻回顧	8
2.1.1旅行銷售員問題(Traveling Salesman Problem, TSP)	8
2.1.2車輛路徑問題(Vehicle Routing Problem, VRP)	9
2.1.3含時窗車輛路徑問題(Vehicle Routing Problem With Time Windows, VRPTW)	15
2.1.4車輛路徑問題之求解方式	16
2.2	撥召運輸問題文獻回顧	17
2.3	巨集啟發式演算法文獻回顧	21
2.3.1巨集啟發式演算法概述	21
2.3.2類電磁演算法概述	23
2.4	復康巴士營運概況	26
2.4.1新北市復康巴士緣起與現況	26
2.4.2新北市政府身心障礙者小型復康巴士服務須知	32
2.4.3新北市政府身心障礙者中型復康巴士服務須知	36
2.5	小結	39
第三章	模式構建	40
3.1	研究假設	40
3.2	模式符號說明	41
3.3	數學模式	43
第四章	求解演算法	45
4.1	求解演算法之架構	45
4.2	車輛途程之建構	47
4.2.1建構車輛之初始途程	47
4.2.2改善車輛之初始途程	53
4.3	小結	57
第五章	案例測試與評析	59
5.1	案例測試與結果	59
5.1.1案例一測試內容	59
5.1.2案例二測試內容	61
5.1.3案例三測試內容	62
5.2	案例之綜整評析	65
5.2.1案例一測試評析	65
5.2.2案例二測試評析	66
5.2.3案例三測試評析	67
5.3	延伸議題討論	74
5.3.1油料價格之變動	74
5.3.2乘車之收費費率變動	76
5.4	小結	77
第六章	結論與建議	79
6.1	結論	79
6.2	建議	80
參考文獻	81
附錄A 測試範例資料	85
附錄B 車輛行駛路徑	92


圖目錄
圖 1.1無障礙計程車	2
圖 1.2低地板公車	2
圖 1.3復康巴士車輛繞境載客示意圖	5
圖 1.4研究架構流程圖	7
圖 2.1傳統TSP繞行示意圖	9
圖 2.2傳統VRP繞行示意圖	10
圖 2.3類電磁演算法流程	24
圖 2.4小型復康巴士	31
圖 2.5中型復康巴士	31
圖 4.1路徑構建流程圖	47
圖 4.2初始車輛路線建構流程圖	49
圖 4.3需求點之時間性	50
圖 4.4需求點共乘之測試	51
圖 4.5第二個插入之需求點	52
圖 4.6第二個插入之需求點(符合共乘條件)	52
圖 4.7插入第二個和第三個需求點(不符合共乘條件下)	53
圖 4.8類電磁演算法之改善流程	54
圖 5.1油價調動與獲利(空駛里程)關係圖	75
圖 5.2油價調動與獲利(車輛里程)關係圖	76
圖 5.3車資費率調動與獲利關係圖	77
圖B.1魏健宏等人(2007)範例測試之車輛行駛路徑1-3	93
圖B.2魏健宏等人(2007)範例測試之車輛行駛路徑4-6	93
圖B.3魏健宏等人(2007)範例測試之車輛行駛路徑7-9	94
圖B.4林奕隆(2007)範例測試之車輛行駛路徑1-3	96
圖B.5林奕隆(2007)範例測試之車輛行駛路徑4-6	96
圖B.6林奕隆(2007)範例測試之車輛行駛路徑7-9	97
圖B.7本研究測試之調整前車輛行駛路徑1-2	99
圖B.8本研究測試之調整前車輛行駛路徑3-4	99
圖B.9本研究測試之調整前車輛行駛路徑5-7	100


表目錄
表1.1 育成復康巴士101年度各月營運統計表	3
表1.2 育成復康巴士102年1月至8月各月營運統計表	4
表 2.1 車輛路徑問題類型	10
表 2.2 VRP問題之延伸應用	12
表 2.3 撥召運輸問題之比較	18
表 2.4 巨集啟發式演算法綜整表	21
表 2.5 新北市復康巴士受理訂車時間	32
表 4.1 不同城市數的TSP以窮舉法搜尋之工作量	45
表 5.1 各需求點之原始資料	59
表 5.2 各需求點間之距離	60
表 5.3 車輛行駛路徑與行駛距離	61
表 5.4 車輛行駛路徑與行駛距離	61
表 5.5 車輛行駛路徑與行駛距離	63
表 5.6 車輛行駛路徑之乘客所需支付費用表	64
表 5.7 測試結果比較表	65
表 5.8 測試結果比較表	66
表 5.9 行駛距離與總旅行時間比較表	68
表 5.10 空駛距離比較表	68
表 5.11 需求者乘車里程數比較表	69
表 5.12 需求者所需支付費用比較表	71
表 5.13 路徑空駛距離比較表	73
表 5.14 油價調動之所需費用與獲利(空駛里程)	74
表 5.15 油價調動之所需費用與獲利(車輛里程)	75
表 5.16 車資費率變動之載客收入與獲利	77
表A.1 Christofides等人(1979)範例測試之資料	85
表A.2魏健宏等人(2007)範例測試之資料	89
表A.3本研究拓增範例測試之資料	90
表B.1 魏健宏等人(2007)範例測試之車輛行駛路徑(時窗長度為二十分鐘)	92
表B.2 林奕隆(2007)範例測試之車輛行駛路徑(時窗長度為二十分鐘)	95
表B.3 本研究範例測試之車輛行駛路徑(時窗長度為二十分鐘)	98
表B.4 拓增範例測試-排程重疊之車輛行駛路徑(時窗長度為二十分鐘)	101
表B.5 拓增範例測試-類電磁演算法之車輛行駛路徑-(時窗長度為二十分鐘)	102

1.方信傑 (2006)，「應用改良式電磁演算法於求解旅行銷售員問題之研究」，碩士論文，義守大學工業工程管理學系。
2.江漢杰 (2005)，「電磁理論應用於解旅行銷售員問題」，碩士論文，義守大學工業工程管理學系。
3.李軍、郭耀煌 (2001)，“物流配送車輛優化調度理論與方法”，中國地質出版社。
4.辛孟鑫(2005)，「撥召運輸系統路線規劃問題之研究－以台北市復康巴士為例」，碩士論文，國立成功大學交通管理科學研究所。
5.吳宗祐 (2008)，「電改良型螞蟻演算法結合模擬退火法於車輛途程問題之應用」，碩士論文，華梵資訊管理學系碩士班。
6.余彥儒 (2010)，「圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用」，碩士論文，國立中央大學土木工程研究所。
7.林聖偉 (2005)，「需求反應運輸服務需求分析之研究－以醫療運輸為例」，碩士論文，淡江大學運輸管理學系運輸科學碩士班。
8.林奕隆 (2011)，「應用蜂群最佳化演算法求解撥召問題－以復康巴士為例」，碩士論文，國立中央大學土木工程學系研究所。
9.許富雄 (2006)，「以模擬退火法結合區域搜索法應用於載重限制車輛途程問題」，碩士論文，華梵資訊管理學系碩士班。
10.曹家瑞 (2000)，「物流業配送系統之車輛指派與路徑規劃」，碩士論文，台北科技大學生產系統工程與管理系。
11.郭有維 (2010)，「應用類電磁演算法解決二階段供應鏈之生產與運輸排程問題」，碩士論文，臺灣科技大學工業管理研究所。
12.陳冠翰 (2010)，「運用仿電磁理論演算法求解單機排程問題」，碩士論文，朝陽科技大學工業與管理系。
13.陳坤煌 (2013)，「應用類電磁演算法於校車路徑規劃之研究」，碩士論文，義守大學工業管理學系。
14.靳蕃、範俊波、譚永東 (1992)，“神經網路與神經計算機原理．應用”，儒林圖書。
15.楊昆展 (2008)，「粒子群演算法應用於多目標車輛途程問題之研究」，碩士論文，淡江大學運輸管理學系運輸科學碩士班。
16.劉建宏 (2005)，「含時窗限制式卡車與拖車途程問題之研究」，碩士論文，國立中央大學土木工程學系研究所。
17.魏健宏、王穆衡、蔡欽同、辛孟鑫 (2007)，「臺北市復康巴士路線規劃問題之研究」，運輸學刊，第十九卷第三期，頁301-332。
18.蘇昭銘、楊琮平 (2000)，「先進撥召公車營運管理系統之研究」，中華管理學報，第一卷，第一期，頁89-114。
19.新北市政府交通局網站，http://www.traffic.ntpc.gov.tw/web/Home?command=display&page=flash。
20.Birbil, S. I. and Fang, S.C. (2003), “An Electromagnetism-likeMechanism for Global Optimization,” Journal of Global Optimization,Vol. 25, pp. 263–282.
21.Bodin, L., Golden, B., Assad, A., Ball, M. (1983), “Routing and Scheduling of Vehicle and Crews,” Computers and Operations Research, Vol. 10, pp. 63-211.
22.Bodin, L.D. and Sexton, T. (1986), “The multi-vehicle subscriber dial-a-ride problem,” TIMS Studies in Management Science, Vol. 2, pp. 73-86.
23.Borndorfer, R., Klostermeier, F., Grotschel, M. and Kuttner, C. (1997), “Telebus Berlin: vehicle scheduling in a dial-a-ride system,” Technical report SC 97-23,Konrad-Zuse-Zentrum fur Informationstechnik, Berlin.
24.Christofides, N., Mingozzi, A. and Toth, P. (1979). The Vehicle Routing Problem. In Combinatorial Optimization, N. Christofides, A. Mingozzi, P. Toth and C. Sandi, (eds), J. Wiley, 315–338.
25.Cordeau, J.F. and Laporte, G. (2003), “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B, Vol. 37, pp. 579-594.
26.Cordeau, J.F. and Laporte, G. (2003), “The dial-a-ride problem (DARP): variants, modeling issues and algorithms,” 4OR-Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol. 1, pp. 89-101.
27.Desrosiers, J., Dumas, Y.,and Soumis, F. (1986), “A dynamic programming solution of the large-scale singlevehicle dial-a-ride problem with time windows,” American Journal of Mathematical and Management Sciences,Vol. 6, pp. 301–325.
28.Desrosiers, J., Dumas,Y.,Soumis, F., Taillefer, S. (1991), Villeneuve, D., “An algorithm for mini-clustering in handicapped transport.” Les Cahiers du GERAD, G-91-02, Ecole des Hautes Etudes Commerciales, Montreal.
29.Dumas, Y., Desrosiers, J. and Soumis, F. (1989), “Large scale multi-vehicle dial-a-ride problems,” Les Cahiers du GERAD, G-89-30, Ecole des Hautes Etudes Commerciales, Montreal.
30.Garey, M. R. and Johnson, D. S. (1979), Computers and intractability: A guide to the theory  of  NP-completeness, Freeman, San Francisco.
31.Gendreau, M. P., Hertz, A. and Laporte G. (1994), “A tabu search heuristic for the vehicle routing problem,” Management Science, Vol. 40, pp. 1276-1290.
32.Gendreau ,M., Laporte G., and Potvin, J.-Y.(2002), Metaheuristics for the VRP. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp129-154.
33.Ioachim, I., Desrosiers, J., Dumas,Y.,amd Solomon,M.M. (1995), “A request clustering algorithm for door-to-door handicapped transportation,” Transportation Science,Vol. 29, pp. 63–78.
34.Jaw, J., Odoni, A. R., Psarafits, H. N. and Wilson, N. H. M. (1986), “A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows,” Transportation Research Part B, Vol. 20, pp. 243-257.
35.Madsen, O. B. G., Ravn, H. F. and Rygaard, J. M. (1995), “A heuristic algorithm for the a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, pp. 193–208.
36.Masson,R.,Lehuede,F. and Peton,O. (2012), “The dial-a-ride problem with transfers.” Computers and Operations Research, submitted.
37.Osman, H. (1993), “Metastrategy Simulated Annealing and Tabu Search Algorithms for t he Vehicle Routing Problem,” Annals of Operations Research, Vol. 41 , pp. 421-451.
38.Psaraftis, Harilaos N. (1980), “A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem,” Transportation Science,Vol. 14, pp. 130–154.
39.Psaraftis, Harilaos N. (1983), “An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science,Vol. 17, pp. 351–357.
40.Ropke,S., Cordeau, J.F. and Laporte, G. (2007), “Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows,” Networks,Vol. 49, pp. 258–272.
41.Sexton T, and Bodin, L.D. (1985a), “Optimizing single vehicle many-to-many operations with desired delivery times: I. Scheduling,” Transportation Science,Vol. 19, pp. 378–410.
42.Sexton, T. and Bodin, L.D. (1985b), “Optimizing single vehicle many-to-many operations with desired delivery times: II. Routing,” Transportation Science,Vol. 19, pp. 411–435.
43.Taillard, E. D. (1993), “Parallel Iterative Search Methods for Vehicle Routing Problem,”Networks, vol. 23, pp. 661-67.
44.Toth, P. and Vigo, D. (1996), “Fast local search algorithms for the handicapped persons transportation problem,” In I. H. Osman and J. P. Kelly (Eds.), Meta-heuristics: theory and applications, pp. 677–690.
45.Toth, P. and Vigo, D. (1997), “Heuristic algorithms for the handicapped persons transportation problem,” Transportation Science, Vol. 31, pp. 60–71.
46.Toth ,P. and Vigo, D. (2003), “The granular tabu search and its application to the vehicle-Routing Problem,” Journal on Computing , vol. 15, pp. 333-346.
47.Wolfler, C. R. and Colorni, A. (2002), “An approximation algorithm for the dial-a-ride problem,” (submitted for publication).
48.Yoshimura,M.,Okumura,M. and  Isozaki.A. (2005), “OPTIMAL FARE ARRANGEMENT AND OPERATIONS FOR DEMAND RESPONSIVE BUS SYSTEM IN SUBURBS.” Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 457 – 466.
49.Yurtkuran,A. and Emel E. (2014), “Efficient Constraint Handling in Electromagnetism-Like Algorithm for Traveling Salesman Problem with Time Windows,” The Scientific World Journal.