隨著城市的發展，共享單車系統的出現滿足了公車、捷運等公共交通設施覆蓋不到的部分。使用者可以使用城市各地共享單車系統所提供的許多車站，從車站內租借單車騎到另一站，達成短程旅行的目的。然而隨著使用者的使用，車站就會出現單車數不足或放置單車的車樁數不足的情況，導致一部分的人無法租用或歸還自行車。車站營運的重要關鍵就是能否供應所有用戶的需求，目前已經有很多論文提出各種解決辦法，多數方案注重於減少未滿足用戶數量以及減少平衡所有車站的成本。本研究基於相同目的提出了一種新的時間窗產生方法，以及如何主動減少平衡過程中所派遣的貨車司機數量，希望可以從不同的角度來優化路徑，減少平衡車站的開銷。針對路徑規劃的部分，我們也提出了應用於可變鄰域搜索的初始解產生算法以及兩種破壞解的方法。我們使用台北Youbike的真實資料進行實驗，在生產時間窗、初始解與最佳化算法三個階段的比較都顯示我們取得了較好的表現。

With the development of cities, bicycle sharing systems appeared to cover the area that other public transportation facilities cannot cover in the city. People can take a short trip by renting and returning bikes at stations in the system, this also make a problem: some users may have no bike to rent or no place to return the bikes at peak hours. The key point of BSS operation is supplying the needs of all users, so many researches have proposed various approaches to rebalance the system. Most of them focus on the number of bicycles required by the station and minimizing the total travel distance of rebalancing trucks. As the same target, we hope to optimize the rebalancing routes by adding less considered viewpoints, so we propose a new method to generate requests with time window, and also apply the route planning algorithm based on Variable Neighborhood Search to plan the rebalancing routes of trucks. It is an iterative evolutionary algorithm which will continuously improve iteratively based on the initial solution, and perform the shaking process several times during the iteration to make the algorithm has the chance to find the global optimum. Under this framework, we also propose an algorithm to make an initial solution and two processes for shaking to make it perform better. We use real data from Youbike in Taipei to evaluate our requests generation algorithm, initial solution generation algorithm, and two shaking processes in different stages by comparing with corresponding algorithms. Experiments show that our method performs better in all aspects.

