关键词: 共享单车, 共享电单车, 调度问题, 混合整数规划, 禁忌搜索

Abstract: Generally, shared two-wheeled cycles refer to shared bikes and shared e-bikes. Shared bikes have been cited as an efficient way to improve the convenience and accessibility of the“last mile, while shared e-bikes are motorized bikes with an integrated electric motor used to assist propulsion, which is more suitable for medium and short-distance travel within 3 to 5 kilometers. In recent years, an increasing number of cities around the world have started to offer both bikes and e-bikes in bike sharing systems (BSS), such as Dubai, New York, Paris, Montreal, Barcelona, and most cities in China. In BSS, the inventory of bikes/e-bikes at some stations cannot satisfy the customer demand, whereas other stations have too many bikes/e-bikes. Thus, dedicated trucks are deployed to allocate and relocate bikes/e-bikes among stations in BSS. This operational problem is called a bike repositioning problem (BRP).
However, for the same or adjacent stations, the repositioning activities of shared bikes and shared e-bikes are often performed simultaneously, resulting in some characteristics that affect repositioning activities, such as the station space-sharing, the customer demand substitution, and the truck loading occupation. To deal with this, a hybrid repositioning problem, that is, the combination of three strategies (i.e., station space-sharing strategy, customer demand substitution strategy, and truck loading occupation strategy) with repositioning routing is considered.
The first strategy is station space-sharing. This study does not consider fixing the parking space for each type of shared two-wheeled cycle (for example, allocating parking space proportionally in the background of the system, or placing a fixed number of different types of locking piles and other facilities, and so on), but dynamically allocate station space for each type of shared two-wheeled cycles according to the contribution to the total costs at each station.
The second strategy is the customer demand substitution. Through user Apps, users can rent any type of shared two-wheeled cycle according to their demands. Thus, a shortage of one type of two-wheeled cycle can be solved by providing the other type as a substitute. For instance, if no shared e-bikes are available at a station, a user can rent a shared bike as a substitute, or he can rent a shared e-bike if no shared bikes are available at a station. The substitution strategy can effectively alleviate demand pressure, but a penalty with respect to each type of substitution accounts for a potential decrease in the demand satisfaction for the specified type at other stations.
The third strategy is the truck loading occupation. This strategy allows one type of two-wheeled cycle to be stored in the compartment for the other designated type during operation. For instance, when the compartment for shared bikes is full, a bike can be put into an empty spot in the compartment for an e-bike, whereas the opposite is infeasible because the size of an e-bike is usually larger than that of a bike. Occupation strategy can also effectively alleviate demand pressure, but a penalty is associated with a shared bike that is put into a space for a shared e-bike because some space of the compartment cannot be used by an e-bike to be picked up at the next station, which results in a waste of resource.
The proposed problem is formulated as mixed-integer linear programming. An improved TS is adopted as the backbone of the solution method of this study. However, in addition to routing variables, the proposed problem involves loading and unloading quantity variables, substitution strategy variables, and occupancy strategy variables. Therefore, the TS cannot be applied directly to solve the proposed problem. This study develops a tailored heuristic and incorporates it into the TS to handle the extra complexity, forming a hybrid TS.
In order to test the performance of hybrid TS, the TS, genetic algorithm (GA), and variable neighborhood search (VNS) are adopted as comparison algorithms. However, there are no test instances available in the literature. For this purpose, 10 instances are generated with sizes varying from 20 stations to 200 stations. Numerical experiments show average objective function values, the minimum objective function values, and the standard deviation of the proposed hybrid TS always outperform those of TS, GA, and VNS.
In addition, to show the effect of the proposed three strategies on the operation cost and the customer demand, four new strategies are adopted as comparison strategies, including removing sharing strategy, substitution strategy, and occupancy strategy at the same time, removing only sharing strategy, removing only substitution strategy, and removing only occupancy strategy. Numerical experiments show that any one of the proposed three strategies proposed has an effect on reducing the total cost and alleviating customer dissatisfaction, especially when the three strategies are used at the same time.
Future research may consider the extension of the current problem and solution method to multiple dedicated truck cases, and a station can be visited by more than one truck.

Key words: shared bike, shared e-bike, repositioning problem, mixed integer programming, tabu search