Rebalancing problem in electric bike sharing systems with heterogeneous fleet: Mathematical model and heuristic algorithm

Öz

Bicycle-sharing systems (BPS) are widespread vehicle-sharing platforms where users can rent bicycles without the burden of purchasing and maintaining them. Rebalancing in BPS is critical because it ensures bicycle availability at high-demand points and ensures the sustainability of maintenance and distribution processes. In recent years, electric bicycles (e-bikes) have become popular in these systems due to their ease of use. Furthermore, the vehicles used for balancing in BPS can vary in terms of size, speed, and capacity. Therefore, this study addresses the static complete rebalancing problem (e-HSTYDP) with a heterogeneous fleet in BPS (e-BPS) using battery-swappable e-bikes. The e-HSTYDP is defined as selecting the vehicle type to be used in the redistribution of e-bikes among stations and performing the balancing process. A mixed-integer mathematical model is developed to consider separately the objectives of minimizing the total balancing time and the total cost. Since the e-HSTYDP is an NP-hard problem, a constructive heuristic based on the Clarke and Wright Savings (CWT) algorithm is developed to generate solutions for medium- and large-sized problems in reasonable time. The performance of the mathematical model and the s-CWT algorithm is investigated on 78 test problems ranging from 6 to 40 nodes. Experimental study shows that optimal or near-optimal solutions can be obtained in a short time (average 700 seconds) with the mathematical model for small-sized e-HSTYDP problems, while the solution time increases rapidly for medium- and large-sized problems. The s-CWT algorithm, on the other hand, is able to obtain feasible solutions for medium- and large-sized problems in less than 125 seconds and improves three solutions obtained with the model.

Anahtar Kelimeler

• Bicycle sharing system
• pedal-assist electric bicycles
• rebalancing problem
• heterogeneous fleet
• battery swapping

Elektrikli bisiklet paylaşım sistemlerinde heterojen filo ile yeniden dengeleme problemi: Matematiksel model ve sezgisel algoritma

Öz

Bisiklet paylaşım sistemleri (BPS), kullanıcıların bisikletleri satın alma ve bakım sorumluluğu olmaksızın kiralayabildikleri yaygın bir araç paylaşım platformudur. BPS’de yeniden dengeleme, yüksek talep noktalarında bisikletlerin erişilebilirliğini ve bakım–dağıtım süreçlerinin sürdürülebilirliğini sağladığı için kritik öneme sahiptir. Son yıllarda kullanım kolaylığı nedeniyle elektrikli bisikletler (e-bisiklet) tercih edilmektedir. Ayrıca dengeleme işlemi için kullanılan araçlar boyut, hız ve kapasite açısından farklılık gösterebilmektedir. Bu nedenle çalışmada, batarya değişimli e-bisikletlerin kullanıldığı BPS’de (e-BPS) heterojen filo ile statik tam yeniden dengeleme problemi (e-HSTYDP) ele alınmıştır. e-HSTYDP, istasyonlar arasında e-bisikletlerin yeniden dağıtımında kullanılacak araç tipinin seçilmesi ve dengelemenin yapılması problemidir. Toplam dengeleme süresi ve toplam maliyet amaçlarının ayrı ayrı ele alındığı problem için karma tamsayılı model geliştirilmiştir. e-HSTYDP, NP-zor sınıfında yer aldığından, orta ve büyük boyutlu problemlere makul zamanlarda çözüm üretebilmek amacıyla Clarke-Wright Tasarruf (CWT) algoritmasına dayalı çözüm kurucu algoritma geliştirilmiştir. Model ve algoritmanın performansı, 6–40 düğüm arasında değişen 78 test problemi üzerinde incelenmiştir. Sonuçlar, küçük boyutlu problemler için modelin en iyi ya da en iyiye yakın çözümleri kısa sürede (en fazla 700 sn) üretebildiğini, ancak problem boyutu arttıkça çözüm süresinin hızla yükseldiğini göstermektedir. s-CWT algoritması ise orta ve büyük boyutlu problemlere 125 sn’den daha kısa sürede uygun çözümler üretmiş ve modelin bulduğu 3 çözümü iyileştirmiştir..

