根據台灣2010年內政部人口統計資料顯示，2006年台灣65歲以上老年人口比例為9.9%，預估於2014年該比例將上升至11.6%，台灣國家發展委員會更預測未來2061年台灣65歲以上老年人口比例高達41%，隨著老年人口比例逐年上升，老年人口之運輸需求亦隨之提高，為滿足老年人口之運輸需求，提供良好的撥召運輸系統服務為政府的重要議題，如何設計車輛路線與排程促使運輸效率之提升並節省成本是撥召運輸系統營運者最關鍵的工作項目。
縱觀撥召運輸問題研究，多數文獻考慮最小車輛旅行成本提出求解架構並建構數學模式，根據問題規模與複雜程度開發演算法或啟發式解法進行問題求解，然而，實務上撥召運輸問題的車輛路線規劃與排程，不僅考慮最小化營運成本亦應考慮顧客對於服務滿意程度，鮮少研究探討考慮顧客服務品質下求解撥召運輸問題。因此，本研究考慮顧客服務品質建構數學模式，數學模式中顧客服務品質考慮顧客平均上車延遲時間、顧客平均下車延遲時間以及顧客平均實際搭乘時間與直接搭乘時間之比值。求解演算法採用分支價格演算法進行單目標撥召運輸問題求解，並利用ε-constraint 方法同時求解兩個衝突目標: 最小總旅行時間與最小顧客平均上車延遲時間之多目標撥召運輸問題且產生柏拉圖最佳解。數值實驗部分採用交通模擬軟體DynaTAIWAN模擬實際路網車輛移動狀況以及產生依時性旅行成本矩陣，求解演算法於高雄三民區路網進行數值實驗測試。
數值實驗結果顯示顧客時窗之長短顯著地影響著車輛配送路徑與相關績效指標，當時窗長度增加，車輛總旅行時間與使用之車輛數明顯減少，然而電腦運算時間、顧客平均接送延遲時間與平均ART/DRT之數值明顯上升。撥召問題之車輛路徑設計同時滿足最小營運成本與最大顧客滿意度是件困難的工作，營運者必須於這些衝突的目標間做出權衡，設計車輛路徑。

According to census from the Ministry of The Interior in Taiwan, the number of people aged 65 and over as a proportion of the global population is 9.9% in 2006 and the government forecasts that the number of people aged 65 and over as a proportion of the global population will expand to 11.6% in 2014. National Development Council, Taiwan indicated that the number of people aged 65 and over as a proportion of the global population will increase to 41.00% in 2061. To meet the transportation demands for the elderly and handicapped people, proving the dial-a-ride systems to ensure the quality of transportation service is an important issue for governments. Well-designed vehicle routes and schedule for dial-a-ride systems can improve transportation efficiency and save total travel costs. How to design an appropriate vehicle routes and schedule is a critical work for dial-a-ride problems (DARP).
For the study of the DARP, most literatures consider the minimum travel costs to construct solution framework or formulate mathematical model and then apply appropriate algorithms or heuristic procedures to solve based on the scale and complexity of the problem. However, in practice, the DARP not only takes into account the operational costs but also the customer satisfaction. Seldom studies explore the quality of service for customers in DARP. The purpose of this paper is to consider customer satisfaction to formulate the mathematical model. In this research, the quality of service for customers are quantitated as measurable indexes including the average pickup delay time, average delivery delay time and the ratio of actual ride time to direct ride time (ART/DRT). The branch-and-price approach is applied to solve DARP with time-dependent travel costs and consideration for the service quality of customers. The ε-constraint method is introduced to consider two contradictory objectives: minimum total travel time and minimum the average pickup delay time simultaneously to obtain non-dominated solutions. The traffic simulation software, DynaTAIWAN (Hu et al., 2007) is uesd to generate time-dependent travel time matrices and simulate traffic flows in the real network. Numerical experiments are conducted in a Kaohsiung network. The numerical results reveal that the length of the time window can significantly affect the vehicle routes and quantitative measurements. As the length of the time window increases, the objective value and the number of vehicles will reduce significantly. However, the CPU time, the average pickup delay time, the average delivery delay time and the average ART/DRT will increase significantly as the length of the time window increases. Designing the vehicle routes to reduce operating costs and satisfy the requirements of customers is a difficult work, and a trade-off must be made between these goals.

