撥召系統 (Dial-a-ride system) 屬於副大眾運輸 (Paratransit) 之子系統，近年來逐漸受政府機關的重視及使用者的注意，相較於傳統大眾運輸較適合需求量大且密集之區域，撥召系統主要在郊區及偏遠地區或提供轉乘大眾運輸系統之接駁服務，一般而言，撥召系統每人成本較高但服務水準較佳。在撥召運輸系統路網建構的過程中，通常若僅追求成本最小，而未考慮服務可靠度，當旅行時間或旅客服務時間因隨機因素而增加時，抵達該路線後續其他旅客之時間容易超過最晚可服務時間，導致整體服務可靠度下降。本研究考慮具有硬時間窗之撥召問題，提出一創新的演算法，於構建車輛路徑與排程階段，同時納入運輸成本與服務可靠度，以產生一個強健 (robust) 的班表。在測試階段，以標準測試範例作為需求點位置資料，透過演算法產生班表，再以模擬方式產生兩點間的隨機旅行時間，比較同時考量運輸成本與服務可靠度之演算法與僅考量運輸成本演算法所建構的班表，結果發現在隨機旅行時間下，同時考量運輸成本與服務可靠度之演算法所建構的路徑能有效降低因旅行時間增加而超出最晚可服務時間之比例；此外，若提高服務可靠度目標的權重，超出旅客時間窗最晚可服務時間限制之比例將隨之下降，整體班表可靠度隨之提升。

Dial-a-ride system, a sub-system of paratransit transportation, is drawing more and more attention by public and government agencies due to population ageing problem. The system mainly provides pickup and delivery service for passengers in suburbs and remote areas or districts with less public transportation availability and efficiency. In general, dial-a-ride system has higher transportation cost per person but more reliable service quality. In order to save more cost while constructing a dial-a-ride network, the slack time of individual passenger nodes in routes is usually consumed to the lowest extent so that more nodes could be serviced with least number of routes. However, the slack time deficiency of nodes results in increasing time window violations in route and decreasing service reliability when travel times are fluctuating. Therefore, we propose a dial-a-ride problem (DARP) with hard time window that considers the tradeoff between transportation cost and service reliability objectives. Then we develop an innovative insertion heuristics to solve the proposed problem, constructing a robust dial-a-ride route schedule. The proposed heuristic is tested on standard instance. After route construction, we conducts a set of simulations to compare the route schedule constructed by the proposed heuristic with the classical heuristic which only considers transportation cost objective under stochastic travel times. The simulation results show that the route built by the proposed heuristic could effectively decrease the percentage of time window violation of nodes caused by stochastic travel times. Furthermore, the higher the weight the proposed heuristic places on service reliability objective, the more significant improvement in percentage of time window violations the route will have, the service reliability raises accordingly.

