Top

Soft Computing

Published in:

31-05-2018 | Methodologies and Application

Lower and upper bounds for scheduling multiple balancing vehicles in bicycle-sharing systems

Authors: Ahmed A. Kadri, Imed Kacem, Karim Labadi

Published in: Soft Computing | Issue 14/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Public bicycle-sharing systems have been implemented in many big cities around the world to face many public transport problems. The exploitation and the management of such transportation systems imply crucial operational challenges. The balancing of stations is the most crucial question for their operational efficiency and economic viability. In this paper, we study the balancing problem of stations with multiple vehicles by considering the static case. A mathematical formulation of the problem is proposed, and two lower bounds based on Eastman’s bound and SPT rule are developed. Moreover, we proposed four upper bounds based on a genetic algorithm, a greedy search algorithm and two hybrid methods that integrate a genetic algorithm, a local search method and a branch-and-bound algorithm. The developed lower and upper bounds are tested and compared on a large set of instances.

previous article Entropy-based multi-item solid transportation problems with uncertain variables

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Anholt R, Coelho L, Laporte G, Vis I (2016) An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines. Transp. Sci. 50(3):1077–1091CrossRef

Aultman-Hall L, Kaltenecker-Georgina M (1999) Toronto bicycle commuter safety rates. Accid Anal Prev 31:675–686CrossRef

Benchimol M, Benchimol P, Chappert B, Taille A, Laroche F, Meunier F, Robinet L (2010) Balancing the stations of a self-service bike hire system. RAIRO Oper. Res. 45:37–61MathSciNetCrossRefMATH

Bordagaray M, Ibeas A, dellOlio L (2012) Modelling user perception of public bicycle services. EWGT 2012, 15th meeting of the EURO working group on transportation. Procedia Soc Behav Sci 54:1308–1316CrossRef

Callé E (2009) Director of Operation in Vélib, April 2009, Personal communication

Carrabs F, Cerulli R, D’Ambrosio C, Raiconi A (2017a) An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints. Optim Lett 11(7):1341–1356MathSciNetCrossRefMATH

Carrabs F, Cerulli R, Sciomachen A (2017b) An exact approach for the grocery delivery problem in urban areas. Soft Comput 21(9):2439–2450CrossRef

Castao F (2016) Partial target coverage to extend the lifetime in wireless multi-role sensor networks. Networks. https://doi.org/10.1002/net.21682 MathSciNet

Chang Y (2010) Adopting co-evolution and constraint-satisfaction concept on genetic algorithms to solve supply chain network design problems. Expert Syst Appl 37(10):6919–6930CrossRef

Chemla D, Meunier F, WolflerCalvo R (2011) Balancing a bike-sharing system with multiple vehicles. ROADEF, Saint-Etienne, France

Chemla D, Meunier F, Wolfer-Calvo R (2013) Bike sharing systems: solving the static rebalancing problem. Discrete Optim 10(2):120–146MathSciNetCrossRefMATH

Christophe P, Hugues B (2007) A gestalt genetic algorithm: less details for better search. In: Genetic and evolutionary computation conference, pp 1328–1334

DeMaio P (2009) Bike-sharing: history, impacts, models of provision, and future. J Public Transp 14(4):41–56CrossRef

Di Gasperro L, Rendl A, Urli T (2013) A hybrid ACO+CP for balancing bicycle-sharing systems. In: Blesa MJ, Blum C, Festa P, Roli A, Sampels M (eds) HM 2013, vol 7919. LNCS, pp 198–212

Eastman WL, Evan S, Issacs IM (1964) Bounds for the optimal scheduling of N jobs on M processors. Manag Sci 11:268–279MathSciNetCrossRef

Fricker C, Gast N, Mohamed H (2012) Mean field analysis for inhomogeneous bike sharing systems. In: Proceedings of the twenty-third international meeting on probabilistic, combinatorial, and asymptotic methods for the analysis of algorithms. DMTCS, pp 365–376

Goldberg D (1989) Genetic algorithm in search, optimization and machine learning. Addison Wesley, Boston, p 36

Kacem I (2013) Genetic algorithms for solving flexible job shop scheduling problems. In: Metaheuristics for production scheduling. ISBN 9781118731598. https://doi.org/10.1002/9781118731598.ch2