Ascheuer, N., Krumke, S., and Rambau.J. (2000), “Online dial-a-ride problems: Minimizing the completion time,” Lecture Notes in Computer Science, Vol. 1770, pp. 639–650.
Berbeglia, G., Cordeau, J. -F., Gribkovskaia, I. and Lapote, G. (2007), “Static pickup and delivery problems: a classification scheme and survey,” Top, Vol. 15, No. 1, pp. 1-31.
Berbeglia, G., Cordeau, J. -F. and Laporte, G. (2011), “A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem,” INFORMS Journal on Computing, Vol. 24, No. 3, pp. 343-355.
Berbeglia, G., Cordeau, J. -F. and Laporte, G. (2010), “Dynamic pickup and delivery problems,” European Journal of Operational Research, Vol. 202, No. 1, pp. 8-15.
Braekers, K., Canis, A. and Janssens, G. K. (2014), “Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots,” Transportation Research Part B, Vol. 67, pp. 166-186.
Ceder, A. (2013), “Integrated smart feeder/shuttle transit service: simulation of new routing strategies,” Journal of Advanced Transportation, Vol. 47, No. 6, pp. 595-618.
Chen, H.-K., Hsueh, C.-F. and Chang, M.-S. (2006), “The real-time time-dependent vehicle routing problem,” Transportation Research Part E, Vol. 42, No. 5, pp. 383-408.
Coslovich, L., Pesenti, R., and Ukovich, W. (2006), “A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem,” European Journal of Operational Research, Vol. 175, No. 3, pp. 1605–1615.
Cordeau, J. -F. and Laporte, G. (2003a), “The Dial-a-Ride Problem (DARP):Variants, modeling issues and algorithms,” Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol. 1, No.2, pp. 89-101.
Cordeau, J. -F., and Laporte, G. (2003b), “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B, Vol. 37, No. 6, pp. 579–594.
Cordeau, J. -F. (2006), “A Branch-and-cut algorithm for the dial-a-ride problem,” Operations Research, Vol. 54, No. 3, pp. 573–586.
Cordeau, J. -F. and Laporte, G. (2007), “The dial-a-ride problem: models and algorithms,” Annals of Operations Research, Vol. 153, pp. 29-46.
Cortes, C.E., Saez, D., Nunez, A. and Muñoz-Carpintero, D. (2009), “Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem,” Transportation Science, Vol. 43, No. 1, pp. 27-42.
Cortes, C.E., Matamala, M. and Contardo, C. (2010), “The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method,” European Journal of Operational Research, Vol. 200, No. 3, pp. 711-724.
Dabia, S., Ropke, S., van Woensel, T. and De Kok, T. (2013), “Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 47, No. 3, pp. 380-396.
Diana, M. and Dessouky, M. M. (2004), “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B, Vol. 38, No.6, pp. 539-557.
D’Souza, C., Omkar, S. N. and Senthilnath, J. (2012), “Pickup and Delivery Problem Using Metaheuristics Techniques,” Expert Systems with Applications, Vol. 39, No. 1, pp.328-334.
Dumas, Y., Desrosiers, J. and Soumis, F. (1991), “The pickup and delivery problem with time windows,” European Journal of Operational Research, Vol. 54, No. 1, pp. 7-22.
Fabri, A. and Recht, P. (2006), “On dynamic pickup and delivery vehicle routing with several time windows and waiting times,” Transportation Research Part B, Vol. 40, No. 4, pp. 335-350.
Feuerstein, E. and Stougie, L. (2001), “On-line single-server dial-a-ride problems,” Theoretical Computer Science, Vol. 268, No. 1, pp. 91-105.
Fu, L. (2002), “Scheduling dial-a-ride paratransit under time-varying, stochastic congestion,” Transportation Research Part B, Vol. 36, No. 6, pp. 485-506.
Haghani, A. and Jung, S. (2005), “A dynamic vehicle routing problem with time-dependent travel times,” Computer & Operations Research, Vol. 32, No. 11, pp. 2959-2986.
Haimes, Y., Lasdon, L. and Wismer, D. (1971), “On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 1, No. 3, pp. 296-297.
Hu, T.Y., Liao, T.Y., Chen, L.W., Huang, Y.K., and Chiang, M.L. (2007) “Dynamic simulation-assignment model (DynaTAIWAN) under mixed traffic flows for ITS application,” In: Proceedings of 86th Transportation Research Board Annual Meeting, Washington, D.C., U.S.A.
Hu, T. Y. and Chang, C. P. (2011), “Time-Dependent Dial-a-Ride Problems: Formulation Development and Numerical Experiments,” Journal of the Eastern Asia Society for Transportation Studies, Vol. 9, pp. 690-701.
Hu, T.Y. and Chang, C.P. (2013), “Exact Algorithm for Dial-A-Ride Problems with Time-Dependent Travel Cost,” Journal of the Eastern Asia Society for Transportation Studies, Vol. 10, pp. 916-933.
Hu, T.Y. and Chang, C.P. (2014), “A revised branch-and-price algorithm for dial-a-ride problems with the consideration of time-dependent travel cost,” Journal of Advanced Transportation. Article first published online: 14 NOV 2014 DOI: 10.1002/atr.1296 (Accepted).
Institute of Transportation, Ministry of Transportation And Communication, Taiwan (2011), “Comprehensive Demand Responsive Transit Services Study (2/3)”.
Institute of Transportation, Ministry of Transportation And Communication, Taiwan (2012), “Comprehensive Demand Responsive Transit Services Study (3/3)”.
Irnich, S. and Villeneuve, D. (2006), “The shortest path problem with resource constraints and k-cycle elimination for k≥3,” INFORMS Journal on Computing, Vol. 18, No. 3, pp. 391-406.
Jabali, O., Van Woensel, T. and de Kok, A. G. (2012), “Analysis of Travel Times and CO2 Emissions in Time-Dependent Vehicle Routing,” Production and Operations Management, Vol. 21, No. 6, pp. 1060-1074.
Jaillet, P. and Wagner, M. (2008), “Online vehicle routing problems: A survey,” In B. Golden, S. Raghavan, and E.Wasil, editors, The vehicle routing problem: Latest advances and new challenges. Springer, Berlin, pp. 221–237.
Jaw, J.-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, No. 3, pp. 243-257.
Pacheco, J., Caballero, R., Laguna, M. and Molina, J. (2013), “Bi-Objective Bus Routing: An Application to School Buses in Rural Areas,” Transportation Science, Vol. 47, No. 3, pp. 397-411.
Jørgensen, R. M., Larsen, J., and Bergvinsdottir, K. B. (2007), “Solving the dial-a-ride problem using genetic algorithms,” Journal of the Operational Research Society, Vol. 58, No. 10, pp. 1321-1331.
Kim, T. and Haghani, A. (2011), “Model and Algorithm Considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem,” In: Proceedings of 87th Transportation Research Board Annual Meeting, Washington D.C., U.S.A.
Kirchler, D. and Calvo, R. W. (2013), “A Granular Tabu Search algorithm for the Dial-a-Ride Problem,” Transportation Research Part B, Vol. 56, pp. 120-135.
Laumanns, M., Thiele, L. and Zitzler, E. (2006), “An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method,” European Journal of Operational Research, Vol. 169, No. 3, pp. 932-942.
Li, H. and Lim, A. (2001), “A MetaHeuristic for the Pickup and Delivery Problem with Time Windows,” In: Proceedings of the 13th International Conference on Tools with Artificial Intelligence, Dallas, Texas, U.S.A.
Liao, T. Y., Hu, T. Y., Chen, L. W. and Ho, W. M. (2010), “Development and Empirical Study of Real-Time Simulation-Based Dynamic Traffic Assignment Model.” Journal of Transportation Engineering-Asce, Vol. 136, No. 11, pp. 1008-1020.
Lois, A., Ziliaskopoulos, A. K. and Aifantopoulou, G (2007), “A Very Large Scale Neighborhood Heuristic Algorithm for the Multivehicle Dial a Ride with Time Windows,” In: Proceedings of 87th Transportation Research Board Annual Meeting, Washington D.C., U.S.A.
Luo, Y. and Schonfeld, P. (2011), “Online Rejected-Reinsertion Heuristics for Dynamic Multivehicle Dial-a-Ride Problem,” In: Proceedings of 87th Transportation Research Board Annual Meeting, Washington D.C., U.S.A.
Madsen, O. B. G., Ravn, H. F., and Rygaard, J. M. (1995), “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, No. 1, pp. 193–208.
Malandraki, C. and Daskin, MS. (1992), “Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms,” Transportation Science, Vol. 26, No.3, pp. 185-199.
Ministry of The Interior, Taiwan (2010), “Ten years program for a long term care”: http://sowf.moi.gov.tw/newpage/tenyearsplan.htm.
National Development Council, Taiwan (2014), “Population Projections for R.O.C. (Taiwan): 2014~2060”.
Parragh, S.N., Doerner, K.F. and Hartl, R.F. (2008) “A survey on pickup and delivery problems. Part II: transportation between pickup and delivery locations,” Journal fur Betriebswirtschaft, Vol. 58, No. 2, pp. 81–117.
Paquette, J., Cordeau, J. -F. and Laporte, G. (2009), “Quality of service in dial-a-ride operations,” Computers & Industrial Engineering, Vol. 56, No. 4, pp. 1721-1734.
Paquette, J., Bellavance, F., Cordeau, J. -F. and Laporte, G. (2012), “Measuring quality of service in dial-a-ride operations: the case of a Canadian city,” Transportation, Vol. 39, No. 3, pp. 539-564.
Paquette, J., Cordeau, J. F., Laporte, G. and Pascoal, M. M. B. (2013), “Combining multicriteria analysis and tabu search for dial-a-ride problems,” Transportation Research Part B, Vol. 52, pp. 1-16.
Psaraftis, H. N. (1980), “A dynamic programming approach to the single-vehicle, many-to-many immediate request dial-a-ride problem,” Transportation Science, Vol. 14, No. 2, pp.130–154.
Psarafits, H. N. (1983), “Analysis of an O(N2) Heuristic for Many-to-many Euclidean Dial-a-ride Problem,” Transportation Research Part B, Vol. 17, No. 2, pp.133-145.
Reiter, P. and Gutjahr, W. J. (2012), “Exact hybrid algorithms for solving a bi-objective vehicle routing problem,” Central European Journal of Operations Research, Vol. 20, No. 1, pp. 19-43.
Ropke, S. (2005), “Heuristic and exact algorithms for vehicle routing problems,” Ph.D. Dissertation, the University of Copenhagen.
Ropke, S. and Pisinger, D. (2006), “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, Vol. 40, No. 4, pp. 455-472.
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, No. 4, pp. 258–272.
Ropke, S. and Cordeau, J. –F. (2009), “Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows,” Transportation Science, Vol.43, No. 3, pp.267-286.
Sheffi, Y. (1985), “Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods.” Published by: Prentice-Hall, Inc. Available online: http://mit.edu/sheffi/www/urbanTransportation.html.
Schilde, M., Doerner, K. F. and Hartl, R. F. (2014), “Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem,” European Journal of Operational Research, Vol. 238, No. 1, pp. 18-30.
Schneider, B. and White, S. S. (2004), “Service quality, research perspectives,” Sage Publications, Thousand Oaks, USA.
Shaw, P. (1997), “A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems,” Technical report, Department of Computer Science, University of Strathclyde, Scotland.
Stein, D. M. (1978), “Scheduling Dail-a-Rride Transportation Systems,” Transportation Science, Vol. 12, No. 3, pp. 232-249.
Wolsey, L. A. (1998), “Wiley-Interscience series in discrete mathematics. Integer Programming.” Wiley-Interscience, New York.
Wong, K. I., and Bell, M. G. H. (2006), “Solution of the dial-a-ride problem with multi-dimensional capacity constraints,” International Transactions in Operational Research, Vol. 13, No. 3, pp. 195–208.
Wong, K. I., Han, A. F. and Yuen, C. W. (2014), “On dynamic demand responsive transport services with degree of dynamism,” Transportmetrica a-Transport Science, Vol. 10, No. 1, pp. 55-73.
Xiang, Z., Chu, C., and Chen, H. (2006), “A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints,” European Journal of Operational Research, Vol. 174, No. 2, pp. 1117–1139.
Xiang, Z., Chu, C., and Chen, H. (2008), “The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments,” European Journal of Operational Research, Vol. 185, No. 2, pp. 534-551.