考虑损坏自行车回收的共享单车调度问题

A Bike Repositioning Problem With Broken Bikes

在共享单车系统中,各站点的自行车需要不断地再平衡以满足用户的需求。同时由于各种因素作用(如自然损耗、人为破坏等),共享单车系统中经常出现大量损坏自行车。为了有效利用卡车装载空间以减少运营商运营成本,提出了一类再平衡可用自行车过程中,对损坏自行车进行回收的共享单车调度问题。以运营商总成本最小化为目标建立了混合整数线性规划模型,并针对问题特性提出了一种混合禁忌搜索算法。数值实验对问题特性和算法性能进行了分析。结果表明回收惩罚系数能改变站点回收优先级,对于调配需求和回收需求都很大的站点,变大回收惩罚系数可以增加站点损坏自行的回收量,所提出算法能有效求解各种规模的问题。

In bike sharing systems,bicycles at each site need to be constantly rebalanced to meet the needs of users.Due to various factors(wear and tear,damage,etc.),a number of broken bikes regularly found in bike sharing systems.This study introduces a bike repositioning problem with broken bikes in order to effectively utilize trucks to reduce the operation cost.A mixed integer linear programming model is proposed to minimize the total cost.A hybrid tabu search is developed to solve the proposed problems.Computation experiments are performed to illustrate problem properties and the performance of the proposed algorithm.Numerical results show that for different stations,the increase of the collection penalty can improve collection priority.For a station with large allocation and collection demands,the increase of the collection penalty can increase the collection number of broken bikes.The proposed solution method can put forward high-quality solutions within short computing time.