Abstract: Bike SharingRebalancing Problem(BRP)is an NP-Hard Problem. With the problem scale expansion, the existing heuristic algorithms computing speed is significantly slower. In this paper, the route feasible transformation property of this problem is discussed firstly, and then it is deduced that the insertion position allows the insertion of the capacity range of the customer point when constructing a feasible solution. On this basis, the concept of Capacity Range Length(CRL)is proposed, and also theCapacity Range Length Insertion Heuristics(CRLIH)is presented. The existing heuristics on the benchmarkproblems show that:1) CRLIHis faster than other reported heuristics and have smaller parameters to set. 2)CRLIH finds the current best solution for the 11 problems, and one of them is the new current best solution. 3)When solving large-capacity problems, the quality of CRLIH is superior to that of medium-and small-capacity problems.

Key words: vehicle routing problem, bike sharingrebalancing problem, insertion heuristics, capacity range length

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

关键词: 车辆路径问题(VRP), 单车再平衡问题(BRP), 插入启发式算法, 容差