access icon free Vehicle scheduling approach and its practice to optimise public bicycle redistribution in Hangzhou

© The Institution of Engineering and Technology
Received 16/09/2017, Accepted 08/05/2018, Revised 10/04/2018, Published 09/05/2018

Public bicycle sharing programmes (PBSPs) have become increasingly popular across many urban areas in China. Hangzhou PBSP is the world's largest and forms this case study. The management of this large inventory of bicycles is a particularly challenging issue with the goal to ensure the demand for bicycles is met at all times across the network. To this end, an efficient scheduling approach is needed with the capacity to guide the redistribution of bicycles across the self-service stations. Drawing on 7 years of disaggregate trip data, this study first captures the usage dynamics across both space and time to extract the candidate stations and redistribution periods for vehicle scheduling. A region partition method with K-means clustering is proposed to satisfy the real-time requirement of large-scale PBSPs' redistribution. Moreover, drawing on the variations in demand a back-propagation neural network short-term prediction model is computed to inform the necessary prospective redistribution of bicycles to ensure demand is always met. Finally, a vehicle scheduling model employing a rolling horizon scheduling algorithm is established and implemented in a GIS-based prototype system. The prototype is evaluated through its effectiveness and found benefit for following 18 months of practical operation in Hangzhou PBSP.

Inspec keywords: neural nets; backpropagation; geographic information systems; public transport; optimisation; traffic information systems; bicycles

Other keywords: vehicle scheduling approach; rolling horizon scheduling algorithm; self-service stations; disaggregate trip data; large-scale PBSP redistribution; public bicycle sharing programmes; public bicycle redistribution optimization; region partition method; k-means clustering; GIS-based prototype system; back-propagation neural network short-term prediction model; O-D relationship; public transit

Subjects: Systems theory applications in transportation; Traffic engineering computing; Geography and cartography computing; Neural computing techniques; Optimisation techniques

