Development of a multi-type bike repositioning model with exact loading and unloading strategies

Abstract

Public bike-sharing systems have been implemented in many cities to provide a sustainable alternative mode for short trips. In every system, the users rent bikes at stations close to their origins and return them at stations close to their destinations, and vehicles with limited capacities are deployed periodically to reposition bikes across stations to restore the station inventory levels. As the bike repositioning operation involves two types of intertwining decisions, routing and loading (and unloading) decisions, it is required to develop models to determine optimal bike repositioning strategy.

This thesis starts with the overviews on the development of public bike-sharing systems and bike-related researches. A review of bike repositioning problem is followed to identify some existing research gaps with respect to problem properties and solution methods. For the problem properties, very few studies modelled problems with multiple bike types, and no studies considered multiple demand classes. For the solution methods, there are rooms for new metaheuristics to solve the routing problem, and simple yet efficient methods for solving the loading problem with exact solutions.

These gaps structure the following parts of this thesis. First, a new metaheuristic, the Artificial Bee Colony (ABC) algorithm, is introduced and enhanced to handle the routing decisions in all bike repositioning problems in this thesis. Computational studies show that the enhanced ABC algorithm outperforms genetic algorithm and the original ABC algorithm in all test instances. Second, two bike repositioning models with single bike type, which aims to firstly minimize demand dissatisfaction and then service time, are investigated. The loading decisions are determined by a new set of loading and unloading (LUL) strategies, which is proved to be the optimal solution for the LUL sub-problem. This set of equations is embedded into the enhanced ABC algorithm for solution evaluation. The models consider the concept of tolerance of total demand dissatisfaction and investigate how it influences the objective values and fleet size. Third, two bike repositioning models with normal and broken bikes are investigated, in which one follows the same objective in the single-bike type model and the other one includes the minimization of broken bikes left in the system. Three new sets of exact LUL strategies are introduced based on the loading hierarchy of normal and broken bikes. Fourth, a bike repositioning model, that considers one-seat and two-seat bikes, is investigated. Four sets of exact LUL strategies are developed based on the substitution and occupancy strategies, in which substitution solves the shortage of some bike types by providing different bike types as a substitute, and occupancy enables some types of bikes to be stored in the rooms for another bike types during repositioning. This model is extended to consider two demand classes, persistent and inconstant demands, in which persistent demand only rides on designated bike type and inconstant demand can ride on any bike type. Another two sets of exact LUL strategies are developed to handle these two demand classes. All the models and relevant algorithms are tested by corresponding test instances.