求解公共自行车再平衡问题的克隆选择算法  

Clonal Selection Algorithm for Solving Bike Sharing Rebalancing Problem

作　　者：刘喜梅[1] 潘立军[1] LIU Ximei;PAN Lijun(School of Management,Hunan Institute of Engineering,Xiangtan,Hunan 411104,China)

机构地区：[1]湖南工程学院管理学院,湖南湘潭411104

出　　处：《计算机工程与应用》2020年第11期252-258,共7页Computer Engineering and Applications

基　　金：湖南省自然科学基金(No.2019JJ60038);湖南省双一流应用特色学科工商管理资助(湘教通[2018]469号)。

摘　　要：公共自行车系统再平衡调度事关城市公共自行车系统的运营效率与客户服务水平高低。在已有研究基础上,设计了求解BRP的人工免疫克隆选择算法,算法采用多维整数编码方法,结合问题特点设计了新的抗体相似性度量方法及抗体抑制策略,并在算法框架中引入二次应答求解机制。运用标准算例测试一次应答表明:该算法在求解规模小于50个点的问题上均能找到最优解,但平均CPU消耗比精确算法快96.80%,在求解规模为50个点到100个点的问题上,该算法求解质量比精确算法低7.43%,与遗传算法相当,平均CPU消耗比精确算法快96.8%;运用改进标准算例进行二次应答测试表明:二次应答的求解质量比一次应答略高,二次应答的求解CPU消耗比一次应答快39%以上。Bicycle repositioning is a key point to the operating efficiency and customer service levels in city public bike system.In this paper,on the basis of existing research,the artificial immune clone selection algorithm for BRP is proposed,which uses multidimensional integer coding method,designs a new method of antibody similarity measure method and suppression strategies based on the problem characteristics,and the secondary response solving mechanism is also integrated into algorithm framework.Using benchmark problems test shows that,in the firstly response test,this algorithm can find all optimal solution in the small size problems(n<50),but the average CPU consumption is 96.80%faster than the exact algorithm,and the solution average quality is 7.43%lower than the exact algorithm in the middle size problems(50<n<100),which is same to the genetic algorithm,but the average CPU consumption is 96.8%faster than the exact algorithm.In the secondary response test,the solution quality is better than the first response slightly,CPU consumption is faster than the first response by more than 39%.

关 键 词：车辆路径问题 自行车再平衡问题 人工免疫 克隆选择 抗体相似性 

分 类 号：O22[理学—运筹学与控制论] TP18[理学—数学]