Dynamic bicycle relocation problem with broken bicycles

Yutong Cai, Ghim Ping Ong and Qiang Meng

Transportation Research Part E: Logistics and Transportation Review, 2022, vol. 165, issue C

Abstract: 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.

Keywords: Bicycle-sharing; Column generation; Branch-and-price; Variable neighborhood search; Markov decision process (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554522002575
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:165:y:2022:i:c:s1366554522002575

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2022.102877

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().