# Optimizing the Cleaning and Disinfection Scheme for Dockless Shared Bikes

Authors: Rong Zheng; Hongtai Yang; Lanzhen Jiang; Jinghai Huo; Xiaoqian Lu; Malik Muneeb Abid
Journal: Journal of Advanced Transportation
 (2023)

---

## Abstract

Shared bikes can help cities achieve carbon neutrality goals. Cleaning and disinfection are vital procedures of the maintenance of shared bikes, especially during the COVID-19 pandemic because shared bikes could be a transmission intermediary of viruses. This study proposes an optimization model of the cleaning and disinfection scheme of the dockless shared bikes. The disinfection is assumed to be performed at night, when the usage is lowest. By regarding the disinfection staff as traveling salesmen, the model is formulated as an extension of the Multidepot Multiple Traveling Salesman Problem (MDMTSP). The objective function is to minimize the total cost; which consists of the cost associated with the working time and per-capita cost of the disinfection staff. A heuristic algorithm combiningk-means clustering and genetic algorithm (K-GA) is adopted to find the lower bound solution. Then, the K-GA-adjustment algorithm has been adopted to find the solutions that satisfy the constraints. To reduce the computing time needed, an approximate function for the lower bound of the optimal number of disinfection staff is obtained by constructing a Continuous Approximation (CA) model. A case study based on real location data of shared bikes in Chengdu, China, is performed to show how the maintenance department could adopt the optimization framework to design an efficient scheme to clean and disinfect the shared bikes.


---

## Body

## 1. Introduction

In recent years, with the increase in motor vehicle ownership, transportation has become a major source of carbon emissions. To achieve the goal of carbon neutrality, it is particularly important to reduce carbon dioxide emissions from the transportation field. There are many low-carbon transportation options for cities, such as ride-sourcing [1, 2], e-scooter sharing, and bike sharing. As a typical low-carbon travel mode, bike sharing has been adopted by cities all over the world. However, there are various challenges in the operation and maintenance of shared bikes. Without proper maintenance, a large number of shared bikes could be scrapped and become “zombie bikes” [3]. Cleaning and disinfection are essential procedures of the daily maintenance of shared bikes [4]. Studies have shown that bike disinfection can increase citizens’ willingness to use shared bikes [5]. This can reduce the usage of other transportation modes, especially the ones with high carbon dioxide emission such as private cars and taxis, and thus reduce the emissions [6].With the outbreak of the COVID-19 pandemic, it becomes more urgent to clean and disinfect shared bikes on a regular basis. On the one hand, shared bikes have become an alternative to public transportation because travellers try to avoid contact with other people due to fear of disease transmission [7]. On the other hand, bikes could be one of the transmission methods of the virus [8], particularly via the handlebars and seats [9]. Therefore, timely cleaning and disinfecting of bikes is important to prevent the transmission of disease and to increase the attractiveness of shared bikes.Many countries have developed standards for the cleaning and disinfection of shared bikes. For example, China’s first group standards on bike sharing disinfection, “Internet Rental Bike Hygiene Guarantee Operation Specification,” was released in March 2020. The standards require that when emergencies of public health happen, the handlebars, baskets, locks, and other parts that are easily accessible to cyclists must be cleaned and disinfected not less than once a day [10].However, to our best knowledge, there has been no research performed on the cleaning and disinfection strategy of shared bikes. In practice, the operators usually do not have a well-designed plan to disinfect the bikes. Without such a plan, some bikes may be left out of disinfection while other bikes may be disinfected many times. The goal of this study is to develop a model to optimize the scheme to disinfect the shared bikes. Since dockless bike sharing is much more widely used than the docked bikes sharing and its bike parking locations are unconstrained, the disinfection of dockless shared bikes is more important and complicated than that of the docked counterpart. Thus, we focus on the disinfection of the dockless shared bikes in this study.According to the standards of cleaning and disinfection, the staff needs to clean all shared bikes through measures such as spraying disinfectants [11]. Each of the disinfection staff is assumed to go through all the bikes he or she is responsible for. Thus, this problem is similar to the Multidepot Multiple Traveling Salesman Problem (MDMTSP). Based on the setup of the MDMTSP, this research assumes that the number of disinfection staff members is equal to the number of depots. The optimization objective is to minimize the total cost, which consists of the cost related to the working time of the staff and a per-capita cost of each staff [12].Because it is very time consuming to obtain the solution to this problem, we divide the problem into two subproblems. The first one is to determine lower bound of the number of disinfection staff needed by constructing a CA model. The second one is to obtain the specific route for each disinfection staff by employing a hybrid algorithm.The contributions of this study are as follows:(i)
This study proposes a routing-based model to describe the disinfection process of shared bikes(ii)
We extend the MDMTSP by setting the number of depots equal to the number of traveling salesmen and considering not only the cost associated with the working time of traveling salesmen but also the fixed cost of hiring each salesman(iii)
The disinfection problem of shared bikes is represented by the Continuous Approximation (CA) model, and the closed-form lower bound solution for the number of disinfection staff is obtained. By doing so, the time needed to obtain the final disinfection scheme can be greatly reduced(iv)
We adopt the K-GA-adjustment algorithm to find the specific disinfection plan for shared bikes and adjust the solution to satisfy the overloading constraintThe structure of this study is as follows. The next section reviews papers related to the operation and routing optimization of shared bikes. The third section introduces the specific cleaning and disinfection process of shared bikes and the model framework. In the fourth section, algorithms and experiment works are described. A case study of Chengdu is presented, and the results are analysed in the fifth section. The last section summarizes the conclusions and recommendations for future works.


