Fleet management is a substantial activity that involves the fields of logistics, transportation, and distribution. Its main goal is to improve operational performance and service efficiency while reducing overall costs [6]. Based on the type and functioning of the system, different fleet management approaches could be considered. For the conventional bike-sharing system (CBSS), the relocation problem has been considered one of the main fleet management challenges that bike-sharing systems face. Since their earliest implementations, CBSS operators recognized the need to improve the bike’s distribution methods, and sometimes, they assessed its associated costs [7]. Therefore, it is essential to find approaches that make fleet relocation more efficient [8].

To date, several methods have been suggested to solve the bike rebalancing problem. Different classifications of the bike repositioning literature were also made. We should first distinguish between the operator-based rebalancing (OBR) strategies where the relocation operation is generally done by a fleet of trucks that collect and drop bikes across the network to satisfy the upcoming demand and the user-based rebalancing (UBR) strategies where incentives are given to customers to encourage a self-rebalance of bikes in the network. While the literature on the OBR strategies is rich and diverse [9,10,11,12,13,14,15,16], the publications on UBR are limited [17,18,19,20]. For the OBR strategies, Ho and Szeto [21] categorized the publications according to the operation types and available rebalancing vehicles. Considering the available repositioning vehicles, we differentiate between relocation problems with a single repositioning truck or multi-trucks. For the operation types, we can roughly distinguish between two categories: the static repositioning problem (SRP) and the dynamic repositioning problem (DRP). The SRP is applied for overnight rebalancing and does not integrate the demand forecasting for the operating day. It is a deterministic problem and can be viewed as a static, many-to-many pickup and delivery problem. We could find a survey of the static bicycle repositioning problem in [22]. The DRP is, on the other hand, applied for intraday rebalancing and considers the upcoming demand during the day [23]. The DRP is both dynamic and stochastic. We can also differentiate between the different OBR strategies according to the type of bike-sharing system: dock-based or free-floating. For an extensive literature review on the rebalancing problem for station-based BSS, we refer to [24]. For the free-floating systems, the rebalancing operation is more complicated as bikes are randomly dispersed in the operational area. The difficulty in seizing the bikes’ location leads to high rebalancing costs [20]. To summarize, we can differentiate between the UBR where papers are still limited and it is mainly performed by giving some incentives to the customers to encourage them to do a self-rebalancing of the system, and the OBR strategies where the service provider needs to solve a static or dynamic vehicle routing problem and here the repositioning (or rebalancing) problem consists on determining the best route for each vehicle (generally a truck), the stations (or points) that should visit and the number of bikes to load or unload at each visited station, such that we minimize the dissatisfaction cost in the overall system. For both types, the relocation problem solved is completely different from the rebalancing of autonomous bikes. For OSABS, we do not require a vehicle to perform the rebalancing task. Instead, the bikes could ride autonomously from one station to another, according to the upcoming demand. Our rebalancing problem is rather considered as a part of the fleet management of autonomous mobility-on-demand (AMoD) services that we are investigating in the next part.

Different studies have demonstrated the importance of AMoD’s fleet management for cost reduction [25] and the minimization of the customer waiting time [26]. Various rebalancing models have been developed in the literature with different assumptions and considerations. Numerous authors suggested solving the relocation problem while considering a grid network. They divide the operation area into blocks and calculate the imbalance of each block. After that, they send vehicles from surplus blocks to deficit blocks [27,28,29]. Other studies modeled the system as a graph network where the nodes represent the stations and the edges are the travel cost. This formulation is solved through linear or integer programming [25,30,31,32]. Some papers used a road network and divide the area into relocation regions [33,34]. Only a few papers are found where a real network (maps) is used [35,36]. This can be explained by the complexity of routing in real maps, which implies high computational times. In conclusion, the literature on the relocation of autonomous vehicles is extensive. However, due to the complexity of the problem, each study uses specific assumptions, which include the routing, the network type, and the demand. These assumptions affect the problem formulation and its resolution. In addition, to the best of our knowledge, all the papers in the literature have only considered either one or different periodic relocation strategies without studying the influence of the rebalancing parameters on their results and the difference between different types of relocation. Only one paper has compared the two different types of relocation (relocation between stations and relocation after rental) for an autonomous car-sharing system, but without including the impact of the periodic relocation frequency in the research [35].