## 1 Introduction  
Bicycle sharing systems (BSSs) have been introduced in many cities around the world as a new public transportation system. Currently, more than 1,700 programs of BSSs are operating in the world [1], for instance, BIXI in Montreal [2], Velib' in Paris [3], docomo bike share in Tokyo [4], citybike in Vienna [5], Citi Bike in New York [6], Capital bikeshare in Washington D.C. [7], BULEBikes in Boston [8] and Bicing in Barcelona [9]. A BSS consists of many distributed automatic rental ports and many rental bicycles. A registered user can rent a bicycle at a port, use it for a short trip and return it to a different port. A BSS is not only a convenient service, but also it can reduce greenhouse gas and traffic congestion issues. For example, [PERSON] et al. (2018) [10] have estimated that the introduction of a BSS at Shanghai saved 8358 tonnes of petrol, and reduced CO\({}_{2}\) and NOx emissions 25,240, and 64 tonnes, respectively in 2016. In a BSS, almost all ports are in either an empty or full state after a while. An empty bicycle port implies that a user cannot rent a bicycle, whereas a full bicycle port implies that a user cannot return a bicycle. Thus, full or empty states lead to dissatisfaction of users. In addition, broken bicycles are left unattended. Consequently, users' frustration is further increased. To address these issues, several capacitated vehicles need to relocate bicycles among ports so that sufficient bicycles are available at each port. If operators can execute repositioning works efficiently, users will not have experience that they cannot rent or return bicycles and BSS companies can reduce labor costs and carbon emissions of vehicles. Thus, both users and BSS companies benefit. Recently, many studies have been conducted on repositioning bicycles of a BSS. The repositioning of BSS can be divided into two cases. The first one is a static case. In the static case problem, the number of bicycles does not change at each port while the bicycles are restored by the vehicle, because the system assumes that the bicycles are not moving much at midnight or after operation hours. As for the static case problem, [PERSON] et al. (2014) [11] proposed a bike sharing rebalancing problem (BRP) and formulated BRP as a mixed integer linear programming problem, and they solved BRP using the branch-and-cut algorithm for the 22 real world instances collected from the web sites. Then, they proposed a destroy and repair algorithm for the BRP, and tested their algorithm on benchmark instances [12]. Although these studies [11; 12] are interesting, they did not consider a time limit constraint: vehicles must return to a depot within a given time limit. Then, it is not guaranteed that all operations will be finished within the working hour in BRP. On the other hand, [PERSON] et al. (2013) [13] proposed a general variable neighborhood search (VNS) with an embedded variable neighborhood descent for finding efficient vehicle tours of a balancing bicycle sharing system (BBSS). In the BBSS, they considered the time limit constraint, and that a vehicle can visit a port multiple times. Then, they tested their algorithm on benchmark instances of real-world data provided by Citybike in Vienna with up to 90 ports, and the result of numerical experiments showed that their algorithm obtained good solutions in a reasonable time. In addition, [PERSON] et al. (2013) [14] proposed efficiently determining optimal loading operation of VNS method for finding efficient vehicle tours of the BBSS. They tested the same instances with [PERSON] et al. (2013), and they reported that their method showed better performance than the original VNS. Moreover, [PERSON] et al. (2013) [15] also address the BBSS, and they proposed two GRASP (Greedy Randomized Adaptive Search Procedure) heuristic approaches and conducted numerical experiments by varying sizes of instances that ranged from 30 to 700.