STATIC BIKE REPOSITIONING AND MAINTENANCE PROBLEM

靜態自行車調度與維護問題

水敬心(Chin-Sum Shui)

Bike repositioning ； Broken bike maintenance ； Bike sharing system ； On-site repair ； 自行車調度 ； 破損自行車維護 ； 共享自行車系統 ； 實地維修

運輸計劃季刊

50卷3期（2021 / 09 / 30）

225 - 252

英文

This paper proposes a new static bike repositioning problem that maintenance operation is simultaneously considered. In this problem, a broken bike at a station can be either collected on the relocation vehicle to be sent back to the depot or repaired on-site to restore its function during repositioning. This on-site repair becomes a new strategy that is examined in this paper and new to the literature. The problem is formulated as a mixed-integer linear programming problem that determines the number of deployed vehicles, the loading and unloading quantities for normal bikes at all stations, and the number of collected and repaired broken bikes at all stations such that the weighted sum of the total service time and the penalties associated with the deviations from the targeted inventory level is minimized. Using the real-world case of Youbike in Taiwan, this paper demonstrates the on-site repair strategy can reduce the repositioning cost and deviations from the target inventory levels more than mere collection strategy. Sensitivity analyses show that the shorter repairing time, larger vehicle, and higher penalty for deviations from the target inventory level can obtain strategies with smaller deviation and shorter travel time. Moreover, a revised problem which includes service time constraint is proposed and the numerical studies show that the increase in allowable service time can reduce the number of deployed vehicles and the total service time.

本研究提出一個全新、考慮破損自行車維護的靜態自行車調度問題：系統當中的破損自行車不但可以經由調度車收集並運送回倉庫進行整修，而且能以本研究首先提出的現場維修方法來進行維護。接著，本文構建了一道混合整數線性規劃問題，同時決定調度車輛數量、所有自行車站點上正常自行車的裝卸數量、以及所有自行車站點上已收集和實地維修的破損自行車的數量，以最小化總服務時間和所有站點與其目標庫存水平之差的懲罰成本的加權總和。透過臺灣Youbike的實際案例，數據實驗顯示現場維修比單純收集更能減少調度成本和與目標庫存水平的偏差。敏感性分析顯示較短的維修時間、較大的車輛以及較高的偏離目標庫存水平的權重，能達至與目標庫存水平偏離較小和行駛時間較短的調度策略。同時，本研究提出增加了限制服務時間的延伸問題，並透過數值研究顯示更長的服務時間能減少調配車輛的數量和總服務時間。

1. Lin, J.-R.,Yang, T.-H.(2020).Strategic Design of Public Bicycle Distribution Systems.Transportation Planning Journal,49(1),43-66.
   連結：
