(18.204.227.34) 您好!臺灣時間:2021/05/19 07:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:簡銘頡
研究生(外文):Ming-Chieh Chien
論文名稱:Q-Learning演算法於求解自助式單車租賃系統
論文名稱(外文):Applying Q-learning Algorithm to the Shift Routing Problem of Self-service Bike Rental System
指導教授:林勢敏林勢敏引用關係
指導教授(外文):Shyh-ming Lin
學位類別:碩士
校院名稱:國立屏東科技大學
系所名稱:工業管理系所
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:101
語文別:中文
論文頁數:71
中文關鍵詞:多站點自助式單車租賃系統車輛途程問題Q-Learning演算法
外文關鍵詞:Self-service bike rental systemVehicle routing problemQ-learning algorithm
相關次數:
  • 被引用被引用:1
  • 點閱點閱:436
  • 評分評分:
  • 下載下載:71
  • 收藏至我的研究室書目清單書目收藏:0
本研究旨在利用Q-Learning演算法來解決都會區多站點自助式單車租賃系統的單車運補途程問題並驗證Q-Learning演算法是否能顯著改善現今業者和林勢敏及蔡育盛(2011)提出單車運補途程規劃方法的效能。近幾年受全球暖化問題日趨嚴重的影響,低碳排、友善環境的大眾交通工具因此而大受歡迎,先進國家如法國、奧地利、瑞典等為達節能減碳目的,陸續建構都會區多站點自助式單車租賃系統,以滿足短程通勤或休閒觀光人士的需求。國內的高雄市及台北市亦有類似系統的設置。這些租賃系統均具備共同的特性,包括:(1)自助服務;(2)多租賃站點散佈在城市中;(3)提供甲地租車乙地還車;(4)每個租賃站點單車及歸還空位的數量固定。這些特性使得某些租賃站點易發生民眾租不到單車或無法還單車的狀況,須要運補車輛在站點間調運單車,以滿足民眾租車及還車的需求。這樣的系統若未採用系統化的途程規劃方式,仍然會有民眾需求無法滿足及營運成本過高的問題。本研究以高雄市的單車租賃系統為例,以實驗法驗證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.

目錄
摘要 I
Abstract III
謝誌 V
表目錄 VIII
圖目錄 IX
1. 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.2 研究範圍與限制 3
1.4 研究使用設備 4
1.5 論文架構 4
2. 文獻探討 6
2.1 都會區單車租賃系統 6
2.2 車輛途程問題 13
2.2.1動、靜態車輛問題 16
2.2.2 隨機車輛途程問題 19
2.2.3 同時處理收貨與送貨車輛途程問題 23
2.3 Q-Learning演算法 24
2.4 小結 28
3. 問題陳述 30
3.1 單車租賃系統的現況及研究問題特性 30
3.2 研究架構 35
3.3 數學模型建立 36
3.4 問題假設與限制 39
4.研究方法 40
4.1 單車租賃系統供需運補求解流程 40
4.2 Q-Learning演算法求解步驟 44
5. 實驗環境建立與設計 46
5.1 實驗模擬系統的建立 46
5.2 研究之效能指標 47
5.3 實驗參數設定 48
5.4 Q-Learning於運補途程規劃最佳參數設計 52
5.5 實驗設計 54
6. 實驗結果與討論 57
6.1 實驗結果 57
6.2 實驗結果討論 60
7. 結論與未來研究方向 62
7.1 結論 62
7.2 未來研究方向 63
參考文獻 64

