偏鄉地區的年長者與身心障礙人士由於公共運輸車站設置距離過遠或是班次時間無法配合，導致外出就醫感到不便，因此傾向自行駕駛私人機動運具前往。然而由於駕駛技術退化容易引發交通事故，往往形成社會問題。有鑑於此，各國政府紛紛推行副大眾運輸服務，以提升年長者與身心障礙人士就醫回診的便利性。目前，台灣政府推行長照十年計畫2.0，提供有長期照護需求和身心障礙人士申請復康巴士交通接送服務。
我們藉由實際參與花蓮縣復康巴士的接送流程，將針對復康巴士的預約服務流程與車輛調度問題進行探討。目前車輛調度中心仍然仰賴人工根據經驗決定復康巴士如何派遣，在這樣的方法下我們發現：1. 派遣過多的車輛執行接送服務2. 許多未乘載使用者的趟次，產生無效里程3. 使用者無法立刻得知是否成功預約服務。本研究將原本調度中心的車輛派遣方法改善，並且設計成演算法，同時結合Open Source Routing Machines (OSRM)的路徑規劃資料，進行系統化調度。如此一來，可以降低車輛派遣數量和無效里程，也能夠即時告知使用者預約是否成功。使得復康巴士交通接送服務更加有效率。我們取得花蓮門諾基金會2016年6月至12月期間復康巴士的交通接送資料，作為系統模擬的對象。在相同需求的情況下重新指派，只要使用到原本52.89%的復康巴士，節省下來的車輛可以再重新投入服務。無效里程則減少51.73%讓行駛成本得以降低。

In rural regions it can be very hard and inconvenient for elderly and disabled people to find transportation service to and from medical treatment because of a lack of public transportation infrastructure and long distances between landmarks even if they use their own vehicles. Those elderly and disabled people who choose to drive private vehicles usually suffer from the degradation of their driving skill that might cause traffic accidents and generate many social losses. Therefore, many governments in the world developed “Paratransit” to elevate the convenience of going out for medical treatment for elderly and disabled people. Currently, Taiwan’s government also promotes “Paratransit” in its Long-Term Care 2.0.
We examined the Hualien rehabilitation bus transportation service reservation process and its current vehicle dispatching system. We obtained data from the Hualien Mennonite Foundation from June 2016 to December 2016. As of now, the dispatching center in Hualien still relies on a human centric dispatching system to accept reservations then assign rehabilitation bus routes with experience. We found three fundamental inefficiencies with this system: 1. They dispatched too much many vehicles to serve demands; 2. It generated excess dead mileage (distance traveled without passengers); 3. Users couldn’t receive immediate reservation confirmation.
Our research improved the dispatching center’s efficiency by implementing a system that is based on a mathematical algorithm. This study also integrated the Open Source Routing Machines (OSRM) route planning data to execute our systemic dispatching process. The results shown that this proposed system successfully reduced number of vehicles used, dead mileage(s), and integrated immediate reservation confirmation. The systemic dispatching system made the rehabilitation bus service process more efficient by using only 52.89% of the total vehicles and reducing dead mileage by 51.73% over the old human centric system.

Acknowledgements…………………………………………………………………...……I
中文摘要………………………………………………………………………………........II
Abstract...………………………………………………………………………………...III
Contents……………………………………………………………………………….......IV
Chapter 1 Introduction………………………………………………………………1
1.1 Background and Motivation……………………………………………1
1.2 Research Purpose………………………………………………………………..4
1.3 Data description………………………………………………………………..4
1.4 Research Methodology…………………………………………………………5
1.5 Research Framework………………………………………………………………5
Chapter 2 Literature Review…………………………………………………7
2.1 Long-term care………………………………………………………………....7
2.2 Dial-A-Ride Problem……………………………………………………………9
2.2.1 Definition of VRP……………………………………………………………9
2.2.2 Time Windows Static and Dynamic Problem…………………………..10
2.3 Dispatching System……………………………………………………………18
2.3.1 Taxi Dispatching System……………………………………………………18
2.3.2 Paratransit Dispatching System…………………………………19
2.4 Comments on the Literature…………………………………21
Chapter 3 Model Formulation………………………………………………23
3.1 Problem Statement…………………………………………………………23
3.2 Demand………………………………………………………………………….....25
3.3 Demand Distribution……………………………………………………28
3.4 OpenStreetMap………………………………………………………………….31
3.5 Model Assumption………………………………………………………..32
3.6 Dispatch Algorithm…………………………………………………….36
3.6.1 Carpooling…………………………………………………….36
3.6.2 Carpool Extra Bound Time……………………………………………….39
3.6.3 Parameter and constraint……………………………………………….40
3.6.4 Pseudocode……………………………………………………………….42
3.7 Total Travel Distance………………………………………………44
3.8 Dead Mileage…………………………………………………………………….44
Chapter 4 Computational Result…………………………………….47
4.1 Data Collection…………………………………………………………….47
4.2 Results…………………………………………………………………………....49
4.2.1 Total Vehicles Used………………………………………………………...50
4.2.2 Total Travel Distance……………………………………………………….52
4.2.3 Dead Mileage/Fuel………………………………………………54
Chapter 5 Conclusions and Suggestion………………………………………………...57
5.1 Conclusion……………………………………………………………57
5.2 Research Limitations……………………………………………58
5.3 Suggestions for Future Research……………………………………59
References………………………………………………………………...........61

