# Hierarchical Vehicle Scheduling Research on Tide Bicycle-Sharing Traffic of Autonomous Transportation Systems

Authors: Mai Hao; Ming Cai; Minghui Fang; Shuxin Jin
Journal: Journal of Advanced Transportation
 (2023)

---

## Abstract

To facilitate the intelligent and automated provision of mobility services by autonomous transportation systems, bike-sharing can be a supplement to public transport for addressing their point-to-point issue, namely, “last mile” service. However, according to the different nature of land use, the uneven spatio-temporal distribution of travel demand can directly lead to difficult access to bikes with high travel costs for users and operating costs for operators. Based on this, this paper analyzes the user behavior patterns within different areas by using GeoHash encoding and proposes a hierarchical autonomous vehicle scheduling model based on tide bicycle-sharing traffic, namely,HATB. It minimizes operating costs and maximizes user satisfaction to dynamically optimize scheduling routes and required vehicles within each layered zone. As for extracting historical orders of Mobike in Beijing, an example analysis through the genetic algorithm of HATB is conducted to support effective and efficient scheduling. Compared to existing scheduling methods, HATB has faster convergence and lower time complexity, which improves bike turnaround efficiency and practical application ability, thus making it more convenient for the public to travel during peak hours.


---

## Body

## 1. Introduction

Nowadays, as the modern transportation systems (TSs) develop, problems among mobility services (MSs), e.g., congestion, route adjustment, user dispersion, and peak-time conflicts have become commonplace [1–3] in terms of the adjustment of urban planning and the year-on-year increase in car ownership. Since the MS are fundamental in propelling current intelligent TS (ITS) evolving towards autonomous TS (ATS), they are also being renovated to assist the public on a daily basis and explore the advancement of ATS. Some theoretical development has revealed that the creation of shared transport, called bicycle-sharing, has effectively alleviated the “last mile” service (LMS), which is the most predominant pain point in the current MS [4] in terms of the most immediate interaction with users, and some emerging companies, e.g., Mobike have also taken this trend to a new level. However, bikes must be parked in GPS-identified areas to address ill-posed problems in the case of illegal parking, vandalism, or theft. Since then, to avoid constant billing, users never consider the capacity of the parking area, resulting in an uneven spatial distribution of bikes, namely, some areas suffer a severe accumulation of bikes while others are “one bike is hard to find” [5]. Therefore, scientific and reasonable scheduling strategies are required to overcome the imbalance between the supply and demand of bikes and improve resource utilization.Rebalancing and optimizing bicycle-sharing distribution constitutes the vehicle routing problem (VRP), and most current research is based on this theory. For instance, Caggiani et al. [6] proposed a decision support system for the reallocation problem by forecasting the demand for spatio-temporal bikes. Similar research can, accordingly, be divided into static and dynamic scheduling to optimize VRP models with different objectives. Specifically, in static scheduling, Kadri et al. [7] and Dell’Amico et al. [8] developed optimization models for user satisfaction and operating cost, respectively. Yan et al. [9] investigated the deterministic and stochastic demand for bicycle-sharing in dynamic scheduling. In general, these methods assume that the overall supply and demand within a scheduling station are in equilibrium without supporting the mobility of bikes between zones. Moreover, limited open literature has reported that current research focuses too much on mathematical modeling, neglecting the analysis of actual demands. Therefore, these methods have encountered three challenges in practice, namely, slow convergence, high time complexity, and problematic application, from perspectives of fulfilling the actual demands in real-time and adjusting scheduling as needed.As current diversified mobility demands tend to be managed and fulfilled by more intelligent and automated systems with fewer human intervention [10], it is an urgent need to collaborate corresponding functions to renovate the conventional MS of ITS in the context of ATS [11], i.e., update the ability to sense user demands and rearrange system supplies [12, 13]. Hence, to promote the MS provided by ATS, this paper proposes a hierarchical autonomous vehicle scheduling model based on tide bicycle-sharing traffic, namely, HATB. This model uses GeoHash coding to divide the scheduling into three layers, i.e., top, middle, and bottom, corresponding to the scheduling terminus, area, and point. Based on the genetic algorithm (GA), the model can achieve hierarchical and dynamic scheduling of vehicles and routes to maximize user satisfaction, while minimizing operating costs.Furthermore, in contrast to current studies on scheduling bikes in ITS, theHATB makes three main contributions to optimizing convergence speed, time complexity, and application difficulties of actual scheduling. The scheduling results based on actual orders ultimately demonstrate HATB can provide a rational reference for LMS in ATS and guide the development of bicycle-sharing regulation and operation.The overall structure of this paper is divided into five sections. Section2 introduces related solutions and emerging challenges. The methodology relevant to HATB is described in Section 3. Section 4 elaborates on the scheduling results and superiority of the model. Finally, Section 5 summarizes this study and sketches future research directions.


### 1.1. Related Works

