张建同 戴倩楠 丁烨

摘 要：   研究考虑需求可拆分的共享单车调度优化问题为可拆分单商品取送货TSP问题，考虑一辆调度车，允许调度车多次访问各站点，每次满足站点的部分需求，即允许对站点的需求进行拆分。首先，考虑到调度车容量限制，统筹安排调度车行驶路径和调度车在每个站点的取车量、送车量，使得企业的运营成本达到最优。其次，提出了一种改进的变邻域搜索算法求解上述问题，使算法在陷入局部最优解时改变邻域结构，扩大搜索范围，以此提升算法跳出局部最优解的能力，加快收敛速度。最后，用数值实验验证了算法的有效性。研究结论拓展了可拆分单商品取送货问题的相关理论，并为共享单车企业的实际运营提供决策支持。

关键词：  共享单车；路径规划；需求可拆分；改进变邻域算法

中图分类号：  F 572

文献标志码：   A

Optimization of Distribution of Ofo BikesConsidering Split-Demand

ZHANG Jiantong DAI Qiannan DING Ye

（School of Economics and Management， Tongji University， Shanghai 200092， China）

Abstract：  This research studies the static bike rebalancing problem considering split-demand which can be viewed as split-demand one-commodity pickup and delivery traveling salesman problem， considering a shunting vehicle， where multiple visits are allowed to be performed at each node， i.e.， the demand for nodes is allowed to be split. The capacity limitation of the shunting vehicle is considered， and the driving path of the shunting vehicle and the amount of the vehicle fetching and delivering at each station are generally arranged， so as to make the operation cost of the enterprise optimal. Secondly， an improved variable neighborhood search algorithm is proposed to solve the problem above， when the algorithm falls into the local optimal solution， the neighborhood structure is changed and the search range is expanded， so as to improve the algorithms ability to jump out of the local optimal solution and speed up the convergence speed. Finally， numerical experiments verify the effectiveness of the algorithm. This research expands the relevant theories of split-demand one-commodity pickup and delivery traveling salesman problem， and provides decision support for the actual operation of bike-sharing companies.

Key words：  free-floating sharing bike；vehicle routing problem；split-demand；improved variable neighborhood search algorithm

作为“共享经济”领域最热的一类产品，共享单车的出现很好地解决了城市出行的“最后一公里”问题。目前共享单车进入稳步发展阶段，后续市场竞争模式从增量竞争转向存量竞争，从扩张转为精细化运营。当前共享单车市场处于稳定期，而随着碳中和、健康出行等倡议以及用户逐渐适应市场，共享单车的用户规模将有一个上升空间。与此同时单车供需不匹配的问题也日益凸显，企业在各大城市投放的共享单车量已超过理论上的需求量，然而调查显示，共享单车的潮汐现象严重。在工作日早高峰时段，交通枢纽吸引了大量的车辆停靠，严重影响周围的交通通行，这些单车在平峰时段处于暂时闲置状态，并且造成了局部地区车辆不足的问题；……