Dynamic bicycle relocation problem with broken bicycles

• This study considers the uncertainties in both broken bicycle quantity and relocation demand during bicycle relocation activities. • This study proposes an effective adaptive relocation strategy for the relocation vehicles to achieve maximum expected satisfied demand. • This study develops an interesting B&P approach with the pricing problem formulated as a MDP to exploit the value of adaptive routing of relocation vehicles. • This study further designs an efficient hybrid heuristics incorporating variable neighbourhood search and partial optimization to solve the large-scale problems. In response to the demand imbalance across stations with broken bicycles in a bicycle sharing system (BSS), this study proposes a novel decision problem that aims to determine the size of the fleet of relocation vehicles, the bicycle stations they are assigned to serve, and efficient adaptive routing plans to ensure a good level of bicycle inventory at each station and on a timely basis, by considering the broken bicycles in each station, which is referred to as the dynamic bicycle relocation problem with broken bicycle consideration (a.k.a DBRPB). Assuming that the numbers of broken bicycles and bicycle relocation demand at each bicycle station are independent random variables and will only be revealed upon the arrival of the relocation vehicle, the objective of the DBRPB is to maximize the expected total satisfied demand, comprising both relocation demand and broken bicycle demand, using the adaptive routing strategy while incorporating the deployment cost of the relocation vehicles. The relocation vehicle will adjust its relocation route after the actual demand is revealed, every time it visits a station. A tailored branch-and-price (B&P) approach is proposed to find the exact optimal solution of the DBRPB. To solve the pricing problem, a tailored Markov decision process (MDP) is formulated in the pricing problem of the B&P approach, to determine both the optimal value of the expected satisfied demand and the next station to visit, given the available information, including time, current station, the unordered set of unvisited stations and the bicycle inventory of the relocation vehicle. A hybrid heuristic method incorporating variable neighbourhood search (VNS) and partial optimization is further proposed to solve the large-scale problem. Numerical experiments using a randomly generated BSS network and the Nanjing BSS respectively are conducted to validate the efficiency and effectiveness of the proposed methodology as well as to obtain insights into the impacts of key parameters on the solution.