周昭平. (2012a). 一卡通後租用量飆公共單車站擬擴300點捷運站2公里內設置 增接駁功能. 蘋果日報 Retrieved 12/05, 2012, from http://tw.nextmedia.com/applenews/article/art_id/34051770/IssueID/20120226/applesearch/
周昭平. (2012b). 一卡通租單車 月增萬人. 蘋果日報 Retrieved 12/05, 2012, from http://tw.nextmedia.com/applenews/article/art_id/33943549/IssueID/20120107
周昭平. (2012c). 高捷一卡通可租公共單車比信用卡安全 借車3分鐘搞定. 蘋果日報 Retrieved 12/05, 2012, from http://tw.nextmedia.com/applenews/article/art_id/33856103/IssueID/20111201/applesearch/
周昭平. (2012d). 單月10萬次 公共單車使用量新高. 蘋果日報 Retrieved 12/05, 2012, from http://appledaily.com.tw/appledaily/article/headline/20121006/34556832
林怡甄. (2003). 隨機救援之含時窗限制車輛途程規劃問題探討. 碩士論文, 中華大學, 新竹市.
林勢敏, 黃仲韻, &; 鄭秋龍. (2010). 都會區多站點自助式單車租賃系統之動態供需運補問題研究. 2010北京科技大學-屏東科技大學學術研討會.
林勢敏, &; 蔡育盛. (2011). 運用基因演算法於單車租賃系統供需運補問題之研究. 2010國立勤益科技大學-永續經營與發展研討會.
侯承旭. (2008). 里昂自行車租借系統. 自由時報 Retrieved 12/05, 2012, from http://www.libertytimes.com.tw/2008/new/apr/8/today-south24.htm
柯景文. (2002). 禁忌收尋法於動態車輛巡迴路線問題之研究. 碩士論文, 逢甲大學, 台中市.
. 高雄市公共腳踏車資訊網. (2012) Retrieved 12/21, 2012, from http://www.c-bike.com.tw/NewsShow.aspx?nid=206
張立蓁. (2010). 都會區公共自行車租借系統之設計與營運方式研究. 碩士論文, 國立成功大學, 台南市.
張清濱. (2008). 動態車輛路線巡迴問題之數學模式與建構. 碩士論文, 國立成功大學, 台南市.
張斌, &; 朱晨. (2009). 杭州力建公共自行車租賃系統. 解放日報 Retrieved 12/05, 2012, from http://big5.cnfol.com/big5/news.cnfol.com/090907/101,1281,6479958,00.shtml
許玉欣. (2007). 隨機需求下車輛配送規劃問題之研究-區域概念規劃模式與解法. 碩士論文, 國立成功大學, 台南市.
郭顏慧. (2012). 省油錢!借免費單車 每天多300人. 自由時報 Retrieved 12/05, 2012, from http://tw.news.yahoo.com/%E7%9C%81%E6%B2%B9%E9%8C%A2-%E5%80%9F%E5%85%8D%E8%B2%BB%E5%96%AE%E8%BB%8A-%E6%AF%8F%E5%A4%A9%E5%A4%9A300%E4%BA%BA-202948555.html
陳菁萍, &; 郭倩瑜. (2010). 高雄地區接駁型公共自行車租賃系統探討. 生活科技教育, 43(6), 51-62.
. 維基百科. (2012) Retrieved 02/18, 2012, from http://zh.wikipedia.org/wiki/%E9%AB%98%E9%9B%84%E5%B8%82%E5%85%AC%E5%85%B1%E8%85%B3%E8%B8%8F%E8%BB%8A%E7%A7%9F%E8%B3%83%E7%B3%BB%E7%B5%B1#.E6.AD.B7.E5.8F.B2
環球雜誌. (2009). 用自行車改變城市生態. 環球雜誌20090617.
Bodin, L. (1981). The state of the art in the routing and scheduling of vehicles and crews (Vol. 1): Office of Policy Research, Urban Mass Transportation Administration.
Bodin, L., &; S. Kursh. (1979). A detailed Description of a Street Sweeper Routing and Scheduling System. Computers &; Operations Research, 6, 191-198.
Bonnette, B. (2007). The Implementation of a Public-Use Bicycle Program in Philadelphia.
Caggiani, L., &; Ottomanelli, M. (2012). A modular soft computing based method for vehicles repositioning in bike-sharing systems. Procedia - Social and Behavioral Sciences 54, 675-684.
Cheung, R. K., &; Powell, W. B. (1996). An algorithm for multistage dynamic networks with random arc capacities, with an application to dynamic fleet management. Operations Research, 951-963.
Dantzig, G. B., &; Ramser, J. H. (1959). The truck dispatching problem. Management science, 80-91.
DeMaio, P. (2008). The Bike-sharing Phenomenon - The History of Bike-sharing. Carbusters Magazine, 36, 12.
DeMaio, P. (2009). Bike-sharing: Its History, Models of Provision, and Future.
Dror, M., Laporte, G., &; Louveaux, F. V. (1993). Vehicle routing with stochastic demands and restricted failures. Mathematical Methods of Operations Research, 37(3), 273-283.
Erlanger, S. (2008). A New Fashion Catches On in Paris: Cheap Bicycle Rentals Retrieved Dec 20, 2012, from http://www.nytimes.com/2008/07/13/world/europe/13paris.html
Fisher, M. L., &; Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gendreau, M., Laporte, G., &; Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12.
Gifford, J., &; Campus, A. (2004). Will smart bikes succeed as public transportation in the United States? Center for Urban Transportation Research, 7(2), 1.
Ho, W., Ho, G. T. S., Ji, P., &; Lau, H. C. W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548-557.
Hvattum, L. M., Lokketangen, A., &; Laporte, G. (2004). A heuristic solution method to a stochastic vehicle routing problem.
Kenyon, A. S., &; Morton, D. P. (2003). Stochastic vehicle routing with random travel times. Transportation Science, 37(1), 69-82.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
Laporte, G., Louveaux, F. V., &; Van Hamme, L. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 415-423.
Mak, K., &; Guo, Z. (2004). A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows.
Martín H, J. A., de Lope, J., &; Maravall, D. (2011). Robust high performance reinforcement learning through weighted k-nearest neighbors. Neurocomputing, 74(8), 1251-1259.
Martens, K. (2007). Promoting bike-and-ride: The Dutch experience. Transportation Research Part A: Policy and Practice, 41(4), 326-338.
Midgley, P. (2009). The role of smart bike-sharing systems in urban mobility. JOURNEYS, 2, 23-31.
Minis, I., &; Tatarakis, A. (2011). Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence. European Journal of Operational Research, 213(1), 37-51.
Noland, R. B., &; Ishaque, M. M. (2006). Smart bicycles in an urban area: Evaluation of a pilot scheme in London. Journal of Public Transportation, 9(5), 71.
Novoa, C., &; Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 196(2), 509-515.
Psaraftis, H. N. (1988). Dynamic vehicle routing problems. Vehicle routing: Methods and studies, 16, 223-248.
Psaraftis, H. N. (1995). Dynamic vehicle routing: Status and prospects. annals of Operations Research, 61(1), 143-164.
Reimann, M. (2005). Analyzing a vehicle routing problem with stochastic demands using ant colony optimization. Advanced OR and AI Methods in Transportation, Publishing House of Poznan University of Technology, 764-769.
Rodhe, H. (1990). A comparison of the contribution of various gases to the greenhouse effect. science, 248(4960), 1217.
Rosenthal, E. (2012). To Encourage Biking, Cities Lose the Helmets Retrieved Dec, 20, 2012, from http://www.nytimes.com/2012/09/30/sunday-review/to-encourage-biking-cities-forget-about-helmets.html?pagewanted=all&;_r=0
Scott, D. (2010). Vancouver's Public Bicycle System.
Secomandi, N. (2001). A rollout policy for the vehicle routing problem with stochastic demands. Operations Research, 796-802.
Shaheen, S. A., Guzman, S., &; Zhang, H. (2010). Bikesharing in Europe, the Americas, and Asia. Transportation Research Record: Journal of the Transportation Research Board, 2143(-1), 159-167.
Shaheen, S. A., Zhang, H., Martin, E., &; Guzman, S. (2011). Hangzhou public bicycle: understanding early adoption and behavioral response to bikesharing in Hangzhou, China.
Sutton, R. S. (1996). Generalization in reinforcement learning: Successful examples using sparse coarse coding. Advances in neural information processing systems, 1038-1044.
Sutton, R. S., &; Barto, A. G. (1998). Reinforcement learning: An introduction (Vol. 28): Cambridge Univ Press.
Tan, K., Cheong, C., &; Goh, C. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of Operational Research, 177(2), 813-839.
Teknomo, K. (2005). Q-Learning Numerical Example Retrieved Dec 20, 2012, from http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/Q-Learning-Example.htm
Van Breedam, A. (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86(3), 480-490.
Van Woensel, T., Kerbache, L., Peremans, H., &; Vandaele, N. (2003). A vehicle routing problem with stochastic travel times. European Journal of Operational Research, 183(3), 870-882.
Van Woensel, T., Kerbache, L., Peremans, H., &; Vandaele, N. (2008). Vehicle routing with dynamic travel times: A queueing approach. European Journal of Operational Research, 186(3), 990-1007.
Vogel, P., Greiser, T., &; Mattfeld, D. C. (2011). Understanding Bike-Sharing Systems using Data Mining: Exploring Activity Patterns. Procedia-Social and Behavioral Sciences, 20, 514-523.
Vogel, P., &; Mattfeld, D. (2010). Modeling of repositioning activities in bike-sharing systems. Paper presented at the World Conference on Transport Research (WCTR).
Wang, Y. C., &; Usher, J. M. (2005). Application of reinforcement learning for agent-based production scheduling. Engineering Applications of Artificial Intelligence, 18(1), 73-82.
Waters, C. (1989). Vehicle-scheduling problems with uncertainty and omitted customers. Journal of the Operational Research Society, 1099-1108.
Watkins, C. J. C. H. (1989). Learning from delayed rewards. Machine learning, 8(2), 242-255.
Watkins, C. J. C. H., &; Dayan, P. (1992). Q-learning. Machine learning, 8(3), 279-292.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top