References

    1. 1)
      • 24. Brandao, J.: ‘A tabu search algorithm for the open vehicle routing problem’, Eur. J. Oper. Res., 2004, 157, (3), pp. 552–564.
    2. 2)
      • 23. Hinton, G.E., Osindero, S., Teh, Y.: ‘A fast learning algorithm for deep belief nets’, Neural Comput., 2006, 18, (7), pp. 1527–1554.
    3. 3)
      • 28. Wu, M.J., Dong, H.Z., Liu, D.X., et al: ‘Research on the dynamic model with multi-objective and algorithm for public bicycle rebalancing problem’, J. Mech. Electr. Eng., 2015, 32, (7), pp. 1006–1011.
    4. 4)
      • 18. Schuijbroek, J., Hampshire, R.C., van Hoeve, W.-J.: ‘Inventory rebalancing and vehicle routing in bike sharing systems’, Eur. J. Oper. Res., 2017, 257, (3), pp. 992–1004.
    5. 5)
      • 14. Repoussis, P.P., Tarantilis, C.D., Loannou, G.: ‘The open vehicle routing problem with time windows’, J. Oper. Res. Soc., 2007, 58, (3), pp. 355–367.
    6. 6)
      • 13. Tan, K.C., Lee, L.H., Ou, K.: ‘Artificial intelligence heuristics in solving vehicle routing problems with time window constraints’, Eng. Appl. Artif. Intell., 2001, 14, (6), pp. 825–837.
    7. 7)
      • 27. Niksirat, M., Ghatee, M., Hashemi, S.M., et al: ‘Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms’, Appl. Math. Model., 2012, 36, pp. 5709–5726.
    8. 8)
      • 19. Adham, M.T., Bentley, P.J.: ‘An ecosystem algorithm for the dynamic redistribution of bicycles in Londonv’. Information Processing in Cells and Tissues. IPCAT 2015, San Diego, CA, USA, September 2015, pp. 39–51.
    9. 9)
      • 17. Liu, Z.P., Li, K.P., Zhu, X.H.: ‘Optimal dispatch between stations for public bicycle based on ant colony algorithm’, Comput. Commun., 2012, 4, (30), pp. 71–74.
    10. 10)
      • 22. Dong, H.Z., Shi, C.X., Chen, N., et al: ‘Clustering division of public bicycle scheduling regional based on association rules’, Bull. Sci. Technol., 2013, 29, (9), pp. 209–213.
    11. 11)
      • 16. Hueykuo, C., Hsueh, C., Chang, M.: ‘The real-time time-dependent vehicle routing problem’, Transp. Res. E, 2006, 42, (5), pp. 383–408.
    12. 12)
      • 10. Chemla, D., Meunier, F., Calvo, R.W.: ‘Bike sharing systems: solving the static rebalancing problem’, Discrete Optim., 2013, 10, (2), pp. 120–146.
    13. 13)
      • 1. Shaheen, S., Guzman, S., Zhang, H.: ‘Bikesharing in Europe, the Americas, and Asia: past, present, and future’, Transp. Res. Rec., 2010, 2143, pp. 159–167.
    14. 14)
      • 21. Kloimüllner, C., Papazek, P., Hu, B.: ‘Balancing bicycle sharing systems: an approach for the dynamic case’, Evol. Comput. Comb. Optim., 2014, 8600, pp. 73–84.
    15. 15)
      • 4. Liu, D.X., Shi, C.X., Dong, H.Z.: ‘Comparison research on operating mode of global public bicycle systems’, Appl. Mech. Mater., 2013, 409–410, pp. 1204–1208.
    16. 16)
      • 5. Dong, H.Z., Zhao, J.Y., Guo, H.F., et al: ‘Research on the scheduling dynamic model and rolling horizon scheduling algorithm for public bicycle system’, Central South Highway Eng., 2009, 34, (6), pp. 68–71.
    17. 17)
      • 15. Çatay, B.: ‘A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery’, Expert Syst. Appl., 2010, 37, (10), pp. 6809–6817.
    18. 18)
      • 3. Corcoran, J., Li, T.: ‘Spatial analytical approaches in public bicycle sharing programs’, J. Transp. Geogr., 2014, 41, pp. 268–271.
    19. 19)
      • 2. Andreas, K., Rodrigo, M., Jens, G., et al: ‘Urban cycles and mobility patterns: exploring and predicting trends in a bicycle-based public transport system’, Pervasive Mob. Comput., 2010, 6, (4), pp. 455–466.
    20. 20)
      • 12. Gaspero, L.D., Rendl, A., Urli, T.: ‘A hybrid ACO + CP for balancing bicycle sharing systems’, Lect. Notes Comput. Sci., 2013, 7919, pp. 198–212.
    21. 21)
      • 9. Fricker, C., Gast, N.: ‘Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity’, EURO J. Transp. Logist., 2016, 5, pp. 261–291.
    22. 22)
      • 11. Raviv, T., Tzur, M., Forma, I.A.: ‘Static repositioning in a bike-sharing system: models and solution approaches’, EURO J. Transp. Logist., 2013, 2, (3), pp. 187–229.
    23. 23)
      • 25. Côté, J.F., Potvin, J.Y.: ‘A tabu search heuristic for the vehicle routing problem with private fleet and common carrier’, Eur. J. Oper. Res., 2009, 198, (2), pp. 464–469.
    24. 24)
      • 26. Asadi, R., Ghatee, M.: ‘A rule-based decision support system in intelligent hazmat transportation system’, IEEE Trans. Intell. Transp. Syst., 2015, 16, (5), pp. 2756–2764.
    25. 25)
      • 6. Shu, J., Chou, M., Liu, Q., et al: ‘Bicycle-sharing system: deployment, utilization and the value of re-distribution’, 2010. Available at http://www.bschool.nus.edu.sg/Staff/bizteocp/BS2010.pdf.
    26. 26)
      • 7. Caggiani, L., Ottomanelli, M.: ‘A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems’, Proc. Soc. Behav. Sci., 2013, 87, pp. 203–210.
    27. 27)
      • 8. Pfrommer, J., Warrington, J., Schildbach, G., et al: ‘Dynamic vehicle redistribution and online price incentives in shared mobility systems’, IEEE Trans. Intell. Transp. Syst., 2014, 15, (4), pp. 1567–1578.
    28. 28)
      • 20. Rainer-Harbach, M., Papazek, P., Raidl, G.R., et al: ‘PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems’, J. Global Optim., 2015, 63, (3), pp. 597–629.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2017.0274
Loading

Related content

content/journals/10.1049/iet-its.2017.0274
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading