吕 畅，张超勇+，张道德，任亚平，孟磊磊

(1.华中科技大学 数字制造装备与技术国家重点实验室，湖北 武汉 430074；2.湖北工业大学 机械工程学院，湖北 武汉 430068；3.聊城大学 计算机学院，山东 聊城 252059)

0 引言

共享单车系统(Bike Sharing System, BSS)1965年起源于荷兰，是一种低碳环保的出行方式。国内近10年发展势头猛烈，由其衍生而来的共享电动车，共享汽车也开始进入人们的视线。但无论如何变化，共享单车的再平衡问题(Bike Sharing Rebalancing Problem, BSRP)，即如何解决各个共享站点供需平衡﹑降低再平衡作业成本提升作业效率，是BSS亟需解决的关键问题之一。与一般的路径规划问题相比，BSRP需要在每一个站点处进行放置或取走多少数量货物的决策，由于调度货车载量的限制，该决策又势必影响到访问站点的选择，极大增添了问题的复杂度。Ho等[1]在2014年已证明BSRP属于NP-hard问题，由于该问题具有重要的理论和实际应用价值，受到社会以及学术界的广泛关注。

实际的BSS通常规模大、站点数量多、仓库不唯一，所需调度车辆较多，但若减少调度车辆，由于车载上限，将导致多次往返，增加行驶路程。因此，允许站点临时停靠以及多次访问，极大增添了再平衡作业模型的灵活性，Chemla等[2]建立了允许站点的临时停靠以及多次访问的共享单车再平衡问题的数学模型，并获得了不错的效果；Erdogan等[3]所提出的模型也允许多次访问和临时停靠，并通过精确算法获得60站点内的最优解。

站点分组访问的思想源于Baldacci等[4]所提出的集群车辆路径(Grouping Vehicle Routing Problem, GVRP)模型，在该模型中站点被分为不同的站点族，每辆调度货车必须访问每个族内的至少一个站点。……