## 2. Literature Review

Since the disinfection of shared bikes is one part of the maintenance operation, we summarize the papers related to the maintenance operation of shared bikes. Since the disinfection operation problem is close to MDMTSP, the studies related to them are also reviewed.


### 2.1. Studies Related to the Maintenance Operation of Shared Bikes

The research on the maintenance operation of shared bikes has been extensively studied and is mainly divided into two aspects: rebalancing and repair.Rebalancing refers to the process of redistributing shared bikes to meet the travel demand of cyclists. The rebalancing problem is mainly divided into the static bike rebalancing problem (SBRP) and dynamic bike rebalancing problem (DBRP). In the SBRP, shared bikes are usually redistributed when cyclists’ demand is low (e.g., during nighttime), while in the DBRP, share bikes are redistributed throughout the day. Another difference is that DBRP considers the temporal variation of the demand throughout the day and adopts different rebalancing strategies based on usage forecasting [13, 14]. Rebalancing problems are variants of the classical vehicle routing problem (VRP) and are NP-hard problems [15]. Since there are no exact algorithms for large-scale rebalancing problems [16], researchers usually adopt heuristic algorithms [17–19]. Several studies adopt the cluster-based algorithm to solve the city-scale rebalancing problem. Lv et al. [15] designed a clustering strategy to decompose the original problem into TSP and multidepot VRP and used the adaptive variable neighborhood search algorithm for routing optimization. Lv et al. [20] proposed a fuzzy clustering strategy considering distance and inventory factors. Although it is difficult for researchers to obtain the optimal solution for the problem using cluster-based algorithms, researchers can efficiently find a near-optimal solution. This study also adopts this cluster-based method to search for a solution for the city-scale shared bike disinfection problem.Regarding bike repair, some scholars have constructed models to address the problem of how to collect and deliver damaged bikes to the warehouse with the lowest cost. Collecting and delivering damaged bikes is usually combined with the rebalancing process and considered in one optimization model [21–25].


### 2.2. Studies Related to MDMTSP

This study formulated the cleaning and disinfection model based on the structure of MDMTSP, which is a variant of TSP. TSP and its variants have been widely studied by researchers in the field of operation research and transportation. The Multiple Traveling Salesman Problem (MTSP) is an extension of the TSP and is equivalent to the VRP problem without capacity constraints [26]. The recent studies of MTSP are reviewed by Bektas [26] and Cheikhrouhou and Khoufi [27]. MDMTSP is a branch of MTSP. It was first proposed by Kara and Bektas [28] and has been applied in many areas. For example, Gao et al. [29] formulated the unmanned aerial vehicle scheduling problem as a MDMTSP and designed the grouping ant colony optimization algorithm to solve it. Chen et al. [30] formulated the multirobot systems as a MDMTSP and used an ant colony optimization-based memetic algorithm to solve it. These researches mainly adopted heuristic algorithms to solve these problems, and the problems are usually of small scale. When dealing with large-scale problems that are usually met in the real world, even these heuristic algorithms could not find a satisfactory solution within reasonable time. Thus, the CA methods have been adopted by researchers to deal with these problems and to obtain an empirical solution that can be easily used to deal with related problems.The routing optimization problem is usually NP-hard; it is difficult to develop an algorithm to obtain the optimal solution for large-scale problems. Thus, many studies use CA models to obtain a near-optimal solution for the routing problem. Daganzo [31] provided an comprehensive view of CA functions of TSP and VRP. Garn [32] used a machine learning approach to derive a CA model for the balanced-dynamic MTSP. Several scholars adopted the CA to solve the large-scale routing problem, such as disaster relief [33], school bus routing [34], and drone routing [35]. Interested readers could refer to Langevin et al. [36] and Ansari et al. [37] for review of studies on CA models in the field of routing optimization.In summary, the previous studies on the operation of shared bikes mainly focused on rebalancing and repair. Shui and Szeto [38] have performed a comprehensive review of these studies. However, to our best knowledge, the optimal cleaning and disinfection scheme of shared bikes has not been investigated before. As a result, this study tries to investigate this topic. Since the problem could be regarded as an extension of the MDMTSP, a NP-hard problem, a combination of the CA method and a heuristic algorithm has been used to solve this problem.


