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

A Modified Bee Colony Optimization for the Dial-a-Ride Problem - A Case Study of Fu-Kang Bus

撥召問題是針對其有特定起迄需求的乘客設計車輛路線，與含時窗之收送貨問題的特性相似，但由於運送對象為乘客而非貨物，因此必須同時考慮乘客乘坐時間與等待時間。本研究延續魏健宏等人（2007）之主題研究，但將復康巴士問題視為撥召問題之應用，考量復康巴士營運特性，將目標函數設定為最小化總旅行時間以及總等待時間之總和，並提出包括先以子路徑插入法構建初始解，再以修正式蜂群最佳化演算法結合區域搜尋法進行廣度與深度搜尋之兩階段演算法。經由測試範例結果比較，本研究之兩階段演算法求解績效優於魏健宏等人（2007）之啟發式解法，因此具有實務應用之潛力，文末並提出未來改進的方向。

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for all defined users who specify pick-up and drop-off requests between origins and destinations. The DARP is similar to the Pickup and Delivery Problem with Time Window (PDPTW) except that commodities to be transported are substituted with passengers who require both travel times and waiting times be considered. This research tackles a special realization of the DARP called Fu-kang Bus routing problem (FKBRP) which was first studied by Wei et al. (2007) without closely elaborating it as a DARP problem. In this study, the objective function of the FKBRP is formed by summing in-vehicle times and waiting times for all travelers subject to a set of constraints. A two-stage solution algorithm is proposed. While an initial solution is constructed using the insertion method in the first stage, a modified bee colony optimization algorithm in combination with a local search method is developed to improve the initial solution in the second stage. The numerical example shows that our solution algorithm performs better than the heuristic solution algorithm proposed by Wei et al. (2007) and hence has greater potential to be applied in real situations. A few remarks conclude the paper by providing future research directions.