2. 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.
3. Chang, S.,Song, R.,He, S.,Qiu, G.(2018).Innovative Bike-Sharing in China: Solving Faulty Bike-Sharing Recycling Problem.Journal of Advanced Transportation,2018(6),1-10.
4. Chemla, D.,Meunier, F.,Calvo, R.W.(2013).Bike Sharing Systems: Solving the Static Rebalancing Problem.Discrete Optimization,10(2),120-146.
5. Citibike, “June 2020 Monthly Report”, Retrieved from https://d21xlh2maitm24.cloudfront.net/nyc/June-2020-Citi-Bike-Monthly-Report.pdf?mtime=20200722104600, 2020.
6. Cruz, F.,Subramanian, A.,Bruck, B.P.,Iori, M.(2017).A Heuristic Algorithm for a Single Vehicle Static Bike Sharing Rebalancing Problem.Computers and Operations Research,79,19-33.
7. Dell’Amico, M.,Hadjicostantinou, E.,Iori, M.,Novellani, S.(2014).The Bike Sharing Rebalancing Problem: Mathematical Formulations and Benchmark Instances.Omega,45,7-19.
8. Dell’Amico, M.,Iori, M.,Novellani, S.,Subramanian, A.(2018).The Bike Sharing Rebalancing Problem with Stochastic Demands.Transportation Research Part B: Methodological,118,362-380.
9. Di Gaspero, L.,Rendl, A.,Urli, T.(2016).Balancing Bike Sharing Systems with Constraint Programming.Constraints,21(2),318-348.
10. Du, M.,Cheng, L.,Li, X.,Tang, F.(2020).Static Rebalancing Optimization with Considering the Collection of Malfunctioning Bikes in Free-Floating Bike Sharing System.Transportation Research Part E: Logistics and Transportation Review,141,102012.
11. Erdoğan, G.,Laporte, G.,Calvo, R.W.(2014).The Static Bicycle Relocation Problem with Demand Intervals.European Journal of Operational Research,238(2),451-457.
12. Haider, Z.,Nikolaev, A.,Kang, J. E.,Kwon, C.(2018).Inventory Rebalancing through Pricing in Public Bike Sharing Systems.European Journal of Operational Research,270(1),103-117.
13. 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.
14. Institute for Transportation and Development Policy, The Bike-share Planning Guide, Institute for Transportation and Development Policy, New York, 2018.
15. Jin, Y.,Ruiz, C.,Liao, H.,Pierson, H.(2019).A Simulation Framework for the Rebalancing and Maintenance of Bicycle-Sharing Systems.2019 Winter Simulation Conference (WSC)
16. Kaspi, M.,Raviv, T.,Tzur, M.(2017).Bike-Sharing Systems: User Dissatisfaction in the Presence of Unusable Bicycles.IISE Transactions,49(2),144-158.
17. Kaspi, M.,Raviv, T.,Tzur, M.(2016).Detection of Unusable Bicycles in Bike-Sharing Systems.Omega,65,10-16.
18. Kaspi, M.,Raviv, T.,Tzur, M.,Galili, H.(2016).Regulating Vehicle Sharing Systems through Parking Reservation Policies: Analysis and Performance Bounds.European Journal of Operational Research,251(3),969-987.
19. Miller, C. E.,Tucker, A. W.,Zemlin, R. A.(1960).Integer Programming Formulation of Traveling Salesman Problems.Journal of the ACM (JACM),7(4),326-329.
20. Pfrommer, J.,Warrington, J.,Schildbach, G.,Morari, M.(2014).Dynamic Vehicle Redistribution and Online Price Incentives in Shared Mobility Systems.IEEE Transactions on Intelligent Transportation Systems,15(4),1567-1578.
21. Rainer-Harbach, M.,Papazek, P.,Raidl, G.R.,Hu, B.,Kloimüllner, C.(2015).Approaches for the Static Balancing of Bicycle Sharing Systems.Journal of Global Optimization,63(3),597-629.
22. Raviv, T.,Tzur, M.,Forma, I. A.(2013).Static Repositioning in a Bike-Sharing System: Models and solution approaches.EURO Journal on Transportation and Logistics,2(3),187-229.
23. Reiss, S.,Bogenberger, K.(2017).A Relocation Strategy for Munich's bike Sharing System: Combining an Operator-based and a User-Based Scheme.Transportation Research Procedia,22,105-114.
24. Shui, C. S.,Szeto, W. Y.(2020).A Review of Bicycle-Sharing Service Planning Problem.Transportation Research Part C: Emerging Technologies,117,102648.
25. 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.
26. Singla, A.,Santoni, M.,Bartók, G.,Mukerji, P.,Meenen, M.,Krause, A.(2015).Incentivizing Users for Balancing Bike Sharing Systems.Proceedings of Twenty-Ninth AAAI Conference of Artificial Intelligence
27. Szeto, W. Y.,Liu, Y.,Ho, S. C.(2016).Chemical Reaction Optimization for Solving a Static Bike Repositioning Problem.Transportation Research Part D: Transport and Environment,47,104-135.
28. Szeto, W. Y.,Shui, C. S.(2018).Exact Loading and Unloading Strategies for the Static Multi-Vehicle Bike Repositioning Problem.Transportation Research Part B: Methodological,109,176-211.
29. Teng, Y.,Zhang, H.,Li, X.,Liang, X.(2020).Optimization Model and Algorithm for Dockless Bike-Sharing Systems Considering Unusable Bikes in China.IEEE Access,8,42948-42959.
30. Usama, M.,Shen, Y.,Zahoor, O.(2019).A Free-Floating Bike Repositioning Problem with Faulty Bikes.Procedia Computer Science,151,155-162.
31. 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.
32. 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 and Operations Research,123,105035.
33. Zhang, S.,Xiang, G.,Huang, Z.(2018).Bike-Sharing Static Rebalancing by Considering the Collection of Bicycles in Need of Repair.Journal of Advanced Transportation,2018(9),1-18.