應用蜂群最佳化演算法求解撥召問題－以復康巴士為例

A bee colony optimization algorithm for the dial-a-ride problem-A case of Fu-kang bus

林奕隆(Yi-Long Lin)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2011年)

摘要

近年來台灣社會福利制度日趨健全，身心障礙者的運輸接送問題也日益受到社會大眾關注，特別是成身心障礙者及年長者的運輸服務。而撥召問題是針對具有特定起迄需求的乘客來設計車輛路線，撥召問題特性與含時窗之收送貨問題(Pickup and Delivery Problem with Time Windows, PDPTW)相似，但運送的是乘客非貨物，因此必須考慮乘客乘坐之時間。
因此，本研究必須先瞭解復康巴士問題特性，考量以乘客預期上車時間前後增減十分鐘之方式設計時窗，再以最少總旅行時間以及車輛等待時間為目標來求解復康巴士車輛途程問題。本研究以蜂群最佳化演算法(Bee Colony Optimization, BCO)為求解演算法，然後以魏健宏等人(2007)與Cordeau and Laporte (2003)之範例進行求解比較，最後提出結論與建議。

關鍵字

復康巴士 ； 撥召問題 ； 巨集啟發式演算法 ； 蜂群最佳化演算法

並列摘要

In recent years, more attention is being focused on the disabilities and elders to their transportation demand. This makes the dial-a-ride system which is provided with high accessibility and mobility an important issue in Taiwan. The dial-a-ride problem (DARP) consists of designing vehicle routes for many users who specify diversified pick-up and drop-off requests between various origins and destinations. DARP is similar to the pick-up and delivery problem with time windows, but considering passenger transportation rather than goods transportation.
In the following study, we will identify the main features of the problem associated with Fu-kang Bus’s specific routing concerns. This study focused on solving Fu-kang Bus’ problem, with minimum total travel time and waiting time. To solve the problem, meta-heuristics called bee colony optimization algorithm (BCO) are proposed. Numerical examples are presented to validate the results of the model. Finally conclusions and suggestions are presented.

並列關鍵字

Fu-kang Bus ； Dial-a-ride problem ； Meta-heuristic ； Bee Colony Optimization

參考文獻

3. 吳韻雯，「長途運輸場站共乘小巴士排程服務之研究」，中原大學土木工程學系，碩士論文，2006。

6. 馮正民、邱裕鈞，研究分析方法，建都文化事業股份有限公司，頁369-384，2004。

1. 魏健宏、王穆衡、蔡欽同、辛孟鑫，「臺北市復康巴士路線規劃問題之研究」，運輸學刊，第十九卷第三期，頁301-332，2007。

7. Attanasio, A., Cordeau, J.F., Ghiani, G., Laporte, G., “Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem,” Parallel Computing, Vol. 30, Issue 3, 2004.

11. Berbeglia, G., Pesant, G., Rousseau, L.M., Checking the feasibility of dial-a-ride instances using constraint programming, research report CIRRELT-2010-16.