A Multi-commodity Pickup and Delivery Open-tour m-TSP Formulation for Bike Sharing Rebalancing Problem

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

2 Department of Industrial Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

3 Department of Industrial Engineering, Shahed University, Tehran, Iran

4 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

Bike sharing systems (BSSs) offer a mobility service whereby public bikes, located at different stations across an urban area, are available for shared use. An important point is that the distribution of rides between stations is not uniformly distributed and certain stations fill up or empty over time. These empty and full stations lead to demand for bikes and return boxes that cannot be fulfilled leading to unsatisfied and possibly even lost customers. To avoid this situation, bikes in the systems are redistributed by the provider. In this paper, a mathematical modelling is proposed to rebalance the stations employing non-identical trucks based on Travelling Salesman Problem (TSP) formulation. This modelling is categorized as static repositioning where the demands of stations in one period is considered. In the modelling, several types of bikes have been considered in BSSs and it has assumed that there are two depots and trucks start from one and return to another one. Finally, a numerical example confirms the applicability of the proposed model. The result shows that the modelling would simultaneously obtain the minimum paths, the minimum implementing truck’s costs and the minimum of loading/unloading bikes program.
 

Keywords

Main Subjects

References

Benchimol, M., Benchimol, P., Chappert, B., De La Taille, A., Laroche, F., Meunier, F., & Robinet, L. (2011). Balancing the stations of a self-service “bike hire” system. RAIRO-Operations Research, 45(01), 37-61.
Brake, J., Mulley, C., Nelson, J. D., & Wright, S. (2007). Key lessons learned from recent experience with Flexible Transport Services. Transport Policy, 14(6), 458-466.
Brussel N (2010). Villo-bevoorrading lijdt onder files (in Dutch). Web newspaper. Publication date: 22 June 2010, Observed: 15 August 2012.
Calle´, E. (2009). Personal communication.
Chemla, D., Meunier, F., & Wolfler Calvo, R. (2011). Bike hiring system: solving the rebalancing problem in the static case. Discrete Optimization (accepted).
Chemla, D., Meunier, F., & Wolfler Calvo, R. (2013). Bike sharing systems: solving the static rebalancing problem. Discrete Optimization, 10(2), 120-146
Dell'Amico, M., Hadjicostantinou, E., Iori, M., & Novellani, S. (2014). The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega, 45, 7-19.
DeMaio, P. (2009). Bike-sharing: History, impacts, models of provision, and future. Journal of Public Transportation, 12(4), 3.
Dikas, G., & Minis, I. (2014). Scheduled paratransit transport systems. Transportation Research Part B: Methodological, 67, 18-34.
Fricker, C., & Gast, N. (2012). Incentives and regulations in bike-sharing systems with stations of finite capacity. arXiv preprint arXiv:1201.1178, 2.
Fu, L. (2002). A simulation model for evaluating advanced dial-a-ride paratransit systems. Transportation Research Part A: Policy and Practice, 36(4), 291-307.
Gutin, G., & Punnen, A. P. (Eds.). (2002). The traveling salesman problem and its variations, Vol. 12. Springer Science & Business Media.
Hampshire R, Marla L (2011) An empirical analysis of bike-sharing systems. Working paper
Hernández-Pérez, H., & Salazar-González, J. J. (2004a). A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Applied Mathematics, 145(1), 126-139.
Hernández-Pérez, H., & Salazar-González, J. J. (2004b). Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science, 38(2), 245-255.
Lin, J. R., & Yang, T. H. (2011). Strategic design of public bicycle sharing systems with service level constraints. Transportation research part E: logistics and transportation review, 47(2), 284-294.
Louveaux, F., & Salazar-González, J. J. (2009). On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands. Mathematical programming, 119(1), 169-194.
Martens, K. (2004). The bicycle as a feedering mode: experiences from three European countries. Transportation Research Part D: Transport and Environment, 9(4), 281-294.
Meddin, Russell, and Paul DeMaio. "The bike-sharing world map." URL http://www. metrobike. net (2012).
Raviv, T., & Kolka, O. (2013). Optimal inventory management of a bike-sharing station. IIE Transactions, 45(10), 1077-1093.
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.
Sayarshad, H., Tavassoli, S., & Zhao, F. (2012). A multi-periodic optimization formulation for bike planning and bike utilization. Applied Mathematical Modelling, 36(10), 4944-4951.
Schalekamp, H., & Behrens, R. (2013). Engaging the paratransit sector in Cape Town on public transport reform: Progress, process and risks. Research in Transportation Economics, 39(1), 185-190.
Shaheen, S., & Guzman, S. (2011). Worldwide bikesharing. Access Magazine, 1(39).
Shu, J., Chou, M., Liu, Q., Teo, C. P., & Wang, I. L. (2010). Bicycle-sharing system: deployment, utilization and the value of re-distribution. National University of Singapore-NUS Business School, Singapore.
Tusia-Cohen M (2012) Invented the wheel: first year of Tel-O-Fun (in Hebrew), Web version of the daily newspaper Maariv. Publication date: 12 April 2012, Observed at 26 August 2012.
Vogel, P., & Mattfeld, D. C. (2010, July). Modeling of repositioning activities in bike-sharing systems. In World Conference on Transport Research (WCTR).
 
Journal of Industrial and Systems Engineering
Volume 9, Issue 3
July 2016
Pages 70-81

Files

History

  • Receive Date: 01 January 2016
  • Revise Date: 17 March 2016
  • Accept Date: 21 May 2016

Share

How to cite

Statistics