计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 114-118.doi: 10.11896/JsJkx.190700120

• 人工智能 • 上一篇    下一篇

求解自行车共享系统静态再平衡问题的单亲遗传算法

冯炳超1, 吴璟莉1, 2, 3   

  1. 1 广西师范大学计算机科学与信息工程学院 广西 桂林 541004;
    2 广西师范大学广西多源信息挖掘与安全重点实验室 广西 桂林 541004;
    3 广西区域多源信息集成与智能处理协同创新中心 广西 桂林 541004
  • 发布日期:2020-07-07
  • 通讯作者: 吴璟莉(wJlhappy@mailbox.gxnu.edu.cn)
  • 作者简介:1620438678@qq.com
  • 基金资助:
    国家自然科学基金项目(61762015,61502111,61662007,61763003);广西自然科学基金项目(2016GXNSFAA380192);广西研究生教育创新计划项目(XYCSZ2018078);“八桂学者”工程专项;广西科技基地和人才专项(AD16380008)

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).

摘要: 自行车共享系统具有改善城市交通出行结构,减少交通污染等优点。各站点自行车数量相对平衡对于提高共享系统的利用率非常重要,自行车共享系统再平衡问题应运而生。该问题属于NP难问题。2017,年Fábio等提出求解单车多访问静态再平衡问题的ILS算法,获得了较好的结果,但是该算法结构较为复杂,修复算子耗费大量时间,且修复后得到劣质解的概率较大,影响了优化结果。针对该问题,提出基于单亲遗传算法的求解方法P-SMSBR,设计了较为简练的优化过程,运用十进制编码表示运载车路径方案,引入7种变异算子参与演化,并采用精英策略增强算法的搜索能力。利用大量模拟数据和真实数据对算法性能进行测试,实验结果表明,P-SMSBR算法具有较好的优化效果,能够在较短的时间内获得较ILS算法更短的运载车路径方案,且随着站点数的增多,P-SMSBR算法优势更加显著,是一种求解自行车共享系统静态再平衡问题的有效方法。

关键词: NP难, 单亲遗传算法, 静态再平衡问题, 启发式, 自行车共享系统

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

中图分类号: 

  • TP301
[1] GOOGLE.Interactive bike sharing world map (V10.17.1).http://bike sharing map.com.
[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.
[14] DELL’AMICO M,HADJICOSTANTINOU E,IORI M,et al.
[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] 张露萍, 徐飞.
具有突触规则的脉冲神经膜系统综述
Survey on Spiking Neural P Systems with Rules on Synapses
计算机科学, 2022, 49(8): 217-224. https://doi.org/10.11896/jsjkx.220300078
[2] 耿海军, 王威, 尹霞.
基于混合软件定义网络的单节点故障保护方法
Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks
计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[3] 郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波.
一种面向动态部分可重构片上系统的列表式软硬件划分算法
List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip
计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198
[4] 刘忠慧, 赵琦, 邹璐, 闵帆.
三元概念的启发式构建及其在社会化推荐中的应用
Heuristic Construction of Triadic Concept and Its Application in Social Recommendation
计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[5] 郭启程, 杜晓玉, 张延宇, 周毅.
基于改进鲸鱼算法的无人机三维路径规划
Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm
计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[6] 唐文君, 刘岳, 陈荣.
移动边缘计算中的动态用户分配方法
User Allocation Approach in Dynamic Mobile Edge Computing
计算机科学, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079
[7] 郭飞雁, 唐兵.
基于用户延迟感知的移动边缘服务器放置方法
Mobile Edge Server Placement Method Based on User Latency-aware
计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[8] 胡士娟, 鲁海燕, 向蕾, 沈莞蔷.
求解MMTSP的模糊聚类单亲遗传算法
Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP
计算机科学, 2020, 47(6): 219-224. https://doi.org/10.11896/jsjkx.190500137
[9] 张旭, 王莉莉, 杨博韬.
带有一刀切约束的二维非规则装箱算法
Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints
计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[10] 潘恒, 李景峰, 马君虎.
可抵御内部威胁的角色动态调整算法
Role Dynamic Adjustment Algorithm for Resisting Insider Threat
计算机科学, 2020, 47(5): 313-318. https://doi.org/10.11896/jsjkx.190800051
[11] 杨婷, 罗飞, 丁炜超, 卢海峰.
一种自适应优化松弛量的装箱算法
Bin Packing Algorithm Based on Adaptive Optimization of Slack
计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[12] 郭超, 王磊, 尹爱华.
求解一刀切式二维矩形Strip Packing问题的混合搜索算法
Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem
计算机科学, 2020, 47(11A): 119-125. https://doi.org/10.11896/jsjkx.200200016
[13] 罗飞, 任强, 丁炜超, 卢海峰.
基于最小松弛量的启发式一维装箱算法
Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack
计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[14] 张澍裕, 宫达, 谢兵, 刘开贵.
基于实时GPS的公交短时动态调度算法
Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS
计算机科学, 2019, 46(6A): 497-501.
[15] 余建军, 吴春明.
基于禁忌遗传优化的离线静态虚拟网映射算法
Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization
计算机科学, 2019, 46(12): 114-119. https://doi.org/10.11896/jsjkx.181001981
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!