[1] 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.
[2] Belhaiza, S. (2016). A game theoretic approach for the real-life multiple-criterion vehicle routing problem with multiple time windows. IEEE Systems Journal, 12(2), 1251-1262.
[3] Bulhões, T., Subramanian, A., Erdoğan, G., & Laporte, G. (2018). The static bike relocation problem with multiple vehicles and visits. European Journal of Operational Research, 264(2), 508-523.
[4] Brinkmann, J., Ulmer, M. W., & Mattfeld, D. C. (2019). Dynamic lookahead policies for stochastic-dynamic inventory routing in bike sharing systems. Computers & Operations Research, 106, 260-279.
[5] Caggiani, L., Camporeale, R., Ottomanelli, M., & Szeto, W. Y. (2018). A modeling framework for the dynamic management of free-floating bike-sharing systems. Transportation Research Part C: Emerging Technologies, 87, 159-182.
[6] Chiariotti, F., Pielli, C., Zanella, A., & Zorzi, M. (2018). A dynamic approach to rebalancing bike-sharing systems. Sensors, 18(2), 512.
[7] Cruz, F., Subramanian, A., Bruck, B. P., & Iori, M. (2017). A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Computers & Operations Research, 79, 19-33.
[8] Datner, S., Raviv, T., Tzur, M., & Chemla, D. (2019). Setting Inventory Levels in a Bike Sharing Network. Transportation Science, 53(1), 62-76.
[9] Ghosh, S., Koh, J. Y., & Jaillet, P. (2019, August). Improving Customer Satisfaction in Bike Sharing Systems through Dynamic Repositioning. In International Joint Conference on Artificial Intelligence (pp. 5864-5870). Macao, China.
[10] Ghosh, S., Varakantham, P., Adulyasak, Y., & Jaillet, P. (2017). Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems. Journal of Artificial Intelligence Research, 58, 387-430.
[11] Ho, S. C., & Szeto, W. Y. (2017). A Hybrid Large Neighborhood Search for The Static Multi-Vehicle Bike-Repositioning Problem. Transportation Research Part B: Methodological, 95, 340-363.
[12] Kloimüllner, C., Papazek, P., Hu, B., & Raidl, G. R. (2014, April). Balancing Bicycle Sharing Systems: An Approach for The Dynamic Case. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 73-84). Berlin, Heidelberg.
[13] Legros, B. (2019). Dynamic Repositioning Strategy in A Bike-Sharing System; How to Prioritize and How to Rebalance A Bike Station. European Journal of Operational Research, 272(2), 740-753.
[14] Liu, Y., Szeto, W. Y., & Ho, S. C. (2018). A Static Free-Floating Bike Repositioning Problem with Multiple Heterogeneous Vehicles, Multiple Depots, and Multiple Visits. Transportation Research Part C: Emerging Technologies, 92, 208-242.
[15] Li, Y., Zheng, Y., & Yang, Q. (2018, July). Dynamic Bike Reposition: A Spatio-Temporal Reinforcement Learning Approach. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 1724-1733). New York, United States.
[16] Lu, E. H. C., & Lin, Z. Q. (2020). Rental prediction in bicycle-sharing system using recurrent neural network. IEEE Access, 8, 92262-92274.
[17] Marinakis, Y., Marinaki, M., & Migdalas, A. (2019). A Multi-Adaptive Particle Swarm Optimization for The Vehicle Routing Problem with Time Windows. Information Sciences, 481, 311-329.
[18] Pal, A., & Zhang, Y. (2017). Free-Floating Bike Sharing: Solving Real-Life Large-Scale Static Rebalancing Problems. Transportation Research Part C: Emerging Technologies, 80, 92-116.
[19] Sörensen, K., Vergeylen, N., 2015. Computer Aided Systems Theory—EUROCAST 2015: 15th International Conference, Las Palmas de Gran Canaria, Spain, February 8–13, 2015, Revised Selected Papers, Springer International Publishing, Cham, pp. 294– 301.
[20] Swaszek, R. M., & Cassandras, C. G. (2019). Receding Horizon Control for Station Inventory Management in a Bike-Sharing System. IEEE Transactions on Automation Science and Engineering, 17(1), 407-417.
[21] Schuijbroek, J., Hampshire, R. C., & Van Hoeve, W. J. (2017). Inventory Rebalancing and Vehicle Routing in Bike Sharing Systems. European Journal of Operational Research, 257(3), 992-1004.
[22] Shui, C. S., & Szeto, W. Y. (2018). Dynamic Green Bike Repositioning Problem - A Hybrid Rolling Horizon Artificial Bee Colony Algorithm Approach. Transportation Research Part D: Transport and Environment, 60, 119-136.
[23] Taha, A., Hachimi, M., & Moudden, A. (2017, April). A discrete bat algorithm for the vehicle routing problem with time windows. In 2017 International Colloquium on Logistics and Supply Chain Management (LOGISTIQUA) (pp. 65-70). IEEE.
[24] Tian, Z., Zhou, J., Szeto, W. Y., Tian, L., & Zhang, W. (2020). The Rebalancing of Bike-Sharing System under Flow-Type Task Window. Transportation Research Part C: Emerging Technologies, 112, 1-27.
[25] Vergeylen, N., Sörensen, K., & Vansteenwegen, P. (2020). Large Neighborhood Search for The Bike Request Scheduling Problem. International Transactions in Operational Research, 27(6), 2695-2714.
[26] Wang, Y., & Szeto, W. Y. (2018). Static Green Repositioning in Bike Sharing Systems with Broken Bikes. Transportation Research Part D: Transport and Environment, 65, 438-457.
[27] You, P. S. (2019). A Two-Phase Heuristic Approach to The Bike Repositioning Problem. Applied Mathematical Modelling, 73, 651-667.
[28] Zhang, D., Xu, W., Ji, B., Li, S., & Liu, Y. (2020). An Adaptive Tabu Search Algorithm Embedded with Iterated Local Search and Route Elimination for The Bike Repositioning and Recycling Problem. Computers & Operations Research, 123, 105035.
[29] Zhang, D., Yu, C., Desai, J., Lau, H. Y. K., & Srivathsan, S. (2017). A Time-Space Network Flow Approach to Dynamic Repositioning in Bicycle Sharing Systems. Transportation Research Part B: Methodological, 103, 188-207.
[30] Zhang, W., Yang, D., Zhang, G., & Gen, M. (2020). Hybrid Multiobjective Evolutionary Algorithm with Fast Sampling Strategy-Based Global Search and Route Sequence Difference-Based Local Search for VRPTW. Expert Systems with Applications, 145, 113151.