時窗限制下單一共用財調配問題

Time-Windowed Tool Relocation Problem of Public Tool Sharing System

金龍(Lung Chin)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701607

摘要

本研究首先定義時窗限制下單一共用財調配問題，再提出一具遺傳演算優化的共用財調配規劃系統，期望有效減少共用財服務系統中未滿足的服務。在已知各站點共用財的數量變化率下，研擬不同情境下站點的未滿足量求算方式。同時推導模擬卡車繞行各站時，各站點未滿足量的計算方法，及共用財真實調配數的設定法。本研究除了提出貪婪式的經驗求解法外，也使用遺傳演算法求解問題，並依問題的特性提出專用的急迫性及距離考量的啟發式交配法(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.

並列關鍵字

Sharing Economic ； Genetic Algorithm ； Bike Sharing

參考文獻

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