Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 114-118.doi: 10.11896/JsJkx.190700120

• Artificial Intelligence • Previous Articles     Next Articles

Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System

FENG Bing-chao1 and WU Jing-li1, 2, 3   

  1. 1 College of Computer Science and Information Technology,Guangxi Normal University,Guilin,Guangxi 541004,China
    2 Guangxi Key Lab of Multi-source Information Mining & Security,Guangxi Normal University,Guilin,Guangxi 541004,China
    3 Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing,Guilin,Guangxi 541004,China
  • Published:2020-07-07
  • About author:FENG Bing-chao, born in 1993, postgraduate.His research interest is intelligent optimization algorithm.
    WU Jing-li, born in 1978.Her current research interests include bioinforma-tics, computational biology, algorithms and complexity.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61762015,61502111,61662007,61763003),Guangxi Natural Scie-nce Foundation (2016GXNSFAA380192),Innovation ProJect of Guangxi Graduate Education(XYCSZ2018078) and “Bagui Scholar” ProJect Special Funds and Guangxi Science Base and Talent Special Support(AD16380008).

Abstract: The bicycle sharing system has the advantages of improving urban traffic travel structure and reducing traffic pollution.The relative balance of the number of bicycles at each site is very important for improving the utilization of the sharing system,and the problem of rebalancing bicycle sharing systemis proposed.Since the problem is NP-hard one,Fábio et al.proposed the ILS algorithm for solving the single-vehicle and multiple-visit static bicycle rebalancing case in 2017,and obtained good results.However,the ILS algorithm has very complicated structure,and the repair operator,which consumes a lot of time,has a good chance of generating inferior solution.To solve this problem,in this paper,a partheno-genetic algorithm based method P-SMSBR is presented.Amore concise optimization process is designed,and decimal code is used to represent a vehicle path solution.Seven mutation operators are introduced,and elite strategy is adopted to enhance the search ability of the algorithm.A large number of simulation and real data were adopted to test the performance of the algorithm.The experimental results indicate that the P-SMSBR algorithm proposed in this paper has better optimization effect,which can obtain a shorter vehicle path than that obtained by the ILS algorithm in a shorter time.In addition,the P-SMSBR algorithm shows moresignificant advantages with the increase of the number of sites.It is an effective method for solving the single-vehicle and multiple-visit static bicycle rebalancing problem.

Key words: Bicycle sharing system, Heuristic, NP hard, Partheno-genetic algorithm, Static bike rebalancing problem

CLC Number: 

  • TP301
