應用ALNS演算法求解多場站運輸撥召問題之研究

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

傅宣維(Hsuan-Wei Fu)

指導教授 ： 張學孔

國立臺灣大學/工學院/土木工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201902277

摘要

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

關鍵字

高齡化 ； 身心障礙者 ； 多場站運輸撥召 ； ALNS演算法

並列摘要

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.

並列關鍵字

Aging society ； the Handicapped ； Multi-depot Dial-a-Ride ； ALNS

參考文獻

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.Birim, Ş. (2016). Vehicle routing problem with cross docking: A simulated annealing approach. Procedia-Social and Behavioral Sciences, 235, 149-158.

3.Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.

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.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.