Q-Learning演算法於求解自助式單車租賃系統

Applying Q-learning Algorithm to the Shift Routing Problem of Self-service Bike Rental System

簡銘頡(Ming-Chieh Chien)

指導教授 ： 林勢敏

國立屏東科技大學/管理學院/工業管理系所/碩士(2013年)

https://doi.org/10.6346/NPUST.2013.00061

摘要

本研究旨在利用Q-Learning演算法來解決都會區多站點自助式單車租賃系統的單車運補途程問題並驗證Q-Learning演算法是否能顯著改善現今業者和林勢敏及蔡育盛(2011)提出單車運補途程規劃方法的效能。近幾年受全球暖化問題日趨嚴重的影響，低碳排、友善環境的大眾交通工具因此而大受歡迎，先進國家如法國、奧地利、瑞典等為達節能減碳目的，陸續建構都會區多站點自助式單車租賃系統，以滿足短程通勤或休閒觀光人士的需求。國內的高雄市及台北市亦有類似系統的設置。這些租賃系統均具備共同的特性，包括：(1)自助服務；(2)多租賃站點散佈在城市中；(3)提供甲地租車乙地還車；(4)每個租賃站點單車及歸還空位的數量固定。這些特性使得某些租賃站點易發生民眾租不到單車或無法還單車的狀況，須要運補車輛在站點間調運單車，以滿足民眾租車及還車的需求。這樣的系統若未採用系統化的途程規劃方式，仍然會有民眾需求無法滿足及營運成本過高的問題。本研究以高雄市的單車租賃系統為例，以實驗法驗證Q-Learning演算法在單車租賃系統最佳運補途程規劃的表現。並將結果與現今業者經驗法則及蔡育盛的基因演算法進行比較。實驗結果顯示，本研究所提出之方法在運補成本及滿足民眾租車及還車需求上均比另兩種方法有顯著的改善效果。

關鍵字

多站點自助式單車租賃系統 ； 車輛途程問題 ； Q-Learning演算法

並列摘要

This study applied the Q-learning algorithm to solve the shift routing problem of self-service bike rental system and further assessed the performance of Q-learning compared to the approach in use and the approach proposed by Tsai (2012). The global warming problem in recent years gets more and more serious. As a result, low carbon and environment friendly public transport system become more and more popular. Some countries, such as France, Denmark and Austria, have developed their automated bike rental systems for short distance commuters, exercisers and tourists in metropolis. In Taiwan, major cities, Taipei and Kaohsiung for example, have also installed similar system. Those bike rental systems can be characterized commonly as follows: (1) The system is a self service system; (2) Multiple rental stations are scattered over the city; (3) Every station has a fixed amount of bikes and parking spaces; (4) People can rent a bike at one station and return it at another. Those characteristics make the bikes or parking spaces very likely unavailable at most frequently used stations. A vehicle therefore has to shift bikes among the stations to satisfy consumers' demands of renting or returning bikes. However, if a systematic approach is not employed to optimize the vehicle supply route, the cost of shift routing operation is not minimized and the demands are still far from satisfied. To evaluate the performance of Q-learning in the shift routing problem of self-service bike rental system, this study took the Kaohsiung's system as an example and executed some experiments on it. The experimental results demonstrated that our proposed approach outperforms Tsai's and is effective in solving the bike shift routing problem of multi-station bike rental system.

並列關鍵字

Self-service bike rental system ； Vehicle routing problem ； Q-learning algorithm

參考文獻

陳菁萍, & 郭倩瑜. (2010). 高雄地區接駁型公共自行車租賃系統探討. 生活科技教育, 43(6), 51-62.

張立蓁. (2010). 都會區公共自行車租借系統之設計與營運方式研究. 碩士論文, 國立成功大學, 台南市.

張清濱. (2008). 動態車輛路線巡迴問題之數學模式與建構. 碩士論文, 國立成功大學, 台南市.

許玉欣. (2007). 隨機需求下車輛配送規劃問題之研究－區域概念規劃模式與解法. 碩士論文, 國立成功大學, 台南市.

Bodin, L., & S. Kursh. (1979). A detailed Description of a Street Sweeper Routing and Scheduling System. Computers & Operations Research, 6, 191-198.