key: cord-0979701-q391k42i authors: Chen, Feng; Peng, Haorong; Ding, Wenlong; Ma, Xiaoxiang; Tang, Daizhong; Ye, Yipeng title: Customized bus passenger boarding and deboarding planning optimization model with the least number of contacts between passengers during COVID-19 date: 2021-11-15 journal: Physica A DOI: 10.1016/j.physa.2021.126244 sha: 9387f37eb7fb08f00c738054b92163a60c138091 doc_id: 979701 cord_uid: q391k42i The COVID-19 epidemic has had a major impact on people’s normal travel. Optimizing the control of the number of passengers boarding and deboarding the customized bus (CB) at CB stops can reduce the contact between passengers in the course of travel, which is meaningful for COVID-19 epidemic prevention and control. In this paper, a dynamic programming model based on nonlinear integer programming (NIP) is established to study the problem of boarding and alighting planning at various CB stops under the influence of COVID-19. Using Gurobi 9.1.1 solver, the optimal plan for passengers boarding and deboarding CB buses could be obtained. Besides, the mathematical model established in this paper can obtain the minimum value of the total number of contacts between passengers during travel under different CB numbers. It is found that the model solution results eventually form a Pareto frontier. When the number of CB buses increases, the total number of contacts between passengers will decrease This study has positive significance for ensuring the normal travel of passengers during the COVID-19 epidemic, and provides useful references for the studies about the planning of the customized bus. Public transportation is a key component in urban development [1] [2] [3] [4] [5] . The COVID-19 has had a major impact on people's lives and travel in many countries and regions, which led to a significant decline in the number of passengers by public transportation [6] . A survey [7] showed that in terms of road and vehicle classification, the changes in traffic volume are most significant in interstate highways and passenger cars and buses under the influence of the COVID-19. Governments, public transportation management departments and policies and decision makers worldwide have taken different measures to minimize the infection of COVID-19 caused by public transportation [8] . Parr et al. [9] described when the U.S. government authorities took actions and how these actions were manifested in road traffic during the COVID-19 epidemic. Customized bus (CB) would be a better choice in terms of guaranteeing passenger travel by reducing the risk of contracting the virus. CB buses provide travelers with advanced, personalized, and flexible travel services [10] . The service level of CB buses is believed higher than that of ordinary buses. Tong et al. [11] described the design of CB services within the framework of time and space. In the study, a joint optimization model was developed to address some of the practical challenges in providing flexible public transportation services. Liu et al. [12] established a two-period hotelling game model to study the service level of CB buses and passengers' choice behavior. Huang et al. [13] studied the optimization of real-time CB route problems with the goal of maximizing customer service rates and operator profits. To better understand CB service passenger loyalty and to make the CB operate better, Wang et al. [14] established three different survival models to study the subscription behavior of travelers. However, these studies on CB services are only for general conditions, and they are not suitable for the situation affected by public health events. Referring to the modeling of CB networks and routes, Ma et al. [15] developed a route selection model for the CB network based on the characteristics of travelers' needs and solved the model with the branch-and-bound method. Huang et al. [5] proposed a mixed-integer programming model for the network design problem of demand-response CB buses and the model takes the maximum revenue of the operator as the objective function. Guo et al. [16] proposed a mixed-integer programming model to study the problem of CB route planning. The model was solved by a genetic algorithm and branchand-cut algorithm, and the two algorithms were compared by a numerical example. Yu et al. [17] introduced a method of CB routes and station planning suggestions based on large demand data. Chen et al. [18] established a bi-objective mathematical model to study the design of CB routes from the perspective of passengers and operators. According to the static ride requests and dynamic ride requests of passengers, Wang et al. [19] presented the optimization problem of a real-time CB route under the random demand of multitarget users. Shen et al. [20] proposed a real-time CB route design model, which is divided into two stages, and then used a column generation algorithm to solve the model. Lyu et al. [21] proposed a CB route planning framework suitable for multiple travel data sources. At the same time, a mathematical programming model was proposed to optimize the location of bus stops, bus routes, timetables, and the probability of passengers choosing CB buses. All these studies provided insightful knowledge on CB problems, but they hold the research on general situations, which may not always be suitable for the situation affected by COVID- 19. In addition, statistical model, game model and data analysis technology are also used to study the problem of CB buses. Cao and Wang [22] , for example, analyzed the key factors influencing customized shuttle buses through logistic pricing. Wang et al. [23] conducted an analysis and research on customized public transportation data in Dalian, which provided empirical evidence for the spatial dependence and spillover effects of CB demand. Above-mentioned papers are all studies on the optimization of CB routes, parking station settings, pricing, and other issues by different mathematical models and algorithms under conventional scenarios. However, they do not consider the occurrence of public health emergencies. Some scholars have conducted research on CB problems under the influence of COVID-19, and they have an important reference value for this paper. For the CB problems in the COVID-19, Wang et al. [24] proposed a CB route optimization method based on an improved Q-learning algorithm to solve the cross-regional CB route optimization problem under the influence of COVID-19. Zhou and Ma [25] believed that booking CB trips through the mobile app during the COVID-19 epidemic is a powerful measure to prevent and control the epidemic. It is found that the research on the problem of CB buses is concentrated in the conventional circumstances and few studies focused on CB buses under the influence of the COVID-19 pandemic. In fact, during the COVID-19, people would inevitably come into contact with each other when traveling by public transportation, and the space on buses is limited. Thus, this situation increases the risk of spreading the epidemic. In order to ensure the normal travel of passengers, it is necessary to study the problems of CB operation management. In this study, it is assumed that every CB stop has passengers boarding and deboarding (As shown in Fig. 1 ). For this situation, if a reasonable plan for the number of passengers boarding and deboarding CB buses was made, the number of contacts between passengers can be reduced. In this way, the risk of passengers contracting the COVID-19 virus will be reduced, and it will be an effective method for preventing and controlling the spread of the epidemic and ensure people's traveling safety. In this paper, a dynamic programming model based on NIP is constructed, and the Gurobi 9.1.1 solver is used to solve the model. The solution results create reasonable arrangements for passengers boarding and deboarding CB buses, thereby reducing the number of contacts between passengers during travel. The remainder of the paper is organized as follows. The next section presents the problem description and assumptions. The section following describes the model used in this paper. After that, an experimental design is presented. The last section concludes the paper. COVID-19 has brought about considerable challenges in people's travel and urban public transportation operations. Traveling by CB buses is an effective method for preventing the spread of COVID-19. However, since the room of the CB buses is very enclosed, passengers will come into contact with each other in the bus, which can also cause the spread of the COVID-19 virus [26] . Shen et al. [27] reported a case of COVID-19 infection among passengers on a bus. It was reported that an asymptomatic infected person transmitted COVID-19 to 22 passengers (out of a total of 67) during two 50-minute bus trips. The more passengers in the CB buses, the more contacts will be made between them, and the more likely it is to spread the virus. To effectively prevent and control COVID-19, it is necessary to reasonably allocate the number of passengers at CB stops during the COVID-19 epidemic to reduce the number of contacts between passengers. 1. Passengers book the CB routes they need to take through the mobile app in advance; 2. CB companies master the basic information of passenger travel, including travel start time, bus route, boarding place, and deboarding location; 3. The CB company uses the information provided by passengers to develop CB travel routes and feedback messages to passengers through the mobile app. The messages include when the passengers should board the CB buses and the license plate number of the CB buses used by passengers; 4. To effectively prevent and control the influence of COVID-19, the CB company will appropriately adjust the time for some passengers to board the CB buses, but it will not have a major impact on the passenger's travel. Passengers are willing to accept the CB company's arrangements. 5. The repeated contact between passengers is considered. Notations are summarized as follows. L: The set of CB stops. If there are n CB stops, and L = {L 1 , L 2 , . . . , L n }. It is assumed that there are n CB stops on a CB line. The CB bus is represented by i, and i ∈ I. The objective function of the dynamic programming model is Subject to x i,k,k ∀i ∈ I.∀k = 1, 2, . . . , n − 1.∀k = k + 1, k + 2, . . . , n x i,k,k ≥ 0 and x i,k,k ∈ Z ∀i ∈ I, ∀k = 1, 2, . . . , n − 1.∀k = k + 1, k + 2, . . . , n where The objective function (1) represents the total number of contacts between passengers on all CB buses at all stages. Constraint (2) represents the initialization of the objective function. Constraint (3) is the initialization of the state variable. Constraint (4) means that there are no passengers on the CB buses at the end of the nth stage. Constraint (5) means that there are no passengers on the CB buses during the initialization stage, so the number of contacts is 0. Constraint (6) means that the number of contacts is 0 because all passengers have deboarded the CB buses at the end of the last stage. Constraint (7) is the dynamic programming index function. Constraint (8) represents the number of passengers boarding the ith CB bus at the kth CB stop. Its value is equal to the sum of the number of passengers who choose to take the ith CB bus to travel with the kth CB stop as the departure point and thekth CB stop as the destination. Constraint (9) represents the number of passengers deboarding the ith CB bus at the kth CB stop. Its value is equal to the sum of the number of passengers traveling on the ith CB bus with the k ′ th CB stop as the departure point and the kth CB stop as the destination. Constraint (10) is the state transition equation of dynamic programming. Constraint (11) means no passengers board the CB buses in the last stage. Constraint (12) means no passengers deboard the CB buses in the first stage. Constraint (13) is the calculation formula of the dynamic equation. Constraint (14) represents the sum of the number of people boarding the CB buses from the kth CB stop and deboarding at thekth CB stop. Constraint (15) means that the number of passengers on the CB buses does not exceed the maximum number of passengers. Constraints (16) and (17) means that x i,k,k and x i,k ′ ,k are non-negative integers. In this section, a numerical example is conducted to verify the rationality of the model. The Gurobi 9.1.1 solver was applied to solve the model proposed in this paper. 600 189 165 64 44 342 605 726 395 -11 10 4 3 20 35 42 23 --5 2 1 10 18 22 12 ---0 0 2 4 5 3 ----2 13 24 29 16 -----13 22 27 15 ------12 14 8 -------36 19 The data used to verify the model were extracted from the research paper [28] , in which the case of K1 bus line in Jiangyin city was applied to study the dispatching problem of bus service frequency and bus size. In the original dataset, the K1 line has 10 bus stops. The number of passengers boarding and deboarding the bus at each stop, namely OD (Origin & Destination) matrix, during the morning peak is shown in Table 1 . It is observed that the number of passengers boarding the bus at the first station is much larger than that at other bus stops. Considering the convenience of displaying results in the form of table in the next section, the data about L 1 station was excluded when conducting the numerical example. As a result, the OD matrix of the bus line applied to trigger the model contains 9 bus stops, and the passenger volume at each station is shown in Table 2 . In the Table, the codes of these 9 bus stations were renamed from {L 2 , L 3 , L 4 , L 5 , L 6 , L 7 , L 8 , L 9 , L 10 } to {L 1 , L 2 , L 3 , L 4 , L 5 , L 6 , L 7 , L 8 , L 9 }. It should be noted that although the K1 line is not a CB line, it is reasonable to use the OD matrix in Table 2 to conduct the numerical example because these data represent the real passenger volume on a bus line. The mathematical model established in this paper is a dynamic programming model based on NIP. There are many variables in the numerical example, which makes it difficult to solve the model. To solve the model within a reasonable time range, the gap of the Gurobi 9.1.1 solver is set to be 0.005 during the solving process. Assume that the maximum number of passengers allowed by the CB bus is 50. To make the paper concise, only the dispatch plan referring to 8 CB buses was presented in detail. These 8 CB buses were coded as {Bus 1 , Bus 2 , Bus 3 , Bus 4 , Bus 5 , Bus 6 , Bus 7 , Bus 8 }. Before obtaining the number of contacts between all passengers, it is necessary to explain the dispatch plan in detail shown in Table 3 . The result of Bus 1 was taken as an example. There were 19 passengers getting on the bus at the L 1 CB stop. Among them, 6 passengers debussed at L 2 CB stop, 10 passengers debussed at L 3 CB stop, 2 passengers debussed at L 5 CB stop, and one passenger debussed at L 6 CB stop. From L 1 to L 2 , the number of contacts between passengers on Bus 1 When Bus 1 arrived at the L 2 bus station, a total of 14 passengers got on the CB bus. Since 6 passengers debussed, there were totally 27 passengers on the Bus 1 between L 2 and L 3 . 12 of these passengers debussed at L 9 stop, one passenger debussed at L 3 stop and one passenger debussed at L 5 station. From L 2 to L 3 , the number of contacts between passengers on Bus 1 is 27 × (27 − 1) × 0.5 = 351. When Bus 1 arrived at the L 3 bus station, the CB bus was boarded by 10 passengers. Excluding 11 passenger deboarding at the L 3 stop, there were totally 26 passengers on the Bus 1 between L 3 and L 4 . As a result, the number of contacts between passengers on Bus 1 from L 3 to L 4 is 26 × (26 − 1) × 0.5 = 325. When Bus 1 arrived at the L 4 bus station, the CB bus was also boarded by 10 passengers with no one deboarding. So the number of passengers on the Bus 1 from L 4 to L 5 is 46 and the number of total contacts is 36 × (36 − 1) × 0.5 = 630. L 1 6 10 0 2 1 0 0 0 L 2 -1 0 1 0 0 0 12 L 3 --0 0 2 0 5 3 L 4 - Abovementioned analysis has presented the process of calculation of contacts between passengers on the Bus 1 along the whole CB line. With the OD matrix shown in Table 2 , the model result indicated that at least 8 buses were needed to satisfy the demand of passengers along the whole CB line. Using the same calculation method mentioned above, the total contacts between passengers on these 8 buses along the whole CB line was obtained, which is 31 741. Certainly, if more buses (above 8) were used, the demand of passengers shown in the OD matrix of Table 2 could also be satisfied. If so, the total contacts between passengers would be changed. Since the analysis method is similar, the results of total contacts corresponding to different number of CB buses are given in Table 4 directly. It is observed that the number of total contacts between passengers decreases as the number of buses increases. The trend could be seen more directly in Fig. 2 , which presents the total contacts when the number of buses changes from 8 to 30. The horizontal axis represents the number of CB buses, and the vertical axis represents the number of contacts between passengers. It is observed that the result of the model forms a Pareto frontier. When the number of CB buses reach 24, the total contacts between passengers would be decreased to less than ten thousand. Therefore, to effectively prevent and control the COVID-19 epidemic and at the same time ensure the normal travel of passengers, increasing the number of CB buses is the key to solving the problem. In practice, the transportation cost of CB buses is also an issue that has to be considered. It is beneficial to prevent and control the epidemic when the number of buses increases, but the transportation cost of CB buses also increases accordingly. Therefore, in the prevention and control of the COVID-19 epidemic, CB companies can reasonably arrange the number of CB buses according to the transportation cost and the actual situation of the local COVID-19 epidemic. In this paper, a dynamic programming model based on NIP is constructed to optimize the number of passengers boarding and deboarding the CB buses at CB stops during the impact of the COVID-19 epidemic, thereby reducing the number of contacts between passengers during travel. This paper verifies the validity and rationality of the established model through a specific example and gives the solution result of the model when the number of CB buses is 8. The solution results include the number of contacts between passengers and the number of people boarding and deboarding each CB bus at every CB stop. In addition, the total number of contacts between passengers was also given when the number of CB buses increases. Conclusions are summarized as follows: 1. The optimized model established in this article can calculate the minimum number of contacts between passengers traveling by CB buses during the period of COVID-19. The model is solved by the Gurobi 9.1.1 solver. The passenger boarding and alighting plans under different numbers of CB buses could be obtained by solving the model. 2. Through the model, the total number of contacts between passengers under different CB numbers can be obtained. It is found that the model solution results eventually form a Pareto frontier. When the number of CB buses increases, the total number of contacts between passengers will decrease. The greater the number of CB buses, the fewer contacts there are between passengers, which is more conducive to the prevention and control of the COVID-19 epidemic. However, when the number of CB buses increases, the transportation cost of CB buses will increase. In practice, a reasonable CB dispatch plan can be formulated according to the actual situation of the COVID-19 epidemic, the cost of CB buses and passenger travel information. In the future, more studies would be conducted from the following two directions: (1) research CB issues in more complex network environments during the period of COVID-19 and (2) study the impact of CB driving distance on the spread of the epidemic during COVID-19. Public transportation and sustainability: A review A general formulation for multi-modal dynamic traffic assignment considering multi-class vehicles, public transit and parking Optimal coordination of public-transit vehicles using operational tactics examined by simulation Determining optimal frequency and vehicle capacity for public transit routes: A generalized newsvendor model A two-phase optimization model for the demand-responsive customized bus network design Mining urban sustainable performance: Spatio-temporal emission potential changes of urban transit buses in post-COVID-19 future Disruption and recovery: Initial assessment of COVID-19 traffic impacts in north carolina and virginia The role of transport accessibility within the spread of the coronavirus pandemic in Italy Multistate assessment of roadway travel, social separation, and COVID-19 cases Analysis of a new public-transport-service concept: Customized bus in China Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing Operational strategy of customized bus considering customers' variety seeking behavior and service level Customized bus route optimization with the real-time data Key determinants and heterogeneous frailties in passenger loyalty toward customized buses: An empirical investigation of the subscription termination hazard of users Large-scale demand driven design of a customized bus network: A methodological framework and Beijing case study Route design problem of customized buses: Mixed integer programming model and case study Mobile phone GPS data in urban customized bus: Dynamic line design and emission reduction potentials analysis Customized bus route design with pickup and delivery and time windows: Model, case study and comparative analysis Multi-objective optimization of real-time customized bus routes based on two-stage method Real-time customized bus routes design with optimal passenger and vehicle matching based on column generation algorithm CB-planner: A bus line planning framework for customized bus systems The key contributing factors of customized shuttle bus in rush hour: A case study in harbin city Spatial dependence and spillover effects in customized bus demand: Empirical evidence using spatial dynamic panel models Cross-regional customized bus route planning considering staggered commuting during the COVID-19 Unconventional prevention strategies for urban public transport in the COVID-19 epidemic: Taking ningbo city as a case study COVID-19 and public transportation: Current assessment, prospects, and research needs Airborne Transmission of COVID-19: Epidemiologic Evidence from an Outbreak Investigation Bus service frequency and bus size optimization model considering passengers' perception The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. This study was supported by the National Natural Science Foundation of China (5197082108).