## 2.1. Studies Related to the Maintenance Operation of Shared Bikes

The research on the maintenance operation of shared bikes has been extensively studied and is mainly divided into two aspects: rebalancing and repair.Rebalancing refers to the process of redistributing shared bikes to meet the travel demand of cyclists. The rebalancing problem is mainly divided into the static bike rebalancing problem (SBRP) and dynamic bike rebalancing problem (DBRP). In the SBRP, shared bikes are usually redistributed when cyclists’ demand is low (e.g., during nighttime), while in the DBRP, share bikes are redistributed throughout the day. Another difference is that DBRP considers the temporal variation of the demand throughout the day and adopts different rebalancing strategies based on usage forecasting [13, 14]. Rebalancing problems are variants of the classical vehicle routing problem (VRP) and are NP-hard problems [15]. Since there are no exact algorithms for large-scale rebalancing problems [16], researchers usually adopt heuristic algorithms [17–19]. Several studies adopt the cluster-based algorithm to solve the city-scale rebalancing problem. Lv et al. [15] designed a clustering strategy to decompose the original problem into TSP and multidepot VRP and used the adaptive variable neighborhood search algorithm for routing optimization. Lv et al. [20] proposed a fuzzy clustering strategy considering distance and inventory factors. Although it is difficult for researchers to obtain the optimal solution for the problem using cluster-based algorithms, researchers can efficiently find a near-optimal solution. This study also adopts this cluster-based method to search for a solution for the city-scale shared bike disinfection problem.Regarding bike repair, some scholars have constructed models to address the problem of how to collect and deliver damaged bikes to the warehouse with the lowest cost. Collecting and delivering damaged bikes is usually combined with the rebalancing process and considered in one optimization model [21–25].


## 2.2. Studies Related to MDMTSP

This study formulated the cleaning and disinfection model based on the structure of MDMTSP, which is a variant of TSP. TSP and its variants have been widely studied by researchers in the field of operation research and transportation. The Multiple Traveling Salesman Problem (MTSP) is an extension of the TSP and is equivalent to the VRP problem without capacity constraints [26]. The recent studies of MTSP are reviewed by Bektas [26] and Cheikhrouhou and Khoufi [27]. MDMTSP is a branch of MTSP. It was first proposed by Kara and Bektas [28] and has been applied in many areas. For example, Gao et al. [29] formulated the unmanned aerial vehicle scheduling problem as a MDMTSP and designed the grouping ant colony optimization algorithm to solve it. Chen et al. [30] formulated the multirobot systems as a MDMTSP and used an ant colony optimization-based memetic algorithm to solve it. These researches mainly adopted heuristic algorithms to solve these problems, and the problems are usually of small scale. When dealing with large-scale problems that are usually met in the real world, even these heuristic algorithms could not find a satisfactory solution within reasonable time. Thus, the CA methods have been adopted by researchers to deal with these problems and to obtain an empirical solution that can be easily used to deal with related problems.The routing optimization problem is usually NP-hard; it is difficult to develop an algorithm to obtain the optimal solution for large-scale problems. Thus, many studies use CA models to obtain a near-optimal solution for the routing problem. Daganzo [31] provided an comprehensive view of CA functions of TSP and VRP. Garn [32] used a machine learning approach to derive a CA model for the balanced-dynamic MTSP. Several scholars adopted the CA to solve the large-scale routing problem, such as disaster relief [33], school bus routing [34], and drone routing [35]. Interested readers could refer to Langevin et al. [36] and Ansari et al. [37] for review of studies on CA models in the field of routing optimization.In summary, the previous studies on the operation of shared bikes mainly focused on rebalancing and repair. Shui and Szeto [38] have performed a comprehensive review of these studies. However, to our best knowledge, the optimal cleaning and disinfection scheme of shared bikes has not been investigated before. As a result, this study tries to investigate this topic. Since the problem could be regarded as an extension of the MDMTSP, a NP-hard problem, a combination of the CA method and a heuristic algorithm has been used to solve this problem.


## 3. Problem Description and Model

This section describes the bike cleaning and disinfection process and assumptions of the model.


### 3.1. Cleaning and Disinfection Process

Cleaning and disinfection are performed during the night. The disinfection staff need to go to the location of bikes that are designated by the platform and disinfect this bike and other bikes perched in a small area around that location. The bell on the lock can help disinfection staff differentiate the responsible bikes.Disinfection staff is assumed to start from one bike, visit the locations of the bikes that need to be disinfected one by one, and return to the first bike. Each bike needs to be disinfected at least once. Therefore, the problem to be solved in this study could be regarded as a MDMTSP. The number of the traveling salesmen (disinfection staff) is equal to the number of depots. The starting point is one of the depots. An example is shown in Figure1. The cleaning and disinfection tasks of the entire area are assigned to m disinfection staff members.Figure 1
Disinfection strategy.


