Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Optimal Rebalancing Strategy for Shared e-Scooter Using Genetic Algorithm

Optimal Rebalancing Strategy for Shared e-Scooter Using Genetic Algorithm Hindawi Journal of Advanced Transportation Volume 2023, Article ID 2696651, 13 pages https://doi.org/10.1155/2023/2696651 Research Article Optimal Rebalancing Strategy for Shared e-Scooter Using Genetic Algorithm 1 1 2 Sujae Kim , Gyeongjae Lee , and Sangho Choo Department of Urban Planning, Hongik University, Seoul 04066, Republic of Korea Department of Urban Design and Planning, Hongik University, Seoul 04066, Republic of Korea Correspondence should be addressed to Sangho Choo; shchoo@hongik.ac.kr Received 7 November 2022; Revised 30 January 2023; Accepted 24 March 2023; Published 6 April 2023 Academic Editor: Lei Wang Copyright © 2023 Sujae Kim et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Shared e-scooters are provided as a free-foating service that can be freely rented and returned within the service area. Although this has a positive efect in terms of convenience for users of shared e-scooters, it is creating new urban problems, such as undermining the aesthetics of the city and obstructing the passage of pedestrians. Terefore, this study developed an optimal rebalancing algorithm to mitigate these problems and proposed an efcient operation plan. Complete relocation was performed to match the demand and supply for an efcient operation by reducing the unnecessary oversupply of shared e-scooters. Te optimal rebalancing algorithm that refects the attributes of e-scooters was developed through genetic algorithms and subsequently applied to actually used cases. Te results indicate that when 20% of the potential demand was considered, an optimal solution could be derived with two relocation vehicles; however, when the potential demand was not considered, three relocation vehicles were required. Terefore, it is anticipated that the results of this study can serve as basic data for solving various urban problems caused by the recent rapid increase in the use of shared e-scooters. method of rebalancing. Rebalancing is a methodology in 1. Introduction which devices are retrieved from areas with low usage Shared e-scooters are provided as a free-foating service demand, and additional devices are placed in areas with that can be freely rented and returned within the service high usage demand. Te rebalancing methodology can be area. Tis type of service has recently become very popular. divided into static and dynamic rebalancing, depending on Shared e-scooter was frst serviced by Lime and Bird in the when devices are relocated, and complete and partial United States in 2017; since then, it has steadily been used rebalancing, according to the level of rebalancing [5]. Static [1–3]. As of August 2020, 16 companies were servicing rebalancing is a methodology for relocating devices in more than 36,000 devices in Korea [4]. However, the ad- account of the usage demand when there is little demand. In the case of dynamic rebalancing, relocation is performed vantage of e-scooters to be used freely without space re- strictions is also a disadvantage because of a phenomenon in consideration of the usage demand during a specifc time period, or relocation is performed when specifc conditions in which the e-scooters get concentrated in a specifc space at a specifc time. Consequently, various companies that are are met. Complete rebalancing is a methodology that de- servicing shared e-scooters in Korea are supplying more rives an optimal solution by precisely matching the supply than the demand at a higher cost. Although this has and demand at all points that require relocation. In the case a positive efect in terms of convenience for users of shared of partial rebalancing, it means that demand and supply e-scooters, it is creating new urban problems, such as cannot be matched at all points, or an optimal solution is undermining the aesthetics of the city and obstructing the derived from a nonconsistent state. Te remainder of this passage of pedestrians by occupying pedestrian paths. One paper is organized as follows: Section 2 (Literature Review) way to tackle this growing problem could be through the reviews studies on the rebalancing of bike sharing and 2 Journal of Advanced Transportation shared e-scooter. Section 3 (Materials and Methods) ex- developed a rebalancing algorithm for the collection of plains how the data were collected and the methodologies broken bikes for repair and for the relocation of shared bikes. A complete rebalancing was performed to match the supply used to rebalance the shared e-scooter. Section 4 (Results and Discussion) presents a shared e-scooter rebalancing and demand for all stations, and the relocation time was model and the evaluation results of applying the model to minimized by moving broken bikes to the warehouse. When real data. Finally, in Section 5 (Conclusions), the conclu- there are more stations, as is the case with the FFBSS, it is sions are drawn and study limitations and future research difcult to fnd an optimal solution to an mTSP; therefore, plans are discussed. the greedy-genetic heuristic algorithm was considered. Te rebalancing algorithm was applied to Share-A-Bull of Florida and Divvy of Chicago and subsequently evaluated by 2. Literature Review comparing the analysis results of CPLEX software, which is As shared e-scooters become a new mode of transportation, commonly used. Sun et al. [32] deployed virtual stations near research has been steadily conducted to identify the infu- public transit stations and major establishments to solve severe parking disorder caused by the FFBSS. Te location encing factors and predict the demand for their use [6–12]. Tese studies were reviewed in detail by Kim et al. [12]. As assignment of virtual stations is optimized to satisfy user regards rebalancing, there are many studies related to bike demand. Optimization problems are usually formulated as and car sharing; however, there is still a lack of research that a mixed-integer linear programming (MILP) model. Ex- suggests an efcient operation plan through the rebalancing perimental results proved that the MILP model and the of shared e-scooters. Terefore, this study only reviewed proposed method were superior to the k-means method. studies on the rebalancing of bike sharing similar to shared Usama et al. [33–35] tried to improve the level of service and e-scooters. Tere are two systems for bike sharing: the solve safety problems by repositioning randomly scattered station-based bike sharing system (SBBSS) and the free- free-foating bike-sharing and faulty bikes. Te objective for foating bike sharing system (FFBSS). In addition, the re- bike relocation is to minimize travel cost [33, 34], demand location problem is a problem of fnding the optimal al- dissatisfaction [34, 35], and relocation cost [35]. Te mechanism optimized the formulated problem with ternative among several alternatives. It is an important criterion to optimize, and this is called the objective func- a branch-and-cut algorithm, and the validity of the model tion. Terefore, studies related to the rebalancing of bike was tested through various numerical experiments using the sharing are classifed into operation types, rebalancing types, CPLEX solver. Liu et al. [36] developed a static partial and objective functions (see Table 1). First, looking at the rebalancing algorithm to minimize bike supply-demand optimal rebalancing study of the SBBSS, the objective imbalance and relocation time. Rebalancing algorithms function for static rebalancing of shared bikes was defned as were developed by improving chemical reaction optimiza- minimizing relocation time [15, 16, 19, 43], travel cost tion (CRO), based on the principle of chemical reaction. For [13, 18, 44], demand dissatisfaction, and relocation volume the evaluation of the developed rebalancing algorithm, the [17]. As regards static partial rebalancing, Raviv et al. [20] algorithm was applied to Citibike in New York and Share- and Schuijbroek et al. [23] minimized relocation time, A-Bull in Florida. Te numerical results were compared with those of the traditional CRO and CPLEX. Caggiani et al. [37] whereas Forma et al. [21], Li et al. [22], and Ho and Szeto [14] minimized relocation costs. In the work of Shui and predicted the demand for the use of the FFBSS and built Szeto [24], relocation time and demand dissatisfaction were a framework for a dynamic rebalancing model. After spatio- minimized. Finally, most of the studies of dynamic reba- temporal clustering was performed on the time and point of lancing minimized demand dissatisfaction [25, 27–30]. In use of the shared bike, the usage demand at a specifc time addition to demand dissatisfaction, relocation time [26, 27], and point was predicted by using a nonlinear autoregressive travel costs [29], and fuel and CO emission costs [24] have neural network with explicit (NARX). Dynamic rebalancing been minimized previously. As the shared e-scooter operates has also been performed to satisfy the predictive demand of in the method similar to the FFBSS, the rebalancing study of each time and point. Lloyd’s algorithm was used to minimize the dissatisfaction of demand at each point (less than the the FFBSS has been reviewed in detail in this study. Pal and Zhang [5] developed the FFBSS rebalancing methodology threshold number of bikes, the number of users unable to use one due to lack of bikes). Unlike other studies [5, 31, 36], based on the SBBSS rebalancing methodology. Each dock of the station was separated and set as an analysis point, and the the developed algorithms were evaluated in a toy network. Zhai et al. [38] improved dynamic optimization for the usage demand between stations was distributed to the analysis point. As a relocation methodology, the multiple standardized management of dockless bike-sharing. An algorithm was proposed, through the Markov stochastic traveling salesman problem (mTSP) using multiple vehicles was applied. Tis is because one vehicle with limited capacity process, to determine the appropriate feet size for dockless cannot fnd an appropriate solution with one community bike-sharing. To improve the practicality of the algorithm, pickup and delivery traveling salesman problem (TSP), the dynamic solution of bike-sharing steady-state feet size, which visits stations only once. Te optimal rebalancing according to time period, was presented. In addition, to verify the efciency of the algorithm, the linear pro- solution was derived to minimize the relocation time. Te developed algorithm was applied to Share-A-Bull in Florida gramming method for bike rebalancing analysis, was used. Experimental results showed that the algorithm could solve and Divvy in Chicago and compared with the results of the exact algorithm and tabu search algorithm. Du et al. [31] the disordered deployment of dockless bike-sharing. Chang Journal of Advanced Transportation 3 Table 1: Summary of the literature based on rebalancing strategies. Target Type Subtype Research article Methodology Objective Chemla et al. [13] Branch-and-cut Travel cost Ho and Szeto [14] Iterated tabu search Relocation time Erdogan et al. [15] Branch-and-cut and bender’s decomposition Travel cost Angeloudis et al. [16] Multistage heuristic Relocation time Complete Erdogan et al. [15] Exact algorithm based on bender’s cuts Relocation time Alvarez-Valdes et al. Demand dissatisfaction and relocation Heuristic based on minimum cost fow [17] volume Zhang et al. [18] Hybrid DPSO-VNS Travel cost Static Bulhoes et al. [19] Branch-and-cut Relocation time Raviv et al. [20] Mixed integer programming Relocation time Forma et al. [21] 3-step math heuristic Relocation cost Li et al. [22] Hybrid genetic algorithm Relocation cost Station based bike sharing system Partial Schuijbroek et al. [23] Constraint programming and MIP Relocation time (SBBSS) Ho and Szeto [14] Hybrid large neighborhood search Relocation cost Demand dissatisfaction and relocation Shui and Szeto [24] Enhanced artifcial bee colony algorithm time Contardo et al. [25] Hybrid MIP approach Demand dissatisfaction Regue and Recker [26] Mixed integer programming Relocation time Demand dissatisfaction and relocation Kloimullner et al. [27] Combination of greedy heuristic, GRASP, and VNS time Dynamic Brinkmann et al. [28] Inventory routing problem Demand dissatisfaction Zhang et al. [29] Time space network fow approach Demand dissatisfaction and travel cost Demand dissatisfaction and fuel and CO Shui and Szeto [24] Enhanced artifcial bee colony algorithm emission Legros [30] Markov decision Demand dissatisfaction Nested large neighborhood search and variable Pal and Zhang [5] Relocation time neighborhood descent Du et al. [31] Greed-genetic heuristic Relocation time Sun et al. [32] Te clustering algorithm and branch-and-cut User satisfed demand Complete Usama et al. [33] Branch-and-cut Travel cost Static Usama et al. [34] Branch-and-cut Demand dissatisfaction and travel cost Free-foating bike sharing system Demand dissatisfaction and relocation (FFBSS) Usama et al. [35] Branch-and-cut cost Demand dissatisfaction and relocation Partial Liu et al. [36] Chemical reaction optimization time Caggiani et al. [37] Lloyd’s algorithm Demand dissatisfaction Dynamic Zhai et al. [38] Branch-and-cut Relocation cost Chang et al. [39] A hybrid metaheuristic algorithm with VNS and ESA Relocation cost Complete Tolomei et al. [40] Simple greedy strategy Relocation distance Free-foating-scooter Static Carrese et al. [41] Integer linear programming Demand dissatisfaction Partial Osorio et al. [42] MIP and discrete-continuous hybrid model Relocation cost 4 Journal of Advanced Transportation plan, which results in a complete rebalancing strategy when et al. [39] suggested that free-foating bike sharing was an innovative and sustainable travel mode; however, there were implemented. imbalances between zones, caused by one-way trips and the need to move damaged bikes for repair. To solve this 3. Materials and Methods problem, a demand forecasting model using an encoder- decoder architecture embedded with the attention mecha- 3.1. Model Formulation nism was developed, and a hybrid metaheuristic algorithm, 3.1.1. Problem Defnition. Te shared e-scooter rebalancing integrating variable neighbourhood search (VNS), and en- algorithm developed in this study is a static rebalancing hanced simulated annealing (ESA) algorithms, were pre- algorithm and is a complete rebalancing algorithm that sented as an optimization model. Te proposed framework matches the demand and supply (the amount adjusted was applied to Beijing and China, and it was found that the through relocation based on the amount of placement at the most efective strategy was to relocate, considering only the start of relocation). Te pick-up and drop-of of e-scooters operational bikes during the peak hours. Recently, a re- was determined considering the usage demand by branches location study on shared e-scooters has also been conducted in the target area and the amount of initial placement. In this [40–42]. Tolomei et al. [40] quantifed the economic costs case, the point where the demand was greater than the initial and additional benefts resulting from the relocation of batch quantity was defned as the drop-of point, the point shared e-scooters. Simulations were performed for actual where the initial batch quantity was large was the pick-up trips operating in Austin and Louisville. A simple greedy point, and the point where relocation was not required by strategy was considered to defne the movement of an e- coincidence was defned as the balance point. In this design, scooter. Experimental results showed that a light and simple the relocation vehicle leaves the warehouse and visits the relocation policy with little relocation per hour improved the drop-of point and the pick-up point once, matches the rate of satisfactory trips by 42%. In other words, even if the drop-of volume of all branches to the demand, and then feet size was reduced, the overall performance would not be returns to the warehouse. Te balance point is not visited; afected. Osorio et al. [42] presented a model for overnight however, if there is a malfunctioning e-scooter or an e- charging and rebalancing by allowing the e-scooter to be scooter that needs recharging, the balance point is visited, charged, while moving in the rebalancing vehicles. For e- and the relocation vehicle picks up the broken e-scooter, scooter charging and rebalancing, a mixed-integer program drops of the same amount, and replaces the battery of the e- and a discrete-continuous hybrid model were developed, scooter that needs recharging. As there was no imbalance respectively. A continuous approximation technique was between demand and supply after relocation, the goal of proposed to avoid the enormous computational burden due rebalancing was, therefore, set to minimize relocation time. to the free-foating service. When applied to actual trips in In addition, when the capacity of the relocation vehicle was Washington, DC, compared to the direct application of the exceeded due to a large amount of pick-up after relocation, discrete formulation, the proposed model produced a better multiple relocation vehicles were considered. quality solution in a shorter time. Carrese et al. [41] sug- gested a plan for rebalancing of e-scooters through short- distance reposition of just a few meters rather than mid-to- 3.1.2. Mathematical Model. Te model used to develop the long-distance reposition within the city performed in tra- rebalancing algorithm in this study was modifed and ditional vehicle-sharing systems. An integer linear pro- supplemented according to the attribute of a shared e- gramming model was developed to solve the relocation scooter by referring to the model of a balancing bicycle problem by utilizing the realistic data of Rome, Italy. Te sharing system developed by Rainer-Harbach et al. [45]. Te good performance of the proposed model was demonstrated shared e-scooter rebalancing model developed in this study by comparing the results of CPLEX. Although e-scooter and is as follows: FFBSS have similar systems of operation, electrically pow- ered e-scooters require periodic charging or battery re- (1) Sets placement. Only one of the studies on e-scooter relocation N � 􏼈0, 1, · · · , n 􏼉(0  is  warehouse) max accounted for charging during relocation [42]; the others K � 􏼈1, 2, · · · , k 􏼉 max [40, 41] neither considered charging nor battery re- (2) Indices placement. In this study, a static complete rebalancing al- gorithm was developed to reduce unnecessary supply, and i, j: index of points derive an efcient operation plan by moving an e-scooter k: index of relocation vehicles from a point with no demand to a point with high usage (3) Parameters demand. Subsequently, we developed an optimal reba- lancing algorithm to improve the problems of shared e- sf : the initial number of e-scooters at point i scooters and to suggest an efcient operation plan. Te sd : the number of target e-scooters at point i rebalancing algorithm, developed in this study, added sr : the number of broken e-scooters at point i constraints on battery replacement that were not considered sb : the number of e-scooters requiring battery re- in previous bike relocation studies and also considered i placement at point i relocation and collection for repair. In addition, the ultimate implication of this study is to propose an efcient operation t : travel time from point i to point j (minutes) ij Journal of Advanced Transportation 5 C : capacity of relocation vehicle k relocation vehicles. Te relocation time was calculated as given in equation (2) and is the sum of the travel time of the RT : total relocation time of relocation vehicle k relocated vehicle, the pick-up and drop-of time of the T : total operable time of relocation vehicle k shared e-scooter, the pick-up time of the broken e-scooter, w : weight of e-scooter pick-up and drop-of time pd and the replacement time of the e-scooter battery. Te w : weight of e-scooter battery replacement time constraint (equation (3)) means that the number of e- scooters remaining at point i after relocation was equal to (4) Variables the sum of the initial number of e-scooters at point i and the x : 1 if relocation vehicle k moves from point i to j; ijk amount rebalanced by the relocation vehicle k. Equation (4) 0 otherwise is a conditional expression for complete relocation, which y : the number of e-scooters that the relocation means that the amount of e-scooters at point i after re- ijk vehicle k moves from point i to j location was the same as the target amount of e-scooters refecting the demand at point i. Equation (5) is a constraint p : the number of e-scooters that the relocation ik on the capacity of the relocation vehicle, which means that vehicle k picks up at point i when the relocation vehicle moves the e-scooter, it cannot d : the number of e-scooters that the relocation ik pick up in excess of the capacity of the relocation vehicle. vehicle k drops of at point i Equations (6) and (7) guarantee the route of the relocation s : the number of e-scooters remaining at point i after vehicle, and when the relocation vehicle leaves or visits point relocation i, it must arrive or depart from point j. Tis implies that the (5) Model formulation relocation vehicle k must move 0 or 1 from point i to j. Tat is, the relocation vehicle can visit each point at the most Te objective function is as follows: once. Equation (8) is a constraint on the pick-up of e- scooters, and it implies that a relocation vehicle cannot Minimize  Max RT , (1) 􏼈 􏼉 pick-up more e-scooters than the number of initial e- scooters at the relevant point. Equation (9) implies that the total relocation time cannot exceed the total operable ⎛ ⎝ ⎞ ⎠ RT � 􏽘 􏽘 t x + w 􏽘 􏽘 y + 􏽘 sr k ij ijk pd ijk i time of the relocation vehicle. i j i j i (2) + w 􏽘 sb , ∀k ∈ K, b i 3.2. Solution Methodology 3.2.1. Genetic Algorithm. In this study, a genetic algorithm s.t  sf + 􏽘 d − p � s , ∀i ∈ , ∀k ∈ K, (3) i ik ik i was applied to solve the static rebalancing problem of shared e-scooters. Te genetic algorithm has been studied to be efective in solving the problem of static rebalancing of s � sd , (4) i i shared bicycles. Te genetic algorithm is an optimization method frst introduced by John Holland in 1975, and it is y ≤ C × x , ∀i, j ∈ , ∀k ∈ K, (5) a methodology for calculating problems by imitating the ijk k ijk evolution of real organisms [46]. Te genetic algorithm is a probabilistic search method that models the evolution x � 􏽘 x , ∀i ∈ , ∀k ∈ K, genes to fnd the near-optimal solution and is used to fnd ijk ijk (6) j∈N,j≠i j∈N,j≠i the global optimal solution without falling into the problem of local optimal solutions by searching for solutions in parallel. However, it is not always possible to fnd a global 􏽘 x ≤ 1, ∀i ∈ , ∀k ∈ K, ijk (7) optimal solution, and even if an optimal solution is found, j∈N/0,j≠i the process cannot be known. Genetic algorithms are used in various felds and are typically used when deriving solutions 􏽘 p ≤ sf , ∀i ∈ , (8) ik i to TSP, approximate solution estimation of higher-order k∈K functions, neural network optimization, and non- deterministic polynomial time-hard problems. Terms used in genetic algorithms are defned as given. A chromosome is ⎛ ⎝ ⎞ ⎠ 􏽘 􏽘 t x + w 􏽘 􏽘 y + 􏽘 sr ij ijk pd ijk i a set containing genetic information and is the solution of i j i j i (9) the problem (relocation vehicle path). A gene is an element + w 􏽘 sb ≤ T , ∀k ∈ K. b i k constituting a chromosome and represents a component of a solution (movement between points). An ofspring is a new chromosome (a new relocation path) generated from the Equation (1) is the objective function of the shared e- chromosomes of the previous generation. Fitness is an in- scooter rebalancing algorithm, and it minimizes the vehicle trinsic value of chromosomes and is a measure (relocation relocation time, with the longest relocation time among the time) of how well the solution to the problem is suitable. 6 Journal of Advanced Transportation Elitism refers to preservation of chromosomes with good ft 01 23 ... N among the chromosomes of the previous generation as they ... Solution 1 0 3 7 12 64 are in the next generation. Te genetic algorithms have operators such as selection, crossover, and mutation. Te ... chromosome of the parent generation is selected through Solution 2 0 11 24 2 153 a selection operation, and an ofspring is produced through operations between the selected chromosomes. Tere are ... Solution x 0 120 89 46 5 various methods for the selection operation, but the basic principle is to increase the selection probability of a chro- Figure 1: Solution example of the genetic algorithm. mosome with good ftness, and lower the selection proba- bility for a chromosome with low ftness. However, caution constituting a chromosome indicates a movement path of is required because selecting only the chromosomes with a relocation vehicle. Tat is, the relocation vehicle visits the good ft can lead to premature convergence. Representative relocation point expressed by the gene in the order of the methods of the selection operation include roulette wheel gene. A chromosome is made up of a total of N genes, which selection, tournament selection, and rank-based selection. indicate a point where relocation is required. Rank-based selection is a method that compensates for the A fow chart representing how the optimal solution is shortcomings of roulette wheel selection. Because the se- derived from the genetic algorithm is shown in Figure 2. lection probability of a roulette wheel selection method is determined according to ftness, only excellent chromo- Step 1: generate a path for the relocation vehicle (initial somes are selected. Tis may lead to an unripe convergence solution (generation 1)) according to the selection problem. Rank-based selection supplements this and ranks operation among the entire solution set according to ftness, and then determines the selection Step 2: calculate the relocation time, which is the ftness probability as a linear function according to the ranking. of the solution Looking at the pros and cons of each selection operation Step 3: create a new relocation path (generation 2) method, roulette wheel selection can generate excellent according to the crossover operation and the mutation descendants with a simple methodology; however, it can fall operation into the problem of local optima. As this problem can be solved by mutation operation, in this study the roulette Step 4: determine whether the next generation is the wheel selection method was applied. Crossover is an op- target number of generation, and if the target number is eration that generates ofspring chromosomes through satisfed, the algorithm is terminated to derive an crossover between chromosomes of the parent generation, optimal solution selected by a selection operation. Tat is, a new chromosome Step 5: if the target number of generation is not met, is created by exchanging the genes of the chromosomes of return to step 2 and repeat the parent generation. Te crossover is the operator with the most diverse alternatives (e.g., one-point crossover, cycle 4. Results and Discussion crossover [47], order crossover [48], and edge re- combination crossover [49]). Edge recombination crossover 4.1. Numerical Study is a crossover operation method developed for the TSP. Tis 4.1.1. Data. XingXing, a shared e-scooter service of the method creates a list of points related to each point on the PUMP Corporation, was in service frst in Gangnam-gu and parent chromosome. After selecting one point, the point Seocho-gu, in 2019. Since December 2021, it has been with the fewest adjacent points is selected. If there are adopted nationwide. When a XingXing service user utilizes multiple candidate points, a random point is selected and a device once, one usage data are collected. Tis includes progeny chromosomes are constructed heuristically. Reba- information such as device ID, rental date and time, rental lancing of the shared e-scooter is performed by the re- location, return date and time, return location, usage time, location vehicle creating an optimal route. Terefore, the usage distance, and user ID. Table 2 is an example of one rebalancing problem can be said to be similar to that of the usage data collected. TSP. Crossover methods can be implemented easily. Te In this study, the data of XingXing was used. Collected sequential crossover method that can be applied when de- data with the following errors were removed from analysis: riving the optimal solution of the TSP is applied in this study. Te mutation operation can fnd a solution that (1) Tere was an error in the coordinates of the rental cannot be found by the crossover operation in that it applies location and the return location, or the device was a gene trait that is not present in the parent chromosome to recorded as been rented or returned from an area the genes of the ofspring to a certain probability. As such, other than the service area the mutation operation can diversify the solution group to (2) Te Euclidean distance between the rental location avoid the local optima problem and fnd the global optimal and the return location was smaller than the usage solution. Te solution, which is the chromosome of the distance genetic algorithm, is expressed as shown in Figure 1. Each (3) Te usage distance was recorded as zero gene constituting a chromosome indicates a point where relocation is required, and the sequence of genes ... Journal of Advanced Transportation 7 Create an initial generation Create a relocation path (G = 1) Evaluate the fitness Calculate the relocation time Apply the crossover operation Change the relocation path and the mutation operation Check the target No Create a new relocation path number of generation (G = G + 1) t+1 t (G = G ) target Yes Deriving the optimal solution Figure 2: Flow of deriving the optimal solution of the genetic algorithm. (4) Usage time was recorded as less than 20 seconds between each grid was assumed to be a Euclidean distance. (according to the service policy, usage of less than 20 As for the speed of the relocated vehicle, 30 km/h, the av- seconds was refunded and considered unused) erage travel speed of inner Seoul roads (excluding urban expressways) during the early morning hours of static (5) Average speed exceeded 25 km/h (the maximum rebalancing, was applied. Second, the capacity of the re- speed of the device is limited to 25 km/h) location vehicle was 30, and the pick-up and drop-of time of Te spatial-temporal scope of the analysis was adopted the e-scooter was assumed to be 30 seconds per device. from Kim et al. [12]. Tey set the spatial and temporal scope Currently, a general cargo truck used when moving shared of Gangnam-gu and Seocho-gu, Seoul, in October 2020. bikes and shared e-scooters can accommodate up to 30 e- After setting the analysis unit as a 200 meters square grid, the scooters. When picking up and dropping of e-scooters, it spatial scope was divided into 5 communities using the was assumed that it took approximately 30 seconds per community structure method. In this study, the community device because people had to load or unload them from the with the most usage among the fve communities was set as relocation vehicle. Furthermore, it was assumed that the the scope of the study. Tis community is located on the east ratio of the broken e-scooter and the e-scooter requiring side of the Gyeongbu Expressway, on the left side of Eonju- recharging was 1% and 5%, respectively. Tese ratios were ro, and on the north side of Teheran-ro, as shown in Figure 3. assumed arbitrarily because it was not possible to obtain Te total number of grids and usage demand was 144 and information such as whether the e-scooter was malfunc- 43,384, respectively, with the highest demand for each grid tioning and the remaining battery capacity. Finally, a re- being 301. Garosu-gil, in Sinsa-dong, and the commercial location vehicle could visit a point that required relocation district of Gangnam Station are also located in the up to once. Tis narrows the scope of analysis for problem community. solving and enables efcient algorithm development [20, 43]. In addition, several parameters of the genetic algorithm were 4.1.2. Parameter Adjustment. Several assumptions were set. Te genetic algorithm selects a certain amount of initial made for the development of the rebalancing algorithm. solutions to derive the optimal solution, and then derives the Trough these assumptions, the problem of rebalancing the next generation solution through crossover and mutation. e-scooter was made simpler, and information that was At this time, it was necessary to optimize the variables to difcult to obtain was refected. First, a Euclidean distance account for the number of initial solutions to select, the ratio was used for the distance between each point, and the speed of variability for solution diversity, the ratio of elitism that of the relocation vehicle was assumed to be 30 km/h. As the maintained a high-quality solution for quick optimal so- analysis unit was set on a 200 meters square grid, the location lution derivation, and the number of generations to derive the optimal solution. Te initial solution, mutation rate, and supply location of the e-scooter placed in the square grid were assumed to be at the center of the grid, and the distance elitism rate, and maximum generation were 100, 0.5%, 10%, 8 Journal of Advanced Transportation Table 2: Example of shared e-scooter usage data. Rental Rental Rental Rental Return Return Return Return Usage Usage Device date time location location date time location location time distance User ID ID (YYMMDD) (HHMMSS) (latitude) (longitude) (YYMMDD) (HHMMSS) (latitude) (longitude) (HHMMSS) (meters) PQJEAD 201001 000032 127.0227 37.5038 201001 000402 127.0243 37.4971 000329 879 5db42## Journal of Advanced Transportation 9 Garosu-gil Gyeongbu Express Bus Expressway Terminal Gangnam sta. Figure 3: Spatial scope of this study. and 200, respectively. Tis solution was further optimized genetic algorithms. However, in the case of the CPLEX, the through scenario analysis of each variable. For scenario analysis time increased exponentially as the number of analysis, the optimal value was derived by changing the points increased. When the number of points was 10, the initial solution value after fxing other variables, and after analysis time was 2 seconds, which was not signifcantly diferent from the genetic algorithm, but when the number refecting this, the optimal value was derived by changing other variables. For scenario analysis, 30 random points in of points was 30, the analysis time was determined to be the analysis range were used. Tere was one relocation more than an hour. Terefore, when the number of analysis vehicle, and the number of e-scooters that required re- points was large, it was deemed that the genetic algorithm location was 78. Te optimization result is shown in Figure 4. with a signifcantly faster analysis time was more Finally, the variables used in the algorithm were 200 initial reasonable. solutions, 1% mutation rate, 25% elitism rate, and 1,000 generations of analysis. 4.1.4. Algorithm Application. Te developed algorithm was applied to an actual case on October 30, 2020. Te initial 4.1.3. Algorithm Evaluation. In this study, the genetic al- feet size was set, based on the foating e-scooter, at 03:00 gorithm developed to rebalance shared e-scooters was am when the demand by time period was the lowest. Te compared with CPLEX, which is commonly used to solve the target feet size was set as the predicted demand at 08:00 am, existing optimization problem [31]. For objective evaluation the frst peak time. 136 of the total 144 points needed of the algorithm, various scenarios were analyzed for the relocation; 8 points needed to be balanced. Among the number of points and the number of relocation vehicles; 10, points requiring relocation, 90 drop-of points and 46 pick- 20, and 30 analysis points were analyzed. Te number of up points were determined. Tis was approximately twice relocation vehicles was considered 1 when there were 10 as many drop-of points as pick-up points. By contrast, the number of points was 270, which indicates 73 more units points, 1 to 2 when there were 20 points, and 1 to 3 when there were 30 points. Based on the number of analysis points than the demand. Tis implies that e-scooters were un- considered, the number of e-scooters that needed relocation, necessarily oversupplied at some points. Herein, we carried the number of broken e-scooters, and the number of e- out a pick-up of the 73 units that were oversupplied by scooters that required recharging are listed in Table 3. performing a complete rebalancing to match the supply and Te results of the rebalancing analysis for each analysis demand. When relocating a shared e-scooter, 1 to 3 re- scenario are presented in Table 4. Te genetic algorithm location vehicles were considered because the capacity of derived the optimal solution randomly because the initial the relocation vehicle was 30. In addition, 20% and 40% of solution selection, crossover, and mutation were all applied the total demand were considered as potential demand. Te randomly. Terefore, the genetic algorithm carried out 10 number of broken e-scooters and the number of e-scooters iterations to compute the best objective value [31]. Re- requiring recharging were assumed to be 2 and 13, re- spectively, according to the basic assumptions presented in garding the rebalancing results of the six scenarios, similar optimal results were obtained for both the CPLEX and parameter adjustment section. Te location of the 10 Journal of Advanced Transportation 77.5 95.0 77.0 90.0 76.5 85.0 76.0 80.0 75.5 75.0 75.0 70.0 74.5 65.0 100 150 200 250 300 0.5 1.0 1.5 2.0 2.5 Initial solution Mutation rate (%) 74.0 75.0 73.5 73.0 73.0 71.0 72.5 69.0 72.0 67.0 71.5 65.0 71.0 63.0 10 15 20 25 30 200 400 600 800 1000 1200 Elitism rate (%) Target number of generation Figure 4: Parameter tuning for the genetic algorithm. Table 3: Scenario of the evaluation algorithm. Number of Number of Number of Number of Number of Scenario points relocation vehicle relocation e-scooters broken e-scooters recharging e-scooters 1 10 1 31 0 1 2 1 20 48 1 2 3 2 4 1 5 30 2 78 1 3 6 3 Table 4: Evaluating results of rebalancing. CPLEX Te genetic algorithm Scenario Relocation time Computing time Relocation time Computing time Maximum load Maximum load (min) (sec) (min) (sec) 1 11 31 2 11 31 1.1 2 15 41 111 15 41 3.0 3 11 21 1,900 11 21 3.5 4 27 66 3,943 27 66 9.3 5 15 34 6,703 15 34 10.4 6 12 23 10,488 12 23 12.1 Note. Te relocation time of the genetic algorithm was the best time of 10 runs, and the computing time was taken as the average time of 10 runs. warehouse, where the relocation vehicle leaves and arrives, genetic algorithm. As a result of the rebalancing analysis, if stores the collected e-scooter, and repairs the broken e- potential demand was not taken into account when op- scooter, was assumed to be approximately 4 km apart. Te erating one relocation vehicle, the maximum load capacity rebalancing result is presented in Table 5. First, the reba- of the relocation vehicle was 76, and the relocation time was lancing results were presented as average values after re- 506 minutes, indicating that both the relocation vehicle peating the analysis 10 times due to the randomness of the capacity condition and the relocation time constraint were Relocation time (min) Relocation time (min) Relocation time (min) Relocation time (min) Journal of Advanced Transportation 11 Table 5: Results of rebalancing. Number Number Number Potential Relocation Number Relocation of Number of of Maximum demand vehicle of broken time relocation of points relocation recharging load (%) # e-scooters (min) vehicle e-scooters e-scooters 0 1 136 73 2 13 76 506 1 20 1 136 49 2 13 53 499 40 1 136 26 2 13 29 494 1 68 38 0 8 45 191 2 68 36 2 5 36 201 1 68 20 0 7 29 210 2 68 29 2 6 29 208 1 45 25 0 5 27 98 3 0 2 46 25 1 3 27 102 3 45 24 1 5 26 98 Note. Te relocation time was calculated as the average time of 10 runs. not satisfed. When 20% of the potential demand was re- 5. Conclusions fected, the number of e-scooters that required relocation decreased from 73 to 49. As a result of the rebalancing Shared e-scooters are provided as a free-foating service that analysis, the maximum load capacity was 53, and the re- can be freely rented and returned within the service area. location time was 499 minutes. Tis violated the as- Recently, this type of service has become very popular and as sumptions, and no optimal solution was derived. When such has created a new set of problems. Tis study, therefore, 40% of the potential demand was refected, the number of developed an optimal rebalancing algorithm to mitigate the e-scooters that needed relocation was reduced to 26, which problems of shared e-scooters and to suggest an efcient was expected to be able to derive an optimal solution. Te operation plan. In this study, complete rebalancing was maximum load capacity was 29, which satisfed the capacity performed to match the demand and supply for efcient requirements of the relocation vehicle; however, the re- operation by reducing unnecessary oversupply of the shared location time was 494 minutes, and this did not meet the e-scooters. Devices that needed to be broken and recharged time constraint. Terefore, it was not possible to derive an were considered, refecting the attributes of e-scooters, and optimal solution for rebalancing an e-scooter when op- a genetic algorithm was used to derive an optimal solution. erating one relocation vehicle. When two relocation ve- Te optimal rebalancing algorithm was applied to an actual hicles were operated, the relocation time was 201 minutes case, wherein one to three relocation vehicles and 20% and (relocation vehicle 2), which satisfed the relocation time 40% of additional potential demand were considered. As constraint; however, it was expected that the optimal so- a result of rebalancing, when 20% of potential demand was lution could not be derived with 38 and 36 e-scooters considered, an optimal solution could be derived with two requiring relocation, respectively. Te maximum load ca- relocation vehicles, and when potential demand was not pacity of the relocation vehicle was 45 and 36, which did not considered, it was found that three relocation vehicles were meet the vehicle capacity requirements. When 20% of the required. Tis study is meaningful in that it applied the potential demand was refected, the optimal solution for genetic algorithm, which is an efective methodology for relocation was expected to be derived, with 20 and 29 units FFBSS rebalancing, to e-scooter relocation, which has yet to required for relocation, respectively. Te maximum loading be studied. In addition, the results can help address new capacity of the relocation vehicle was 29 for both relocation urban problems (undermining the aesthetics of the city, vehicles 1 and 2, and the relocation time was derived as obstructing the passage of pedestrians, etc.) by reducing 210 minutes (relocation vehicle 1). Terefore, when op- unnecessary feets through demand forecasting and re- erating two relocation vehicles, an optimal solution was location. Tis study has some limitations that require further derived with a relocation time of 210 minutes when 20% of research in the future. First, there are limitations in the potential demand was refected. In the case of operating analysis methodology used. Te genetic algorithm was used three relocation vehicles, the number of e-scooters that to derive the optimal solution of the rebalancing algorithm, required relocation per vehicle was 25, 25, and 24, re- and the results were compared with those of CPLEX, which spectively. As a result of rebalancing, the maximum loading is generally used to evaluate the developed algorithm. Apart capacities of the relocated vehicles were 27, 27, and 26, from the genetic algorithm, there are various methodologies respectively. Tus, the capacity conditions of the relocation for deriving the optimal solution of the rebalancing algo- vehicle were satisfed, and the relocation time was derived rithm. Additional comparative review with these various as 102 minutes (relocation vehicle 2). When operating three methodologies as well as with CPLEX is necessary. In ad- relocation vehicles, the optimal solution for relocation of e- dition, the static rebalancing algorithm that performs re- location based on a specifc time point was developed in this scooters was derived without potential demand; therefore, potential demand was not additionally considered. study. Due to the limitation of static rebalancing, which is 12 Journal of Advanced Transportation mode and distance in New York city,” 2019, https://arxiv.org/ based on a specifc point in time, usage during relocation was abs/1908.08127. not refected, and the situation after relocation was not [7] S. Bai and J. Jiao, “Dockless E-scooter usage patterns and considered. A representative methodology that can improve urban built environments: a comparison study of Austin, tx, this is dynamic programming. However, it faces difculties and minneapolis, mn,” Travel Behaviour and society, vol. 20, in deriving an optimal solution when the analysis range is pp. 264–272, 2020. large, such as in free-foating services. Tis can be solved by [8] H. Yang, J. Huo, Y. Bao, X. Li, L. Yang, and C. R. Cherry, reducing the time step of the static rebalancing methodology “Impact of e-scooter sharing on bike sharing in Chicago,” (analyzed for 5 h ours, from 3 to 8, in this study) and re- Transportation Research Part A: Policy and Practice, vol. 154, peating relocation. Terefore, it is thought that a study pp. 23–36, 2021. through a scenario review is necessary. However, if the [9] O. Caspi, M. J. Smart, and R. B. Noland, “Spatial associations number of relocation increases, the cost of relocation in- of dockless shared E-scooter usage,” Transportation Research creases accordingly. Terefore, it is necessary to also review Part D: Transport and Environment, vol. 86, Article ID 102396, 2020. the optimal scenario considering the relocation cost and the [10] A. Hosseinzadeh, M. Algomaiah, R. Kluger, and Z. Li, “E- number of relocations. In this study, only the operation plan Scooters and sustainability: investigating the relationship for optimal rebalancing (operating three relocation vehicles) between the density of E-scooter trips and characteristics of was presented. Terefore, additional review on the evalua- sustainable urban development,” Sustainable Cities and So- tion index that can quantitatively evaluate the results of the ciety, vol. 66, Article ID 102624, 2021. study is necessary. Finally, this study presented an e-scooter [11] S. W. Ham, J. H. Cho, S. Park, and D. K. Kim, “Spatiotemporal rebalancing methodology to solve new urban problems, but demand prediction model for E-scooter sharing services with the fundamental solution to these problems would be a new latent feature and deep learning,” Transportation Research legislation regarding the infrastructure. Record Journal of the Transportation Research Board, vol. 2675, no. 11, pp. 34–43, 2021. [12] S. Kim, S. Choo, G. Lee, and S. Kim, “Predicting demand for Data Availability shared E-scooter using community structure and deep Te data are not publicly available due to privacy. learning method,” Sustainability, vol. 14, no. 5, p. 2564, 2022. [13] D. Chemla, F. Meunier, and R. Wolfer Calvo, “Bike sharing systems: solving the static rebalancing problem,” Discrete Conflicts of Interest Optimization, vol. 10, no. 2, pp. 120–146, 2013. [14] S. C. Ho and W. Y. Szeto, “A hybrid large neighborhood Te authors declare that they have no conficts of interest search for the static multi-vehicle bike-repositioning prob- regarding the publication of this paper. lem,” Transportation Research Part B: Methodological, vol. 95, pp. 340–363, 2017. Acknowledgments [15] G. Erdogan, ˘ M. Battarra, and R. Wolfer Calvo, “An exact algorithm for the static rebalancing problem arising in bicycle Tis research was supported by Basic Science Research sharing systems,” European Journal of Operational Research, Program through the National Research Foundation of vol. 245, no. 3, pp. 667–679, 2015. Korea (NRF) funded by the Ministry of Science and ICT [16] P. Angeloudis, J. Hu, and M. G. H. Bell, “A strategic repo- (NRF-2020R1A2C2014561). sitioning algorithm for bicycle-sharing schemes,” Trans- portmetrica: Transportation Science, vol. 10, no. 8, pp. 759–774, 2014. References [17] R. Alvarez-Valdes, J. M. Belenguer, E. Benavent et al., “Op- timizing the level of service quality of a bike-sharing system,” [1] R. R. Clewlow, “Te micro-mobility revolution: the in- Omega, vol. 62, pp. 163–175, 2016. troduction and adoption of electric scooters in the [18] S. Zhang, G. Xiang, and Z. Huang, “Bike-sharing static United States,” in Proceedings of the 98th Annual Meeting of rebalancing by considering the collection of bicycles in need the Transportation Research Board, Washington, DC, January of repair,” Journal of Advanced Transportation, vol. 2018, no. 1,Article ID 8086378, 18 pages, 2018. [2] M. Liu, S. Seeder, and H. Li, “Analysis of E-scooter trips and [19] T. Bulhões, A. Subramanian, G. Erdogan, ˘ and G. Laporte, their temporal usage patterns,” Institute of Transportation “Te static bike relocation problem with multiple vehicles and Engineers Journal, vol. 89, no. 6, pp. 44–49, 2019. visits,” European Journal of Operational Research, vol. 264, [3] G. McKenzie, “Spatiotemporal comparative analysis of no. 2, pp. 508–523, 2018. scooter-share and bike-share usage patterns in Washington, [20] T. Raviv, M. Tzur, and I. A. Forma, “Static repositioning in DC,” Journal of Transport Geography, vol. 78, pp. 19–28, 2019. a bike-sharing system: models and solution approaches,” [4] S. Kim, M. Koack, S. Choo, and S. Kim, “Analysing spatial usage characteristics of shared E-scooter: focused on spatial EURO Journal on Transportation and Logistics, vol. 2, no. 3, pp. 187–229, 2013. autocorrelation modeling,” Te Journal of Te Korea Institute of Intelligent Transport Systems, vol. 20, no. 1, pp. 54–69, 2021. [21] I. A. Forma, T. Raviv, and M. Tzur, “A 3-step math heuristic for the static repositioning problem in bike-sharing systems,” [5] A. Pal and Y. Zhang, “Free-foating bike sharing: solving real- life large-scale static rebalancing problems,” Transportation Transportation Research Part B: Methodological, vol. 71, pp. 230–247, 2015. Research Part C: Emerging Technologies, vol. 80, pp. 92–116, 2017. [22] Y. Li, W. Y. Szeto, J. Long, and C. S. Shui, “A multiple type bike repositioning problem,” Transportation Research Part B: [6] M. Lee, J. Y. Chow, G. Yoon, and B. Yueshuai He, “Fore- casting E-scooter competition with direct and access trips by Methodological, vol. 90, pp. 263–278, 2016. Journal of Advanced Transportation 13 [23] J. Schuijbroek, R. C. Hampshire, and W. J. Van Hoeve, chain,” ISPRS International Journal of Geo-Information, vol. 8, no. 8, p. 334, 2019. “Inventory rebalancing and vehicle routing in bike sharing systems,” European Journal of Operational Research, vol. 257, [39] X. Chang, J. Wu, H. Sun, and J. Chen, “Relocating operational and damaged bikes in free-foating systems: a data-driven no. 3, pp. 992–1004, 2017. [24] C. S. Shui and W. Y. Szeto, “Dynamic green bike repositioning modeling framework for level of service enhancement,” Transportation Research Part A: Policy and Practice, vol. 153, problem–A hybrid rolling horizon artifcial bee colony al- pp. 235–260, 2021. gorithm approach,” Transportation Research Part D: Trans- [40] L. Tolomei, S. Fiorini, A. Ciociola, L. Vassio, D. Giordano, and port and Environment, vol. 60, pp. 119–136, 2018. M. Mellia, “Benefts of relocation on E-scooter sharing-adata- [25] C. Contardo, C. Morency, and L. M. Rousseau, “Balancing informed approach,” in Proceedings of the 2021 IEEE In- a dynamic public bike-sharing system,” Montreal: Cirrelt, ternational Intelligent Transportation Systems Conference vol. 4, 2012. (ITSC), pp. 3170–3175, Indianapolis, IN, USA, September [26] R. Regue and W. Recker, “Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing prob- [41] S. Carrese, F. D’Andreagiovanni, T. Giacchetti, A. Nardin, and lem,” Transportation Research Part E: Logistics and Trans- L. Zamberlan, “A beautiful feet: optimal repositioning in e- portation Review, vol. 72, pp. 192–209, 2014. scooter sharing systems for urban decorum,” Transportation [27] C. Kloimullner, ¨ P. Papazek, B. Hu, and G. R. Raidl, “Balancing Research Procedia, vol. 52, pp. 581–588, 2021. bicycle sharing systems: an approach for the dynamic case,” in [42] J. Osorio, C. Lei, and Y. Ouyang, “Optimal rebalancing and Proceedings of the European conference on evolutionary on-board charging of shared electric scooters,” Transportation computation in combinatorial optimization, pp. 73–84, Research Part B: Methodological, vol. 147, pp. 197–219, 2021. Granada, Spain, April 2014. [43] S. C. Ho and W. Y. Szeto, “Solving a static repositioning [28] J. Brinkmann, M. W. Ulmer, and D. C. Mattfeld, “Short-term problem in bike-sharing systems using iterated tabu search,” strategies for stochastic inventory routing in bike sharing Transportation Research Part E: Logistics and Transportation systems,” Transportation Research Procedia, vol. 10, pp. 364– Review, vol. 69, pp. 180–198, 2014. 373, 2015. [44] G. Erdogan, ˘ G. Laporte, and R. Wolfer Calvo, “Te static [29] D. Zhang, C. Yu, J. Desai, H. Y. K. Lau, and S. Srivathsan, “A bicycle relocation problem with demand intervals,” European time-space network fow approach to dynamic repositioning Journal of Operational Research, vol. 238, no. 2, pp. 451–457, in bicycle sharing systems,” Transportation Research Part B: Methodological, vol. 103, pp. 188–207, 2017. [45] M. Rainer-Harbach, P. Papazek, G. R. Raidl, B. Hu, [30] B. Legros, “Dynamic repositioning strategy in a bike-sharing C. Kloimullner, ¨ and C. Kloimullner, ¨ “PILOT, GRASP, and system; how to prioritize and how to rebalance a bike station,” VNS approaches for the static balancing of bicycle sharing European Journal of Operational Research, vol. 272, no. 2, systems,” Journal of Global Optimization, vol. 63, no. 3, pp. 740–753, 2019. pp. 597–629, 2015. [31] M. Du, L. Cheng, X. Li, and F. Tang, “Static rebalancing [46] J. H. Holland, Adaptation in Natural and Artifcial Systems: optimization with considering the collection of malfunc- An Introductory Analysis with Applications to Biology, Con- tioning bikes in free-foating bike sharing system,” Trans- trol, and Artifcial Intelligence, MIT press, Cambridge, MA, portation Research Part E: Logistics and Transportation USA, 1992. Review, vol. 141, Article ID 102012, 2020. [47] I. M. Oliver, D. Smith, and J. R. Holland, “Study of permu- [32] Z. Sun, Y. Li, and Y. Zuo, “Optimizing the location of virtual tation crossover operators on the traveling salesman prob- stations in free-foating bike-sharing systems with the user lem,” Genetic Algorithms and Teir Applications: Proceedings demand during morning and evening rush hours,” Journal of of the Second International Conference on Genetic Algorithms, Advanced Transportation, vol. 2019, no. 1, Article ID 4308509, Massachusetts Institute of Technology, Cambridge, MA. 11 pages, 2019. Hillsdale, NJ, 1987. [33] M. Usama, Y. Shen, and O. Zahoor, “A free-foating bike [48] L. Davis, “Applying adaptive algorithms to epistatic domains,” repositioning problem with faulty bikes,” Procedia Computer IJCAI, vol. 85, pp. 162–164, 1985. Science, vol. 151, pp. 155–162, 2019. [49] T. Starkweather, S. McDaniel, K. E. Mathias, L. D. Whitley, [34] M. Usama, O. Zahoor, Q. Bao, Z. Liu, and Y. Shen, “Dockless and C. Whitley, A Comparison of Genetic Sequencing Oper- bike-sharing rebalancing problem with simultaneous faulty ators, ICGA, Maharashtra, India, 1991. bike recycling,” in Proceedings of the 19th COTA International Conference of Transportation Professionals, pp. 4963–4974, Nanjing, China, July 2019. [35] M. Usama, O. Zahoor, Y. Shen, and Q. Bao, “Dockless bike- sharing system: solving the problem of faulty bikes with si- multaneous rebalancing operation,” Journal of Transport and Land Use, vol. 13, no. 1, pp. 491–515, 2020. [36] Y. Liu, W. Y. Szeto, and S. C. Ho, “A static free-foating bike repositioning problem with multiple heterogeneous vehicles, multiple depots, and multiple visits,” Transportation Research Part C: Emerging Technologies, vol. 92, pp. 208–242, 2018. [37] L. Caggiani, R. Camporeale, M. Ottomanelli, and W. Y. Szeto, “A modeling framework for the dynamic management of free- foating bike-sharing systems,” Transportation Research Part C: Emerging Technologies, vol. 87, pp. 159–182, 2018. [38] Y. Zhai, J. Liu, J. Du, and H. Wu, “Fleet size and rebalancing analysis of dockless bike-sharing stations based on Markov http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Advanced Transportation Hindawi Publishing Corporation

