Translated Titles

Solving Multi-Depot Dial-a-Ride Problem by Adapted Large Neighborhood Search Algorithm





Key Words

高齡化 ; 身心障礙者 ; 多場站運輸撥召 ; ALNS演算法 ; Aging society ; the Handicapped ; Multi-depot Dial-a-Ride ; ALNS



Volume or Term/Year and Month of Publication


Academic Degree Category




Content Language


Chinese Abstract

高齡化與身心障礙者福利是近年來已開發國家面對之重要課題,根據國家發展委員會預測,我國高齡化比例將於2031年突破25%,成為超高齡社會。截至2018年底,衛生福利部統計我國身心障礙人口達1,173,978人,占總人口數比例5 %,直轄六都以台南市5.19 %位居第一。對此,我國政府陸續提出復康巴士、通用計程車、長照巴士等無障礙運輸服務,期能保障高齡與身心障礙者日常出行之權利,同時因應長照政策中基本行動力的提供。 本研究調查六都復康巴士業者與主管機關,得知目前人工排班效率不彰,每張班表花費1至3個工作天,且一旦排定便難以再做調整。另外,根據業者數與排班分區方式,營運情境可劃分成單一業者與多元業者對應至分區排班與全區排班共4種情境。對此,本研究以多場站運輸撥召問題來描述各縣市目前營運之情境,並應用ALNS演算法實作自動排班系統,以探討自動化排班基於不同營運情境所提供之效益。 實證分析中,本研究藉由小型測試案例驗證ALNS演算法與精確解之誤差控制於5 %以內。同時藉由營運資料分析,歸納出復康巴士每週之營運具高度重現性,因而實際大型案例選用台南復康巴士進行驗證,結果顯示ALNS演算法多能於10分鐘內收斂,總成本相較人工排班節省12.28 %。此外,若將多元業者整併為單一業者全區排班之情境,則可節省16.93 %,其中整併之效益有7成來自於前20 %之需求釋出。總結自動化排班能有效改善人為作業之困境,具體提升營運效率與服務水準,研究成果可作為各種無障礙運輸服務之重要參考。

English Abstract

Aging society and handicapped welfare are both crucial issues for developed and developing countries in recent years. According to National Development Council and Ministry of Health and Welfare (2018), the population of the handicapped is about 1.17 million; especially, Tainan has the highest handicapped rate among all municipalities. The aging rate has been reached 14.1%, and expected to approaching 25% when 2031, which means Taiwan will become a super-aged society. Currently, government provides handicapped bus, long-term care bus, universal taxi service to guarantee daily mobility for the handicapped. However, due to manual handling on feet management, each scheduling task takes about 1 to 3 days. This research mainly focuses on the operation of handicapped bus. It concludes four kinds of operation ways with considering company numbers and partitioning method on scheduling, while an automatic scheduling method by ALNS algorithm is developed for optimizing the operation. Two cases with small scale have been used to prove the average accuracy of solutions obtained by ALNS algorithm and exact method. It is shown that the difference between ALNS algorithm and exact solution is lower than 5%. An empirical case of Tainan handicapped bus has been conducted with its operational pattern of highly repeatability. The average compile time of ALNS algorithm is less than 10 minutes, and the solution can improve up to 12.8% compared with the solution of manual scheduling. In addition, 16.93% can be improved if it considers all the companies’ resources. It is also shown that about 70% of benefits comes from releasing the top 20% demands. Results of this study show that automatic scheduling method can effectively improve the current operation situation which can also be a good reference for formulating policy for accessible mobility.