### 3.2. Model Assumptions

The assumptions of the model are listed as follows:(i)
Each staff starts from one bike and returns to the bike to form a closed loop. The returning to the starting point could be justified by that the staff usually starts from the bike that is closest to his/her home (or other locations), and after finishing the disinfection task, he/she needs to return home, which could be regarded as returning to the first bike(ii)
The locations of the bikes do not change during the disinfection process. This is close to the actual situation because the cleaning and disinfection is performed during the night(iii)
The distance between shared bikes is measured by Euclidean distance, which is a justifiable simplification of the real road network, especially in urban areas where the density of intersections is high [39–42].


### 3.3. Notations

### 3.4. Model Framework

We formulate this model on the basis of MDMTSP. The difference is that the objective function is composed of the employment cost per capita of the disinfection staff [12] and the cost related to the working time of the disinfection staff, as shown in function (1). As for the working time cost, the reason for choosing the average value is that the disinfection of bikes needs to be as fast as possible, and the average working time represents the average efficiency of disinfection work.It should be noted that the disinfectors usually disinfect all the shared bikes in one area regardless of the platforms that the shared bikes belong to. As the number of bikes that can be disinfected is positively correlated with the working time of a disinfector and that the time spent on the way to the next bike location should also be counted as working time, we regard it as reasonable to calculate the employment cost of the disinfectors based on a basic salary and the working time.Since each bike needs to be disinfected, the cost related to the consumption of disinfection supplies and total cleaning and disinfecting time is fixed. Therefore, this cost does not need to be considered in the objective function. Decision variables includem and xijk. The explanation of each variable in the model is shown in Table 1.
(1)minz=p1m+p2mv∑k∈K∑i∈Nk∑j≠i,j∈Nkcijxijk.Table 1
Notation and base values.
SymbolNotation declarationUnitsBase valueDecision variablesmThe number of disinfection staff——xijkWhether the route fromi toj is chosen by the staff member k (0: no, 1: yes)——ParameterscijTravel distance between pointsi and jkm—iIndex of shared bikes——jIndex of shared bikes——kIndex of disinfection staff——nThe number of shared bikes that need to be disinfected——p1Cost coefficient for hiring disinfection staff$/member/day3p2Cost coefficient related to working time$/h6QkSubset ofNk, the auxiliary variable for eliminating the subtour——tlAllowed maximum working timeh8txAverage time for cleaning and disinfecting of each bike and its surrounding bikesh0.01vTraveling speed of disinfection staff memberkm/h3zTotal cost$/day—KThe set of disinfection staff:K≔1,2,⋯,m——NThe set of shared bikes:N≔1,2,⋯,n——NkThe set of bikes visited by the staff memberk——Subject to(2)Nk≥2∀k∈K,(3)∑i∈Nkxijk=1∀k∈K,∀j∈Nk,i≠j,(4)∑j∈Nkxijk=1∀k∈K,∀i∈Nk,i≠j,(5)⋃k=1mNk=N,⋂k=1mNk=∅,(6)∑i∈Qk∑j≠i,j∈Qkxijk≤Qk−1∀k∈K,∀Qk⊂Nk,2≤Qk≤Nk−1,(7)xijk∈0,1∀i,j∈Nk,∀k∈K,(8)∑iϵNk∑j≠i,jϵNkcijxijkv+tx∑iϵNk∑j≠i,jϵNkxijk≤tl∀k∈K.Constraint (2) indicates that each disinfection staff member is responsible for at least 2 shared bikes, which ensures that the path can form a loop. Constraints (3) and (4) indicate that each bike needs to be visited once, and there are two edges connecting to each point. Constraint (5) shows that there is no intersection between the sets of shared bikes disinfected by different staff members and that all the shared bikes need to be cleaned. Based on Dantzig et al. [43], constraint (6) is used to eliminate the subtour. In function (7),xijk equals 1 if the staff member k goes from point i to point j, and 0 otherwise. Constraint (8) ensures that disinfection staff does not work overtime: the first term is the travel time of each staff and the second term is the bike cleaning and disinfecting time of each staff.


## 3.1. Cleaning and Disinfection Process

Cleaning and disinfection are performed during the night. The disinfection staff need to go to the location of bikes that are designated by the platform and disinfect this bike and other bikes perched in a small area around that location. The bell on the lock can help disinfection staff differentiate the responsible bikes.Disinfection staff is assumed to start from one bike, visit the locations of the bikes that need to be disinfected one by one, and return to the first bike. Each bike needs to be disinfected at least once. Therefore, the problem to be solved in this study could be regarded as a MDMTSP. The number of the traveling salesmen (disinfection staff) is equal to the number of depots. The starting point is one of the depots. An example is shown in Figure1. The cleaning and disinfection tasks of the entire area are assigned to m disinfection staff members.Figure 1
Disinfection strategy.


