论文部分内容阅读
随着社会经济的快速发展,私家车数量快速增长,给城市带来了交通拥挤、空气污染等一系列问题,共享自行车是解决这些问题的一种有效工具,并且为市民短距离出行带来便利,符合国家推广的绿色环保政策。然而,伴随而来的站点自行车数目不平衡会一定程度上降低自行车共享系统的利用率,因此需要运营商根据历史使用情况重新平衡每个站点的自行车数目。本文即对该问题进行研究,主要工作如下:对单车多访问静态再平衡问题进行研究,由于该问题是NP难问题,2017年Cruz等提出求解该问题的ILS算法,获得较好的结果,但是该算法结构较为复杂,修复算子耗费大量时间,且修复后得到劣质解的几率较大,影响优化结果。针对该问题,本文提出基于单亲遗传算法的求解方法P-SMSBR,设计较为简练的优化过程,运用十进制编码表示运载车路径方案,引入7种变异算子参与演化,并采用精英策略增强算法的搜索能力。利用大量模拟数据和真实城市数据对算法ILS和P-SMSBR的优化性能进行测试和对比分析。实验结果表明,P-SMSBR算法能够在较短的时间内获得较ILS算法更短的运载车路径方案,且随着站点数增多,P-SMSBR算法优势更加显著。为进一步增强P-SMSBR算法的爬山能力,引入模拟退火算法,并将其与单亲遗传算法相结合,提出求解单车多访问静态再平衡问题的启发式算法CPS。利用模拟退火算法温度控制演化迭代,从某一初始温度开始,伴随温度不断下降,结合概率突跳特性在解空间中随机寻找全局最优解。采用相同的实验测试数据集,对算法ILS、P-SMSBR和CPS的优化性能进行对比分析。实验结果表明,在满足站点需求情况下,随着车站数量增多,算法CPS能够获得较算法ILS和P-SMSBR更短的调度路径。基于算法P-SMSBR和CPS,设计一款用于生成运载车最短调度路径的应用软件。该软件使用Java语言开发,包含部署与设计、运行记录存储、简述和关于产品等四个主要功能模块。部署与设计模块是该软件的核心部分,集成了算法P-SMSBR和CPS的最短调度路径设计方案;运行记录存储模块用于保存相应设计方案的结果;简述模块主要介绍该软件使用注意事项;关于产品模块主要介绍开发团队信息和联系方式,以便后期提供技术支持等。综上所述,本文对自行车共享系统静态再平衡问题进行研究,提出求解单车多访问子问题的有效求解算法P-SMSBR和CPS,并设计一款相关的应用软件,这些研究工作将进一步推进自行车共享系统的优化与发展。