Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 11

Proceedings of the 2017 Federated Conference on Computer Science and Information Systems

Vehicle Oriented Algorithms for the Relocation of Vehicle Sharing Systems


DOI: http://dx.doi.org/10.15439/2017F28

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 473480 ()

Full text

Abstract. Managing a one-way vehicle sharing system means periodically moving free access vehicles from excess to deficit stations in order to avoid local shortages. We perform a lower bound analysis for the static version of the resulting operational decision problem, and derive from this analysis two heuristic algorithms whose main feature is to be vehicle oriented, which means that they focus on the way vehicles are exchanged between excess and deficit stations.


  1. C. Archetti, M. Speranza: The split delivery vehicle routing problem, a survey; in The vehicle routing problem: latest advances and new challenges; p 103-122, Springer U.S, (2008). http://dx.doi.org/10.1111/j.1475-3995.2011.00811.x
  2. S. Anily, M. Gendreau, G. Laporte: Uncapacitated swapping problem on line and circle ; Networks 58, p 83-94, (2011). http://dx.doi.org/10.1016/j.dam.2012.07.002
  3. B. Bernay, S. Deleplanque, A. Quilliot: Routing in Dynamic Networks: Grasp Versus Genetics, 7 th WCO Workshop, FEDCIS Conf, Warwsaw, p 487, 492, (2014), http://dx.doi.org/10.15439/978-83-60810-58-3
  4. J. Aronson: A survey on dynamic network flows; Annals of O.R, 20, p 1-66, (1989). http://dx.doi.org/10.1007/BF02216922
  5. M. Barth, M. Todd: Simulation model analysis of a multiple station shared vehicle system. Transp. Res. C, 7(4): 237–259, (1999), http://dx.doi.org/10.1016/S0968-090X(99)00021-2
  6. M. and P. Benchimol, B. Chappert, A. De la Taille, F. Laroche, F. Meunier, L. Robinet : Balancing the stations of a self service bike systems, RAIRO-RO 45, p 37-61, (2011). http://dx.doi.org/ 10.1051/ro/2011102
  7. C. Bordenave, M. Gendreau, G. Laporte: A branch and cut algorithm for the preemptive swapping problem; Networks 59, 4, p 387-399, (2012). http://dx.doi.org/10.1002/net.20447
  8. B. Boyaci, K. Zografos, N. Geroliminis: An optimization framework for the development of efficient one-way car-sharing systems. EJOR, 240(3):718–733, (2015), http://dx.doi.org/10.1016/j.ejor.2014.07.020
  9. A. Carlier, A. Munier-Kordon, W. Klaudel: Mathematical model for the study of relocation strategies in one-way carsharing systems. Transp. Res. Procedia, 10:374–383, (2015). http://dx.doi.org/10.1016/j.trpro.2015.09.087
  10. D. Chemla, F. Meunier, R. Wolfler Calvo: Bike sharing systems: solving the static rebalancing problem; Discrete Optimization 10 (2), p 120-146, (2013). http://dx.doi.org/10.1016/j.disopt.2012.11.005
  11. C. Contardo, C. Morency, L. M. Rousseau: Balancing a dynamic public bike-sharing system; Rapport CIRRELT, Univ. MONTREAL (2012).
  12. J. F. Cordeau, G. Laporte: A Tabu search heuristic algorithm for the static multi-vehicle Dial and Ride Problem; Transportation Research B 37, p 579-594, (2003), doi.org/10.1016/S0191-2615(02)00045-0
  13. D. Gavalas, C. Konstantopoulos, G. Pantziou: Design and management of vehicle sharing systems: a survey of algorithmic approaches; ArXiv e-prints, arxiv.org/pdf/1510.01158, Oct. 2015. https://arxiv.org/abs/1510.01158v1
  14. G. H. Kek, R. L. Cheu, Q. Meng, C. Ha Fung: A decision support system for vehicle relocation operations in carsharing systems; Transportation Research E: Logistics and Transportation Review 45 (1), p 149-158, (2009). http://dx.doi.org/10.1016/j.tre.2014.01.007
  15. H. Hernandez Perez, J. Salazar Gonzalez: Heuristics for the one commodity pick up and delivery traveling salesman problem; Transportation Sciences 38, p 244-255, (2004), doi>10.1287/trsc.1030.0086
  16. J. Lee, G. L. Park: Design of a team based relocation scheme in electric vehicle sharing systems; Proc. Int. Conf. Computat. Sci. and Applications 7973, p 368-377, (2013).
  17. M. Nourinedjad, M. J. Roorda: A dynamic carsharing decision support system, Transportation Research E, 66, p 36-50, (2014). http://dx.doi.org/10.1016/j.tre.2014.03.003
  18. M. Rainer-Harbach, P. Papazeck, B. Hu, G. Raidl: Balancing bicycle sharing systems: a variable neighbourhood search approach, Journal of Global optimization, 63-3, p 597-629 (2015)
  19. T. Raviv, M. Tzur, I. Forma: Static repositioning in a bike sharing system: models and solution approaches; EURO Journal on Transportation and Logistics 2 (3), p 187-229, (2013).DOI A0.1007/a13676-012-0017-6.