摘要：共享单车再平衡问题(BRP)是单一商品旅行商问题(1-PDTSP)的扩展,是一类NP难问题。针对已有算法求解速度慢,不利于实现实时调度优化的缺点,提出一种求解BRP的非代际遗传算法。基于个体搜索机制保留优异个体,设计线路交叉算子和k点破坏修复变异算子,引入破坏修复机制,当算法收敛变慢时自动生成新个体进入种群以避免陷入局部最优解。应用BRP标准算例测试表明:在小规模算例上该算法均能找到最优解,平均CPU消耗为3.8 s;在中等规模与大规模算例上,该算法找到9个算例的最优解,并且其运算速度相较于分支定界算法和线路破坏与修复启发式算法提升77%以上。

摘要：公共自行车系统再平衡调度事关城市公共自行车系统的运营效率与客户服务水平高低。在已有研究基础上,设计了求解BRP的人工免疫克隆选择算法,算法采用多维整数编码方法,结合问题特点设计了新的抗体相似性度量方法及抗体抑制策略,并在算法框架中引入二次应答求解机制。运用标准算例测试一次应答表明:该算法在求解规模小于50个点的问题上均能找到最优解,但平均CPU消耗比精确算法快96.80%,在求解规模为50个点到100个点的问题上,该算法求解质量比精确算法低7.43%,与遗传算法相当,平均CPU消耗比精确算法快96.8%;运用改进标准算例进行二次应答测试表明:二次应答的求解质量比一次应答略高,二次应答的求解CPU消耗比一次应答快39%以上。

摘要：共享单车再平衡问题是一类NP-难问题,已有启发式求解算法随着问题规模扩大求解速度显著变慢。本文先讨论了该问题的线路可行变换性质,推导证明了插入构造可行解时,被插入位置允许插入客户点的容量区间。在此基础上,提出容差概念,设计了容差插入启发式算法,对该算法应用标准算例测试表明,算法速度快,参数设置简单;算法找到11个测试算例的当前最好解,其中1个为新的当前最好解;算法求解大容量问题的质量优于中、小容量问题。