1. Ando, N., & Taniguchi, E. (2006). Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows. Networks and Spatial Economics, 6(3), 293-311.
2. Bruni, M. E., Guerriero, F., & Beraldi, P. (2014). Designing robust routes for demand-responsive transport systems. Transportation Research Part E: Logistics and Transportation Review, 70, 1-16.
3. Charnes, A., & Cooper, W. W. (1959). Chance-constrained programming. Management science, 6(1), 73-79.
4. Chassaing, M., Fleury, G., Duhamel, C., & Lacomme, P. (2016). Determination of robust solutions for the DARP with variations in transportation time. IFAC-PapersOnLine, 49(12), 943-948.
5. Chevrier, R., Liefooghe, A., Jourdan, L., & Dhaenens, C. (2012). Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport. Applied Soft Computing, 12(4), 1247-1258.
6. Cook, T. M., & Russell, R. A. (1978). A simulation and statistical analysis of stochastic vehicle routing with timing constraints. Decision sciences, 9(4), 673-687.
7. Cortés, C. E., Sáez, D., Milla, F., Núñez, A., & Riquelme, M. (2010). Hybrid predictive control for real-time optimization of public transport systems’ operations based on evolutionary multi-objective optimization. Transportation Research Part C: Emerging Technologies, 18(5), 757-769.
8. Detti, P., Papalini, F., & Lara, G. Z. M. d. (2017). A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega, 70, 1-14.
9. Ehmke, J. F., Campbell, A. M., & Urban, T. L. (2015). Ensuring service levels in routing problems with time windows and stochastic travel times. European Journal of Operational Research, 240(2), 539-550.
10. Firat, M., & Woeginger, G. J. (2011). Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. Operations Research Letters, 39(1), 32-35.
11. Firew, T. (2016). Analysis of Service Reliability of Public Transportation in the Helsinki Capital Region: The Case of Bus Line 550. (Master of Science in Technology), Aalto University, P.O. BOX 11000, 00076 AALTO, (ENG3036)
12. Fu, L. (1999). Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time. Transportation Research Record: Journal of the Transportation Research Board(1666), 74-81.
13. Fu, L. (2002). Scheduling dial-a-ride paratransit under time-varying, stochastic congestion. Transportation Research Part B: Methodological, 36(6), 485-506.
14. Jain, S., Ronald, N., Thompson, R., & Winter, S. (2017). Predicting susceptibility to use demand responsive transport using demographic and trip characteristics of the population. Travel Behaviour and Society, 6, 44-56.
15. 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.
16. 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.
17. Kenyon, A. S., & Morton, D. P. (2003). Stochastic vehicle routing with random travel times. Transportation Science, 37(1), 69-82.
18. Lecluyse, C., Van Woensel, T., & Peremans, H. (2009). Vehicle routing with stochastic time-dependent travel times. 4OR, 7(4), 363.
19. Lee, C., Lee, K., & Park, S. (2012). Robust vehicle routing problem with deadlines and travel time/demand uncertainty. Journal of the Operational Research Society, 63(9), 1294-1306.
20. Li, H., & Lim, A. (2003). A metaheuristic for the pickup and delivery problem with time windows. International Journal on Artificial Intelligence Tools, 12(02), 173-186.
21. Li, X., Tian, P., & Leung, S. C. H. (2010). Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics, 125(1), 137-145.
22. Lu, Q., & Dessouky, M. M. (2006). A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows. European Journal of Operational Research, 175(2), 672-687.
23. Lu, W., Lu, L., & Quadrifoglio, L. (2011, October). Scheduling multiple vehicle mobility allowance shuttle transit (m-MAST) services. In Intelligent Transportation Systems (ITSC), 2011 14th International IEEE Conference on (pp. 125-132). IEEE.
24. Mendes, R. S., & Wanner, E. F. (2016). Multiobjective Approach to the Vehicle Routing Problem with Demand Responsive Transport. 2016 IEEE Congress on Evolutionary Computation (CEC).
25. Mitrović-Minić, S., Krishnamurti, R., & Laporte, G. (2004). Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(8), 669-685.
26. Oort, N. v., & Nes, R. v. (2003). Service regularity analysis for urban transit network design. Paper presented at the Proceedings of the 82nd Annual meeting of the transportation Research Board, Washington, DC.
27. Paquette, J., Cordeau, J.-F., Laporte, G., & Pascoal, M. M. (2013). Combining multicriteria analysis and tabu search for dial-a-ride problems. Transportation Research Part B: Methodological, 52, 1-16.
28. Quadrifoglio, L., Dessouky, M. M., & Palmer, K. (2007). An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services. Journal of Scheduling, 10(1), 25-40.
29. Rosenkrantz, D. J., Stearns, R. E., & Lewis, I., Philip M. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3), 563-581.
30. Russell, R., & Urban, T. (2008). Vehicle routing with soft time windows and Erlang travel times. Journal of the Operational Research Society, 59(9), 1220-1228.
31. Taniguchi, E., R. G. Thompson, T. Yamada, J. H. R. van Duin. (2001). City Logistics: Network Modelling and Intelligent Transport Systems. Pergamon, Amsterdam.
32. Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M., Jin, Y., & Grimme, C. (2017). Dimensionality Reduction Approach for Many-Objective Vehicle Routing Problem with Demand Responsive Transport.
33. Zhang, J., Lam, W. H. K., & Chen, B. Y. (2013). A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service. Networks and Spatial Economics, 13(4), 471-496.