Multi-vehicle static bike repositioning problems

Abstract

Bike repositioning problems (BRPs) emerged from the operation of Bike Sharing Systems (BSSs). Due to the asymmetrical bike trips of the users, it is common for the distribution of bikes in the system to be imbalanced. Bike repositioning is typically conducted by traversing the locations using vehicles, loading bikes from oversupplied locations to the vehicles, and unloading bikes to locations in deficit. One observation is that heavy vehicles like fossil fuel trucks have been widely used in conventional repositioning activities. The fuel consumption and emission may impair the environmental friendliness of BSSs. Given that emission-free light vehicles like bike trailers have been used for repositioning operations, a repositioning fleet including light vehicles may mitigate the issue. This thesis first investigates a static green bike-repositioning problem with heavy and light vehicles, aiming to minimize the total cost, including the expected penalty costs for user dissatisfaction, internal variable costs (operating and fuel costs), and external costs. The circumstances that incorporating light vehicles into the repositioning fleet can reduce both the total cost and fuel consumption are figured out.

Another observation is that e-bikes have been provided by operators in recent years, which brings about two new concerns. One concern is that some operators offer e-bikes and conventional bikes, complicating the repositioning operations. This thesis addresses this concern by looking into a static double-type bike repositioning problem with the objective of minimizing the weighted sum of the total deficiencies of e-bikes and conventional bikes, the total travel time, and the total loading and unloading time. Subject to two special yet practical situations, two algorithms are developed to solve the loading subproblem and embedded in a hybrid genetic search (HGS) algorithm to solve the master problem effectively.

The other concern is about the charging problem of e-bikes. Existing studies mainly focused on battery swapping with little attention on charging the e-bikes using charging docks. This thesis then investigates an e-bike repositioning problem with charging and non-charging docks with the objective of minimizing the weighted sum of the total penalty that incorporates e-bikes with adequate or inadequate batteries, the total travel time, and the total loading, unloading, and moving time. The effects of the percentage of charging docks and the repositioning time budget are examined. Since the charging operations complicate the repositioning operations, three heuristics are provided to solve the loading, unloading, and moving subproblem, which are embedded in HGS for solving the master problem efficiently.