跳到主要內容

臺灣博碩士論文加值系統

(44.212.99.208) 您好!臺灣時間:2024/04/17 18:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:金龍
研究生(外文):Lung Chin
論文名稱:時窗限制下單一共用財調配問題
論文名稱(外文):Time-Windowed Tool Relocation Problem of Public Tool Sharing System
指導教授:楊烽正楊烽正引用關係
指導教授(外文):FENG-CHENG YANG
口試日期:2017-07-12
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:工業工程學研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:中文
論文頁數:135
中文關鍵詞:共享經濟遺傳演算法公共自行車系統
外文關鍵詞:Sharing EconomicGenetic AlgorithmBike Sharing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:144
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究首先定義時窗限制下單一共用財調配問題,再提出一具遺傳演算優化的共用財調配規劃系統,期望有效減少共用財服務系統中未滿足的服務。在已知各站點共用財的數量變化率下,研擬不同情境下站點的未滿足量求算方式。同時推導模擬卡車繞行各站時,各站點未滿足量的計算方法,及共用財真實調配數的設定法。本研究除了提出貪婪式的經驗求解法外,也使用遺傳演算法求解問題,並依問題的特性提出專用的急迫性及距離考量的啟發式交配法(Imminence & Distance Considered Crossover)及突變法提升遺傳演算的求解效能及品質。再將本研究的問題應用在單車共用系統並測試範例,結果顯示本研究提示的優化演算法能使卡車在給定的時窗限制內,有效改善單車共用系統的未滿足量。另一方面在測試不同染色體交配法的效能下,結果顯示採用本研究研擬的急迫性及距離考量的啟發式交配及突變法明顯優於泛用型的,也較貪婪式的經驗求解法求得更佳的繞行調配解。
This paper defines Time-Windowed Tool Relocation Problem of Public Tool Sharing System and uses genetic algorithm to construct a public tool rebalancing planning system. With this planning system we expect to reduce unfulfilled amount in public tool sharing system. We also discuss kinds of equation to calculate unfulfilled amount in different situation with public tool increasing/decreasing rate known. Besides, we simulate truck routing service station to calculate unfulfilled amount and determine pickup and delivery amount in service stations. Our research propose not only a greedy heuristic method but also genetic algorithm to solve this problem. By observing characteristic of this problem, we propose Imminence & Distance Considered crossover and mutation method to improve planning system performance. After applying this problem to bike sharing system and testing several benchmarks, the conclusion shows that our research can reduce unfulfilled amount in bike sharing system in timed windowed by rebalancing public tool effectively. Last but not least, Imminence & Distance Considered crossover and mutation method also has a better performance than canonical and greedy heuristic method.
致謝 i
中文摘要 ii
Abstract iii
圖目錄 vii
表目錄 viii
1. 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3研究方法 2
2. 文獻探討 4
2.1一般取卸貨問題 4
2.2 PDP與PDPTW問題 5
2.3 Open VRP問題 5
2.4 VRPSD問題 5
2.5卸貨後回程取貨車輛途程問題 5
2.6混合取卸貨車輛途程問題 5
2.7同步取卸貨車輛途程問題 6
2.8 1-PDTSP問題 6
2.9共用單車服務系統營運相關問題 7
2.10遺傳演算法 8
2.11小結 11
3. 時窗限制下單一共用財調配問題及遺傳演算求解法 12
3.1時窗限制下單一共用財調配問題 (Time-Windowed Tool Relocation Problem of a Public Tool Sharing System) 12
3.1.1問題描述與假設 12
3.2 TWTRP問題的貪婪式經驗求解法 27
3.3 TWTRP問題模式的遺傳演算求解法 28
3.3.1繞行途程段及調配數量段的染色體編碼 29
3.3.2染色體的適應值 29
3.3.3遺傳演算的母體初始化 29
3.3.4繞行途程段的交配及突變運算 30
3.3.5調配量段的基因交配及突變法 34
3.3.6小結 36
4.時窗限制下單一共用財調配問題的應用及求解測試 37
4.1單車調配標竿問題 37
4.2單車調配優化問題求解系統 43
4.3範例測試及效能分析 47
4.3.1單車共用系統的TWTRP範例測試與效能分析 47
4.3.2不同情境範例測試與分析 54
4.3.3小結 56
5.結論與未來研究建議 57
5.1結論 57
5.2未來研究建議 57
參考文獻 59
附錄一 61
Ubike262M標竿問題 61
附錄二 68
Ubike262A標竿問題 68
附錄三 76
Ubike262N標竿問題 76
附錄四 84
Ubike372M標竿問題 84
附錄五 94
Ubike372A標竿問題 94
附錄六 105
Ubike372N標竿問題 105
附錄七 116
CityBike217M標竿問題 116
附錄八 122
CityBike217A標竿問題 122
附錄九 129
CityBike217N標竿問題 129
Harversine 公式 135
Alvarez-Valdes, R., Belenguer, J. M., Benavent, E., Bermudez, J. D., Muñoz, F., Vercher, E., & Verdejo, F. (2016). Optimizing the level of service quality of a bike-sharing system. Omega, 62, 163-175.
Cao, E., & Lai, M. (2010). The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, 37(3), 2405-2411. doi:10.1016/j.eswa.2009.07.021
Chemla, D., Meunier, F., & Calvo, R. W. (2013). Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization, 10(2), 120-146. doi:10.1016/j.disopt.2012.11.005
Dell''Amico, M., Hadjicostantinou, E., Iori, M., & Novellani, S. (2014). The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega-International Journal of Management Science, 45, 7-19. doi:10.1016/j.omega.2013.12.001
Dib, O., Manier, M.-A., Moalic, L., & Caminada, A. (2017). Combining VNS with Genetic Algorithm to solve the one-to-one routing issue in road networks. Computers & Operations Research, 78, 420-430. doi:10.1016/j.cor.2015.11.010
Erdoğan, G., Battarra, M., & Wolfler Calvo, R. (2015). An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. European Journal of Operational Research, 245(3), 667-679. doi:10.1016/j.ejor.2015.03.043
Frade, I., & Ribeiro, A. (2015). Bike-sharing stations: A maximal covering location approach. Transportation Research Part a-Policy and Practice, 82, 216-227. doi:10.1016/j.tra.2015.09.014
Gen, M., & Cheng, R. (1997). Genetic algorithms and engineering optimization (Vol. 7). New York: John Wiley & Sons.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning (Vol. 412): Addison-wesley Reading Menlo Park.
Hernández-Pérez, H., & Salazar-González, J.-J. (2003). The one-commodity pickup-and-delivery travelling salesman problem Combinatorial Optimization—Eureka, You Shrink! (pp. 89-104): Springer.
Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Oxford, England: U Michigan Press.
Li, F., Golden, B., & Wasil, E. (2007). A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 34(9), 2734-2742. doi:10.1016/j.cor.2005.10.015
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21-51.
Syswerda, G. (1989). Uniform crossover in genetic algorithms. Paper presented at the the Third International Conference on Genetic Algorithms
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.
Zhao, F., Li, S., Sun, J., & Mei, D. (2009). Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Industrial Engineering, 56(4), 1642-1648.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top