In the transport domain, LMS refers to the direct interaction between the end of public transport and users, which often suffers from scattered users, peak-time conflicts, and uneven distribution. As an effective way to cope with the LMS problems, bicycle-sharing has become a non-negligible component of urban transport. For example, Cheng et al. [14] have demonstrated that bicycle-sharing increases the proportion of green transport in cities and solves the low efficiency at the end of the travel chain.In general, current research on bike-sharing mainly focuses on its development status and travel characteristics, but few on its scheduling. Researchers like Soriguera and Jiménez-Meroño [15], Gimon [16], and Lu et al. [17] concur that even while bicycle-sharing has considerable quantities, the spatio-temporal differences in user demands, no fixed parking area, and fewer available bikes may lead to a more significant overall imbalance. Therefore, it is vital to take effective scheduling strategies to rebalance and optimize the distribution of bikes, thereby addressing difficulties in management and operation. In this context, scheduling bicycle-sharing can be regarded as a heuristic algorithm-based, e.g., GA, ant colony algorithm (ACO), and vehicle routing problem (VRP) [18–20], which can be classified as static or dynamic scheduling according to different strategies and objectives.Dynamic scheduling mainly focuses on peak time and relies on user demands. For instance, a mathematical model for dynamic scheduling is created by Zhang et al. [21] based on the parking area’s actual capacity and users’ predicted arrival times. Shui and Szeto [22] partition peak time to optimize scheduling routes by regarding scheduling in each time interval as static scheduling. Chiariotti et al. [23] propose that scheduling bikes can dynamically determine the scheduling time through historical orders. In general, dynamic scheduling lessens operating costs’ impact on operators by prescheduling bikes to avoid a shortage occurs. However, based on the uncertain use of bikes, frequent scheduling with complex constraints is necessary, which may lead to higher operating costs and slower convergence, thus making it challenging to fulfill user demands in real-time.Another more common scheduling strategy is static scheduling during off-peak time. For example, Lang [24] provides a multiwarehouse model based on the Tabu search algorithm to minimize scheduling distance and improve scheduling efficiency and robustness. Bae and Moon [25] use a dual time window with customer service levels to reduce total transport and labor costs. Since static scheduling only considers the predicted demands of stations, increasing more bikes for stations to guarantee user demands means that the time complexity of the heuristic algorithm grows exponentially. Moreover, to fulfill the actual demands, the allocated bikes by these studies may exceed the station’s capacity.Besides, such above-given studies are mainly applied to typical scenarios, as presented in Figure1, where a single scheduling station serves one zone and only the routes within the scheduling zone are considered. It is often limited in actual scheduling by the service range of the station, which needs to frequently adjust the boundaries of this scheduling zone, thus leading to some research on hierarchical scheduling strategies. By defining scheduling priorities based on demand intensity, Sakakibara et al. [26] and Ni et al. [27] highlight the feasibility and reliability of hierarchical scheduling. In order to illustrate the flexibility, Zhang [28] and Ma et al. [29] set stations with similar demands in the same layer in accordance with the spatio-temporal characteristics of bikes. However, the definition of hierarchies in these methods is too subjective and not clear, making it difficult to implement in practice.Figure 1
The schema of existing scheduling (map data (part of Beijing):https://www.beijing.gov.cn).In summary, whilst a considerable body of research has been carried out on VRP, much less fits the spatial-temporal and cross-regional mobility characteristics of bicycle-sharing. In addition, it seems to be a common problem that existing studies focus more on mathematical modeling but neglect the analysis of actual demands. When scheduling according to the above-given methods, three challenges in terms of the problematic application in practice, namely, the high time complexity of models and slow convergence for algorithms, are increasingly apparent.Particularly driven by diverse and emerging technologies and demands, ITS is evolving into ATS, which illustrates that MS should be autonomously fulfilled and managed by more intelligent systems with fewer human intervention [30]. Therefore, it is an urgent need to study and improve the monolithic strategies and rationalize the actual demands to achieve hierarchical and autonomous scheduling of bicycle-sharing, thus rationally guiding the provision of the LMS by ATS.


## 1.1. Related Works

In the transport domain, LMS refers to the direct interaction between the end of public transport and users, which often suffers from scattered users, peak-time conflicts, and uneven distribution. As an effective way to cope with the LMS problems, bicycle-sharing has become a non-negligible component of urban transport. For example, Cheng et al. [14] have demonstrated that bicycle-sharing increases the proportion of green transport in cities and solves the low efficiency at the end of the travel chain.In general, current research on bike-sharing mainly focuses on its development status and travel characteristics, but few on its scheduling. Researchers like Soriguera and Jiménez-Meroño [15], Gimon [16], and Lu et al. [17] concur that even while bicycle-sharing has considerable quantities, the spatio-temporal differences in user demands, no fixed parking area, and fewer available bikes may lead to a more significant overall imbalance. Therefore, it is vital to take effective scheduling strategies to rebalance and optimize the distribution of bikes, thereby addressing difficulties in management and operation. In this context, scheduling bicycle-sharing can be regarded as a heuristic algorithm-based, e.g., GA, ant colony algorithm (ACO), and vehicle routing problem (VRP) [18–20], which can be classified as static or dynamic scheduling according to different strategies and objectives.Dynamic scheduling mainly focuses on peak time and relies on user demands. For instance, a mathematical model for dynamic scheduling is created by Zhang et al. [21] based on the parking area’s actual capacity and users’ predicted arrival times. Shui and Szeto [22] partition peak time to optimize scheduling routes by regarding scheduling in each time interval as static scheduling. Chiariotti et al. [23] propose that scheduling bikes can dynamically determine the scheduling time through historical orders. In general, dynamic scheduling lessens operating costs’ impact on operators by prescheduling bikes to avoid a shortage occurs. However, based on the uncertain use of bikes, frequent scheduling with complex constraints is necessary, which may lead to higher operating costs and slower convergence, thus making it challenging to fulfill user demands in real-time.Another more common scheduling strategy is static scheduling during off-peak time. For example, Lang [24] provides a multiwarehouse model based on the Tabu search algorithm to minimize scheduling distance and improve scheduling efficiency and robustness. Bae and Moon [25] use a dual time window with customer service levels to reduce total transport and labor costs. Since static scheduling only considers the predicted demands of stations, increasing more bikes for stations to guarantee user demands means that the time complexity of the heuristic algorithm grows exponentially. Moreover, to fulfill the actual demands, the allocated bikes by these studies may exceed the station’s capacity.Besides, such above-given studies are mainly applied to typical scenarios, as presented in Figure1, where a single scheduling station serves one zone and only the routes within the scheduling zone are considered. It is often limited in actual scheduling by the service range of the station, which needs to frequently adjust the boundaries of this scheduling zone, thus leading to some research on hierarchical scheduling strategies. By defining scheduling priorities based on demand intensity, Sakakibara et al. [26] and Ni et al. [27] highlight the feasibility and reliability of hierarchical scheduling. In order to illustrate the flexibility, Zhang [28] and Ma et al. [29] set stations with similar demands in the same layer in accordance with the spatio-temporal characteristics of bikes. However, the definition of hierarchies in these methods is too subjective and not clear, making it difficult to implement in practice.Figure 1
The schema of existing scheduling (map data (part of Beijing):https://www.beijing.gov.cn).In summary, whilst a considerable body of research has been carried out on VRP, much less fits the spatial-temporal and cross-regional mobility characteristics of bicycle-sharing. In addition, it seems to be a common problem that existing studies focus more on mathematical modeling but neglect the analysis of actual demands. When scheduling according to the above-given methods, three challenges in terms of the problematic application in practice, namely, the high time complexity of models and slow convergence for algorithms, are increasingly apparent.Particularly driven by diverse and emerging technologies and demands, ITS is evolving into ATS, which illustrates that MS should be autonomously fulfilled and managed by more intelligent systems with fewer human intervention [30]. Therefore, it is an urgent need to study and improve the monolithic strategies and rationalize the actual demands to achieve hierarchical and autonomous scheduling of bicycle-sharing, thus rationally guiding the provision of the LMS by ATS.


## 2. TheHATB Methodology

This section uses three subsections to present the framework, hypotheses, and construction of the proposedHATB.


### 2.1. Model Framework

As existing scheduling methods, in general, require frequently adjusting boundaries and increasing vehicles to alleviate the difference between bikes’ supply and demand, which may inevitably increase transport time and costs; the scheduling framework can be set up as a hierarchical scheduling structure, i.e., a top-middle-bottom hierarchy of scheduling terminus-area-point.However, since current hierarchical methods have a subjective definition of their hierarchies, geocode can ensure the objective; e.g., what3words [31] uses fixed 3m×3m squares to divide the earth, and pluscode [32] represents each latitude and longitude level by 2-bit code, whose length range in levels 1 to 3 jumps from 110km and 5.5km to 275m. These geocodes, accordingly, have good accuracy but loss flexibility; they may not meet the actual scheduling requirements.Therefore, GeoHash encoding, proposed by Morton [33], can be used to better support effective and efficient scheduling. Its maximum length of 12 bits can represent a geographic location with arbitrary precision. For example, the GeoHash strings WX4ER and WX4G2 represent two regions of Beijing (China), where each character is a certain rectangular area. Moreover, the order information (Data Sources: https://biendata.xyz/competition/mobike/) on bicycle-sharing, as extracted in Table 1, also indicates the feasibility of dividing the scheduling layer via GeoHash.Table 1
The order information of corresponding GeoHash string length.
GeoHash string length5-bit6-bit7-bitAverage orders436.99478828.2141193.689289Area width4.89 km1.22 km153 mArea height4.89 km0.61 km153 mThe coding definition, as described in Table1, illustrates that the 7-bit string matches the characteristics of actual bike stops, namely, area size, and the 5-bit string suits for vehicles to dispatch bikes in light of their loading capacity, i.e., 400 bikes. Therefore, the overall framework of the proposed hierarchical scheduling model, called HATB, can be obtained as presented in Figure 2. In general, this framework is characterized by a number of scheduling areas in each of the three layers, namely, bike stops consist of the bottom layer of scheduling, while the top and middle layers likewise have demands and capacity restrictions for bikes, and hence, the scheduling within the same layers is regional scheduling for seeking optimization.Figure 2
The framework ofHATB.


### 2.2. Model Hypotheses

Considering the complexity of actual scheduling, the proposedHATB in this paper defines the following hypotheses and the frequency of scheduling as once in the morning peak and once in the evening peak, respectively.(1)
All scheduling vehicles own the same attributes(2)
In each scheduling route, the vehicle departs from one scheduling terminus (area) and returns to this place after deploying bikes to corresponding areas (points) contained(3)
Fuel consumption and vehicle loss should be considered(4)
Each scheduling area can only be served once(5)
The actual orders determine the scheduling demand(6)
All scheduling tasks are required to be completed within the specified scheduling cycle(7)
The scheduling areas and points have sufficient space to accommodate the bikes deployed in or out during a scheduling cycle


### 2.3. Model Construction

Based on the above-given hypotheses and the actual operations of bike-sharing, considering only the operating costs will gradually lose customers, and weighing only user satisfaction runs counter to the essence of business profitability. Hence combining these two factors, this paper constructs a regional scheduling model for bikes to minimize operating costsF1 and maximize user satisfaction F2.(1)min:∂F1+μF2,s.t.∂+μ=1∂,μ>0.The parameters ∂ andμ indicate that bike-sharing operators need to adjust the weight coefficients of operating and penalty costs according to their own emphasis.


#### 2.3.1.F1: The Objective of Minimizing Operating Costs

The actual operation costs need to consider both fixed and flexible costs, as summarized in equation (2), which is determined jointly by the value of scheduling vehicles [34], the unit transport cost (i.e., vehicle loss: 1 CNY/km, fuel consumption: 1 CNY/km, and labor cost: 100 CNY/person), and the scheduling distance.(2)minF1=minFxd+Flx=min∑wW∑tT∑iIxwjtCt+∑tT∑iR∑jRxijtdijMt,(3)s.t.∑iIxwit=∑iIxwit≤1∀w∈W,t∈T,(4)∑tT∑j=1j≠iRxjit=∑tT∑j=1j≠iRxjit=1∀i,j∈I,t∈T,(5)0≤∑iR∑j=1j≠iRxijtdij≤Lt∀t∈T,(6)0≤aijt≤aijtxijt∀i,j∈R,i≠j,t∈T,(7)xijt=0or1∀i,j∈R,i≠j,t∈T,(8)aijt∈Z+∀i,j∈R,i≠j,t∈T,Equation (3) indicates that this scheduling vehicle starts and ends at the terminus; equation (4) suggests that each area can only be served once; equation (5) shows that the transport distance must not exceed the maximum scheduling distance; equation (6) points that the number of bikes loaded by the vehicle must not exceed its maximum capacity, namely, 400; equation (7) means xijt as 0-1 variable; equation (8) proves that the number of bikes deployed by the vehicle is a non-negative integer.


#### 2.3.2.F2: The Objective of Maximizing User Satisfaction

User satisfaction can be improved by adding time window constraints, as described in equation (9), which means maximizing user satisfaction can equivalently transfer into minimizing the penalty cost of scheduling timeout.(9)maxF2=min∑iIωiρiti,(10)s.t.TMwt=0∀t∈T,(11)TMj=∑tT∑iRxijtTMi+TMj+S⋅GAPi,∀j∈I,(12)TMi+TMj+S⋅GAPi−K1−xijt≤TMj,(13)FQi≤TMi≤FRi,∀i∈I.Equation (10) indicates that the vehicle departs from the terminus at time zero; equation (11) means that the time calculation for a vehicle to arrive in an area; equation (12) demonstrates that the scheduling cannot arrive in area j from area i before TMi+TMj+S⋅GAPi−K1−xijt; equation (13) represents that vehicle needs to arrive in an area within the time window.The meaning of the parameters in the above-given equationsare shown in Table2.Table 2
The meaning of parameters for formulations 1–14.
ParameterMeaningIScheduling areaTScheduling vehiclesWScheduling terminusRVehicle pools for scheduling terminus and areasatMaximum capacity of vehicletaijtLoading bikes of vehiclet from area i to area jLtMaximum operation distanceCtFixed cost per vehicleMtFlexible cost per vehicleVAverage speeddijTransport distance by vehicle from areai to area jGAPiNumber of vehicles to be deployed in/out of areaiωiImportance of areaiTMiTime for vehicle to arrive in areaiSTime cost for loading/unloading bikesTMwtTime for vehicle to depart from terminusFQi,FRiPenalty time window


## 2.1. Model Framework

As existing scheduling methods, in general, require frequently adjusting boundaries and increasing vehicles to alleviate the difference between bikes’ supply and demand, which may inevitably increase transport time and costs; the scheduling framework can be set up as a hierarchical scheduling structure, i.e., a top-middle-bottom hierarchy of scheduling terminus-area-point.However, since current hierarchical methods have a subjective definition of their hierarchies, geocode can ensure the objective; e.g., what3words [31] uses fixed 3m×3m squares to divide the earth, and pluscode [32] represents each latitude and longitude level by 2-bit code, whose length range in levels 1 to 3 jumps from 110km and 5.5km to 275m. These geocodes, accordingly, have good accuracy but loss flexibility; they may not meet the actual scheduling requirements.Therefore, GeoHash encoding, proposed by Morton [33], can be used to better support effective and efficient scheduling. Its maximum length of 12 bits can represent a geographic location with arbitrary precision. For example, the GeoHash strings WX4ER and WX4G2 represent two regions of Beijing (China), where each character is a certain rectangular area. Moreover, the order information (Data Sources: https://biendata.xyz/competition/mobike/) on bicycle-sharing, as extracted in Table 1, also indicates the feasibility of dividing the scheduling layer via GeoHash.Table 1
The order information of corresponding GeoHash string length.
GeoHash string length5-bit6-bit7-bitAverage orders436.99478828.2141193.689289Area width4.89 km1.22 km153 mArea height4.89 km0.61 km153 mThe coding definition, as described in Table1, illustrates that the 7-bit string matches the characteristics of actual bike stops, namely, area size, and the 5-bit string suits for vehicles to dispatch bikes in light of their loading capacity, i.e., 400 bikes. Therefore, the overall framework of the proposed hierarchical scheduling model, called HATB, can be obtained as presented in Figure 2. In general, this framework is characterized by a number of scheduling areas in each of the three layers, namely, bike stops consist of the bottom layer of scheduling, while the top and middle layers likewise have demands and capacity restrictions for bikes, and hence, the scheduling within the same layers is regional scheduling for seeking optimization.Figure 2
The framework ofHATB.


## 2.2. Model Hypotheses

Considering the complexity of actual scheduling, the proposedHATB in this paper defines the following hypotheses and the frequency of scheduling as once in the morning peak and once in the evening peak, respectively.(1)
All scheduling vehicles own the same attributes(2)
In each scheduling route, the vehicle departs from one scheduling terminus (area) and returns to this place after deploying bikes to corresponding areas (points) contained(3)
Fuel consumption and vehicle loss should be considered(4)
Each scheduling area can only be served once(5)
The actual orders determine the scheduling demand(6)
All scheduling tasks are required to be completed within the specified scheduling cycle(7)
The scheduling areas and points have sufficient space to accommodate the bikes deployed in or out during a scheduling cycle


## 2.3. Model Construction

Based on the above-given hypotheses and the actual operations of bike-sharing, considering only the operating costs will gradually lose customers, and weighing only user satisfaction runs counter to the essence of business profitability. Hence combining these two factors, this paper constructs a regional scheduling model for bikes to minimize operating costsF1 and maximize user satisfaction F2.(1)min:∂F1+μF2,s.t.∂+μ=1∂,μ>0.The parameters ∂ andμ indicate that bike-sharing operators need to adjust the weight coefficients of operating and penalty costs according to their own emphasis.


### 2.3.1.F1: The Objective of Minimizing Operating Costs

The actual operation costs need to consider both fixed and flexible costs, as summarized in equation (2), which is determined jointly by the value of scheduling vehicles [34], the unit transport cost (i.e., vehicle loss: 1 CNY/km, fuel consumption: 1 CNY/km, and labor cost: 100 CNY/person), and the scheduling distance.(2)minF1=minFxd+Flx=min∑wW∑tT∑iIxwjtCt+∑tT∑iR∑jRxijtdijMt,(3)s.t.∑iIxwit=∑iIxwit≤1∀w∈W,t∈T,(4)∑tT∑j=1j≠iRxjit=∑tT∑j=1j≠iRxjit=1∀i,j∈I,t∈T,(5)0≤∑iR∑j=1j≠iRxijtdij≤Lt∀t∈T,(6)0≤aijt≤aijtxijt∀i,j∈R,i≠j,t∈T,(7)xijt=0or1∀i,j∈R,i≠j,t∈T,(8)aijt∈Z+∀i,j∈R,i≠j,t∈T,Equation (3) indicates that this scheduling vehicle starts and ends at the terminus; equation (4) suggests that each area can only be served once; equation (5) shows that the transport distance must not exceed the maximum scheduling distance; equation (6) points that the number of bikes loaded by the vehicle must not exceed its maximum capacity, namely, 400; equation (7) means xijt as 0-1 variable; equation (8) proves that the number of bikes deployed by the vehicle is a non-negative integer.


### 2.3.2.F2: The Objective of Maximizing User Satisfaction

User satisfaction can be improved by adding time window constraints, as described in equation (9), which means maximizing user satisfaction can equivalently transfer into minimizing the penalty cost of scheduling timeout.(9)maxF2=min∑iIωiρiti,(10)s.t.TMwt=0∀t∈T,(11)TMj=∑tT∑iRxijtTMi+TMj+S⋅GAPi,∀j∈I,(12)TMi+TMj+S⋅GAPi−K1−xijt≤TMj,(13)FQi≤TMi≤FRi,∀i∈I.Equation (10) indicates that the vehicle departs from the terminus at time zero; equation (11) means that the time calculation for a vehicle to arrive in an area; equation (12) demonstrates that the scheduling cannot arrive in area j from area i before TMi+TMj+S⋅GAPi−K1−xijt; equation (13) represents that vehicle needs to arrive in an area within the time window.The meaning of the parameters in the above-given equationsare shown in Table2.Table 2
The meaning of parameters for formulations 1–14.
ParameterMeaningIScheduling areaTScheduling vehiclesWScheduling terminusRVehicle pools for scheduling terminus and areasatMaximum capacity of vehicletaijtLoading bikes of vehiclet from area i to area jLtMaximum operation distanceCtFixed cost per vehicleMtFlexible cost per vehicleVAverage speeddijTransport distance by vehicle from areai to area jGAPiNumber of vehicles to be deployed in/out of areaiωiImportance of areaiTMiTime for vehicle to arrive in areaiSTime cost for loading/unloading bikesTMwtTime for vehicle to depart from terminusFQi,FRiPenalty time window


## 2.3.1.F1: The Objective of Minimizing Operating Costs

The actual operation costs need to consider both fixed and flexible costs, as summarized in equation (2), which is determined jointly by the value of scheduling vehicles [34], the unit transport cost (i.e., vehicle loss: 1 CNY/km, fuel consumption: 1 CNY/km, and labor cost: 100 CNY/person), and the scheduling distance.(2)minF1=minFxd+Flx=min∑wW∑tT∑iIxwjtCt+∑tT∑iR∑jRxijtdijMt,(3)s.t.∑iIxwit=∑iIxwit≤1∀w∈W,t∈T,(4)∑tT∑j=1j≠iRxjit=∑tT∑j=1j≠iRxjit=1∀i,j∈I,t∈T,(5)0≤∑iR∑j=1j≠iRxijtdij≤Lt∀t∈T,(6)0≤aijt≤aijtxijt∀i,j∈R,i≠j,t∈T,(7)xijt=0or1∀i,j∈R,i≠j,t∈T,(8)aijt∈Z+∀i,j∈R,i≠j,t∈T,Equation (3) indicates that this scheduling vehicle starts and ends at the terminus; equation (4) suggests that each area can only be served once; equation (5) shows that the transport distance must not exceed the maximum scheduling distance; equation (6) points that the number of bikes loaded by the vehicle must not exceed its maximum capacity, namely, 400; equation (7) means xijt as 0-1 variable; equation (8) proves that the number of bikes deployed by the vehicle is a non-negative integer.


## 2.3.2.F2: The Objective of Maximizing User Satisfaction

User satisfaction can be improved by adding time window constraints, as described in equation (9), which means maximizing user satisfaction can equivalently transfer into minimizing the penalty cost of scheduling timeout.(9)maxF2=min∑iIωiρiti,(10)s.t.TMwt=0∀t∈T,(11)TMj=∑tT∑iRxijtTMi+TMj+S⋅GAPi,∀j∈I,(12)TMi+TMj+S⋅GAPi−K1−xijt≤TMj,(13)FQi≤TMi≤FRi,∀i∈I.Equation (10) indicates that the vehicle departs from the terminus at time zero; equation (11) means that the time calculation for a vehicle to arrive in an area; equation (12) demonstrates that the scheduling cannot arrive in area j from area i before TMi+TMj+S⋅GAPi−K1−xijt; equation (13) represents that vehicle needs to arrive in an area within the time window.The meaning of the parameters in the above-given equationsare shown in Table2.Table 2
The meaning of parameters for formulations 1–14.
ParameterMeaningIScheduling areaTScheduling vehiclesWScheduling terminusRVehicle pools for scheduling terminus and areasatMaximum capacity of vehicletaijtLoading bikes of vehiclet from area i to area jLtMaximum operation distanceCtFixed cost per vehicleMtFlexible cost per vehicleVAverage speeddijTransport distance by vehicle from areai to area jGAPiNumber of vehicles to be deployed in/out of areaiωiImportance of areaiTMiTime for vehicle to arrive in areaiSTime cost for loading/unloading bikesTMwtTime for vehicle to depart from terminusFQi,FRiPenalty time window


## 3. Case Study

The highlights ofHATB solving are illustrated in terms of algorithm settings, scheduling results, and model evaluation in this section.


### 3.1. Algorithm Settings

The experiment data comes from the 2017 Mobike cup algorithm challenge, which involves 3,214,096 orders and 485,465 bikes (10th May 2017–23rd May 2017). The characterized user travel, as presented in Table 3, reflects that the data are consistent with the “last mile” definition [16], and hence, shows its reasonable usability according to prominent tidal characteristics.Table 3
Examples of user travel characteristics.
Travel informationTimeOrdersAverage distance: 815 m7 a.m18957818 p.m1736548 a.m171011Median distance: 660 m17 p.m16412619 p.m12538312 p.m119883This paper proposes a GA with natural number encoding (NGA), as defined in Algorithm1, to optimize the scheduling. In general, the first and the last 0 s represent the scheduling terminus or area, [1, N] represents the zones that need to be scheduled, and other 0 s separate the routes of different vehicles, e.g., a chromosome example might be 0-3-0-1-2-5-7-0-4-8-6-0, namely, three vehicles serving eight zones.Since the crossover and mutated sub chromosomes may lead to transport overload and overtime and the time window is more likely to be violated, the penalty factors for the two constraints are set to 10 and 500, respectively.Algorithm 1: NGA for scheduling optimisation.
Input: SchedulingAreaSA, DistanceMatrix DMOutput: SchedulingRoute SR, SchedulingVehicle SV, DeployedBikes DRInitialization: GenerationGen = 100, CrossoverRate CR = 0.8, MutationRate MR = 0.2, Population Pop ← ∅, Chromosome CH ← ∅, Fitness Fit = Null,(1)
For all theSAdo(2)
Pop ← CH.generate (SA.Encoding)//Randomly Generation for Population (100)(3)
End for(4)
Fit ← Fit.Calculation//Calculate the Fitness(5)
ifFit.change or Gen < 100 then(6)
For all theCHdo(7)
CH.select//Chromosome Selection(8)
CH.crossover//Chromosome Crossover(9)
CH.mutate//Chromosome Mutation(10)
Pop ← CH.NewGenerate//New Population(11)
Fit ← Fit.NewCalculation(12)
End for(13)
End if(14)
SR ← CH.Decoding(15)
ReturnSR, SV, DR


### 3.2. Scheduling Results

A total of 220 scheduling areas in the morning peak are used asHATB test cases to obtain the optimal hierarchical scheduling routes, as shown in Figure 3 and Tables 4 and 5.Figure 3
The schema ofHATB.Table 4
The optimal routes for scheduling areas in the morning peak.
Routes for scheduling areaDemandNumber of vehiclesTotal distance (km)0-135-29-113-112-150-205-20-44-170-130-146-01431719.5420070-40-88-138-104-65-12-191-115-52-162-83-157-014210-7-45-93-61-129-188-199-158-217-87-53-165-85-119-36-34-210-014010-5-6-50-47-41-75-63-86-27-101-125-200-178-81-78-89-122-187-195-203-207-014010-18-21-95-132-148-91-71-161-192-117-013910-181-106-102-145-135-29-113-112-150-205-20-013810-51-177-92-79-84-26-38-214-215-166-168-183-013310-31-143-114-37-118-99-156-163-137-149-194-011410-54-66-74-128-94-136-201-179-190-152-35-30-33-204-218-011410-90-78-89-97-64-105-185-131-127-189-140-100-8-82-22-25-98-24-144-124-197-011310-3-70-55-169-172-182-109-208-011310-62-103-202-43-11-16-57-23-108-153-211-011110-4-1-2-14-17-67-48-15-42-56-72-68-99-156-219-011010-44-170-30-146-159-173-174-69-9-46-49-19-141-186-175-171-39-213-154-51-60-011010-180-139-142-198-147-116-212-134-167-184-126-216-011010-76-164-10-77-73-60-111-120-196-209-08010-28-133-110-193-123-154-32-13-107-121-155-206-0791Table 5
Examples of hierarchical autonomous scheduling results for route one.
Routes for scheduling pointScheduling areaTotal distance (km)a0-a11-a4-a18-a17-a9-a1-a12-a15-a19-a5-a0170 (a0)1.443b0-b1-b3-b11-b4-b48-b39-b18-b42-b38-b7-b19-b54-b2-b28-b25-b26-b27-b43-b31-b12-b21-b45- b52-b30-b20-b46-b47-b6-b29-b40-b37-b14-b33-b9-b34-b51-b24-b32-b15-b55-b10-b44-b22-b16-b41-b17-b5-b13-b23-b53-b8-b50-b49-b36-b35-b0130 (b0)3.905c0-c17-c23-c13-c15-c29-c32-c10-c35-c31-c2-c34-c5-c4-c14-c33-c22-c11-c9-c3-c6-c21-c20-c25-c30-c28-c24-c16-c27-c19-c8-c12-c26-c1-c18-c7-c0146 (c0)2.951As described in the previous section, regional scheduling is applied for each layer. Note that, each scheduling area has a positive or negative raw demand that reflects the redundancy or scarcity of bikes. Furthermore, scheduling prioritizes self-satisfaction in the route, namely, redundancy supports scarcity, and hence, route demand indicates the self-satisfaction gap for corresponding regional scheduling.Therefore, the experimental results can be summarized as the total scheduling distance for optimal routes in the entire Beijing is around 719.5 km. As for satisfying the demands, 17 vehicles are required to participate in the scheduling to deploy bikes. Moreover, using route one in Table4 as an example, the scheduling can be summarized as a vehicle departing from the scheduling terminus and returning to the terminus after completing regional scheduling sequentially and autonomously in accordance with the area-point (middle-bottom) hierarchy. In addition, the routes’ information in reality for Table 5 is mapped to Table 6 via GeoHash.Table 6
The mapped scheduling results with examples of route one (Table5).
Scheduling area (5-bit)Routes for scheduling point (7-bit)WX54C (no. 170)WX54Cwith 0W, 20, E4, 06, 0C, J8, JB, LJ, NC, BW, BX, 0WWX4GW (no. 130)WX4GWwith 00, 02, 08, PL, 06, 77, 7K, P4, NF, 7M, ZH, YY, N8, P0, PF, PY, PV, PS, ND, JL, P3, PB, N9, 03, JH, PZ, 7B, 78, 7F, 7E, KH, 7U, 7Q, EQ, ZN, EN, 09, Q8,G7, ZQ, GJ, ZK, NB, P8, P9, P5, 01, 04, 2N, U4, FZ, ZV, 0D, 3K, 86, DK, 00WX5H2 (no. 146)WX5H2with 5X, 7C, QX, DM, GL, 6M, Y6, F9, 4N, 4J, DS, DT, VC, TY, DC, D3, TZ, ER, G0, G8, 74, UE, UK, GE, 1E, 12, QK, 7D, 75, 77, W2, EP, G9, ZG, 79, 48, 5X


### 3.3. Model Evaluation

To further verify the reliability of this model, Figure4 shows the comparison for iteration between the HATB and other models proposed in the literature with similar objectives. Specifically, based on the GA, Gao et al. [35] provided a promising perspective on improving operation efficiency by reducing operating costs and service quality during peak times to minimize the total operating costs. Angeloudis et al. [36] achieved user appeal increase by offering a new method of planning bike routes and distributions. Moreover, Zhao et al. [37] optimized the total scheduling distance to accommodate large-scale scheduling via an ACO.Figure 4
The comparison between different scheduling models.The proposedHATB converged at the 64th generation, and the total time cost is 148.9 s, with an average running time of 15 s per generation. Due to the different objectives, only the convergence speed of the above models is compared. It can be seen from Figure 4 that the HATB significantly outperforms the model proposed in the existing literature. Such a result indicates that this model is more proper for practical scheduling applications since it optimizes with higher convergence speed and lower time complexity.


## 3.1. Algorithm Settings

The experiment data comes from the 2017 Mobike cup algorithm challenge, which involves 3,214,096 orders and 485,465 bikes (10th May 2017–23rd May 2017). The characterized user travel, as presented in Table 3, reflects that the data are consistent with the “last mile” definition [16], and hence, shows its reasonable usability according to prominent tidal characteristics.Table 3
Examples of user travel characteristics.
Travel informationTimeOrdersAverage distance: 815 m7 a.m18957818 p.m1736548 a.m171011Median distance: 660 m17 p.m16412619 p.m12538312 p.m119883This paper proposes a GA with natural number encoding (NGA), as defined in Algorithm1, to optimize the scheduling. In general, the first and the last 0 s represent the scheduling terminus or area, [1, N] represents the zones that need to be scheduled, and other 0 s separate the routes of different vehicles, e.g., a chromosome example might be 0-3-0-1-2-5-7-0-4-8-6-0, namely, three vehicles serving eight zones.Since the crossover and mutated sub chromosomes may lead to transport overload and overtime and the time window is more likely to be violated, the penalty factors for the two constraints are set to 10 and 500, respectively.Algorithm 1: NGA for scheduling optimisation.
Input: SchedulingAreaSA, DistanceMatrix DMOutput: SchedulingRoute SR, SchedulingVehicle SV, DeployedBikes DRInitialization: GenerationGen = 100, CrossoverRate CR = 0.8, MutationRate MR = 0.2, Population Pop ← ∅, Chromosome CH ← ∅, Fitness Fit = Null,(1)
For all theSAdo(2)
Pop ← CH.generate (SA.Encoding)//Randomly Generation for Population (100)(3)
End for(4)
Fit ← Fit.Calculation//Calculate the Fitness(5)
ifFit.change or Gen < 100 then(6)
For all theCHdo(7)
CH.select//Chromosome Selection(8)
CH.crossover//Chromosome Crossover(9)
CH.mutate//Chromosome Mutation(10)
Pop ← CH.NewGenerate//New Population(11)
Fit ← Fit.NewCalculation(12)
End for(13)
End if(14)
SR ← CH.Decoding(15)
ReturnSR, SV, DR


## 3.2. Scheduling Results

A total of 220 scheduling areas in the morning peak are used asHATB test cases to obtain the optimal hierarchical scheduling routes, as shown in Figure 3 and Tables 4 and 5.Figure 3
The schema ofHATB.Table 4
The optimal routes for scheduling areas in the morning peak.
Routes for scheduling areaDemandNumber of vehiclesTotal distance (km)0-135-29-113-112-150-205-20-44-170-130-146-01431719.5420070-40-88-138-104-65-12-191-115-52-162-83-157-014210-7-45-93-61-129-188-199-158-217-87-53-165-85-119-36-34-210-014010-5-6-50-47-41-75-63-86-27-101-125-200-178-81-78-89-122-187-195-203-207-014010-18-21-95-132-148-91-71-161-192-117-013910-181-106-102-145-135-29-113-112-150-205-20-013810-51-177-92-79-84-26-38-214-215-166-168-183-013310-31-143-114-37-118-99-156-163-137-149-194-011410-54-66-74-128-94-136-201-179-190-152-35-30-33-204-218-011410-90-78-89-97-64-105-185-131-127-189-140-100-8-82-22-25-98-24-144-124-197-011310-3-70-55-169-172-182-109-208-011310-62-103-202-43-11-16-57-23-108-153-211-011110-4-1-2-14-17-67-48-15-42-56-72-68-99-156-219-011010-44-170-30-146-159-173-174-69-9-46-49-19-141-186-175-171-39-213-154-51-60-011010-180-139-142-198-147-116-212-134-167-184-126-216-011010-76-164-10-77-73-60-111-120-196-209-08010-28-133-110-193-123-154-32-13-107-121-155-206-0791Table 5
Examples of hierarchical autonomous scheduling results for route one.
Routes for scheduling pointScheduling areaTotal distance (km)a0-a11-a4-a18-a17-a9-a1-a12-a15-a19-a5-a0170 (a0)1.443b0-b1-b3-b11-b4-b48-b39-b18-b42-b38-b7-b19-b54-b2-b28-b25-b26-b27-b43-b31-b12-b21-b45- b52-b30-b20-b46-b47-b6-b29-b40-b37-b14-b33-b9-b34-b51-b24-b32-b15-b55-b10-b44-b22-b16-b41-b17-b5-b13-b23-b53-b8-b50-b49-b36-b35-b0130 (b0)3.905c0-c17-c23-c13-c15-c29-c32-c10-c35-c31-c2-c34-c5-c4-c14-c33-c22-c11-c9-c3-c6-c21-c20-c25-c30-c28-c24-c16-c27-c19-c8-c12-c26-c1-c18-c7-c0146 (c0)2.951As described in the previous section, regional scheduling is applied for each layer. Note that, each scheduling area has a positive or negative raw demand that reflects the redundancy or scarcity of bikes. Furthermore, scheduling prioritizes self-satisfaction in the route, namely, redundancy supports scarcity, and hence, route demand indicates the self-satisfaction gap for corresponding regional scheduling.Therefore, the experimental results can be summarized as the total scheduling distance for optimal routes in the entire Beijing is around 719.5 km. As for satisfying the demands, 17 vehicles are required to participate in the scheduling to deploy bikes. Moreover, using route one in Table4 as an example, the scheduling can be summarized as a vehicle departing from the scheduling terminus and returning to the terminus after completing regional scheduling sequentially and autonomously in accordance with the area-point (middle-bottom) hierarchy. In addition, the routes’ information in reality for Table 5 is mapped to Table 6 via GeoHash.Table 6
The mapped scheduling results with examples of route one (Table5).
Scheduling area (5-bit)Routes for scheduling point (7-bit)WX54C (no. 170)WX54Cwith 0W, 20, E4, 06, 0C, J8, JB, LJ, NC, BW, BX, 0WWX4GW (no. 130)WX4GWwith 00, 02, 08, PL, 06, 77, 7K, P4, NF, 7M, ZH, YY, N8, P0, PF, PY, PV, PS, ND, JL, P3, PB, N9, 03, JH, PZ, 7B, 78, 7F, 7E, KH, 7U, 7Q, EQ, ZN, EN, 09, Q8,G7, ZQ, GJ, ZK, NB, P8, P9, P5, 01, 04, 2N, U4, FZ, ZV, 0D, 3K, 86, DK, 00WX5H2 (no. 146)WX5H2with 5X, 7C, QX, DM, GL, 6M, Y6, F9, 4N, 4J, DS, DT, VC, TY, DC, D3, TZ, ER, G0, G8, 74, UE, UK, GE, 1E, 12, QK, 7D, 75, 77, W2, EP, G9, ZG, 79, 48, 5X


## 3.3. Model Evaluation

To further verify the reliability of this model, Figure4 shows the comparison for iteration between the HATB and other models proposed in the literature with similar objectives. Specifically, based on the GA, Gao et al. [35] provided a promising perspective on improving operation efficiency by reducing operating costs and service quality during peak times to minimize the total operating costs. Angeloudis et al. [36] achieved user appeal increase by offering a new method of planning bike routes and distributions. Moreover, Zhao et al. [37] optimized the total scheduling distance to accommodate large-scale scheduling via an ACO.Figure 4
The comparison between different scheduling models.The proposedHATB converged at the 64th generation, and the total time cost is 148.9 s, with an average running time of 15 s per generation. Due to the different objectives, only the convergence speed of the above models is compared. It can be seen from Figure 4 that the HATB significantly outperforms the model proposed in the existing literature. Such a result indicates that this model is more proper for practical scheduling applications since it optimizes with higher convergence speed and lower time complexity.


## 4. Conclusion and Future Works

Even though the emerging and diversified technologies and demands are driving TS to renovate conventional MS to be self-actuating, the current bicycle-sharing scheduling and maintenance rely on manual experience, which lacks scientific guidance and efficiency. Therefore, to achieve sustainable development, operators urgently need to develop a rational scheduling strategy to balance the distribution conflicts and supply user demands in time.Therefore, this paper proposes a hierarchical scheduling model, calledHATB, to address the unsolved issues by current studies in terms of slow convergence, high time complexity, and problematic application, and hence, to support the rational and autonomous provision of LMS. In summary, according to bicycle-sharing properties, namely, spatio-temporal characteristics, cross-regional mobilities, and actual demands, HATB takes 220-morning peak areas as tests to validate its improved validity, feasibility, and efficiency for practical application.As compared to the similarly used methods,HATB can, accordingly, obtain the following improvements. A hierarchical framework is first designed through GeoHash encoding to solve the cross-regional mobility of bikes and reduce the time complexity of global optimization. Next, a GA for regional scheduling is built by combining the tidal characteristics of bicycle-sharing to minimize operating costs and maximize user satisfaction, which significantly accelerates the algorithm’s convergence. Last, the use of actual orders considerably enhances the ability in the practical application of instant response to any regional scheduling demand.This work was carried out as a preliminary to obtain the present results. However, there are still problems such as the inability to adapt scheduling throughout 24 hours or the lack of comprehensive constraints. As the closure of this study, one recommendation for further research is to use a form of “GA + Tabu” algorithm to exploit its global search capability and thus improve the big data processing capability. Another research direction is adding weather and road characteristics to optimize the model reliability further.



---

*Source: 5725009-2023-02-18.xml*