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

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

作　　者：冯炳超 吴璟莉[1,2,3] FENG Bing-chao;WU Jing-li(College of Computer Science and Information Technology,Guangxi Normal University,Guilin,Guangxi 541004,China;Guangxi Key Lab of Multi-source Information Mining&Security,Guangxi Normal University,Guilin,Guangxi 541004,China;Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing,Guilin,Guangxi 541004,China)

机构地区：[1]广西师范大学计算机科学与信息工程学院,广西桂林541004 [2]广西师范大学广西多源信息挖掘与安全重点实验室,广西桂林541004 [3]广西区域多源信息集成与智能处理协同创新中心,广西桂林541004

出　　处：《计算机科学》2020年第S01期114-118,共5页Computer Science

基　　金：国家自然科学基金项目(61762015,61502111,61662007,61763003);广西自然科学基金项目(2016GXNSFAA380192);广西研究生教育创新计划项目(XYCSZ2018078);“八桂学者”工程专项;广西科技基地和人才专项(AD16380008)。

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]