[1] GOOGLE.Interactive bike sharing world map (V10.17.1).http://bike sharing
[2] CRUZF,SUBRAMANIAN A,BRUCK B P,etal.A heuristic algorithm for a single vehicle static bike sharing rebalancing problem .Computers & Operations Research,2017,79:19-33.
[3] BENCHIMOL M,BENCHIMOL P,CHAPPERT B,et al.Ba-lancing the stations of a self service “bike hire” system .RAIRO Oper Res,2011,45(1):33-61.
[4] CAGGIANI L,OTTOMANELLI M.A dynamic simulation based model for optimal fleet repositioning in bike sharing systems.Procedia Social and Behavioral Sciences,2013,87:203-210.
[5] ERDOGˇAN G,BATTARRA M,CALVOR W,et al.An exact algorithm for the static rebalancing problem arising in bicycle sharing systems.Eur J Oper Res,2015,245(3):667-679.
[6] CHEMLA D,MEUNIER F,CALVOR W,et al.Bike sharing systems:solving the static rebalancing problem.Discrete Optimization,2013,10(2):120-146.
[7] LI Y F,SZETO W Y,LONG J C,et al.A multipletype bike repositioning problem.Transportation Research,2016,90:263-278.
[8] ERDOGˇAN G,LAPORTE G,CALVOR W,et al.The static bicycle relocation problem with demand intervals.European Journal of Operational Research,2014,238(2):451-457.
[9] HOS C,SZETO W Y.Solving a static repositioning problem in bike-sharing systems using iterated tabu search.Transportation Research Part E,2014,69:180-198.
[10] CAGGIANI L,OTTOMANELLI M.A modular soft computing based method for vehicles repositioning in bike-sharing systems.Proc Social Behav,2012,54:675-684.
[11] TING C K,LIAO X L.The selective pickup and delivery problem:Formulation and a memetic algorithm.Int J Prod Econ,2013,141(1):199-211.
[12] SALAZAR J J,SANTOS B.The split-demand one-commoditypickup-and-delivery travelling salesman problem.Transp Res Part B:Methodol,2015,75:58-73.
[13] DELL’AMICO M,IORI M,NOVELLANI S,et al.A destroyand repair algorithm for thebike sharing rebalancing problem.Comput Oper Res,2016,71:149-162.
[15] The bike sharing rebalancing problem:mathematicalformulations and benchmark instances.Omega,2014,45:7-19.
[16] FORMA I A,RAVIV T,TZUR M,et al.A3-step math heuristic for the static repositioningproblem in bike-sharing systems.Transp Res Part B:Methodol,2015,71:230-247.
[17] RAVIV T,TZURM,FORMA I A,et al.Static repositioning in a bike-sharing system:models and solution approaches.EURO J Transp Logist,2013,2:187-229.
[18] LIN J H,CHOU T C.A geo-aware and VRP-based public bicycle redistribution system.International Journal of Vehicular Technology,2012,10:1-14.
[19] ALVAREZR,BELENGUERJM,BENAVENTE,et al.Optimizing the level of service quality of a bike-sharing system.Omega,2016,62:163-175.
[20] GASPEROLD,RENDLA,URLIT,et al.A Hybrid ACO+CP for Balancing Bicycle Sharing Systems.Hybrid Metaheuristics,2013,7919:198-212.
[21] BULHES T,SUBRAMANIAN A,ERDOCˇA N G,et al.The static bike relocation problem with multiple vehicles and visits.European Journal of Operational Research,2018,264:508-523.
[22] RAINER M,PAPAZEK P,RAIDL G,et al.Raidl,PILOT, GRASP,and VNS approaches for the static balancing of bicycle sharing systems.J Glob Optim,2015,63:597-629.
[23] ESPEGREN H M,KRISTIANSLUND J,ANDERSSON H, et al.The static bicycle repositioning problem.Literature Survey and Newformulation,2016,9855:337-351.
[24] MLADENOVIC' N,HANSEN P.Variable neighborhood search.Comput Oper Res,1997,24(11):1097-1100.
[25] HERNNDEZ H,SALAZAR J J.A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery.Discret Appl Math,2004,145:126-139.
[1] GENG Hai-jun, WANG Wei, YIN Xia. Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks [J]. Computer Science, 2022, 49(2): 329-335.
[2] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[3] GUO Biao, TANG Qi, WEN Zhi-min, FU Juan, WANG Ling, WEI Ji-bo. List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip [J]. Computer Science, 2021, 48(6): 19-25.
[4] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[5] TANG Wen-jun, LIU Yue, CHEN Rong. User Allocation Approach in Dynamic Mobile Edge Computing [J]. Computer Science, 2021, 48(1): 58-64.
[6] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[7] HU Shi-juan, LU Hai-yan, XIANG Lei, SHEN Wan-qiang. Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP [J]. Computer Science, 2020, 47(6): 219-224.
[8] ZHANG Xu, WANG Li-li, YANG Bo-tao. Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints [J]. Computer Science, 2020, 47(5): 212-216.
[9] PAN Heng, LI Jing feng, MA Jun hu. Role Dynamic Adjustment Algorithm for Resisting Insider Threat [J]. Computer Science, 2020, 47(5): 313-318.
[10] YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack [J]. Computer Science, 2020, 47(4): 211-216.
[11] GUO Chao, WANG Lei, YIN Ai-hua. Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem [J]. Computer Science, 2020, 47(11A): 119-125.
[12] LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng. Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack [J]. Computer Science, 2019, 46(9): 315-320.
[13] ZHANG Shu-yu, DONG Da, XIE Bing, LIU Kai-gui. Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS [J]. Computer Science, 2019, 46(6A): 497-501.
[14] JIANG Ze-hua, WANG Yi-bo, XU Gang, YANG Xi-bei, WANG Ping-xin. Multi-scale Based Accelerator for Attribute Reduction [J]. Computer Science, 2019, 46(12): 250-256.
[15] ZHANG Ming, WEI Bo, WANG Jin-dong. Satellite Reactive Scheduling Based on Heuristic Algorithm [J]. Computer Science, 2019, 46(10): 90-96.
Full text



No Suggested Reading articles found!