Optimization Model and Algorithm for Dockless Bike-Sharing Systems Considering Unusable Bikes in China

Abstract

The damaged dockless shared-bikes are increasingly common in large cities of China, which not only reduce users' satisfactions but also harm the public environment. It is a merging issue for dockless bike-sharing systems to timely recall unusable bikes and replenish new/usable bikes. This paper addresses a maintenance network for a dockless bike-sharing system within a specific region in which the random demands and returns of shared-bikes are considered and the returned bikes have a certain probability to be unusable. The problem is to jointly determine the numbers of unusable and usable bikes to be recalled and replenished, respectively, and the corresponding routes of maintenance vehicles via the maintenance network. The problem is formulated as a stochastic mixed-integer programming model with the objective to maximize the expected revenue of the maintenance network within a operational period. To resolve the such complicated integration-optimization problem efficiently, the formulated model is decomposed into a multi-location newsvendor subproblem and a multiple vehicle routing subproblem with simultaneous delivery and pick-up. An efficient two-stage heuristics is then proposed, which resolves the two subproblems in the two stages of the algorithm, respectively. The computational results based on an real numerical case and a large number of numerical instances validate the performance of the proposed model and algorithm.

Keywords

• Dockless bike
• bike-sharing system
• maintenance
• stochastic mixed-integer programming model
• heuristics