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

发布时间：2022-02-12 13:23

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

【文章来源】：计算机科学. 2020,47(S1)北大核心CSCD

【文章页数】：5 页

【部分图文】：

不同n下的路径长度

不同n下的运行时间

图3和图4给出了不同Q取值下的路径长度。在图3中,站点数n=40;在图4中,站点数n=60。图中数据表明,P-SMSBR算法在不同运载车容量下均能获得较ILS算法更短的调度路径。此外,随着运载车容量的增大,由于站点访问次数会有所减少,因此两种算法的调度路径长度均得以缩短,且差距逐渐减小。由此可见,当运载车容量较小时,P-SMSBR算法的优势较为明显。


本文编号：3621798