## 3.2. Model Assumptions

The assumptions of the model are listed as follows:(i)
Each staff starts from one bike and returns to the bike to form a closed loop. The returning to the starting point could be justified by that the staff usually starts from the bike that is closest to his/her home (or other locations), and after finishing the disinfection task, he/she needs to return home, which could be regarded as returning to the first bike(ii)
The locations of the bikes do not change during the disinfection process. This is close to the actual situation because the cleaning and disinfection is performed during the night(iii)
The distance between shared bikes is measured by Euclidean distance, which is a justifiable simplification of the real road network, especially in urban areas where the density of intersections is high [39–42].


## 3.3. Notations

## 3.4. Model Framework

We formulate this model on the basis of MDMTSP. The difference is that the objective function is composed of the employment cost per capita of the disinfection staff [12] and the cost related to the working time of the disinfection staff, as shown in function (1). As for the working time cost, the reason for choosing the average value is that the disinfection of bikes needs to be as fast as possible, and the average working time represents the average efficiency of disinfection work.It should be noted that the disinfectors usually disinfect all the shared bikes in one area regardless of the platforms that the shared bikes belong to. As the number of bikes that can be disinfected is positively correlated with the working time of a disinfector and that the time spent on the way to the next bike location should also be counted as working time, we regard it as reasonable to calculate the employment cost of the disinfectors based on a basic salary and the working time.Since each bike needs to be disinfected, the cost related to the consumption of disinfection supplies and total cleaning and disinfecting time is fixed. Therefore, this cost does not need to be considered in the objective function. Decision variables includem and xijk. The explanation of each variable in the model is shown in Table 1.
(1)minz=p1m+p2mv∑k∈K∑i∈Nk∑j≠i,j∈Nkcijxijk.Table 1
Notation and base values.
SymbolNotation declarationUnitsBase valueDecision variablesmThe number of disinfection staff——xijkWhether the route fromi toj is chosen by the staff member k (0: no, 1: yes)——ParameterscijTravel distance between pointsi and jkm—iIndex of shared bikes——jIndex of shared bikes——kIndex of disinfection staff——nThe number of shared bikes that need to be disinfected——p1Cost coefficient for hiring disinfection staff$/member/day3p2Cost coefficient related to working time$/h6QkSubset ofNk, the auxiliary variable for eliminating the subtour——tlAllowed maximum working timeh8txAverage time for cleaning and disinfecting of each bike and its surrounding bikesh0.01vTraveling speed of disinfection staff memberkm/h3zTotal cost$/day—KThe set of disinfection staff:K≔1,2,⋯,m——NThe set of shared bikes:N≔1,2,⋯,n——NkThe set of bikes visited by the staff memberk——Subject to(2)Nk≥2∀k∈K,(3)∑i∈Nkxijk=1∀k∈K,∀j∈Nk,i≠j,(4)∑j∈Nkxijk=1∀k∈K,∀i∈Nk,i≠j,(5)⋃k=1mNk=N,⋂k=1mNk=∅,(6)∑i∈Qk∑j≠i,j∈Qkxijk≤Qk−1∀k∈K,∀Qk⊂Nk,2≤Qk≤Nk−1,(7)xijk∈0,1∀i,j∈Nk,∀k∈K,(8)∑iϵNk∑j≠i,jϵNkcijxijkv+tx∑iϵNk∑j≠i,jϵNkxijk≤tl∀k∈K.Constraint (2) indicates that each disinfection staff member is responsible for at least 2 shared bikes, which ensures that the path can form a loop. Constraints (3) and (4) indicate that each bike needs to be visited once, and there are two edges connecting to each point. Constraint (5) shows that there is no intersection between the sets of shared bikes disinfected by different staff members and that all the shared bikes need to be cleaned. Based on Dantzig et al. [43], constraint (6) is used to eliminate the subtour. In function (7),xijk equals 1 if the staff member k goes from point i to point j, and 0 otherwise. Constraint (8) ensures that disinfection staff does not work overtime: the first term is the travel time of each staff and the second term is the bike cleaning and disinfecting time of each staff.


## 4. Approximate Function and Heuristic Algorithm