Topic Category 工學院 > 土木工程學研究所
工程學 > 土木與建築工程
  1. 1.Braekers, K. & Kovacs, A. A. (2016). A multi-period dial-a-ride problem with driver consistency. Transportation Research Part B: Methodological, 94, 355-377.
  2. 2.Birim, Ş. (2016). Vehicle routing problem with cross docking: A simulated annealing approach. Procedia-Social and Behavioral Sciences, 235, 149-158.
  3. 3.Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.
  4. 4.Cordeau, J. F. & Laporte, G. (2003). The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), 89-101.
  5. 5.Curtois, T., Landa-Silva, D., Qu, Y. & Laesanklang, W. (2018). Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows. EURO Journal on Transportation and Logistics, 7(2), 151-192.
  6. 6.Dumas, Y., Desrosiers, J. & Soumis, F. (1991). The pickup and delivery problem with time windows. European journal of operational research, 54(1), 7-22.
  7. 7.Diana, M. & Dessouky, M. M. (2004). A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows. Transportation Research Part B: Methodological, 38(6), 539-557.
  8. 8.Hyytiä, E., Aalto, S., Penttinen, A. & Sulonen, R. (2010). A stochastic model for a vehicle in a dial-a-ride system. Operations Research Letters, 38(5), 432-435.
  9. 9.Häme, L. & Hakula, H. (2014). A maximum cluster algorithm for checking the feasibility of dial-a-ride instances. Transportation Science, 49(2), 295-310.
  10. 10.Häll, C. H., Lundgren, J. T. & Voß, S. (2015). Evaluating the performance of a dial-a-ride service using simulation. Public Transport, 7(2), 139-157.
  11. 11.Ho, S. C. & Haugland, D. (2011). Local search heuristics for the probabilistic dial-a-ride problem. Or Spectrum, 33(4), 961-988.
  12. 12.Ho, S. C., Szeto, W. Y., Kuo, Y. H., Leung, J. M., Petering, M. & Tou, T. W. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111, 395-421.
  13. 13.Heilporn, G., Cordeau, J. F. & Laporte, G. (2011). An integer L-shaped algorithm for the dial-a-ride problem with stochastic customer delays. Discrete Applied Mathematics, 159(9), 883-895.
  14. 14.Kallehauge, B., Larsen, J. & Madsen, O. B. (2005). Vehicle Routing Problem with Time Windows, chap. 3. Desaulniers G., Desrosiers J., Solomon MM: Column Generation.
  15. 15.Knight, K. W. & Hofer, J. P. (1968). Vehicle scheduling with timed and connected calls: A case study. Journal of the Operational Research Society, 19(3), 299-310.
  16. 16.Lim, A., Zhang, Z. & Qin, H. (2016). Pickup and delivery service with manpower planning in Hong Kong public hospitals. Transportation Science, 51(2), 688-705.
  17. 17.Muñoz-Carpintero, D., Sáez, D., Cortés, C. E. & Núñez, A. (2015). A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach. Transportation Science, 49(2), 239-253.
  18. 18.Marković, N., Nair, R., Schonfeld, P., Miller-Hooks, E. & Mohebbi, M. (2015). Optimizing dial-a-ride services in Maryland: benefits of computerized routing and scheduling. Transportation Research Part C: Emerging Technologies, 55, 156-165.
  19. 19.Madsen, O. B. G. (1976). Optimal scheduling of trucks-A routing problem with tight due times for delivery. Optimization applied to transportation systems, 126-136.
  20. 20.Molenbruch, Y., Braekers, K. & Caris, A. (2017). Benefits of horizontal cooperation in dial-a-ride services. Transportation Research Part E: Logistics and Transportation Review, 107, 97-119.
  21. 21.Masmoudi, M. A., Hosny, M., Braekers, K. & Dammak, A. (2016). Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. Transportation Research Part E: Logistics and Transportation Review, 96, 60-80.
  22. 22.Mauri, G. R., Antonio, L. & Lorena, N. (2009). Customers' satisfaction in a dial-a-ride problem. IEEE Intelligent Transportation Systems Magazine, 1(3), 6-14.
  23. 23.Pullen, H. G. M. & Webb, M. H. J. (1967). A computer application to a transport scheduling problem. The computer journal, 10(1), 10-13.
  24. 24.Parragh, S. N. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C: Emerging Technologies, 19(5), 912-930.
  25. 25.Potvin, J.Y., Rousseau, J.M. 1993. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research 66, 331-340.
  26. 26.Schönberger, J. (2017). Scheduling constraints in dial-a-ride problems with transfers: a metaheuristic approach incorporating a cross-route scheduling procedure with postponement opportunities. Public Transport, 9(1-2), 243-272.
  27. 27.Shen, C. W. & Quadrifoglio, L. (2012). Evaluating centralized versus decentralized zoning strategies for metropolitan ADA paratransit services. Journal of Transportation Engineering, 139(5), 524-532.
  28. 28.Santos, D. O. & Xavier, E. C. (2015). Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive. Expert Systems with Applications, 42(19), 6728-6737.
  29. 29.Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. International conference on principles and practice of constraint programming, 417-431.
  30. 30.Vincent, F. Y., Jewpanya, P., & Redi, A. P. (2016). Open vehicle routing problem with cross-docking. Computers & Industrial Engineering, 94, 6-17.
  31. 31.白峻安(2015),利用類電磁演算法求解於需求反應式撥召問題-以新北市復康巴士為例,淡江大學運輸管理學系碩士論文。
  32. 32.呂昆達(2003),反應需求式宅配車輛排程與派遣系統之建立,交通大學運輸與物流管理學系碩士論文。
  33. 33.辛孟鑫(2005),撥召運輸系統路線規劃問題之研究-以台北市復康巴士為例,成功大學交通管理科學系碩士論文。
  34. 34.李忠憲(2010),運用粒子群最佳化解決多場站之收送貨問題 ,交通大學運輸與物流管理學系碩士論文。
  35. 35.陳俊穎、蘇昭銘(2014),以接駁型需求反應式公車服務模型解決偏遠地區運輸問題之初探,都市交通半年刊,第二十九卷,第一期,第32-41頁。
  36. 36.陳菀惠等人(2009),高齡者旅運特性與就醫需求回應運輸系統需求分析,運輸學刊,第二十一卷,第三期,第329-354頁。
  37. 37.陳品齊(2017),復康巴士成本函數與經濟特性分析,臺灣大學土木工程學研究所碩士論文。
  38. 38.張學孔、張朝能、周文生、洪鈞澤等人(2018),預約式無障礙小客車運輸服務之整合研究(1/2),交通部運輸研究所與中華智慧運輸協會合作研究報告。
  39. 39.張學孔、張朝能、周文生、洪鈞澤等人(2019),預約式無障礙小客車運輸服務之整合研究(2/2),交通部運輸研究所與中華智慧運輸協會合作研究報告。
  40. 40.賈若可(2014),復康巴士營運績效評估,臺灣大學土木工程學研究所碩士論文。
  41. 41.靳蕃、範俊波、譚永東(1992)「神經網路與神經計算機」,儒林出版社。
  42. 42.蔡依靜(2012),需求反應式公共運輸服務評鑑制度之研究,臺灣大學土木工程學研究所碩士論文。
  43. 43.蔡孟儒(2013),求解動態撥召問題: 以復康巴士為例,淡江大學資訊管理學系碩士論文。
  44. 44.簡培原(2014),高齡需求反應式運輸系統之效益評估,臺灣大學土木工程學研究所碩士論文。
  45. 45.蘇昭銘、游文松(2006),單場站公路客運司機員與車輛排班問題之研究,運輸計劃季刊,第三十五卷,第二期,第131-157頁。
  46. 46.內政部戶政司全球資訊網(2019),各縣市人口年齡結構重要指標,取自:https://www.ris.gov.tw/app/portal/346.
  47. 47.衛生福利部社會及家庭署身心障礙服務入口網(2019),各直轄市、縣市政府辦理身心障礙者復康巴士服務彙整表,取自:https://dpws.sfaa.gov.tw/commonch/home.jsp?menudata=DisbMenu&contlink=ap/statistics_view.jsp&dataserno=201405300001&mserno=200805260001&serno=200805260001.
  48. 48.國家發展委員會(2019),中華民國人口推估(2018至2065年),取自:https://www.ndc.gov.tw/Content_List.aspx?n=84223C65B6F94D72.
  49. 49.衛生福利部統計處(2019),身心障礙者人數按縣市及類別分,取自:https://dep.mohw.gov.tw/DOS/lp-2976-113.html.