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

作者：冯炳超; 吴璟莉^*

来源：计算机科学, 2020, S1: 114-118.

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

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

• 单位
  广西师范大学