Since the number of shared bikes that need to be cleaned and disinfected in one city is very large, it is challenging to design an algorithm to solve the large-scale NP-hard problem and obtain the global optimal solution within reasonable time. Even the classical heuristic algorithm needs much computing time to generate a satisfactory solution. Hence, we propose a CA method to find a lower bound solution of the number of disinfection staff relaxing the overtime working constraint. In contrast, if we use the one-dimensional search algorithm [44] to search for the solution of the number of disinfection staff, the total computation time equals the number of searches times the computation time of the CA method. The CA method can derive an approximate function that can directly calculate the lower bound solution of the number of disinfection staff. Based on the results of CA, we design a heuristic algorithm to find the near-optimal solution. The solution includes the number of disinfection staff needed and their travel route for bike disinfection.We first introduce the CA method. Previous studies have used the CA method to obtain the functions to express the average length of the shortest path of TSPkTSPnA [45, 46] and VRP 2rv/Vn+kVRPnA [31]. The design of the CA model is as follows: n customers are randomly distributed in a region A. Each customer has a random quantity of demand with the expected value of v. Each vehicle can serve V unit demand. r is the distance between the depot and the center of the area A. kTSP and kVRP are the constants. Since the average length of the shortest path of the MDMTSP has not been studied, based on previous studies, we believe that the average length can also be approximated by a function via employing the CA method. By setting πx,m=∑kϵK∑iϵNk∑j≠i,jϵNkcijxijk, function (1) can be converted to minp1m+p2πx,m/mv. If there is a function to express the average length of the shortest path of the MDMSTP, the term πx,m could be replaced by that function. To find the lower bound solution of m, we relax the constraint (8) into the constraint (9) to ensure that the average working time of staff does not exceed the maximum.
(9)∑kϵK∑iϵNk∑j≠i,jϵNkcijxijkmv+txnm≤tl.Then, the problem can be converted to a simpler optimization problem with one decision variablem.In order to obtain the function, which is usually a regression model, according to the CA method, we need to develop a series of problems with different settings and use an algorithm to solve those problems. The data of the solution and the settings of the problems would be used to train the regression model.We first assume thatm is a fixed parameter and πx,m is converted toπx, which can be regarded as a MDMTSP. Many researchers have adopted the heuristic algorithms to solve MDMTSP [29, 30]. This research adopts the Genetic Algorithm (GA) which is also one of the excellent heuristic algorithms to solve the MDMTSP by firstly assigning all points (bikes) to the disinfection staff member randomly and performs crossover and mutation to find the solution [47, 48]. On the other hand, K-GA is a combination of the K-means algorithm and GA, which is designed to reduce the computation through clustering so as to obtain a better feasible solution within shorter time. An example of the clustering of the bikes is shown in Figure 2.Figure 2
Clusters of shared bikes.We have carried out experiments that randomly generate a thousand points in a square area of 400 km2. Both GA and K-GA are used to solve the problem. MATLAB 2019a software is used for coding. The operating parameters of the computer system are Intel(R) Core (TM) i7-4720HQ CPU@2.60 GHz and 16 G operating memory. The initial parameters of GA are as follows: the population size is 80 and the number of iterations is 100 times the number of shared bikes that need to be disinfected.The solutions obtained by GA and K-GA are shown in Figure3. As can be seen, when the number of disinfection staff increases, the shortest path obtained by the GA becomes longer while the shortest path obtained by K-GA fluctuates around 520 km. This indicates the solution obtained by K-GA is better than that by GA. Figure 4 compares the computing time of the two algorithms. For the GA, as the number of disinfection staff increases, the computing time gradually increases. But for the K-GA, the computing time decreases. This is because when solving the problem, the time-consuming part is the search for the shortest path. As the number of staff increases, there are more clusters and probably less points in each cluster, which reduces the time needed to search for the shortest path. In summary, the K-GA could generate a better solution within shorter time than the GA. Hence, the K-GA is used to generate the shortest path in the following work.Figure 3
Relationship between the number of staff and the length of the shortest path.Figure 4
Relationship between the number of staff and the computing time.Following the methodology of previous studies [45, 46, 49], we perform the following steps to construct the CA model and obtain the approximate function: design different experiment scenarios, generate random problems under each experiment scenario, solve the problem to obtain the solution, and train the approximate function based on the settings of the experiment and the solution.In this study, the experiment scenarios are designed by combining different service areas, number of bikes, and number of staff. The service area is assumed to be square, and the side length is set as 5, 10, 15, and 20. The number of bikes that need to be cleaned is set as 200, 400, 600, 800, and 1000.The number of disinfection staff is set as ranging from 1 to 30 with an interval of 1. Combining four service areas, five levels of bike numbers, and 30 levels of staff numbers, there are 600 experiment scenarios generated. Assuming bikes are uniformly distributed, the locations of bikes are randomly generated for 50 times for each experiment scenario. The shortest path for each experiment is obtained using the K-GA. The average length of the shortest paths of each experiment scenario is calculated. The results are shown in Figure5.Figure 5
Experiment resultsAs can be seen from Figure5, m has little effect on πx,m. Thus, the approximate function of the average length of the shortest path does not need to include m. This study adopts the widely used function form for the expected length of the shortest path of TSP, which is μnA, proposed by Beardwood et al. [46]. When the side length and the number of bikes are fixed, different numbers of disinfection staff lead to little change of the shortest path. Therefore, we select all the samples to fit the model. Results show that the value of μ is 0.826, the R2 reaches 0.997, RMSE equals to 4.931, and the model is significant. Hence, πx,m can be approximated by 0.826nA.Afterπx,m is represented by the CA function, the decision variable of function (1) is only m, and the function is obviously a unimodal convex function. The large-scale search for the optimal value of m∗ can be avoided. By taking the derivative, the near-minimum lower bound point can be approximated as m¯=p2π/p1v. Since the value may not be an integer, calculation and comparison need to be performed to determine whether the number should be rounded up or down, which could be represented by ∙. When constraint (9) can be satisfied, the near-minimum lower bound point can be regarded as the global minimum lower bound point. In this case, constraint (9) can be approximately converted to πp1/p2v+txnp1v/p2π≤tl. Otherwise, the lower bound solution m¯ can be obtained by taking the equal sign in constraint (9), that is, m¯=π/vtl+txn/tl; ∙ means rounded up. In summary,
(10)m¯=p2πp1v,πp1p2v+txnp1vp2π≤tl,πvtl+txntl,πp1p2v+txnp1vp2π>tl.By substitutingπ by the CA function, we can obtain the closed-form lower bound solution:
(11)m¯=p2μnAp1v,μp1nAp2v+txnp1vμp2nA≤tl,μnAvtl+txntl,μp1nAp2v+txnp1vμp2nA>tl,(12)z¯≈2p1p2μnAv,μp1nAp2v+txnp1vμp2nA≤tl,p1μnAvtl+p1txntl+tlp2μnAμnA+vtxn,μp1nAp2v+txnp1vμp2nA>tl.Therefore, in practice, the lower bound solutionm¯ can be determined through function (10). The K-GA algorithm could be used to obtain the cluster of bikes that each staff member is responsible for and the specific working time for cleaning and disinfection. For staff whose working time exceeds the working time constraints, we design the K-GA-adjustment algorithm to allocate some of the bikes they are responsible for to other employees who are not overloaded. At the same time, this process can enhance the balance of the work load of each staff. The specific K-GA-adjustment algorithm is shown in Algorithm 1.Algorithm 1: K-GA-adjustment algorithm.
(1)Input: lower bound solution m¯ by function (11), the initial value of parameters in Table 1, and the position of shared bikes that needed to be disinfected.(2) Employ thek-means algorithm to determine the clusters and their center position under the condition of m¯staff.(3)First loop: Line3−7 (calculate the adjustment volume.)(4)for each k∈K(5)  Calculate the travel route length and the working time by GA.(6)  Compute the adjustment volume of each staff byAdjustmentk=∑iϵNk∑j≠i,jϵNkxijk−tl∑iϵNk∑j≠i,jϵNkxijk/∑iϵNk∑j≠i,jϵNkcijxijk/v+tx∑iϵNk∑j≠i,jϵNkxijk∀k∈K.(7)end for(8)if sumAdjustmentk>0(9)m¯=m¯+1 and goto line 2(10)end if(11)Second loop: Line11−33 (allocate some bikes from overloaded staff to staff not overloaded.)(12)while max (Adjustmentk) >0 do(13)for each k∈K and Adjustmentk≥0(14)  Calculate the distance from each point to the center of thek-th cluster and sort it in descending order.(15)  Take the topAdjustmentk in the distance order.(16)  Seti=1 and kk=Adjustmentk.(17)whilei<Adjustmentkdo(18)for each j∈K and Adjustmentj<0(19)    Compute the distance fromj-th center to i-th point in k-th cluster and find the minimum.(20)end for(21)if distance from j-th center to i-th point < distance from j-th center to k-th center(22)kk=kk+1.(23)    Replace thei-th point with the kk-th point in the k-th cluster.(24)else(25)i=i+1.(26)Adjustmentj=Adjustmentj+1.(27)    Transfer pointi from cluster k to cluster j.(28)end if(29)end while(30)  Update the position of the center of each cluster.(31)end for(32) Recompute the adjustment volume of each staff.(33)end while(34)Output: the travel route, travel distance, and working time of each staff.