Kadri AA, Labadi K, Kacem I (2013) An integrated stochastic petri net and GA for dynamic rebalancing in public bicycle-sharing systems. In: 43rd international conference on computer and industrial engineering (CIE43), October 16–18, 2013, vol 2. Hong Kong, pp 1304–1311

Kadri AA, Labadi K, Kacem I (2015) An integrated petri net and genetic algorithm based approach for performance optimization of bicycle-sharing systems. Eur J Ind Eng 9(5):638–663CrossRef

Kadri AA, Kacem I, Labadi K (2016) A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems. Comput Ind Eng 95(2016):41–52CrossRef

Kaltenbrunner A, Meza R, Grivolla J, Codina J, Banchs R (2010) Urban cycles and mobility patterns: exploring and predicting trends in a bicycle-based public transport system. Pervasive Mob Comput 6:455–466CrossRef

Ko CH, Wang SF (2011) Precast production scheduling using multi-objective genetic algorithms. Expert Syst Appl 38(7):8293–8302CrossRef

Laporte G, Meunier F, Calvo RW (2015) Shared mobility systems. 4OR 13(4):341–360. https://doi.org/10.1007/s10288-015-0301-z MathSciNetCrossRefMATH

Martens K (2007) Promoting bike and ride: the Dutch experience. Transp Res Part A 41:326–338

Meddin R, DeMaio P (2016) The bike sharing world map. http://www.metrobike.net/

Midgley P (2009) The role of smart bike-sharing systems in urban mobility. Journeys 2:23–31

Pan G, Li K, Ouyang A, Li K (2016) Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP. Soft Comput 20(2):555–566CrossRef

Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244CrossRefMATH

Papazek P, Raidl GR, Rainer-Harbach M, Hu B (2013) A PILOT/VND/GRASP hybrid for the static balancing of public bicycle-sharing systems. In: Moreno-Diaz R, Pichler F, Quesada-Arencibia A (eds) EUROCAST, vol 8111. LNCS, pp 372–379

Pucher J, Buehler R, Seinen M (2011) Bicycling renaissance in North America? An update and re-appraisal of cycling trends and policies. Transp Res 45(6):451–475

Rainer-Harbach M, Papazek P, Hu B, Raidl GR (2013) Balancing bicycle-sharing systems: a variable neighborhood search approach. In: Middendorf M, Blum C (eds) EvoCOP 2013, vol 7832. LNCS, pp 121–132

Raviv T, Tzur M, Forma I (2013) Static repositioning in a bike-sharing system: models and solution approaches. EURO J Transp Logist 2:187–229CrossRef

Samanlioglu F, Ferrell WG, Kurz ME (2012) An interactive memetic algorithm for production and manufacturing problems modelled as a multi-objective travelling salesman problem. Int J Prod Res 50(20):5671–5682CrossRef

Schulz AS (1996) Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Proceedings of the 5th IPCO conference, pp 301–315

Shaheen SA, Stacey G, Hua Z (2010) Bike sharing in Europe, the Americas, and Asia past, present, and future. J Transp Res Board 2143:159–167CrossRef

Sharma G, Abbas S, Gupt V (2012) Solving transportation problem with the various method of linear programming problem. Asian J Curr Eng Maths 1(3):81–83

Shu J, Chou M, Liu Q, Teo CP, Wang IL (2013) Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems. Oper Res 61(6):1346–1359MathSciNetCrossRefMATH

Vogel P, Greisera T, Mattfeld D (2011) Understanding bike-sharing systems using data mining: exploring activity patterns. 14th EWGT, 26th MEC, 1st RH, Procedia Soc Behav Sci 20:514–523CrossRef

Title: Lower and upper bounds for scheduling multiple balancing vehicles in bicycle-sharing systems
Authors: Ahmed A. Kadri
Imed Kacem
Karim Labadi
Publication date: 31-05-2018
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 14/2019
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3258-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 14/2019

Realized Laplace transforms for pure jump semimartingales with presence of microstructure noise

Trapezoidal cubic fuzzy number Einstein hybrid weighted averaging operators and its application to decision making

Dealer using a new trapezoidal cubic hesitant fuzzy TOPSIS method and application to group decision-making program

Application of neural-networks and neuro-fuzzy systems for the prediction of short-duration forces acting on the blunt bodies

Differential privacy for publishing enterprise-scale WLAN traces

Neyman–Pearson lemma based on intuitionistic fuzzy parameters

Premium Partner