Abstract: Shared bike has been developing rapidly in China, encouraging people to cycle and use this low-carbon transport mode to make trips. Accelerating the development of shared bikes is an important way to solve the last mile, urban congestion and environmental pollution problems. With the irregularity of people parking share bikes, the station inventory is unbalanced in the shared bike system. How to optimize the station inventory to meet user demand that must be solved by related companies. The repositioning routing optimization of shared bikes is a key mean to realize the reasonable inventory level at stations. This paper investigates a static bike repositioning problem (SBRP) with multiple depots, and a mixed-integer nonlinear programming model is proposed. Different from the objective function of cost or time used in the path optimization problems, this paper uses the nonlinear penalty objective functions based on station inventory to describe user demand, leading to a convex optimization problem. In order to simplify our problem, we utilize a piecewise linear function to linearize the objective function. Based on characteristics ofstationnetwork,avariableneighborhoodsearchalgorithm(VNS)andagreedyalgorithmforconstructing the initial solutions are designed to solve our problem. Finally, a case study of a shared bike company is presentedtoaccountfortherationalityandeffectivenessofthemodelandalgorithm.

Key words: multiple depots, shared bike, routing optimization, VNS

摘要： 共享单车是我国大力提倡的低碳交通出行模式,加快共享单车发展是解决最后一公里、城市拥堵和环境污染等问题的重要途径。由于人们停放共享单车的无规律性,使得共享单车系统中各车桩的单车库存量存在不平衡。如何合理的对车桩中的单车进行重新调配,来满足用户的需求,是相关企业亟待解决的问题。共享单车的调配路线优化是优化车桩库存量的重要手段之一。本文研究多仓库条件下的货车调配路线优化问题,建立了一个混合整数非线性规划模型。不同于传统的路径优化问题的研究大多是以成本或时间为目标,本文采用基于车桩库存量的非线性惩罚函数来表示用户需求,从而使得所研究的问题是一个凸函数优化问题。为了简化本文的问题,将目标函数分段线性化。基于车桩网络的特点,设计了变邻域搜索算法,以及构建初始解的贪婪算法。最后,以某共享单车公司为例,进行算例分析,来说明模型和算法的合理性和有效性。

关键词: 多仓库, 共享单车, 路线优化, 变邻域搜索