## 5. Case Study

In this case study, we use the bike sharing trip data of one of the most popular bike sharing companies in Chengdu to demonstrate the application of our proposed method. The trips within the First Ring Road on March 1, 2018, are used to develop the static cleaning and disinfection scheme. There were 3,632 shared bikes that needed be disinfected on March 1, 2018. We collect the final positions of these shared bikes. According to China’s first shared bike disinfection group standard, they all need to be disinfected and cleaned. The area within the First Ring Road is 27.85 km2. If we do not consider the working time constraint, the first function of equation (9) could be used to calculate the number of staff, which is 13. However, in this case, the working time constraint is violated. Thus, the second function of equation (9) is used to calculate the number of staff. CA results indicate that 16 disinfection staff are required, and the total cost (objective function) is 80.39 ($/day).We apply the K-GA to solve the specific disinfection plan to get the initial solution and then apply the K-GA-adjustment algorithm to adjust each staff to avoid being overworked. The results are shown in Table2. It can be seen that the K-GA-adjustment algorithm not only avoids overwork but also reduces the total working time. The specific disinfection routes are shown in Figure 6. The lines of different colors represent different disinfection staff members. The details of the designated path can be shown on the staff’s mobile phone. The total cost is 83.84 ($/day), which is slightly higher than the results obtained by the approximate function, with an error of 4.11%. The reason may be that the spatial distribution of bikes does not follow the uniform distribution. The computation time for this example is equal to 1.52 hours. Without the approximate function, the commonly used method is to apply the one-dimensional search algorithm [44] to find the optimal number of disinfection staff. It takes at least three times the computing time as the CA method. This illustrates that by using the approximate function, the computing time could be largely reduced, which makes the method applicable to large-scale problems.Table 2
The solution of the case study.
Disinfection staff numberInitial solutionAdjustment solutionLength of routes (km)Working time (hour)Length of routes (km)Working time (hour)115.767.2815.897.35214.436.8914.887.04318.688.8216.967.98416.217.5716.467.76516.037.5415.587.41616.407.6417.177.95716.297.3517.527.87817.437.9816.747.70917.807.9817.487.901017.978.3016.687.791112.766.0313.046.221218.658.6916.507.741318.218.1517.407.861416.497.8416.567.861516.027.3517.447.931614.977.0215.867.401716.307.3517.287.71Total280.39129.78279.42129.46Mean16.497.6316.447.62Figure 6
The specific disinfection routes in the case study.To investigate the impact of the cost coefficient (p1 and p2) on the results, we perform the sensitivity analysis by the CA model. Figures 7 and 8 show the value of the disinfection staff and the total cost change with the p1 and p2, which range from 0.1 to 100 ($). It can be seen that if the constraint (9) is satisfied, the increase in cost coefficient for hiring disinfection staff (p1) leads to a decrease in the number of the disinfection staff. The increase in cost coefficient related to working time (p2) leads to an increase in the number of the disinfection staff. When the constraint (9) is not satisfied, the number of the disinfection staff will remain at the value of 16. Obviously, the increase of both cost coefficients p1 and p2 causes the increase in the total cost.Figure 7
Effects ofp1 and p2 on the number of disinfection staff.Figure 8
Effects ofp1 and p2 on total cost.