Anahtar Kelimeler

• Bisiklet paylaşım sistemi
• pedal destekli elektrikli bisikletler
• yeniden dengeleme problemi
• heterojen filo
• batarya değişimi

Kaynakça

1. 1. Shi J.G., Si H., Wu G., Su Y., Lan J., Critical factors to achieve dockless bike-sharing sustainability in China: A stakeholder-oriented network perspective, Sustainability, 10 (6), 2090, 2018.
2. 2. Midgley P., Bicycle-sharing schemes: enhancing sustainable mobility in urban areas, United Nations, Department of Economic and Social Affairs, 8, 1-12, 2011.
3. 3. Chen F., Turoń K., Kłos M., Czech P., Pamuła W., Sierpiński G., Fifth-generation bike-sharing systems: examples from Poland and China, Zeszyty Naukowe, Transport/Politechnika Śląska, 2018.
4. 4. Nath R.B., Rambha T., Modelling methods for planning and operation of bike-sharing systems, Journal of the Indian Institute of Science 99, 621-645, 2019.
5. 5. Vallez C.M., Castro M., Contreras D., Challenges and opportunities in dock-based bike-sharing rebalancing: A systematic review, Sustainability, 13 (4), 1829, 2021.
6. 6. Lebetkin M., Best bike-sharing cities in the world. https://www.usato day.com/story/travel/destinations/2013/10/01/best-cities-bike-sharing/2896227/. Yayın tarihi Ekim 1, 2013. Erişim tarihi Ekim 6, 2025.
7. 7. Fricker C., Gast N., Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity, Euro journal on transportation and logistics, 5 (3), 261-291, 2016.
8. 8. Pal A., Zhang Y., Free-floating bike sharing: Solving real-life large-scale static rebalancing problems, Transportation Research Part C: Emerging Technologies, 80, 92-116, 2017.

