共享单车再平衡问题及其容差插入启发式算法  

Bike Sharing Rebalancing Problem and Capacity Range Length Insertion Heuristic Algorithm

作　　者：潘立军[1] 符卓[2] 刘喜梅[1] PAN Li-jun;FU Zhuo;LIU Xi-mei(Management Department,Hunan Institute of Engineering,Xiangtan 411201,China;School of Traffic and Transportation Engineering,Central South University,Changsha 410075,China)

机构地区：[1]湖南工程学院管理学院,湖南湘潭411104 [2]中南大学交通运输工程学院,湖南长沙410075

出　　处：《运筹与管理》2019年第10期26-32,共7页Operations Research and Management Science

基　　金：国家自然科学基金面上项目(71271220);湖南省自然科学基金项目(2019JJ60038);湖南省双一流应用特色学科工商管理资助(湘教通[2018]469号)

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

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

分 类 号：O22[理学—运筹学与控制论] TP18[理学—数学]