Aldaihani, M., & Dessouky, M. M. (2003). Hybrid scheduling methods for paratransit operations. Computers & Industrial Engineering, 45(1), 75-96.
Ombuki, B., Ross, B. J., & Hanshar, F. (2006). Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, 24(1), 17-30.
Cardoso, P. J., Schütz, G., Mazayev, A., Ey, E., & Corrêa, T. (2015). A solution for a real-time stochastic capacitated vehicle routing problem with time windows. In Procedia Computer Science, International Conference On Computational Science, ICCS 2015—Computational Science at the Gates of Nature (Vol. 51, pp. 2227-2236). Elsevier.
Ting, C. J., & Chen, C. H., (2005). Solving the Vehicle Routing Problem with Time Windows Using Ant Algorithm. Journal of the Chinese Institute of Transportation. , 17(3), 261-280.
Colorni, A., & Righini, G. (2001). Modeling and Optimizing Dynamic Dial‐a‐Ride Problems. International transactions in operational research, 8(2), 155-166.
Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.
Cordeau, J. F., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of operations research, 153(1), 29-46.
Coslovich, L., Pesenti, R., & Ukovich, W. (2006). A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. European Journal of Operational Research, 175(3), 1605-1615.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., & Soumis, F. (2002). VRP with Pickup and Delivery The Vehicle Routing Problem (pp. 225-242).
Fu, L. (2002). Scheduling dial-a-ride paratransit under time-varying, stochastic congestion. Transportation Research Part B: Methodological, 36(6), 485-506.
Fu, L. (2002). A simulation model for evaluating advanced dial-a-ride paratransit systems. Transportation Research Part A: Policy and Practice , 36(4), 291-307.
Jaw, J. J., Odoni, A. R., Psaraftis, H. N., & Wilson, N. H. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological, 20(3), 243-257.
Jorgensen, R. M., Larsen, J., & Bergvinsdottir, K. B. (2007). Solving the dial-a-ride problem using genetic algorithms. Journal of the operational research society, 58(10), 1321-1331.
Jung, J., Jayakrishnan, R., & Park, J. Y. (2016). Dynamic Shared‐Taxi Dispatch Algorithm with Hybrid‐Simulated Annealing. Computer‐Aided Civil and Infrastructure Engineering, 31(4), 275-291.
Seow, K. T., Dang, N. H., & Lee, D. H. (2010). A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, 7(3), 607-616.
McCall, N. (2001). Long Term Care: Definition, Demand, Cost, and Financing. Who Will Pay for Long-term Care.
Ministry of Health and Welfare. (2016). Long-term care 2.0 plan.
Toth, P., & Vigo, D. (1996). Fast local search algorithms for the handicapped persons transportation problem. In Meta-Heuristics (pp. 677-690). Springer, Boston, MA.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010). Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research, 37(6), 1129-1138.
Rekiek, B., Delchambre, A., & Saleh, H. A. (2006). Handicapped person transportation: An application of the grouping genetic algorithm. Engineering Applications of Artificial Intelligence, 19(5), 511-520.
Satoshi, S. (2013). The Future of Long-term Care in Japan.
Prakash, S., Balaji, B. V., & Tuteja, D. (1999). Optimizing dead mileage in urban bus routes through a nondominated solution approach. European Journal of Operational Research, 114(3), 465-473.
Schulz, E. (2010). The Long-Term Care System in Germany.
Wang, H., Lee, D. H., & Cheu, R. (2009, August). PDPTW based taxi dispatch modeling for booking service. In Natural Computation, 2009. ICNC'09. Fifth International Conference on (Vol. 1, pp. 242-247). IEEE.
Zidi, I., Zidi, K., Mesghouni, K., & Ghedira, K. (2011). A multi-agent system based on the multi-objective simulated annealing algorithm for the static dial a ride problem. In 18th World Congress of the International Federation of Automatic Control (IFAC), Milan (Italy).