Chemical reaction optimization for bike repositioning problems

Abstract

Bike sharing is very popular worldwide. It provides an alternative to the use of private cars and can serve the last-mile mode for passengers to public transportation. There are currently two types of bike-sharing system (BSS) operated: traditional BSS and free-floating BSS. One common phenomenon of bike-sharing in both systems is the imbalanced distribution of bikes. Hence, in practice, trucks are deployed to reallocate the bikes to improve the performance of BSS. This operational problem is called a bike repositioning problem (BRP). This thesis focuses on the bike repositioning operated during the night time, which is referred to as static BRPs. In this thesis, single-vehicle and multiple-vehicle static BRPs are proposed for the traditional BSS and a multiple-vehicle static BRP is studied for free-floating BSS. For both the traditional and free-floating BRPs, the objectives of the repositioning are to minimize the unmet demand and the total operational time (including vehicle travel time and the time used for loading and unloading bikes). In addition, minimizing the inconvenience of getting a bike from the free-floating BSS is added when solving a free-floating BRP. For solving the proposed static BRPs, a new metaheuristic called chemical reaction optimization (CRO) algorithm, which mimics interactions between molecules in elementary reactions, is considered. To make the metaheuristic fit the solution of the problems, an enhanced version incorporating new concepts, operators, and subroutines are proposed. The numerical experiments demonstrate the efficiency and effectiveness of the enhanced CRO and prove that the enhanced CRO obtains better solutions than the original CRO.