计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 114-118.doi: 10.11896/JsJkx.190700120
冯炳超1, 吴璟莉1, 2, 3
FENG Bing-chao1 and WU Jing-li1, 2, 3
摘要: 自行车共享系统具有改善城市交通出行结构,减少交通污染等优点。各站点自行车数量相对平衡对于提高共享系统的利用率非常重要,自行车共享系统再平衡问题应运而生。该问题属于NP难问题。2017,年Fábio等提出求解单车多访问静态再平衡问题的ILS算法,获得了较好的结果,但是该算法结构较为复杂,修复算子耗费大量时间,且修复后得到劣质解的概率较大,影响了优化结果。针对该问题,提出基于单亲遗传算法的求解方法P-SMSBR,设计了较为简练的优化过程,运用十进制编码表示运载车路径方案,引入7种变异算子参与演化,并采用精英策略增强算法的搜索能力。利用大量模拟数据和真实数据对算法性能进行测试,实验结果表明,P-SMSBR算法具有较好的优化效果,能够在较短的时间内获得较ILS算法更短的运载车路径方案,且随着站点数的增多,P-SMSBR算法优势更加显著,是一种求解自行车共享系统静态再平衡问题的有效方法。
中图分类号:
[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 |
|