基于抽样和变邻域搜索的随机共享单车重平衡问题

Stochastic bike-sharing rebalance problem based on sampling and variable neighbourhood search

针对需求随机的共享单车重平衡问题,建立基于场景抽样的两阶段随机规划模型,第一阶段为车辆路径规划模型,第二阶段基于第一阶段得到的车辆路径信息,最大化重平衡效用度期望。为了求解该模型,提出基于拉丁超立方抽样的变邻域搜索算法,并设计了多种不同规模的测试算例,测试结果表明该算法能在短时间内获得具有较高稳定性的有效解。

Aiming at the bike-sharing rebalancing problem with stochastic demands,a two-stage stochastic programming model based on scenarios sampling was established.The first stage is the vehicle routing model,and the second stage is based on the vehicle route obtained by the first stage to maximize the rebalancing utility expectation.A variable neighbourhood search algorithm based on Latin hypercube sampling was proposed to solve the problem.A variety of test cases with different scales were designed.The test results show that the proposed algorithm can obtain effective solutions with high stability in a short time.