Optimal Rebalancing Strategy for Shared e-Scooter Using Genetic Algorithm

Download PDF
13 pages

Loading next page...
 
/lp/hindawi-publishing-corporation/optimal-rebalancing-strategy-for-shared-e-scooter-using-genetic-537Cv52EOl

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Hindawi Publishing Corporation
ISSN
0197-6729
eISSN
2042-3195
DOI
10.1155/2023/2696651
Publisher site
See Article on Publisher Site

Abstract

Hindawi Journal of Advanced Transportation Volume 2023, Article ID 2696651, 13 pages https://doi.org/10.1155/2023/2696651 Research Article Optimal Rebalancing Strategy for Shared e-Scooter Using Genetic Algorithm 1 1 2 Sujae Kim , Gyeongjae Lee , and Sangho Choo Department of Urban Planning, Hongik University, Seoul 04066, Republic of Korea Department of Urban Design and Planning, Hongik University, Seoul 04066, Republic of Korea Correspondence should be addressed to Sangho Choo; shchoo@hongik.ac.kr Received 7 November 2022; Revised 30 January 2023; Accepted 24 March 2023; Published 6 April 2023 Academic Editor: Lei Wang Copyright © 2023 Sujae Kim et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Shared e-scooters are provided as a free-foating service that can be freely rented and returned within the service area. Although this has a positive efect in terms of convenience for users of shared e-scooters, it is creating new urban problems, such as undermining the aesthetics of the city and obstructing the passage of pedestrians. Terefore, this study developed an optimal rebalancing algorithm to mitigate these problems and proposed an efcient operation plan. Complete relocation was performed to match the demand and supply for an efcient operation by reducing the unnecessary oversupply of shared e-scooters. Te optimal rebalancing algorithm that refects the attributes of e-scooters was developed through genetic algorithms and subsequently applied to actually used cases. Te results indicate that when 20% of the potential demand was considered, an optimal solution could be derived with two relocation vehicles; however, when the potential demand was not considered, three relocation vehicles were required. Terefore, it is anticipated that the results of this study can serve as basic data for solving various urban problems caused by the recent rapid increase in the use of shared e-scooters. method of rebalancing. Rebalancing is a methodology in 1. Introduction which devices are retrieved from areas with low usage Shared e-scooters are provided as a free-foating service demand, and additional devices are placed in areas with that can be freely rented and returned within the service high usage demand. Te rebalancing methodology can be area. Tis type of service has recently become very popular. divided into static and dynamic rebalancing, depending on Shared e-scooter was frst serviced by Lime and Bird in the when devices are relocated, and complete and partial United States in 2017; since then, it has steadily been used rebalancing, according to the level of rebalancing [5]. Static [1–3]. As of August 2020, 16 companies were servicing rebalancing is a methodology for relocating devices in more than 36,000 devices in Korea [4]. However, the ad- account of the usage demand when there is little demand. In the case of dynamic rebalancing, relocation is performed vantage of e-scooters to be used freely without space re- strictions is also a disadvantage because of a phenomenon in consideration of the usage demand during a specifc time period, or relocation is performed when specifc conditions in which the e-scooters get concentrated in a specifc space at a specifc time. Consequently, various companies that are are met. Complete rebalancing is a methodology that de- servicing shared e-scooters in Korea are supplying more rives an optimal solution by precisely matching the supply than the demand at a higher cost. Although this has and demand at all points that require relocation. In the case a positive efect in terms of convenience for users of shared of partial rebalancing, it means that demand and supply e-scooters, it is creating new urban problems, such as cannot be matched at all points, or an optimal solution is undermining the aesthetics of the city and obstructing the derived from a nonconsistent state. Te remainder of this passage of pedestrians by occupying pedestrian paths. One paper is organized as follows: Section 2 (Literature Review) way to tackle this growing problem could be through the reviews studies on the rebalancing of bike sharing and 2 Journal of Advanced Transportation shared e-scooter. Section 3 (Materials and Methods) ex- developed a rebalancing algorithm for the collection of plains how the data were collected and the methodologies broken bikes for repair and for the relocation of shared bikes. A complete rebalancing was performed to match the supply used to rebalance the shared e-scooter. Section 4 (Results and Discussion) presents a shared e-scooter rebalancing and demand for all stations, and the relocation time was model and the evaluation results of applying the model to minimized by moving broken bikes to the warehouse. When real data. Finally, in Section 5 (Conclusions), the conclu- there are more stations, as is the case with the FFBSS, it is sions are drawn and study limitations and future research difcult to fnd an optimal solution to an mTSP; therefore, plans are discussed. the greedy-genetic heuristic algorithm was considered. Te rebalancing algorithm was applied to Share-A-Bull of Florida and Divvy of Chicago and subsequently evaluated by 2. Literature Review comparing the analysis results of CPLEX software, which is As shared e-scooters become a new mode of transportation, commonly used. Sun et al. [32] deployed virtual stations near research has been steadily conducted to identify the infu- public transit stations and major establishments to solve severe parking disorder caused by the FFBSS. Te location encing factors and predict the demand for their use [6–12]. Tese studies were reviewed in detail by Kim et al. [12]. As assignment of virtual stations is optimized to satisfy user regards rebalancing, there are many studies related to bike demand. Optimization problems are usually formulated as and car sharing; however, there is still a lack of research that a mixed-integer linear programming (MILP) model. Ex- suggests an efcient operation plan through the rebalancing perimental results proved that the MILP model and the of shared e-scooters. Terefore, this study only reviewed proposed method were superior to the k-means method. studies on the rebalancing of bike sharing similar to shared Usama et al. [33–35] tried to improve the level of service and e-scooters. Tere are two systems for bike sharing: the solve safety problems by repositioning randomly scattered station-based bike sharing system (SBBSS) and the free- free-foating bike-sharing and faulty bikes. Te objective for foating bike sharing system (FFBSS). In addition, the re- bike relocation is to minimize travel cost [33, 34], demand location problem is a problem of fnding the optimal al- dissatisfaction [34, 35], and relocation cost [35]. Te mechanism optimized the formulated problem with ternative among several alternatives. It is an important criterion to optimize, and this is called the objective func- a branch-and-cut algorithm, and the validity of the model tion. Terefore, studies related to the rebalancing of bike was tested through various numerical experiments using the sharing are classifed into operation types, rebalancing types, CPLEX solver. Liu et al. [36] developed a static partial and objective functions (see Table 1). First, looking at the rebalancing algorithm to minimize bike supply-demand optimal rebalancing study of the SBBSS, the objective imbalance and relocation time. Rebalancing algorithms function for static rebalancing of shared bikes was defned as were developed by improving chemical reaction optimiza- minimizing relocation time [15, 16, 19, 43], travel cost tion (CRO), based on the principle of chemical reaction. For [13, 18, 44], demand dissatisfaction, and relocation volume the evaluation of the developed rebalancing algorithm, the [17]. As regards static partial rebalancing, Raviv et al. [20] algorithm was applied to Citibike in New York and Share- and Schuijbroek et al. [23] minimized relocation time, A-Bull in Florida. Te numerical results were compared with those of the traditional CRO and CPLEX. Caggiani et al. [37] whereas Forma et al. [21], Li et al. [22], and Ho and Szeto [14] minimized relocation costs. In the work of Shui and predicted the demand for the use of the FFBSS and built Szeto [24], relocation time and demand dissatisfaction were a framework for a dynamic rebalancing model. After spatio- minimized. Finally, most of the studies of dynamic reba- temporal clustering was performed on the time and point of lancing minimized demand dissatisfaction [25, 27–30]. In use of the shared bike, the usage demand at a specifc time addition to demand dissatisfaction, relocation time [26, 27], and point was predicted by using a nonlinear autoregressive travel costs [29], and fuel and CO emission costs [24] have neural network with explicit (NARX). Dynamic rebalancing been minimized previously. As the shared e-scooter operates has also been performed to satisfy the predictive demand of in the method similar to the FFBSS, the rebalancing study of each time and point. Lloyd’s algorithm was used to minimize the dissatisfaction of demand at each point (less than the the FFBSS has been reviewed in detail in this study. Pal and Zhang [5] developed the FFBSS rebalancing methodology threshold number of bikes, the number of users unable to use one due to lack of bikes). Unlike other studies [5, 31, 36], based on the SBBSS rebalancing methodology. Each dock of the station was separated and set as an analysis point, and the the developed algorithms were evaluated in a toy network. Zhai et al. [38] improved dynamic optimization for the usage demand between stations was distributed to the analysis point. As a relocation methodology, the multiple standardized management of dockless bike-sharing. An algorithm was proposed, through the Markov stochastic traveling salesman problem (mTSP) using multiple vehicles was applied. Tis is because one vehicle with limited capacity process, to determine the appropriate feet size for dockless cannot fnd an appropriate solution with one community bike-sharing. To improve the practicality of the algorithm, pickup and delivery traveling salesman problem (TSP), the dynamic solution of bike-sharing steady-state feet size, which visits stations only once. Te optimal rebalancing according to time period, was presented. In addition, to verify the efciency of the algorithm, the linear pro- solution was derived to minimize the relocation time. Te developed algorithm was applied to Share-A-Bull in Florida gramming method for bike rebalancing analysis, was used. Experimental results showed that the algorithm could solve and Divvy in Chicago and compared with the results of the exact algorithm and tabu search algorithm. Du et al. [31] the disordered deployment of dockless bike-sharing. Chang Journal of Advanced Transportation 3 Table 1: Summary of the literature based on rebalancing strategies. Target Type Subtype Research article Methodology Objective Chemla et al. [13] Branch-and-cut Travel cost Ho and Szeto [14] Iterated tabu search Relocation time Erdogan et al. [15] Branch-and-cut and bender’s decomposition Travel cost Angeloudis et al. [16] Multistage heuristic Relocation time Complete Erdogan et al. [15] Exact algorithm based on bender’s cuts Relocation time Alvarez-Valdes et al. Demand dissatisfaction and relocation Heuristic based on minimum cost fow [17] volume Zhang et al. [18] Hybrid DPSO-VNS Travel cost Static Bulhoes et al. [19] Branch-and-cut Relocation time Raviv et al. [20] Mixed integer programming Relocation time Forma et al. [21] 3-step math heuristic Relocation cost Li et al. [22] Hybrid genetic algorithm Relocation cost Station based bike sharing system Partial Schuijbroek et al. [23] Constraint programming and MIP Relocation time (SBBSS) Ho and Szeto [14] Hybrid large neighborhood search Relocation cost Demand dissatisfaction and relocation Shui and Szeto [24] Enhanced artifcial bee colony algorithm time Contardo et al. [25] Hybrid MIP approach Demand dissatisfaction Regue and Recker [26] Mixed integer programming Relocation time Demand dissatisfaction and relocation Kloimullner et al. [27] Combination of greedy heuristic, GRASP, and VNS time Dynamic Brinkmann et al. [28] Inventory routing problem Demand dissatisfaction Zhang et al. [29] Time space network fow approach Demand dissatisfaction and travel cost Demand dissatisfaction and fuel and CO Shui and Szeto [24] Enhanced artifcial bee colony algorithm emission Legros [30] Markov decision Demand dissatisfaction Nested large neighborhood search and variable Pal and Zhang [5] Relocation time neighborhood descent Du et al. [31] Greed-genetic heuristic Relocation time Sun et al. [32] Te clustering algorithm and branch-and-cut User satisfed demand Complete Usama et al. [33] Branch-and-cut Travel cost Static Usama et al. [34] Branch-and-cut Demand dissatisfaction and travel cost Free-foating bike sharing system Demand dissatisfaction and relocation (FFBSS) Usama et al. [35] Branch-and-cut cost Demand dissatisfaction and relocation Partial Liu et al. [36] Chemical reaction optimization time Caggiani et al. [37] Lloyd’s algorithm Demand dissatisfaction Dynamic Zhai et al. [38] Branch-and-cut Relocation cost Chang et al. [39] A hybrid metaheuristic algorithm with VNS and ESA Relocation cost Complete Tolomei et al. [40] Simple greedy strategy Relocation distance Free-foating-scooter Static Carrese et al. [41] Integer linear programming Demand dissatisfaction Partial Osorio et al. [42] MIP and discrete-continuous hybrid model Relocation cost 4 Journal of Advanced Transportation plan, which results in a complete rebalancing strategy when et al. [39] suggested that free-foating bike sharing was an innovative and sustainable travel mode; however, there were implemented. imbalances between zones, caused by one-way trips and the need to move damaged bikes for repair. To solve this 3. Materials and Methods problem, a demand forecasting model using an encoder- decoder architecture embedded with the attention mecha- 3.1. Model Formulation nism was developed, and a hybrid metaheuristic algorithm, 3.1.1. Problem Defnition. Te shared e-scooter rebalancing integrating variable neighbourhood search (VNS), and en- algorithm developed in this study is a static rebalancing hanced simulated annealing (ESA) algorithms, were pre- algorithm and is a complete rebalancing algorithm that sented as an optimization model. Te proposed framework matches the demand and supply (the amount adjusted was applied to Beijing and China, and it was found that the through relocation based on the amount of placement at the most efective strategy was to relocate, considering only the start of relocation). Te pick-up and drop-of of e-scooters operational bikes during the peak hours. Recently, a re- was determined considering the usage demand by branches location study on shared e-scooters has also been conducted in the target area and the amount of initial placement. In this [40–42]. Tolomei et al. [40] quantifed the economic costs case, the point where the demand was greater than the initial and additional benefts resulting from the relocation of batch quantity was defned as the drop-of point, the point shared e-scooters. Simulations were performed for actual where the initial batch quantity was large was the pick-up trips operating in Austin and Louisville. A simple greedy point, and the point where relocation was not required by strategy was considered to defne the movement of an e- coincidence was defned as the balance point. In this design, scooter. Experimental results showed that a light and simple the relocation vehicle leaves the warehouse and visits the relocation policy with little relocation per hour improved the drop-of point and the pick-up point once, matches the rate of satisfactory trips by 42%. In other words, even if the drop-of volume of all branches to the demand, and then feet size was reduced, the overall performance would not be returns to the warehouse. Te balance point is not visited; afected. Osorio et al. [42] presented a model for overnight however, if there is a malfunctioning e-scooter or an e- charging and rebalancing by allowing the e-scooter to be scooter that needs recharging, the balance point is visited, charged, while moving in the rebalancing vehicles. For e- and the relocation vehicle picks up the broken e-scooter, scooter charging and rebalancing, a mixed-integer program drops of the same amount, and replaces the battery of the e- and a discrete-continuous hybrid model were developed, scooter that needs recharging. As there was no imbalance respectively. A continuous approximation technique was between demand and supply after relocation, the goal of proposed to avoid the enormous computational burden due rebalancing was, therefore, set to minimize relocation time. to the free-foating service. When applied to actual trips in In addition, when the capacity of the relocation vehicle was Washington, DC, compared to the direct application of the exceeded due to a large amount of pick-up after relocation, discrete formulation, the proposed model produced a better multiple relocation vehicles were considered. quality solution in a shorter time. Carrese et al. [41] sug- gested a plan for rebalancing of e-scooters through short- distance reposition of just a few meters rather than mid-to- 3.1.2. Mathematical Model. Te model used to develop the long-distance reposition within the city performed in tra- rebalancing algorithm in this study was modifed and ditional vehicle-sharing systems. An integer linear pro- supplemented according to the attribute of a shared e- gramming model was developed to solve the relocation scooter by referring to the model of a balancing bicycle problem by utilizing the realistic data of Rome, Italy. Te sharing system developed by Rainer-Harbach et al. [45]. Te good performance of the proposed model was demonstrated shared e-scooter rebalancing model developed in this study by comparing the results of CPLEX. Although e-scooter and is as follows: FFBSS have similar systems of operation, electrically pow- ered e-scooters require periodic charging or battery re- (1) Sets placement. Only one of the studies on e-scooter relocation N � 􏼈0, 1, · · · , n 􏼉(0  is  warehouse) max accounted for charging during relocation [42]; the others K � 􏼈1, 2, · · · , k 􏼉 max [40, 41] neither considered charging nor battery re- (2) Indices placement. In this study, a static complete rebalancing al- gorithm was developed to reduce unnecessary supply, and i, j: index of points derive an efcient operation plan by moving an e-scooter k: index of relocation vehicles from a point with no demand to a point with high usage (3) Parameters demand. Subsequently, we developed an optimal reba- lancing algorithm to improve the problems of shared e- sf : the initial number of e-scooters at point i scooters and to suggest an efcient operation plan. Te sd : the number of target e-scooters at point i rebalancing algorithm, developed in this study, added sr : the number of broken e-scooters at point i constraints on battery replacement that were not considered sb : the number of e-scooters requiring battery re- in previous bike relocation studies and also considered i placement at point i relocation and collection for repair. In addition, the ultimate implication of this study is to propose an efcient operation t : travel time from point i to point j (minutes) ij Journal of Advanced Transportation 5 C : capacity of relocation vehicle k relocation vehicles. Te relocation time was calculated as given in equation (2) and is the sum of the travel time of the RT : total relocation time of relocation vehicle k relocated vehicle, the pick-up and drop-of time of the T : total operable time of relocation vehicle k shared e-scooter, the pick-up time of the broken e-scooter, w : weight of e-scooter pick-up and drop-of time pd and the replacement time of the e-scooter battery. Te w : weight of e-scooter battery replacement time constraint (equation (3)) means that the number of e- scooters remaining at point i after relocation was equal to (4) Variables the sum of the initial number of e-scooters at point i and the x : 1 if relocation vehicle k moves from point i to j; ijk amount rebalanced by the relocation vehicle k. Equation (4) 0 otherwise is a conditional expression for complete relocation, which y : the number of e-scooters that the relocation means that the amount of e-scooters at point i after re- ijk vehicle k moves from point i to j location was the same as the target amount of e-scooters refecting the demand at point i. Equation (5) is a constraint p : the number of e-scooters that the relocation ik on the capacity of the relocation vehicle, which means that vehicle k picks up at point i when the relocation vehicle moves the e-scooter, it cannot d : the number of e-scooters that the relocation ik pick up in excess of the capacity of the relocation vehicle. vehicle k drops of at point i Equations (6) and (7) guarantee the route of the relocation s : the number of e-scooters remaining at point i after vehicle, and when the relocation vehicle leaves or visits point relocation i, it must arrive or depart from point j. Tis implies that the (5) Model formulation relocation vehicle k must move 0 or 1 from point i to j. Tat is, the relocation vehicle can visit each point at the most Te objective function is as follows: once. Equation (8) is a constraint on the pick-up of e- scooters, and it implies that a relocation vehicle cannot Minimize  Max RT , (1) 􏼈 􏼉 pick-up more e-scooters than the number of initial e- scooters at the relevant point. Equation (9) implies that the total relocation time cannot exceed the total operable ⎛ ⎝ ⎞ ⎠ RT � 􏽘 􏽘 t x + w 􏽘 􏽘 y + 􏽘 sr k ij ijk pd ijk i time of the relocation vehicle. i j i j i (2) + w 􏽘 sb , ∀k ∈ K, b i 3.2. Solution Methodology 3.2.1. Genetic Algorithm. In this study, a genetic algorithm s.t  sf + 􏽘 d − p � s , ∀i ∈ , ∀k ∈ K, (3) i ik ik i was applied to solve the static rebalancing problem of shared e-scooters. Te genetic algorithm has been studied to be efective in solving the problem of static rebalancing of s � sd , (4) i i shared bicycles. Te genetic algorithm is an optimization method frst introduced by John Holland in 1975, and it is y ≤ C × x , ∀i, j ∈ , ∀k ∈ K, (5) a methodology for calculating problems by imitating the ijk k ijk evolution of real organisms [46]. Te genetic algorithm is a probabilistic search method that models the evolution x � 􏽘 x , ∀i ∈ , ∀k ∈ K, genes to fnd the near-optimal solution and is used to fnd ijk ijk (6) j∈N,j≠i j∈N,j≠i the global optimal solution without falling into the problem of local optimal solutions by searching for solutions in parallel. However, it is not always possible to fnd a global 􏽘 x ≤ 1, ∀i ∈ , ∀k ∈ K, ijk (7) optimal solution, and even if an optimal solution is found, j∈N/0,j≠i the process cannot be known. Genetic algorithms are used in various felds and are typically used when deriving solutions 􏽘 p ≤ sf , ∀i ∈ , (8) ik i to TSP, approximate solution estimation of higher-order k∈K functions, neural network optimization, and non- deterministic polynomial time-hard problems. Terms used in genetic algorithms are defned as given. A chromosome is ⎛ ⎝ ⎞ ⎠ 􏽘 􏽘 t x + w 􏽘 􏽘 y + 􏽘 sr ij ijk pd ijk i a set containing genetic information and is the solution of i j i j i (9) the problem (relocation vehicle path). A gene is an element + w 􏽘 sb ≤ T , ∀k ∈ K. b i k constituting a chromosome and represents a component of a solution (movement between points). An ofspring is a new chromosome (a new relocation path) generated from the Equation (1) is the objective function of the shared e- chromosomes of the previous generation. Fitness is an in- scooter rebalancing algorithm, and it minimizes the vehicle trinsic value of chromosomes and is a measure (relocation relocation time, with the longest relocation time among the time) of how well the solution to the problem is suitable. 6 Journal of Advanced Transportation Elitism refers to preservation of chromosomes with good ft 01 23 ... N among the chromosomes of the previous generation as they ... Solution 1 0 3 7 12 64 are in the next generation. Te genetic algorithms have operators such as selection, crossover, and mutation. Te ... chromosome of the parent generation is selected through Solution 2 0 11 24 2 153 a selection operation, and an ofspring is produced through operations between the selected chromosomes. Tere are ... Solution x 0 120 89 46 5 various methods for the selection operation, but the basic principle is to increase the selection probability of a chro- Figure 1: Solution example of the genetic algorithm. mosome with good ftness, and lower the selection proba- bility for a chromosome with low ftness. However, caution constituting a chromosome indicates a movement path of is required because selecting only the chromosomes with a relocation vehicle. Tat is, the relocation vehicle visits the good ft can lead to premature convergence. Representative relocation point expressed by the gene in the order of the methods of the selection operation include roulette wheel gene. A chromosome is made up of a total of N genes, which selection, tournament selection, and rank-based selection. indicate a point where relocation is required. Rank-based selection is a method that compensates for the A fow chart representing how the optimal solution is shortcomings of roulette wheel selection. Because the se- derived from the genetic algorithm is shown in Figure 2. lection probability of a roulette wheel selection method is determined according to ftness, only excellent chromo- Step 1: generate a path for the relocation vehicle (initial somes are selected. Tis may lead to an unripe convergence solution (generation 1)) according to the selection problem. Rank-based selection supplements this and ranks operation among the entire solution set according to ftness, and then determines the selection Step 2: calculate the relocation time, which is the ftness probability as a linear function according to the ranking. of the solution Looking at the pros and cons of each selection operation Step 3: create a new relocation path (generation 2) method, roulette wheel selection can generate excellent according to the crossover operation and the mutation descendants with a simple methodology; however, it can fall operation into the problem of local optima. As this problem can be solved by mutation operation, in this study the roulette Step 4: determine whether the next generation is the wheel selection method was applied. Crossover is an op- target number of generation, and if the target number is eration that generates ofspring chromosomes through satisfed, the algorithm is terminated to derive an crossover between chromosomes of the parent generation, optimal solution selected by a selection operation. Tat is, a new chromosome Step 5: if the target number of generation is not met, is created by exchanging the genes of the chromosomes of return to step 2 and repeat the parent generation. Te crossover is the operator with the most diverse alternatives (e.g., one-point crossover, cycle 4. Results and Discussion crossover [47], order crossover [48], and edge re- combination crossover [49]). Edge recombination crossover 4.1. Numerical Study is a crossover operation method developed for the TSP. Tis 4.1.1. Data. XingXing, a shared e-scooter service of the method creates a list of points related to each point on the PUMP Corporation, was in service frst in Gangnam-gu and parent chromosome. After selecting one point, the point Seocho-gu, in 2019. Since December 2021, it has been with the fewest adjacent points is selected. If there are adopted nationwide. When a XingXing service user utilizes multiple candidate points, a random point is selected and a device once, one usage data are collected. Tis includes progeny chromosomes are constructed heuristically. Reba- information such as device ID, rental date and time, rental lancing of the shared e-scooter is performed by the re- location, return date and time, return location, usage time, location vehicle creating an optimal route. Terefore, the usage distance, and user ID. Table 2 is an example of one rebalancing problem can be said to be similar to that of the usage data collected. TSP. Crossover methods can be implemented easily. Te In this study, the data of XingXing was used. Collected sequential crossover method that can be applied when de- data with the following errors were removed from analysis: riving the optimal solution of the TSP is applied in this study. Te mutation operation can fnd a solution that (1) Tere was an error in the coordinates of the rental cannot be found by the crossover operation in that it applies location and the return location, or the device was a gene trait that is not present in the parent chromosome to recorded as been rented or returned from an area the genes of the ofspring to a certain probability. As such, other than the service area the mutation operation can diversify the solution group to (2) Te Euclidean distance between the rental location avoid the local optima problem and fnd the global optimal and the return location was smaller than the usage solution. Te solution, which is the chromosome of the distance genetic algorithm, is expressed as shown in Figure 1. Each (3) Te usage distance was recorded as zero gene constituting a chromosome indicates a point where relocation is required, and the sequence of genes ... Journal of Advanced Transportation 7 Create an initial generation Create a relocation path (G = 1) Evaluate the fitness Calculate the relocation time Apply the crossover operation Change the relocation path and the mutation operation Check the target No Create a new relocation path number of generation (G = G + 1) t+1 t (G = G ) target Yes Deriving the optimal solution Figure 2: Flow of deriving the optimal solution of the genetic algorithm. (4) Usage time was recorded as less than 20 seconds between each grid was assumed to be a Euclidean distance. (according to the service policy, usage of less than 20 As for the speed of the relocated vehicle, 30 km/h, the av- seconds was refunded and considered unused) erage travel speed of inner Seoul roads (excluding urban expressways) during the early morning hours of static (5) Average speed exceeded 25 km/h (the maximum rebalancing, was applied. Second, the capacity of the re- speed of the device is limited to 25 km/h) location vehicle was 30, and the pick-up and drop-of time of Te spatial-temporal scope of the analysis was adopted the e-scooter was assumed to be 30 seconds per device. from Kim et al. [12]. Tey set the spatial and temporal scope Currently, a general cargo truck used when moving shared of Gangnam-gu and Seocho-gu, Seoul, in October 2020. bikes and shared e-scooters can accommodate up to 30 e- After setting the analysis unit as a 200 meters square grid, the scooters. When picking up and dropping of e-scooters, it spatial scope was divided into 5 communities using the was assumed that it took approximately 30 seconds per community structure method. In this study, the community device because people had to load or unload them from the with the most usage among the fve communities was set as relocation vehicle. Furthermore, it was assumed that the the scope of the study. Tis community is located on the east ratio of the broken e-scooter and the e-scooter requiring side of the Gyeongbu Expressway, on the left side of Eonju- recharging was 1% and 5%, respectively. Tese ratios were ro, and on the north side of Teheran-ro, as shown in Figure 3. assumed arbitrarily because it was not possible to obtain Te total number of grids and usage demand was 144 and information such as whether the e-scooter was malfunc- 43,384, respectively, with the highest demand for each grid tioning and the remaining battery capacity. Finally, a re- being 301. Garosu-gil, in Sinsa-dong, and the commercial location vehicle could visit a point that required relocation district of Gangnam Station are also located in the up to once. Tis narrows the scope of analysis for problem community. solving and enables efcient algorithm development [20, 43]. In addition, several parameters of the genetic algorithm were 4.1.2. Parameter Adjustment. Several assumptions were set. Te genetic algorithm selects a certain amount of initial made for the development of the rebalancing algorithm. solutions to derive the optimal solution, and then derives the Trough these assumptions, the problem of rebalancing the next generation solution through crossover and mutation. e-scooter was made simpler, and information that was At this time, it was necessary to optimize the variables to difcult to obtain was refected. First, a Euclidean distance account for the number of initial solutions to select, the ratio was used for the distance between each point, and the speed of variability for solution diversity, the ratio of elitism that of the relocation vehicle was assumed to be 30 km/h. As the maintained a high-quality solution for quick optimal so- analysis unit was set on a 200 meters square grid, the location lution derivation, and the number of generations to derive the optimal solution. Te initial solution, mutation rate, and supply location of the e-scooter placed in the square grid were assumed to be at the center of the grid, and the distance elitism rate, and maximum generation were 100, 0.5%, 10%, 8 Journal of Advanced Transportation Table 2: Example of shared e-scooter usage data. Rental Rental Rental Rental Return Return Return Return Usage Usage Device date time location location date time location location time distance User ID ID (YYMMDD) (HHMMSS) (latitude) (longitude) (YYMMDD) (HHMMSS) (latitude) (longitude) (HHMMSS) (meters) PQJEAD 201001 000032 127.0227 37.5038 201001 000402 127.0243 37.4971 000329 879 5db42## Journal of Advanced Transportation 9 Garosu-gil Gyeongbu Express Bus Expressway Terminal Gangnam sta. Figure 3: Spatial scope of this study. and 200, respectively. Tis solution was further optimized genetic algorithms. However, in the case of the CPLEX, the through scenario analysis of each variable. For scenario analysis time increased exponentially as the number of analysis, the optimal value was derived by changing the points increased. When the number of points was 10, the initial solution value after fxing other variables, and after analysis time was 2 seconds, which was not signifcantly diferent from the genetic algorithm, but when the number refecting this, the optimal value was derived by changing other variables. For scenario analysis, 30 random points in of points was 30, the analysis time was determined to be the analysis range were used. Tere was one relocation more than an hour. Terefore, when the number of analysis vehicle, and the number of e-scooters that required re- points was large, it was deemed that the genetic algorithm location was 78. Te optimization result is shown in Figure 4. with a signifcantly faster analysis time was more Finally, the variables used in the algorithm were 200 initial reasonable. solutions, 1% mutation rate, 25% elitism rate, and 1,000 generations of analysis. 4.1.4. Algorithm Application. Te developed algorithm was applied to an actual case on October 30, 2020. Te initial 4.1.3. Algorithm Evaluation. In this study, the genetic al- feet size was set, based on the foating e-scooter, at 03:00 gorithm developed to rebalance shared e-scooters was am when the demand by time period was the lowest. Te compared with CPLEX, which is commonly used to solve the target feet size was set as the predicted demand at 08:00 am, existing optimization problem [31]. For objective evaluation the frst peak time. 136 of the total 144 points needed of the algorithm, various scenarios were analyzed for the relocation; 8 points needed to be balanced. Among the number of points and the number of relocation vehicles; 10, points requiring relocation, 90 drop-of points and 46 pick- 20, and 30 analysis points were analyzed. Te number of up points were determined. Tis was approximately twice relocation vehicles was considered 1 when there were 10 as many drop-of points as pick-up points. By contrast, the number of points was 270, which indicates 73 more units points, 1 to 2 when there were 20 points, and 1 to 3 when there were 30 points. Based on the number of analysis points than the demand. Tis implies that e-scooters were un- considered, the number of e-scooters that needed relocation, necessarily oversupplied at some points. Herein, we carried the number of broken e-scooters, and the number of e- out a pick-up of the 73 units that were oversupplied by scooters that required recharging are listed in Table 3. performing a complete rebalancing to match the supply and Te results of the rebalancing analysis for each analysis demand. When relocating a shared e-scooter, 1 to 3 re- scenario are presented in Table 4. Te genetic algorithm location vehicles were considered because the capacity of derived the optimal solution randomly because the initial the relocation vehicle was 30. In addition, 20% and 40% of solution selection, crossover, and mutation were all applied the total demand were considered as potential demand. Te randomly. Terefore, the genetic algorithm carried out 10 number of broken e-scooters and the number of e-scooters iterations to compute the best objective value [31]. Re- requiring recharging were assumed to be 2 and 13, re- spectively, according to the basic assumptions presented in garding the rebalancing results of the six scenarios, similar optimal results were obtained for both the CPLEX and parameter adjustment section. Te location of the 10 Journal of Advanced Transportation 77.5 95.0 77.0 90.0 76.5 85.0 76.0 80.0 75.5 75.0 75.0 70.0 74.5 65.0 100 150 200 250 300 0.5 1.0 1.5 2.0 2.5 Initial solution Mutation rate (%) 74.0 75.0 73.5 73.0 73.0 71.0 72.5 69.0 72.0 67.0 71.5 65.0 71.0 63.0 10 15 20 25 30 200 400 600 800 1000 1200 Elitism rate (%) Target number of generation Figure 4: Parameter tuning for the genetic algorithm. Table 3: Scenario of the evaluation algorithm. Number of Number of Number of Number of Number of Scenario points relocation vehicle relocation e-scooters broken e-scooters recharging e-scooters 1 10 1 31 0 1 2 1 20 48 1 2 3 2 4 1 5 30 2 78 1 3 6 3 Table 4: Evaluating results of rebalancing. CPLEX Te genetic algorithm Scenario Relocation time Computing time Relocation time Computing time Maximum load Maximum load (min) (sec) (min) (sec) 1 11 31 2 11 31 1.1 2 15 41 111 15 41 3.0 3 11 21 1,900 11 21 3.5 4 27 66 3,943 27 66 9.3 5 15 34 6,703 15 34 10.4 6 12 23 10,488 12 23 12.1 Note. Te relocation time of the genetic algorithm was the best time of 10 runs, and the computing time was taken as the average time of 10 runs. warehouse, where the relocation vehicle leaves and arrives, genetic algorithm. As a result of the rebalancing analysis, if stores the collected e-scooter, and repairs the broken e- potential demand was not taken into account when op- scooter, was assumed to be approximately 4 km apart. Te erating one relocation vehicle, the maximum load capacity rebalancing result is presented in Table 5. First, the reba- of the relocation vehicle was 76, and the relocation time was lancing results were presented as average values after re- 506 minutes, indicating that both the relocation vehicle peating the analysis 10 times due to the randomness of the capacity condition and the relocation time constraint were Relocation time (min) Relocation time (min) Relocation time (min) Relocation time (min) Journal of Advanced Transportation 11 Table 5: Results of rebalancing. Number Number Number Potential Relocation Number Relocation of Number of of Maximum demand vehicle of broken time relocation of points relocation recharging load (%) # e-scooters (min) vehicle e-scooters e-scooters 0 1 136 73 2 13 76 506 1 20 1 136 49 2 13 53 499 40 1 136 26 2 13 29 494 1 68 38 0 8 45 191 2 68 36 2 5 36 201 1 68 20 0 7 29 210 2 68 29 2 6 29 208 1 45 25 0 5 27 98 3 0 2 46 25 1 3 27 102 3 45 24 1 5 26 98 Note. Te relocation time was calculated as the average time of 10 runs. not satisfed. When 20% of the potential demand was re- 5. Conclusions fected, the number of e-scooters that required relocation decreased from 73 to 49. As a result of the rebalancing Shared e-scooters are provided as a free-foating service that analysis, the maximum load capacity was 53, and the re- can be freely rented and returned within the service area. location time was 499 minutes. Tis violated the as- Recently, this type of service has become very popular and as sumptions, and no optimal solution was derived. When such has created a new set of problems. Tis study, therefore, 40% of the potential demand was refected, the number of developed an optimal rebalancing algorithm to mitigate the e-scooters that needed relocation was reduced to 26, which problems of shared e-scooters and to suggest an efcient was expected to be able to derive an optimal solution. Te operation plan. In this study, complete rebalancing was maximum load capacity was 29, which satisfed the capacity performed to match the demand and supply for efcient requirements of the relocation vehicle; however, the re- operation by reducing unnecessary oversupply of the shared location time was 494 minutes, and this did not meet the e-scooters. Devices that needed to be broken and recharged time constraint. Terefore, it was not possible to derive an were considered, refecting the attributes of e-scooters, and optimal solution for rebalancing an e-scooter when op- a genetic algorithm was used to derive an optimal solution. erating one relocation vehicle. When two relocation ve- Te optimal rebalancing algorithm was applied to an actual hicles were operated, the relocation time was 201 minutes case, wherein one to three relocation vehicles and 20% and (relocation vehicle 2), which satisfed the relocation time 40% of additional potential demand were considered. As constraint; however, it was expected that the optimal so- a result of rebalancing, when 20% of potential demand was lution could not be derived with 38 and 36 e-scooters considered, an optimal solution could be derived with two requiring relocation, respectively. Te maximum load ca- relocation vehicles, and when potential demand was not pacity of the relocation vehicle was 45 and 36, which did not considered, it was found that three relocation vehicles were meet the vehicle capacity requirements. When 20% of the required. Tis study is meaningful in that it applied the potential demand was refected, the optimal solution for genetic algorithm, which is an efective methodology for relocation was expected to be derived, with 20 and 29 units FFBSS rebalancing, to e-scooter relocation, which has yet to required for relocation, respectively. Te maximum loading be studied. In addition, the results can help address new capacity of the relocation vehicle was 29 for both relocation urban problems (undermining the aesthetics of the city, vehicles 1 and 2, and the relocation time was derived as obstructing the passage of pedestrians, etc.) by reducing 210 minutes (relocation vehicle 1). Terefore, when op- unnecessary feets through demand forecasting and re- erating two relocation vehicles, an optimal solution was location. Tis study has some limitations that require further derived with a relocation time of 210 minutes when 20% of research in the future. First, there are limitations in the potential demand was refected. In the case of operating analysis methodology used. Te genetic algorithm was used three relocation vehicles, the number of e-scooters that to derive the optimal solution of the rebalancing algorithm, required relocation per vehicle was 25, 25, and 24, re- and the results were compared with those of CPLEX, which spectively. As a result of rebalancing, the maximum loading is generally used to evaluate the developed algorithm. Apart capacities of the relocated vehicles were 27, 27, and 26, from the genetic algorithm, there are various methodologies respectively. Tus, the capacity conditions of the relocation for deriving the optimal solution of the rebalancing algo- vehicle were satisfed, and the relocation time was derived rithm. Additional comparative review with these various as 102 minutes (relocation vehicle 2). When operating three methodologies as well as with CPLEX is necessary. In ad- relocation vehicles, the optimal solution for relocation of e- dition, the static rebalancing algorithm that performs re- location based on a specifc time point was developed in this scooters was derived without potential demand; therefore, potential demand was not additionally considered. study. Due to the limitation of static rebalancing, which is 12 Journal of Advanced Transportation mode and distance in New York city,” 2019, https://arxiv.org/ based on a specifc point in time, usage during relocation was abs/1908.08127. not refected, and the situation after relocation was not [7] S. Bai and J. Jiao, “Dockless E-scooter usage patterns and considered. A representative methodology that can improve urban built environments: a comparison study of Austin, tx, this is dynamic programming. However, it faces difculties and minneapolis, mn,” Travel Behaviour and society, vol. 20, in deriving an optimal solution when the analysis range is pp. 264–272, 2020. large, such as in free-foating services. Tis can be solved by [8] H. Yang, J. Huo, Y. Bao, X. Li, L. Yang, and C. R. Cherry, reducing the time step of the static rebalancing methodology “Impact of e-scooter sharing on bike sharing in Chicago,” (analyzed for 5 h ours, from 3 to 8, in this study) and re- Transportation Research Part A: Policy and Practice, vol. 154, peating relocation. Terefore, it is thought that a study pp. 23–36, 2021. through a scenario review is necessary. However, if the [9] O. Caspi, M. J. Smart, and R. B. Noland, “Spatial associations number of relocation increases, the cost of relocation in- of dockless shared E-scooter usage,” Transportation Research creases accordingly. Terefore, it is necessary to also review Part D: Transport and Environment, vol. 86, Article ID 102396, 2020. the optimal scenario considering the relocation cost and the [10] A. Hosseinzadeh, M. Algomaiah, R. Kluger, and Z. Li, “E- number of relocations. In this study, only the operation plan Scooters and sustainability: investigating the relationship for optimal rebalancing (operating three relocation vehicles) between the density of E-scooter trips and characteristics of was presented. Terefore, additional review on the evalua- sustainable urban development,” Sustainable Cities and So- tion index that can quantitatively evaluate the results of the ciety, vol. 66, Article ID 102624, 2021. study is necessary. Finally, this study presented an e-scooter [11] S. W. Ham, J. H. Cho, S. Park, and D. K. Kim, “Spatiotemporal rebalancing methodology to solve new urban problems, but demand prediction model for E-scooter sharing services with the fundamental solution to these problems would be a new latent feature and deep learning,” Transportation Research legislation regarding the infrastructure. Record Journal of the Transportation Research Board, vol. 2675, no. 11, pp. 34–43, 2021. [12] S. Kim, S. Choo, G. Lee, and S. Kim, “Predicting demand for Data Availability shared E-scooter using community structure and deep Te data are not publicly available due to privacy. learning method,” Sustainability, vol. 14, no. 5, p. 2564, 2022. [13] D. Chemla, F. Meunier, and R. Wolfer Calvo, “Bike sharing systems: solving the static rebalancing problem,” Discrete Conflicts of Interest Optimization, vol. 10, no. 2, pp. 120–146, 2013. [14] S. C. Ho and W. Y. Szeto, “A hybrid large neighborhood Te authors declare that they have no conficts of interest search for the static multi-vehicle bike-repositioning prob- regarding the publication of this paper. lem,” Transportation Research Part B: Methodological, vol. 95, pp. 340–363, 2017. Acknowledgments [15] G. Erdogan, ˘ M. Battarra, and R. Wolfer Calvo, “An exact algorithm for the static rebalancing problem arising in bicycle Tis research was supported by Basic Science Research sharing systems,” European Journal of Operational Research, Program through the National Research Foundation of vol. 245, no. 3, pp. 667–679, 2015. Korea (NRF) funded by the Ministry of Science and ICT [16] P. Angeloudis, J. Hu, and M. G. H. Bell, “A strategic repo- (NRF-2020R1A2C2014561). sitioning algorithm for bicycle-sharing schemes,” Trans- portmetrica: Transportation Science, vol. 10, no. 8, pp. 759–774, 2014. References [17] R. Alvarez-Valdes, J. M. Belenguer, E. Benavent et al., “Op- timizing the level of service quality of a bike-sharing system,” [1] R. R. Clewlow, “Te micro-mobility revolution: the in- Omega, vol. 62, pp. 163–175, 2016. troduction and adoption of electric scooters in the [18] S. Zhang, G. Xiang, and Z. Huang, “Bike-sharing static United States,” in Proceedings of the 98th Annual Meeting of rebalancing by considering the collection of bicycles in need the Transportation Research Board, Washington, DC, January of repair,” Journal of Advanced Transportation, vol. 2018, no. 1,Article ID 8086378, 18 pages, 2018. [2] M. Liu, S. Seeder, and H. Li, “Analysis of E-scooter trips and [19] T. Bulhões, A. Subramanian, G. Erdogan, ˘ and G. Laporte, their temporal usage patterns,” Institute of Transportation “Te static bike relocation problem with multiple vehicles and Engineers Journal, vol. 89, no. 6, pp. 44–49, 2019. visits,” European Journal of Operational Research, vol. 264, [3] G. McKenzie, “Spatiotemporal comparative analysis of no. 2, pp. 508–523, 2018. scooter-share and bike-share usage patterns in Washington, [20] T. Raviv, M. Tzur, and I. A. Forma, “Static repositioning in DC,” Journal of Transport Geography, vol. 78, pp. 19–28, 2019. a bike-sharing system: models and solution approaches,” [4] S. Kim, M. Koack, S. Choo, and S. Kim, “Analysing spatial usage characteristics of shared E-scooter: focused on spatial EURO Journal on Transportation and Logistics, vol. 2, no. 3, pp. 187–229, 2013. autocorrelation modeling,” Te Journal of Te Korea Institute of Intelligent Transport Systems, vol. 20, no. 1, pp. 54–69, 2021. [21] I. A. Forma, T. Raviv, and M. Tzur, “A 3-step math heuristic for the static repositioning problem in bike-sharing systems,” [5] A. Pal and Y. Zhang, “Free-foating bike sharing: solving real- life large-scale static rebalancing problems,” Transportation Transportation Research Part B: Methodological, vol. 71, pp. 230–247, 2015. Research Part C: Emerging Technologies, vol. 80, pp. 92–116, 2017. [22] Y. Li, W. Y. Szeto, J. Long, and C. S. Shui, “A multiple type bike repositioning problem,” Transportation Research Part B: [6] M. Lee, J. Y. Chow, G. Yoon, and B. Yueshuai He, “Fore- casting E-scooter competition with direct and access trips by Methodological, vol. 90, pp. 263–278, 2016. Journal of Advanced Transportation 13 [23] J. Schuijbroek, R. C. Hampshire, and W. J. Van Hoeve, chain,” ISPRS International Journal of Geo-Information, vol. 8, no. 8, p. 334, 2019. “Inventory rebalancing and vehicle routing in bike sharing systems,” European Journal of Operational Research, vol. 257, [39] X. Chang, J. Wu, H. Sun, and J. Chen, “Relocating operational and damaged bikes in free-foating systems: a data-driven no. 3, pp. 992–1004, 2017. [24] C. S. Shui and W. Y. Szeto, “Dynamic green bike repositioning modeling framework for level of service enhancement,” Transportation Research Part A: Policy and Practice, vol. 153, problem–A hybrid rolling horizon artifcial bee colony al- pp. 235–260, 2021. gorithm approach,” Transportation Research Part D: Trans- [40] L. Tolomei, S. Fiorini, A. Ciociola, L. Vassio, D. Giordano, and port and Environment, vol. 60, pp. 119–136, 2018. M. Mellia, “Benefts of relocation on E-scooter sharing-adata- [25] C. Contardo, C. Morency, and L. M. Rousseau, “Balancing informed approach,” in Proceedings of the 2021 IEEE In- a dynamic public bike-sharing system,” Montreal: Cirrelt, ternational Intelligent Transportation Systems Conference vol. 4, 2012. (ITSC), pp. 3170–3175, Indianapolis, IN, USA, September [26] R. Regue and W. Recker, “Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing prob- [41] S. Carrese, F. D’Andreagiovanni, T. Giacchetti, A. Nardin, and lem,” Transportation Research Part E: Logistics and Trans- L. Zamberlan, “A beautiful feet: optimal repositioning in e- portation Review, vol. 72, pp. 192–209, 2014. scooter sharing systems for urban decorum,” Transportation [27] C. Kloimullner, ¨ P. Papazek, B. Hu, and G. R. Raidl, “Balancing Research Procedia, vol. 52, pp. 581–588, 2021. bicycle sharing systems: an approach for the dynamic case,” in [42] J. Osorio, C. Lei, and Y. Ouyang, “Optimal rebalancing and Proceedings of the European conference on evolutionary on-board charging of shared electric scooters,” Transportation computation in combinatorial optimization, pp. 73–84, Research Part B: Methodological, vol. 147, pp. 197–219, 2021. Granada, Spain, April 2014. [43] S. C. Ho and W. Y. Szeto, “Solving a static repositioning [28] J. Brinkmann, M. W. Ulmer, and D. C. Mattfeld, “Short-term problem in bike-sharing systems using iterated tabu search,” strategies for stochastic inventory routing in bike sharing Transportation Research Part E: Logistics and Transportation systems,” Transportation Research Procedia, vol. 10, pp. 364– Review, vol. 69, pp. 180–198, 2014. 373, 2015. [44] G. Erdogan, ˘ G. Laporte, and R. Wolfer Calvo, “Te static [29] D. Zhang, C. Yu, J. Desai, H. Y. K. Lau, and S. Srivathsan, “A bicycle relocation problem with demand intervals,” European time-space network fow approach to dynamic repositioning Journal of Operational Research, vol. 238, no. 2, pp. 451–457, in bicycle sharing systems,” Transportation Research Part B: Methodological, vol. 103, pp. 188–207, 2017. [45] M. Rainer-Harbach, P. Papazek, G. R. Raidl, B. Hu, [30] B. Legros, “Dynamic repositioning strategy in a bike-sharing C. Kloimullner, ¨ and C. Kloimullner, ¨ “PILOT, GRASP, and system; how to prioritize and how to rebalance a bike station,” VNS approaches for the static balancing of bicycle sharing European Journal of Operational Research, vol. 272, no. 2, systems,” Journal of Global Optimization, vol. 63, no. 3, pp. 740–753, 2019. pp. 597–629, 2015. [31] M. Du, L. Cheng, X. Li, and F. Tang, “Static rebalancing [46] J. H. Holland, Adaptation in Natural and Artifcial Systems: optimization with considering the collection of malfunc- An Introductory Analysis with Applications to Biology, Con- tioning bikes in free-foating bike sharing system,” Trans- trol, and Artifcial Intelligence, MIT press, Cambridge, MA, portation Research Part E: Logistics and Transportation USA, 1992. Review, vol. 141, Article ID 102012, 2020. [47] I. M. Oliver, D. Smith, and J. R. Holland, “Study of permu- [32] Z. Sun, Y. Li, and Y. Zuo, “Optimizing the location of virtual tation crossover operators on the traveling salesman prob- stations in free-foating bike-sharing systems with the user lem,” Genetic Algorithms and Teir Applications: Proceedings demand during morning and evening rush hours,” Journal of of the Second International Conference on Genetic Algorithms, Advanced Transportation, vol. 2019, no. 1, Article ID 4308509, Massachusetts Institute of Technology, Cambridge, MA. 11 pages, 2019. Hillsdale, NJ, 1987. [33] M. Usama, Y. Shen, and O. Zahoor, “A free-foating bike [48] L. Davis, “Applying adaptive algorithms to epistatic domains,” repositioning problem with faulty bikes,” Procedia Computer IJCAI, vol. 85, pp. 162–164, 1985. Science, vol. 151, pp. 155–162, 2019. [49] T. Starkweather, S. McDaniel, K. E. Mathias, L. D. Whitley, [34] M. Usama, O. Zahoor, Q. Bao, Z. Liu, and Y. Shen, “Dockless and C. Whitley, A Comparison of Genetic Sequencing Oper- bike-sharing rebalancing problem with simultaneous faulty ators, ICGA, Maharashtra, India, 1991. bike recycling,” in Proceedings of the 19th COTA International Conference of Transportation Professionals, pp. 4963–4974, Nanjing, China, July 2019. [35] M. Usama, O. Zahoor, Y. Shen, and Q. Bao, “Dockless bike- sharing system: solving the problem of faulty bikes with si- multaneous rebalancing operation,” Journal of Transport and Land Use, vol. 13, no. 1, pp. 491–515, 2020. [36] Y. Liu, W. Y. Szeto, and S. C. Ho, “A static free-foating bike repositioning problem with multiple heterogeneous vehicles, multiple depots, and multiple visits,” Transportation Research Part C: Emerging Technologies, vol. 92, pp. 208–242, 2018. [37] L. Caggiani, R. Camporeale, M. Ottomanelli, and W. Y. Szeto, “A modeling framework for the dynamic management of free- foating bike-sharing systems,” Transportation Research Part C: Emerging Technologies, vol. 87, pp. 159–182, 2018. [38] Y. Zhai, J. Liu, J. Du, and H. Wu, “Fleet size and rebalancing analysis of dockless bike-sharing stations based on Markov

Journal

Journal of Advanced Transportation – Hindawi Publishing Corporation

Published: Apr 6, 2023

There are no references for this article.