## 6. Conclusions

The cleaning and disinfection of shared bikes are essential parts of the operation and maintenance work. According to the cleaning standards, each bike needs to be cleaned at least once a day. During the COVID-19 pandemic, it has become more important to clean and disinfect the shared bikes as they could be a way to transmit the disease. Since this topic has not been explored before, in this study, we investigate this topic by proposing a method to design the optimal disinfection scheme. As the problem could be regarded as a variant of the MDMTSP, this study proposes an optimization model to describe the disinfection process of shared bikes and an effective method to obtain the disinfection scheme, which allows the operation and maintenance staff to disinfect all the shared bikes as required. The objective function is composed of the employment cost per capita of the disinfection staff and the cost related to the working time of the disinfection staff. The decision variables are the number of disinfection staff and their route. As the problem solving process requires a large amount of computation, a CA model is designed to obtain an approximate function for the lower bound of the optimal number of staff. Based on determining the lower bound of the optimal number of disinfection staff by using the approximate function, the K-GA could be applied to obtain the initial solution, and the K-GA-adjustment algorithm can help to get the specific disinfection scheme. The process could largely reduce the computing time. A case study based on the real world bike location data of Chengdu has been presented. Results show that the proposed method could be used for large-scale disinfection problems. The results indicate that the CA method can obtain the near-optimal number of staff with relatively short computing time. The proposed method can also be used in other scenarios, such as the cleaning and disinfection of shared e-scooters [50, 51], shared cars, shared power banks, and shared basketballs.This research still has some limitations that may be addressed in the future. Firstly, due to the assumption of uniform distribution, satisfactory results can be obtained by using the K-GA-adjustment algorithm. If the distribution of shared bikes is not uniform, the approximate function may not accurately estimate the lower bound of the number of disinfection staff, and it may take a longer time for the K-GA-adjustment algorithm to find a solution. Therefore, the disinfection scheme under different bike-sharing distributions can be explored in the future. Secondly, although this study chooses the period with the lowest ridership for disinfection, a small amount of bike sharing usage may still interfere with the disinfection process. Thirdly, the focus of this study is to propose a problem solving framework. When the method is applied to the real world problem, it is necessary to consider the actual road network, heuristic algorithms that are more efficient than GA, and high-level programming languages such as Java and C++.



---

*Source: 5702188-2023-03-23.xml*