9. 9. Nair R., Miller-Hooks E., Fleet management for vehicle sharing operations, Transportation Science, 45 (4), 524-540, 2011.
10. 10. Chemla D., Meunier F., Calvo R.W., Bike sharing systems: Solving the static rebalancing problem, Discrete Optimization, 10 (2), 120-146, 2013.
11. 11. Raviv T., Tzur M., Forma I.A., Static repositioning in a bike-sharing system: models and solution approaches, EURO Journal on Transportation and Logistics, 2 (3), 187-229, 2013.
12. 12. Lin J.R., Yang T.H., Chang Y.C., A hub location inventory model for bicycle sharing system design: Formulation and solution, Computers & Industrial Engineering, 65 (1), 77-86, 2013.
13. 13. Erdoğan G., Laporte G., Calvo R.W., The static bicycle relocation problem with demand intervals, European Journal of Operational Research, 238 (2), 451-457, 2014.
14. 14. Dell'Amico M., Hadjicostantinou E., Iori M., Novellani S., The bike sharing rebalancing problem: Mathematical formulations and benchmark instances, Omega, 45, 7-19, 2014.
15. 15. Ho S.C., Szeto W.Y., Solving a static repositioning problem in bike-sharing systems using iterated tabu search, Transportation Research Part E: Logistics and Transportation Review, 69, 180-198, 2014.
16. 16. Kadri A.A., Kacem I., Labadi K., A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems, Computers & Industrial Engineering, 95, 41-52, 2016.
17. 17. Li Y., Szeto W.Y., Long J., Shui C.S., A multiple type bike repositioning problem, Transportation Research Part B: Methodological, 90, 263-278, 2016.
18. 18. Liu J., Sun L., Chen W., Xiong H., Rebalancing bike sharing systems: A multi-source data smart optimization, In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, 1005-1014, 2016.
19. 19. Regue R., Recker W., Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing problem, Transportation Research Part E: Logistics and Transportation Review, 72, 192-209, 2014.
20. 20. Zhang D., Yu C., Desai J., Lau H.Y.K., Srivathsan S., A time-space network flow approach to dynamic repositioning in bicycle sharing systems, Transportation research part B: methodological, 103, 188-207, 2017.
21. 21. Liang J., Silva M.C.M., Aloise D., Jena S.D., Dynamic rebalancing for bike-sharing systems under inventory interval and target predictions, EURO Journal on Transportation and Logistics, 13, 100147, 2024.
22. 22. Gleditsch M.D., Hagen K., Andersson H., Bakker S.J., Fagerholt K., A column generation heuristic for the dynamic bicycle rebalancing problem, European Journal of Operational Research, 317 (3), 762-775, 2024.
23. 23. Ho S.C., Szeto W.Y., A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem, Transportation Research Part B: Methodological, 95, 340-363, 2017.
24. 24. Forma I.A., Raviv T., Tzur M., A 3-step math heuristic for the static repositioning problem in bike-sharing systems, Transportation research part B: methodological, 71, 230-247, 2015.
25. 25. Schuijbroek J., Hampshire R.C., Van Hoeve W.J., Inventory rebalancing and vehicle routing in bike sharing systems, European Journal of Operational Research, 257 (3), 992-1004, 2017.
26. 26. Bulhões T., Subramanian A., Erdoğan G., Laporte G., The static bike relocation problem with multiple vehicles and visits, European Journal of Operational Research, 264 (2), 508-523, 2018.
27. 27. Szeto W.Y., Shui C.S., Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem, Transportation Research Part B: Methodological, 109, 176-211, 2018.
28. 28. Arabzad S.M., Shirouyehzad H., Bashiri M., Tavakkoli-Moghaddam R., Najafi E., Rebalancing static bike-sharing systems: a two-period two-commodity multi-depot mathematical model, Transport, 33 (3), 718-726, 2018.
29. 29. Zhang S., Xiang G., Huang Z., Bike-sharing static rebalancing by considering the collection of bicycles in need of repair, Journal of Advanced Transportation, 2018.
30. 30. Kacem I., Kadri A., Laroche P., A clustering-based approach for balancing and scheduling bicycle-sharing systems, Intelligent Automation & Soft Computing, 24 (2), 2018.
31. 31. Wang S., Wu R., The Static Rebalancing Problem in Bicycle-Sharing Systems with Unusable Bicycles, In 2019 16th International Conference on Service Systems and Service Management (ICSSSM), 1-6, IEEE, 2019.
32. 32. Du M., Cheng L., Li X., Tang F., 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, 2020.
33. 33. Sun J., He Y., Zhang J., A cluster-then-route framework for bike rebalancing in free-floating bike-sharing systems, Sustainability, 15(22), 15994, 2023.
34. 34. Ren Y., Zhao F., Jin H., Jiao Z., Meng L., Zhang C., Sutherland J.W., Rebalancing bike sharing systems for minimizing depot inventory and traveling costs, IEEE Transactions on Intelligent Transportation Systems, 21 (9), 3871-3882, 2019.
35. 35. Shi L., Zhang Y., Rui W., Yang X., Study on the bike-sharing inventory rebalancing and vehicle routing for bike-sharing system, Transportation research Procedia, 39, 624-633, 2019.
36. 36. Zhang D., Xu W., Ji B., Li S., Liu Y., 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, 2020.
37. 37. Kaveh F., Shirouyehzad H., Zolfani S.H., Arabzad S.M., Proposing a mathematical model of balancing the inventory of multi-zone bicycle sharing systems with mobile stations and applying maintenance constraints, Transport, 37 (3), 145-160, 2022.
38. 38. Chastre M.R., Andrade A.R., Rebalancing in bike sharing systems: Application to the Lisbon case study, Case studies on transport policy, 13, 101071, 2023.
39. 39. Pan X., Tang J., Yu T., Cai J., Xiong Y., Gao F., Reposition optimization in the free-floating bike-sharing system considering transferring travels from urban rail transit, Computers & Industrial Engineering, 178, 109127, 2023.
40. 40. Guo Y., Li J., Xiao L., Allaoui H., Choudhary A., Zhang L., Efficient inventory routing for Bike-Sharing Systems: A combinatorial reinforcement learning framework, Transportation research part E: logistics and transportation review, 182, 103415, 2024.
41. 41. Liang S., Ye Y., Wu J., An effective hybrid optimization algorithm for static rebalance problem of bicycle-sharing system, IET Intelligent Transport Systems, 19 (1), e70050, 2025.
42. 42. Jenkins M., Lustosa L., Chia V., Wildish S., Tan M., Hoornweg D., ..., Dogra S., What do we know about pedal assist E-bikes? A scoping review to inform future directions, Transport policy, 2022.
43. 43. Baptista P., Pina A., Duarte G., Rolim C., Pereira G., Silva C., From onroad trial evaluation of electric and conventional bicycles to comparison with other urban transport modes: case study in the city of Lisbon, Portugal, Energy Convers. Manag., 92, 10–18, 2015.
44. 44. Zhou Y., Lin Z., Guan R., Sheu J.B., Dynamic battery swapping and rebalancing strategies for e-bike sharing systems, Transportation Research Part B: Methodological, 177, 102820, 2023.
45. 45. Guan R., Lin Z., Zhou Y., Zhu Z., User-based relocation for e-bike sharing systems through power-level recommendation, IEEE Transactions on Intelligent Transportation Systems, 26 (9), 13954–13966, 2025.
46. 46. Cui, J., Szeto, W.Y., Wang, Y., A static mixed bike repositioning problem with both man-powered bikes and e-bikes, Transportation Research Part E: Logistics and Transportation Review, 203, 104275, 2025.
47. 47. Xu M., Di Y., Zhu Z., Yang H., Chen X., Designing van-based mobile battery swapping and rebalancing services for dockless ebike-sharing systems based on the dueling double deep Q-network, Transportation Research Part C: Emerging Technologies, 138, 103620, 2022.
48. 48. Gajpal Y., Abad P., Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery, The Journal of the Operational Research Society, 61 (10), 1498-1509, 2010.
49. 49. [49] Cordeau J.F., Gendreau M., Laporte G., Potvin J.Y., Semet F., A Guide to vehicle routing heuristics, The Journal of the Operational Research Society, 53, 512-522, 2002.
50. 50. Clarke G., Wright J.W., Scheduling vehicles from a central delivery depot to a number of delivery points, Operations Research, 12 (4), 568–581, 1964.
51. 51. Keçeci B., Altiparmak F., Kara I., Heterogeneous Vehicle Routing Problem With Simultaneous Pickup And Delivery: Mathematical Formulations And A Heuristic Algorithm, Journal of The Faculty of Engineering and Architecture of Gazi University, 30 (2), 185-195, 2015.
52. 52. Yildiz E.A., Karaoglan I., Altiparmak F., A mixed integer mathematical model and a heuristic approach for two echelon location routing problem with simultaneous pickup and delivery, Journal of The Faculty of Engineering and Architecture of Gazi University, 36 (2), 807-822, 2021.
53. 53. Dönmez S., Koç Ç., Altiparmak F., The mixed fleet vehicle routing problem with partial recharging by multiple chargers: A formulation and an insertion based constructive heuristic, Journal of The Faculty of Engineering and Architecture of Gazi University, 39 (1), 1-16, 2024.
54. 54. Zhang F., Lyu H., Ji Y., Wong M., Kuai C., Fan J., Battery swapping demand simulation for electric micromobility vehicles considering multi-source information interaction and behavior decision, Journal of Cleaner Production, 414, 2023.
55. 55. Akpınar İ.D., e-HSTYDP test problemi veri seti. GitHub. https://github.com/idakpinar/e-HSTYDP/issues. Yayın tarihi 2025. Erişim tarihi 19 Kasım 2025.