# Vehicle Scheduling Optimization considering the Passenger Waiting Cost

Authors: Huayan Shang; Yanping Liu; Haijun Huang; Renyong Guo
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

In the operational planning process of public transport, the time a passenger spends on waiting is a very critical element for judging passenger service. Schedule synchronization is a useful strategy for reducing bus waiting time and improving service connectivity. This paper develops an extended vehicle scheduling model, taking into account the interests of passengers and operators in attaining optimization of timetable synchronization integrated with vehicle scheduling and considering the passenger waiting cost. Deficit functions at terminals are formulated. Deadheading (DH), shifting departure time (SDT), and network flow technique are used for vehicle scheduling with the consideration of passenger waiting times. An experimental study in Beijing is conducted and three important bus lines are selected as a regional bus network to demonstrate the methodology developed. Results show that both the fleet size of bus operators and the waiting cost of passengers are minimized. For example, the minimum fleet size can be reduced from 28 vehicles to 24 ones while the passenger times are less than 20 minutes in this multidepot network.


---

## Body

## 1. Introduction

In the past 40 years, urbanization in China increased in speed. By the end of 2017, 58.52% of the total population lived in urban areas, a dramatic increase from 17.92% in 1978. Urban population grew rapidly from 170 million to 810 million, and the number of cities increased from 193 to 657. Meanwhile, levels of car ownership in China have risen significantly. By the end of 2018, car ownership reached 240 million, with more than 3 million in eight cities, 2 million in 27 cities, and 1 million in 61 cities [1]. With the continuous expansion of urban scale and the improvement of motorization level, the urban traffic demand increases day by day, which results in a serious imbalance between the huge demand and the limited traffic supply. Taking Beijing as an example, the average daily traffic jam time (moderate and severe traffic jams) in 2016 reached 2 hours and 55 minutes, which accounted for 27% per day [2].To alleviate traffic congestion, urban public transport (PT) priority has become a strategic choice for China. The policy of vigorously developing PT has been listed in The 13th Five-year Plan for National Economy and Social Development and issued by the State Council [3]. Since it is difficult to operate the rail transit in a network in a short term, the PT system should still be dominated by the bus transit in the near future. However, lots of problems for bus including low speed, low punctuality, poor comfort, inconvenient transferring, and low coverage have not been effectively solved. To gain an in-depth understanding of the bus operations in real traffic, we have conducted a series of field surveys, including ones on public transport along Chang’an Avenue, a major thoroughfare in Beijing, China [4]. The survey results demonstrate that, although a huge number of buses are in service during peak hours, lots of passengers queue at bus stops (see Figure 1(a)), and some passengers even have to climb up the bus windows for riding in a bus (see Figure 1(b)). The numbers of passengers waiting for a bus line at the evening peak period are more than 500 (per interval of 5 minutes) and the average waiting times for riding in buses are over 20 minutes [5]. Long waiting times reduce the level of bus service and make the passengers anxious.Figure 1
Crowding at the bus stop. (a) Queuing for a bus line. (b) Climbing by windows.
(a)
(b)In the operational planning process of public transport, timetable synchronization is an important issue to reduce transfer waiting time and improve service connectivity. Minimizing waiting times can improve customer satisfaction, which in turn leads to increases in ridership and revenues. However, most of the studies on PT timetable synchronization design have treated the problem independently of other operations planning activities and have focused only on minimizing transfer waiting time. In addition, the impact of schedule changes on PT users’ route/trip choice behavior has not been well investigated yet [6]. Shang et al. [5] provided a three-procedure bus timetabling method which was practical and applicable in China. The method was verified by field data and the results demonstrated that it had the advantage of reducing waiting time and lessening on-board discomfort. But the model was highly simplified and only considered the arrivals at the original stops except those at the downstream stops.Vehicle scheduling is a crucial step of the PT planning process since it is desirable to minimize the number of vehicles used and operational cost. The purpose of the paper is to address a multidepot vehicle scheduling problem considering the passenger waiting cost. This paper develops an extended vehicle scheduling model together with the deficit function (DF) as follows: First, a practical timetable compromising the passenger waiting cost and the bus operating cost is proposed. Secondly, deadheading (DH), shifting departure time (SDT), and network flow technique are used for vehicle scheduling with the consideration of passenger waiting times. Finally, an experimental study in Beijing is conducted and three important bus lines are selected as a regional bus network to demonstrate the methodology developed. Results show that both the fleet size of bus operators and the waiting cost of passengers are minimized.Therefore, the contributions of this research are threefold: (a) An extended vehicle scheduling model considering the interests of both passengers and operators is proposed; (b) Timetable synchronization integrated with vehicle scheduling and passenger waiting cost is attained. (c) A detailed numerical example is provided to illustrate the performance of the mathematical model and solution method developed, with a discussion on some promising future research directions.The rest of the paper is organized as follows. In the next section, a literature review of vehicle scheduling problem (VSP) is provided. Deficit function and an extended vehicle scheduling model are presented in Section3. In Section 4, we formulate the solution method. The practical application of the method is illustrated in Section 5. Section 6 concludes the paper.


## 2. Literature Review

In the last decades, a fruitful development of models and solution techniques were addressed in bus transport systems. The global PT problem is computationally intractable and can hardly be tackled at once [7]. Desaulniers and Hickman (2007) divided it into a set of subproblems that were usually solved sequentially at various stages of the planning process (strategic, tactical, and operational) and during operations (real-time control). They provided a systematic way of reviewing state-of-the-art models and approaches for solving the public transit problems [8]. Ibarra-Rojas et al. (2015) followed this classification and reviewed the literature on the planning, operation, and control of the bus transport systems [9].Guihaire and Hao (2008) presented a global review of the crucial strategic and tactical steps of transit planning: the design and scheduling of the network [10]. They followed a five-step planning process including network design, frequencies setting, timetable development, bus scheduling, and driver scheduling [11].PT operational planning can be considered a multistep process. Because of its complexity, each step is normally conducted separately and sequentially fed into the other. The process includes (1) network route design, (2) timetable development, (3) vehicle scheduling, and (4) crew scheduling [11, 12]. It can be seen that bus vehicle scheduling is a very important link in bus planning and operation.Vehicle scheduling refers to determining the optimal allocation of vehicles in a given transportation schedule based on the execution of all trips [9, 11]. The simplest version of the vehicle scheduling problem (VSP) is known as the single-depot single-type vehicle scheduling problem. This problem determines the vehicles’ schedules so that all trips are covered by vehicles departing (returning) from (to) the same depot. A vehicle schedule is composed of vehicle blocks, where each block represents the departure from the depot to serve a sequence of trips and then return to the depot. Freling et al. (2001) and Bunte and Kliewer (2009) introduced several models and algorithms for single-depot vehicle scheduling. They argued that the new algorithms showed a significant performance improvement with respect to computation time [13, 14].Another version of the VSP is the multidepot vehicle scheduling problem, where vehicles can depart from different locations. This assumption leads to complex formulations, such as multicommodity network flow problems. The problem is intractable since it is nondeterministic polynomial hard (NP-hard) (proved by Bertossi et al., 1987) [15].However, exact approaches towards solving large instances of the multidepot VSP have been presented in recent studies (see reviews by Ibarra-Rojas et al., 2015) [9]. For example, Haghani and Banihashemi (2002) presented an exact and two heuristic solution procedures for solving a multiple depot problem with route time constraints in order to reduce the scale of real problems [16]. Haghani et al. (2003) analyzed a multidepot and two single depot vehicle scheduling models comparatively. Actually, these two single depot models were special cases of the multidepot model. An analysis process was conducted by solving the congestion problem [17].The deficit function (DF) with information graphics technology features, which represented the deficit number of vehicles required at a specific terminal in a multidepot transit network, was proposed to the multidepot VSP problem (see reviews by Liu and Ceder, 2017) [18]. Ceder (2002, 2005) described the DF optimization tool for minimizing the number of vehicles required for a given timetable of trips in a multidepot transit system [19, 20]. The DF was allowed to insert deadheading (DH) and shift the departure times. In order to achieve the greatest vehicle saving, a procedure allowed the experienced transit schedulers to introduce their practical considerations in the schedule. An improved lower bound on the fleet size was established afterward, which was based upon extending each trip’s arrival time to a trip’s first feasible departure time or to the end of the limited time horizon. From the perspective of PT operators and users, Liu and Ceder (2017) developed a new biobjective bilevel integer programming model using the DF approach. Based on the bilevel structure characteristics of the model, a new DF-based sequential search method combining with network flow and departure time adjustment techniques was proposed to obtain a set of Pareto-efficient solutions [6]. Tang et al. (2018) proposed a DF methodology to reduce the vehicles required by taking limited stops, deadheading, and mixed strategies into account. The schedulers could select a variable trip schedule based on the best applied strategies. Two optimization models were formulated to minimize the passenger travel time and determine a set of stops served by a variable trip schedule [21].Linear programming models were also commonly used in the study of vehicle scheduling. Ibarra-Rojas et al. (2014) discussed the trade-off between the level of service and the operating cost, which involved the timetabling and the VSP problems at the operational level. They presented two integer linear programming models combining a biobjective integrated model [22]. For solving this biobjective problem, ∈-constraint method was proposed and implemented. Lin and Kwan (2014) developed a two-phase approach for the train unit scheduling problem [23]. The first phase was modeled as an integer fixed-charge multicommodity flow problem ignoring some station infrastructure details and solved by a branch-and-price method. The second phase was formulated as a multidimensional matching problem with a mixed integer linear programming formulation. A column-and-dependent-row generation method was developed for it.Solving the multidepot VSP in an integrated manner can better reflect the operational planning process. Schöbel (2017) described that PT operation system was a multiobjective problem including line planning, timetabling, and vehicle scheduling [24]. They developed a generic, biobjective model and an eigenmodel to apply for these three stages. Wagale (2013) used a demand-and-travel-time responsive model to realize a timetable for each bus stop on account of optimal departure frequency. From a systematic perspective, an optimization model considering both bus stop and route was presented [25].Table1 summarizes our literature review for the multidepot VSP. The second and third columns present the objective and characteristics in each paper. The fourth column exhibits the solution approach.Table 1
Literature review for the multidepot vehicle scheduling problem.
Authors (year)
Objective
Characteristics
Solution method
Haghani and Banihashemi (2002)
Solving the possible fuel dissipation constraints
Route time constraints
Decomposition & Heuristic
Ceder (2002, 2005)
Minimum size of the fleet
Extending each trip’s arrival time
DF method
Wagale M (2013)
Optimize the bus scheduling process.
An integrated demand- and travel time responsive model
Sensitivity analysis
Ibarra-Rojas et al. (2014)
Trade-off between the level of service and operating costs
∈-constraint
Linear programming & composition
Schöbel (2017)
Optimizing the whole process
Eigenmodel for the design of reoptimization procedures
Heuristic & Iterative approaches
Liu (2017)
Integrated timetable synchronization and vehicle scheduling problem with transit assignment
A new biobjective, bilevel integer programming model.
Mathematical programming approach & Pareto-efficient solutions
Tang (2018)
Minimum fleet size for single-line
Adjusting variable trips to accommodate different strategies
DF methodology


## 3. Model Formulation

### 3.1. Nomenclature

Consider a directed graphG=N,A with a finite number of nodes N connected by A arcs, which constitutes the connection network. Unless otherwise specified, the notations used in this paper are indicated as follows:R=r: set of PT routesK=k: set of terminals, k∈1,2,…,qI: set of required trips, I∈1,…i,…j,…,npi: departure terminaltsi: departure timeqi: arrival terminaltei: arrival time[T1,T2]: schedule horizonS: timetabled(k,t,S): value of DF for terminal k at time t for schedule SD(k,S): deficit number of vehicles required at terminal kl: l-th peak period from T1 of the DF diagram, l∈1,2,…,n(k)slk: departure time of the l-th peak period at terminal kelk: arrival time of the l-th peak period at terminal kHlk: a hollow interval, defined as the interval between two maximum intervalsMgk: a maximum interval, defined as the interval between two hollow intervalsn(k): total number of maximal intervals in d(k,t)g(t): sum of all DFs at k,g(t)=∑k∈kd(k,t)G: lower bound of the minimum fleet sizeN: number of trip chainswr: expected initial waiting time on route rH: departure intervalP=p: set of number of passengers waiting at a stationM=m: set of number of departurescm: average operating cost per vehicleLr: lower limit of the departure frequencyUr: upper limit of the departure frequencydpk: number of waiting passengers at station kcn: waiting cost per passengerαpk: waiting weight of the passenger at station kθij: 0-1 variable associated with cell (i,j)xmr: 1, if m departures are selected for route r; 0, otherwise.


### 3.2. Deficit Function

The deficit function (DF) was proposed by Ceder and Stern (1981) and Ceder (2016) which is a brief description of a step function method for assigning the least number of vehicles to a given schedule [11, 26]. Gertsbach and Gurevich (1977) referred to this step function as DF, whose value represents the shortage of vehicles required for a specific station involved in a multidepot bus system [27]. The deficit function was also called as a step function that increased by one at the time of each trip departure and decreased by one at the time of each trip arrival. The only information required to build a DF is the driving timetable for each trip of the station. The DF has its appeal in graphical nature and visual simplicity, showing the situation where any station departs and arrives at any operating time which facilitates the operators to make timely vehicle scheduling according to the trips of each station. Let I=i:i=1,…,n denote a set of required trips. The trips are conducted between a set of terminals K=k:k=1,…,q. Each trip is serviced by a single vehicle, and each vehicle is able to service any trip. Each trip i can be represented as a 4-tuple pi,tsi,qi,tei, in which the ordered elements denote departure terminal, departure time, arrival terminal, and arrival time. It is assumed that each trip i lies within a schedule horizon [T1,T2], i.e., T1≤tsi≤tei≤T2. The set of all trips S=pi,tsi,qi,tei,pi,qi∈K,i∈I constitutes the timetable. Let d(k,t,S) denote the DF for terminal k at time t for schedule S. The maximum value of d(k,t,S) over the schedule horizon [T1,T2], designated as D(k,S), depicts the deficit number of vehicles required at k.The description line segment ofd(k,t) is divided into (H0k,M1k,H1k,…,Hlk,Ml+1k,…,Mn(k)k,Hn(k)k), which is the number of intervals consisting of alternating peaks and valleys. It should be noted that when the driving plan is determined, S will be omitted. The peak period Mlk=[slk,elk], l=1,2,…,n(k), represents the maximum value of d(k,t) in the interval, where l denotes the l-th peak period from the left. n(k) denotes the total number of peak hours in d(k,t), slk denotes the time of departure from station k, and elk represents the arrival time of the trip arriving at station k. The only exception is when the deficit function reaches its maximum value at the peak Mn(k)k, no subsequent vehicles arrive at which time en(k)k=T2. The flat peak period Hlk,l=0,1,2,…,n(k), represents the interval of two peak periods, including the first flat peak period H0k=[T1,s1k] from T1 to the first peak starting point and the flat peak period Hn(k)k=enkk,T2 from the end of the last peak to T2.The sum of all DFs overk is defined as the overall DF, g(t)=∑k∈kd(k,t). This function g(t) represents the number of trips that are simultaneously in operation.Theorem 1.
Given a set of stationsK and a fixed set of required trips I, all the trips arrive and departure within the schedule horizon [T1,T2] in the driving plan and do not consider inserting deadheading (DH). Then the minimum number of vehicles required to service all the trips in I is equal to the sum of all the deficits.(1)min⁡N=∑k∈KDk,S=∑k∈Kmaxt∈T1,T2⁡dk,t,SProof.
This theorem is also called as the DF fleet size theorem. A formal proof can be found in the study by Ceder (2016) [11].


### 3.3. Extended Vehicle Scheduling Model Formulation

As shown in the study by Ceder (2016) [11], the expected initial waiting time on route r for randomly arriving passengers can be calculated as (2)wr=EH21+var⁡HE2H,r∈Rwhere E(H) and var⁡H are the mean and variance of the departure interval H between vehicles, respectively.This formula is based on two assumptions:(1)
Passengers can always leave on the first bus (without overload)(2)
The passenger’s random arrival rate at the terminals is independent of the vehicle’s departure rate, which is a constant within a certain periodIn the real traffic, passengers expect more efficient service (e.g., high bus frequency) to reduce the waiting time and improve the in-vehicle comfort. In contrast, bus operators are unwilling to operate the routes with low ridership. They always expect a longer headway to reduce the operating cost. Yet they also need to accommodate the observed passenger demand as well as possible. This article considers the interests of both the bus operators and the passengers. On the one hand, the total operating cost related to the fleet size should be reduced. On the other hand, the average passenger waiting time should also be reduced.In the operational system, the operating cost is expressed by the number of vehicles required to complete all trips inI.(3)min⁡Z1=∑r∈RCmxmr(4)∑r∈Rxmr=1where Cm in Eq. (3) represents the operating cost of per kilometer per vehicle, and Eq. (4) indicates that each planned trip can only be completed by one vehicle.The mathematical model contains three groups of constraints, which are the bundle departure constraints, the DF bound constraints, and the fleet size constraints.The first group of constraints are the bundle departure constraints as follows:(5)∑m=LrUrxmr=1,∀r∈RThe number of departures indexm is between Lr and Ur, where Lr (Ur) represents the lower (upper) limit of the departure frequency for a given route r. Then F=Lr,Lr+1,Lr+2,…,Ur-1,Ur holds. This group of constraints guarantee that only one bundle of departures are selected for a given route.The second group of constraints are the vehicle constraints (i.e., the DF bound constraints):(6)dk,t≤Dk,t∈T1,T2,k∈Kwhere d(k,t) is the net value of the number of departures at station k minus the number of arrivals before time t (including t) which is determined by xmr. Therefore, the left side of Eq. (6) is the value of the associated DF at station k at time t. This group of constraints limit the allocation of vehicles and guarantee that the number of vehicles used at a given station k before time t (including t) is less than or equal to the number of vehicles D(k) assigned to station k.The third group of constraints are the resource constraints (i.e., the fleet size constraints):(7)∑k∈KDk≤Nwhere N is the total fleet size which is fixed and known. This group of constraints ensure that the total number of vehicles assigned to all the stations should not exceed the maximum required fleet size.Based on the DF, this paper adjusts the departure time and reduces the passenger waiting times to improve the bus service. The total waiting time is expressed by the product of the number of waiting passengers and the waiting times, namely,(8)min⁡Z2=∑r∈R∑p∈Pwrdpk60cnαpk(9)∑p∈P∑k∈Kαpk=1In Eq. (8), dpk denotes the number of waiting passengers at station k, Cn denotes the waiting cost per passenger, and αpk denotes the waiting weight. Eq. (9) indicates that the total waiting weight is 1.Since objective function components of Eq. (3) and Eq. (8) are all in terms of monetary cost, they can be summed up for the sake of simplicity. The constraints are listed in Eq. (4)-(7) and Eq. (9). Thus, the extended model can be formulated as follows:(10)minZ=∑r∈R∑p∈PCmxmr+wrdpk60cnαpkst.∑r∈Rxmr=1∑m=LrUrxmr=1,r∈Rdk,t≤Dk,t∈T1,T2,k∈K∑k∈KDk≤N∑p∈P∑k∈Kαpk=1where m∈M.In model (10), the proposed minimization model is nonlinear and the objective function is not convex or concave. Thus, this optimization model is difficult to be solved. Some approaches including Branch & Cut, a Column Generation approach, Lagrangian Heuristic, Tabu Search, and Large Neighborhood Search have been presented in recent studies [9]. And there are also some commercially available software packages in the area of transit scheduling, such as AUSTRICS (www.austrics.com.au), HASTUS (www.giro.ca), and ILOG (www.ilog.co.uk), etc. However, these approaches and software packages concentrate primarily on the activities of vehicle and crew scheduling. Moreover, since some of the scheduling problems are oversimplified and decomposed into subproblems, a completely satisfactory or optimal solution is not assured [11]. As introduced in Section 3.2, the deficit function (DF) is a highly informative graphical technique for the problem of finding the least number of vehicles. Therefore, the DF technique is used in this paper.For an optimal timetable with proper route offset times, all the trips, including the empty trips, need to be connected to form a vehicle driving plan (the trip chain or the trip group). The construction of a trip chain can follow two rules: the first-in first-out (FIFO) rule or the trip chain extraction process rule [11, 27]. The FIFO rule only connects two trips that have closest arrival time of a unified station to the departure time until new connections cannot be made. The trip chain extraction process allows an arrival-departure pair to be connected during any given peak period. Arrival-issued trip pairs that have been considered will be deleted. Figure 2 shows an example. For a given driving plan S,d(k,t) at station k has three flat peak periods Hlk(l=0,1,2), and the flat peak period H1k has three arrival trips 1, 2, 3 and departure trips 4, 5, 6. The links established by applying FIFO rules and other possible connections are listed in Figure 2. Then, the number of vehicles D(k,S) can be obtained.Figure 2
An example of building a connection in a flat peak timeH1k.It should be noted that transfers for passengers are not considered in this paper. That is to say, there are no alternative modes for their trips and all the passengers are captive public transport users. Moreover, only the waiting times spent at the beginning station are considered. Transfer is an important issue in the calculation of the waiting cost; thus more models should be presented in future.


## 3.1. Nomenclature

Consider a directed graphG=N,A with a finite number of nodes N connected by A arcs, which constitutes the connection network. Unless otherwise specified, the notations used in this paper are indicated as follows:R=r: set of PT routesK=k: set of terminals, k∈1,2,…,qI: set of required trips, I∈1,…i,…j,…,npi: departure terminaltsi: departure timeqi: arrival terminaltei: arrival time[T1,T2]: schedule horizonS: timetabled(k,t,S): value of DF for terminal k at time t for schedule SD(k,S): deficit number of vehicles required at terminal kl: l-th peak period from T1 of the DF diagram, l∈1,2,…,n(k)slk: departure time of the l-th peak period at terminal kelk: arrival time of the l-th peak period at terminal kHlk: a hollow interval, defined as the interval between two maximum intervalsMgk: a maximum interval, defined as the interval between two hollow intervalsn(k): total number of maximal intervals in d(k,t)g(t): sum of all DFs at k,g(t)=∑k∈kd(k,t)G: lower bound of the minimum fleet sizeN: number of trip chainswr: expected initial waiting time on route rH: departure intervalP=p: set of number of passengers waiting at a stationM=m: set of number of departurescm: average operating cost per vehicleLr: lower limit of the departure frequencyUr: upper limit of the departure frequencydpk: number of waiting passengers at station kcn: waiting cost per passengerαpk: waiting weight of the passenger at station kθij: 0-1 variable associated with cell (i,j)xmr: 1, if m departures are selected for route r; 0, otherwise.


## 3.2. Deficit Function

The deficit function (DF) was proposed by Ceder and Stern (1981) and Ceder (2016) which is a brief description of a step function method for assigning the least number of vehicles to a given schedule [11, 26]. Gertsbach and Gurevich (1977) referred to this step function as DF, whose value represents the shortage of vehicles required for a specific station involved in a multidepot bus system [27]. The deficit function was also called as a step function that increased by one at the time of each trip departure and decreased by one at the time of each trip arrival. The only information required to build a DF is the driving timetable for each trip of the station. The DF has its appeal in graphical nature and visual simplicity, showing the situation where any station departs and arrives at any operating time which facilitates the operators to make timely vehicle scheduling according to the trips of each station. Let I=i:i=1,…,n denote a set of required trips. The trips are conducted between a set of terminals K=k:k=1,…,q. Each trip is serviced by a single vehicle, and each vehicle is able to service any trip. Each trip i can be represented as a 4-tuple pi,tsi,qi,tei, in which the ordered elements denote departure terminal, departure time, arrival terminal, and arrival time. It is assumed that each trip i lies within a schedule horizon [T1,T2], i.e., T1≤tsi≤tei≤T2. The set of all trips S=pi,tsi,qi,tei,pi,qi∈K,i∈I constitutes the timetable. Let d(k,t,S) denote the DF for terminal k at time t for schedule S. The maximum value of d(k,t,S) over the schedule horizon [T1,T2], designated as D(k,S), depicts the deficit number of vehicles required at k.The description line segment ofd(k,t) is divided into (H0k,M1k,H1k,…,Hlk,Ml+1k,…,Mn(k)k,Hn(k)k), which is the number of intervals consisting of alternating peaks and valleys. It should be noted that when the driving plan is determined, S will be omitted. The peak period Mlk=[slk,elk], l=1,2,…,n(k), represents the maximum value of d(k,t) in the interval, where l denotes the l-th peak period from the left. n(k) denotes the total number of peak hours in d(k,t), slk denotes the time of departure from station k, and elk represents the arrival time of the trip arriving at station k. The only exception is when the deficit function reaches its maximum value at the peak Mn(k)k, no subsequent vehicles arrive at which time en(k)k=T2. The flat peak period Hlk,l=0,1,2,…,n(k), represents the interval of two peak periods, including the first flat peak period H0k=[T1,s1k] from T1 to the first peak starting point and the flat peak period Hn(k)k=enkk,T2 from the end of the last peak to T2.The sum of all DFs overk is defined as the overall DF, g(t)=∑k∈kd(k,t). This function g(t) represents the number of trips that are simultaneously in operation.Theorem 1.
Given a set of stationsK and a fixed set of required trips I, all the trips arrive and departure within the schedule horizon [T1,T2] in the driving plan and do not consider inserting deadheading (DH). Then the minimum number of vehicles required to service all the trips in I is equal to the sum of all the deficits.(1)min⁡N=∑k∈KDk,S=∑k∈Kmaxt∈T1,T2⁡dk,t,SProof.
This theorem is also called as the DF fleet size theorem. A formal proof can be found in the study by Ceder (2016) [11].


## 3.3. Extended Vehicle Scheduling Model Formulation

As shown in the study by Ceder (2016) [11], the expected initial waiting time on route r for randomly arriving passengers can be calculated as (2)wr=EH21+var⁡HE2H,r∈Rwhere E(H) and var⁡H are the mean and variance of the departure interval H between vehicles, respectively.This formula is based on two assumptions:(1)
Passengers can always leave on the first bus (without overload)(2)
The passenger’s random arrival rate at the terminals is independent of the vehicle’s departure rate, which is a constant within a certain periodIn the real traffic, passengers expect more efficient service (e.g., high bus frequency) to reduce the waiting time and improve the in-vehicle comfort. In contrast, bus operators are unwilling to operate the routes with low ridership. They always expect a longer headway to reduce the operating cost. Yet they also need to accommodate the observed passenger demand as well as possible. This article considers the interests of both the bus operators and the passengers. On the one hand, the total operating cost related to the fleet size should be reduced. On the other hand, the average passenger waiting time should also be reduced.In the operational system, the operating cost is expressed by the number of vehicles required to complete all trips inI.(3)min⁡Z1=∑r∈RCmxmr(4)∑r∈Rxmr=1where Cm in Eq. (3) represents the operating cost of per kilometer per vehicle, and Eq. (4) indicates that each planned trip can only be completed by one vehicle.The mathematical model contains three groups of constraints, which are the bundle departure constraints, the DF bound constraints, and the fleet size constraints.The first group of constraints are the bundle departure constraints as follows:(5)∑m=LrUrxmr=1,∀r∈RThe number of departures indexm is between Lr and Ur, where Lr (Ur) represents the lower (upper) limit of the departure frequency for a given route r. Then F=Lr,Lr+1,Lr+2,…,Ur-1,Ur holds. This group of constraints guarantee that only one bundle of departures are selected for a given route.The second group of constraints are the vehicle constraints (i.e., the DF bound constraints):(6)dk,t≤Dk,t∈T1,T2,k∈Kwhere d(k,t) is the net value of the number of departures at station k minus the number of arrivals before time t (including t) which is determined by xmr. Therefore, the left side of Eq. (6) is the value of the associated DF at station k at time t. This group of constraints limit the allocation of vehicles and guarantee that the number of vehicles used at a given station k before time t (including t) is less than or equal to the number of vehicles D(k) assigned to station k.The third group of constraints are the resource constraints (i.e., the fleet size constraints):(7)∑k∈KDk≤Nwhere N is the total fleet size which is fixed and known. This group of constraints ensure that the total number of vehicles assigned to all the stations should not exceed the maximum required fleet size.Based on the DF, this paper adjusts the departure time and reduces the passenger waiting times to improve the bus service. The total waiting time is expressed by the product of the number of waiting passengers and the waiting times, namely,(8)min⁡Z2=∑r∈R∑p∈Pwrdpk60cnαpk(9)∑p∈P∑k∈Kαpk=1In Eq. (8), dpk denotes the number of waiting passengers at station k, Cn denotes the waiting cost per passenger, and αpk denotes the waiting weight. Eq. (9) indicates that the total waiting weight is 1.Since objective function components of Eq. (3) and Eq. (8) are all in terms of monetary cost, they can be summed up for the sake of simplicity. The constraints are listed in Eq. (4)-(7) and Eq. (9). Thus, the extended model can be formulated as follows:(10)minZ=∑r∈R∑p∈PCmxmr+wrdpk60cnαpkst.∑r∈Rxmr=1∑m=LrUrxmr=1,r∈Rdk,t≤Dk,t∈T1,T2,k∈K∑k∈KDk≤N∑p∈P∑k∈Kαpk=1where m∈M.In model (10), the proposed minimization model is nonlinear and the objective function is not convex or concave. Thus, this optimization model is difficult to be solved. Some approaches including Branch & Cut, a Column Generation approach, Lagrangian Heuristic, Tabu Search, and Large Neighborhood Search have been presented in recent studies [9]. And there are also some commercially available software packages in the area of transit scheduling, such as AUSTRICS (www.austrics.com.au), HASTUS (www.giro.ca), and ILOG (www.ilog.co.uk), etc. However, these approaches and software packages concentrate primarily on the activities of vehicle and crew scheduling. Moreover, since some of the scheduling problems are oversimplified and decomposed into subproblems, a completely satisfactory or optimal solution is not assured [11]. As introduced in Section 3.2, the deficit function (DF) is a highly informative graphical technique for the problem of finding the least number of vehicles. Therefore, the DF technique is used in this paper.For an optimal timetable with proper route offset times, all the trips, including the empty trips, need to be connected to form a vehicle driving plan (the trip chain or the trip group). The construction of a trip chain can follow two rules: the first-in first-out (FIFO) rule or the trip chain extraction process rule [11, 27]. The FIFO rule only connects two trips that have closest arrival time of a unified station to the departure time until new connections cannot be made. The trip chain extraction process allows an arrival-departure pair to be connected during any given peak period. Arrival-issued trip pairs that have been considered will be deleted. Figure 2 shows an example. For a given driving plan S,d(k,t) at station k has three flat peak periods Hlk(l=0,1,2), and the flat peak period H1k has three arrival trips 1, 2, 3 and departure trips 4, 5, 6. The links established by applying FIFO rules and other possible connections are listed in Figure 2. Then, the number of vehicles D(k,S) can be obtained.Figure 2
An example of building a connection in a flat peak timeH1k.It should be noted that transfers for passengers are not considered in this paper. That is to say, there are no alternative modes for their trips and all the passengers are captive public transport users. Moreover, only the waiting times spent at the beginning station are considered. Transfer is an important issue in the calculation of the waiting cost; thus more models should be presented in future.


## 4. Solution Method

### 4.1. Deadheading (DH)

Regional bus cross-line scheduling can be divided into two types: interstation scheduling and intrastation scheduling. To optimize the cross-line scheduling, some driving directions can be inserted into the schedule based on DF, and a more scientific scheduling plan can be formulated. The deadheading (DH) is a type of nonpassenger bus which is inserted into the driving plan and runs between two stations. Its insertion can effectively improve the utilization of the operating vehicles. A dispatch with idle time and the empty travel distance being zero can be regarded as DH. However, the reliability of a vehicle may be reduced. Therefore, to ensure smooth transition between the operating vehicles, path and time must be fully considered before inserting the DH trip.When a DH trip is allowed, the minimum fleet size is determined by the maximum number of the operating vehicles:(11)G=maxt∈T1,T2⁡gt≤∑k∈Kmaxt∈T1,T2⁡dk,t=min⁡NMore details can be found in the study by Ceder (2016) [11].IfG≤Nmin, a DH insertion can further reduce the fleet size, and if G=Nmin, the fleet size reaches the minimum. The DH insertion process can be performed in an interactive mode based on the dispatchers’ actual considerations or in an automatic mode using a computer program.Figure3 illustrates the process of the DH insertion taking a three-trip, two-terminal network for example. Two vehicles are required at the terminal a while no vehicle is required at the terminal b. The black arrows in Figure 3 represent the DH1 insertion trip from b to a and the DH2 trip from a to b. The red dotted line indicates the optimized DFs after inserting these two DH trips. Results show that the number of vehicles required at a is reduced by one. And the sum of all DFs is D(S)=1.Figure 3
An example of the DH trips.


### 4.2. Shifting Departure Time (SDT)

The small adjustment of the departure times in the driving schedule can make it possible to further reduce the fleet size and the passenger waiting cost. Shifting departure time (SDT) implicates that, for each stop and each two timest1 and t2(t1<t2), the minimum number of vehicles required to complete all the trips in a timetable is equal to the sum of all the DFs. Therefore, in the DF diagram, the process of eliminating peaks is to reduce the fleet size. Attempts are made to shift the departure times (offset times) of all vehicles arriving at t1 so that they can arrive at t2. If SDT is successfully shifted, the timetable will be changed accordingly and the passenger waiting times may be reduced.However, failure SDT may lead to unbalanced loads, including overcrowding or empty, or bus bunching. Therefore, an experienced operator should be performed very carefully with the help of the DF diagram. See the study by Ceder (2002) for details [19].This paper harmonizes the vehicles’ departure times with the passengers’ waiting demands. Let[ti-Δi(-),ti+Δi(+)] denote the interval in which the departure time of trip i can be adjusted. Δi(-) (Δi(+)) denotes the maximum advance (delay) of the departure time. Figure 4 illustrates an example with a simple two-terminal, four-trip network. The fleet size reduces by using the SDT technique. The tolerance ranges are set to be Δi(-)=Δi(+)=±15min for all the trips in the schedule. Results show that to shift trip 3 backwards can reduce the number of vehicles required at station a from 3 to 2. The sum of all DFs is D(S)=3. And the red dotted line in Figure 4 depicts the optimized DF graph.Figure 4
An example of the SDT process.


### 4.3. Network Flow Technique for Vehicle Scheduling

The network flow technique is used to estimate the minimum fleet size for a given scheduleS. The i-th row represents the arrival event of trip i, and the j-th column represents the departure event of trip j. Related i-row and j-columns constitute the trip connection array. If the connection of i and j is feasible, cell (i,j) is an allowable connection; otherwise, cell (i,j) is unallowable. Let θij be a binary variable associated with cell (i,j), and the following questions are considered:(12)maxZ=∑i∈I∑j∈Jθijst.∑j∈Jθij≤1,i∈I∑i∈Iθij≤1,j∈Iθij=1,alli,jareadmissibleθij=0,alli,jareinadmissiblewhere θij=1 indicates that trips i and j are connected. The objective function is to maximize the connection numbers. And the first constraint ensures that each trip can be connected to no more than one successor trip. Similarly, the second constraint represents the previous trip connection for each trip with no more than one time. This problem can be thought as a special case in the maximum flow problem. The maximum flow algorithm through the DH trips in the vehicle scheduling problem (VSP) is called the augmenting path algorithm. Fulkerson (1962) [28] and Ceder (2016) [11] elaborated on this algorithm. The VSP can be transformed into a two-part network with unit capacity, where the time complexity of the solution is O(n1/2m) with n nodes (departure time) and m arcs. The following theorem shows that to maximize N of the objective function in model (12) is equivalent to minimizing the trip chains formed by n trips.Theorem 2 (maximum flow fleet theorem).
LetN and n denote the trip chain and the number of vehicles, respectively; then(13)min⁡N=n-max⁡ZProof.
GivenI=i:i=1,…,n, each trip is assigned to n vehicles. If xij=1, trip j can be performed by the same vehicle after trip i. Thus, the vehicle assigned to trip j is retained. The required fleet size can be reduced from n to n-1. Similarly, the maximum flow Zmax can be saved by linking the trips together. Therefore, the minimum fleet size required to perform all the trips in I is n-max⁡Z, and the proof is completed.


### 4.4. Overall Solution Procedure

An overview of the solution procedure is outlined as follows:Step 1.
Apply the network flow technique to obtain an initial number of vehicles required for a given timetableS.Step 2.
Use the DF method with graphical features to depict the number of vehicles required at each station. Calculate the DF for eachdk,t,S, and calculate the sum of the DFs D(S).Step 3.
Use the SDT procedure to modify the route offset times.Step 4.
Insert DH trips to reduce the idle times of vehicles and further reduce the fleet size.Step 5.
Compare the operating cost and the passenger waiting cost.


## 4.1. Deadheading (DH)

Regional bus cross-line scheduling can be divided into two types: interstation scheduling and intrastation scheduling. To optimize the cross-line scheduling, some driving directions can be inserted into the schedule based on DF, and a more scientific scheduling plan can be formulated. The deadheading (DH) is a type of nonpassenger bus which is inserted into the driving plan and runs between two stations. Its insertion can effectively improve the utilization of the operating vehicles. A dispatch with idle time and the empty travel distance being zero can be regarded as DH. However, the reliability of a vehicle may be reduced. Therefore, to ensure smooth transition between the operating vehicles, path and time must be fully considered before inserting the DH trip.When a DH trip is allowed, the minimum fleet size is determined by the maximum number of the operating vehicles:(11)G=maxt∈T1,T2⁡gt≤∑k∈Kmaxt∈T1,T2⁡dk,t=min⁡NMore details can be found in the study by Ceder (2016) [11].IfG≤Nmin, a DH insertion can further reduce the fleet size, and if G=Nmin, the fleet size reaches the minimum. The DH insertion process can be performed in an interactive mode based on the dispatchers’ actual considerations or in an automatic mode using a computer program.Figure3 illustrates the process of the DH insertion taking a three-trip, two-terminal network for example. Two vehicles are required at the terminal a while no vehicle is required at the terminal b. The black arrows in Figure 3 represent the DH1 insertion trip from b to a and the DH2 trip from a to b. The red dotted line indicates the optimized DFs after inserting these two DH trips. Results show that the number of vehicles required at a is reduced by one. And the sum of all DFs is D(S)=1.Figure 3
An example of the DH trips.


## 4.2. Shifting Departure Time (SDT)

The small adjustment of the departure times in the driving schedule can make it possible to further reduce the fleet size and the passenger waiting cost. Shifting departure time (SDT) implicates that, for each stop and each two timest1 and t2(t1<t2), the minimum number of vehicles required to complete all the trips in a timetable is equal to the sum of all the DFs. Therefore, in the DF diagram, the process of eliminating peaks is to reduce the fleet size. Attempts are made to shift the departure times (offset times) of all vehicles arriving at t1 so that they can arrive at t2. If SDT is successfully shifted, the timetable will be changed accordingly and the passenger waiting times may be reduced.However, failure SDT may lead to unbalanced loads, including overcrowding or empty, or bus bunching. Therefore, an experienced operator should be performed very carefully with the help of the DF diagram. See the study by Ceder (2002) for details [19].This paper harmonizes the vehicles’ departure times with the passengers’ waiting demands. Let[ti-Δi(-),ti+Δi(+)] denote the interval in which the departure time of trip i can be adjusted. Δi(-) (Δi(+)) denotes the maximum advance (delay) of the departure time. Figure 4 illustrates an example with a simple two-terminal, four-trip network. The fleet size reduces by using the SDT technique. The tolerance ranges are set to be Δi(-)=Δi(+)=±15min for all the trips in the schedule. Results show that to shift trip 3 backwards can reduce the number of vehicles required at station a from 3 to 2. The sum of all DFs is D(S)=3. And the red dotted line in Figure 4 depicts the optimized DF graph.Figure 4
An example of the SDT process.


## 4.3. Network Flow Technique for Vehicle Scheduling

The network flow technique is used to estimate the minimum fleet size for a given scheduleS. The i-th row represents the arrival event of trip i, and the j-th column represents the departure event of trip j. Related i-row and j-columns constitute the trip connection array. If the connection of i and j is feasible, cell (i,j) is an allowable connection; otherwise, cell (i,j) is unallowable. Let θij be a binary variable associated with cell (i,j), and the following questions are considered:(12)maxZ=∑i∈I∑j∈Jθijst.∑j∈Jθij≤1,i∈I∑i∈Iθij≤1,j∈Iθij=1,alli,jareadmissibleθij=0,alli,jareinadmissiblewhere θij=1 indicates that trips i and j are connected. The objective function is to maximize the connection numbers. And the first constraint ensures that each trip can be connected to no more than one successor trip. Similarly, the second constraint represents the previous trip connection for each trip with no more than one time. This problem can be thought as a special case in the maximum flow problem. The maximum flow algorithm through the DH trips in the vehicle scheduling problem (VSP) is called the augmenting path algorithm. Fulkerson (1962) [28] and Ceder (2016) [11] elaborated on this algorithm. The VSP can be transformed into a two-part network with unit capacity, where the time complexity of the solution is O(n1/2m) with n nodes (departure time) and m arcs. The following theorem shows that to maximize N of the objective function in model (12) is equivalent to minimizing the trip chains formed by n trips.Theorem 2 (maximum flow fleet theorem).
LetN and n denote the trip chain and the number of vehicles, respectively; then(13)min⁡N=n-max⁡ZProof.
GivenI=i:i=1,…,n, each trip is assigned to n vehicles. If xij=1, trip j can be performed by the same vehicle after trip i. Thus, the vehicle assigned to trip j is retained. The required fleet size can be reduced from n to n-1. Similarly, the maximum flow Zmax can be saved by linking the trips together. Therefore, the minimum fleet size required to perform all the trips in I is n-max⁡Z, and the proof is completed.


## 4.4. Overall Solution Procedure

An overview of the solution procedure is outlined as follows:Step 1.
Apply the network flow technique to obtain an initial number of vehicles required for a given timetableS.Step 2.
Use the DF method with graphical features to depict the number of vehicles required at each station. Calculate the DF for eachdk,t,S, and calculate the sum of the DFs D(S).Step 3.
Use the SDT procedure to modify the route offset times.Step 4.
Insert DH trips to reduce the idle times of vehicles and further reduce the fleet size.Step 5.
Compare the operating cost and the passenger waiting cost.


## 5. Numerical Study Applied to Beijing PT Network

### 5.1. Data Collection

City bus in Beijing is the most widely used and affordable amongst all means of public transportation, although it can be very crowded and may meet a traffic jam. In 2016, the entire public bus network has 876 routes with 22688 buses [2]. Since 2013, in an effort to reduce urban air pollution, Beijing has been converting regular bus routes to trolleybus routes by installing overhead power lines on several corridors. Public bus service in the city began in 1921. Today there are two operators. The city’s primary public bus operator, the state-owned Beijing Public Transport Holdings, Ltd., operates most routes and the Beijing Xianglong Bus Co., Ltd., an independent operator, provides service on 32 Yuntong bus routes [2].Public buses are identified either by numbers or by Chinese characters. Lines 1-751 are downtown regular ones and bus routes are mostly in the city’s urban core district. They start running at 05:00-05:30 and stop at 22:00-23:00.Public transport along Chang’an Avenue, a major thoroughfare in Beijing, China, was selected for data collection during the evening peak hours (17:00-19:30 pm). We recorded the passenger flows generated from these sites. The survey lasted for 2 months from May 2015 to June 2015, and more than 30 undergraduate students were recruited. Direct observation and video tape recording were simultaneously employed. Moreover, bus smart card data were obtained from a bus company. All field works were finished on weekdays with good weather conditions.Three bus lines including lines 1, 57, and 52 are selected since they all belong to the same bus company. Among them, Line 1 is one of the busiest bus routes in Beijing and is known as “the city boat on Chang’an Street.” Moreover, overlapped or parallel routes help to reschedule vehicles, as shown in Figure5. The first and last stations of Line 1 are Laoshan Bus Station (a) and Sihui Hub Station (b). And the first and last stations of Line 57 are Sihui Hub Station (b) and Dianchang Village Station (c). The first and last stations of Line 52 are Dianchang Village Station (c) and Peace Park Station (d). The lengths of lines 1, 57, and 52 are 25.31km, 23.5km, and 22.0km, respectively.Figure 5
Bus routes of Line1, Line 57, and Line 52.The schedulesS between 17:00 and 19:00 with the four terminals (a, b, c, d) were collected. A 20-trip schedule is shown in Table 2. The passenger demands at the four terminals are shown in Table 3 and the average DH travel times for all trips are shown in Table 4.Table 2
A 20-trip schedule with the four terminals.
Trip Number
Route
Departure time
Arrival time
1
a-b
17:03
17:43
2
a-b
17:15
17:55
3
a-b
17:18
17:58
4
a-b
17:22
18:02
5
a-b
17:40
18:20
6
a-b
17:55
18:35
7
a-b
18:03
18:43
8
a-b
18:20
19:00
9
a-b
18:25
19:05
10
a-b
18:47
19:23
11
b-a
17:20
18:00
12
b-a
17:35
18:15
13
b-a
17:50
18:30
14
b-a
18:00
18:40
15
b-a
18:15
18:55
16
b-a
18:32
19:12
17
b-a
18:45
19:25
18
c-b
17:00
18:00
19
c-b
17:13
18:13
20
c-b
17:20
18:20Table 3
Passenger demands at the four terminals.
Time
Terminal
a
b
c
d
17:00-18:00
294
153
297
72
18:00-19:00
293
115
238
46
Total
587
268
535
118Table 4
Average DH travel time (minutes) matrix.
DH Trip
a-b
b-c
c-d
DH Time (minute)
18
20
25It is assumed that passengers will board the first feasible transfer connecting trip (i.e., the vehicle capacity is sufficient). And the waiting weights at the four terminals are assumed to be equal. Namely,αpa=0.25, αpb=0.25, αpc=0.25, and αpd=0.25 hold. Other data are from the field surveys of previous studies [29–31] or the government report [32]. The waiting cost of each passenger Cn is assumed to be 25 yuan/h (Cn=25) [29]. The operating cost of each vehicle Cm is 1.4 yuan/km (Cm=1.4) [30, 31]. According to the government report [32], the average bus speed in Beijing is 22 km/h and the average bus operating cost is 50 yuan/h during evening peak hours.


### 5.2. Results

Based on the data in Table2, the DF technology can be used to obtain the required fleet size for each terminal. As shown in the blue solid line ladder diagram in Figure 6, the initial DF values of the four terminals a, b, c, and d are, respectively, d(a,t)=7, d(b,t)=7, d(c,t)=9, and d(d,t)=5. Then the minimum number of vehicles required to complete all the trips is equal to the sum of all the maximum inverse differences, i.e., min⁡N=∑k∈Kmaxt∈[17:00,19:00]⁡d(k,t)=28. Figure 7 shows the number of vehicles operating simultaneously for the four lines. The lower limit of the number of vehicles required for the four stations is G=maxt∈[17:00,19:00]⁡g(t)=26. According to Eq. (11), G=maxt∈[17:00,19:00]⁡g(t)=26, and the fleet size can be further reduced.Figure 6
DF values at four terminals.Figure 7
Sum of deficit functions (of vehicles in service).Since the passenger waiting time is very critical to judge the bus service, this paper makes endeavor to keep it within 20 minutes. The DH trips are inserted to reduce the fleet size. As shown in Figure6, the insertion of the DH trips reduces the peak of the solid line diagram. The passengers waiting at a station are assumed to be not affected by the adjustment of the departure time. The time for the 39th trip to the right is 14min, and the range for the left/right adjustment for other adjustments is 8min, i.e., Δ=±8min. The number of the vehicles for adjusting the departure time is shown in Table 5 and the time to insert a DH trip is shown in Table 6.Table 5
SDT for the twelve trips.
Trip No.
Travel Route
Original Time
Time After SDT
Departure time
Arrival time
Departure time
Arrival time
10
a-b
18:47
19:23
18:45
19:25
12
b-a
17:35
18:15
17:43
18:23
31
b-c
17:54
18:54
17:55
18:55
13
b-a
17:50
18:30
17:58
18:38
39
c-d
17:46
18:36
18:00
18:50
24
c-b
18:05
19:05
18:10
19:10
32
b-c
18:05
19:05
18:13
19:13
15
b-a
18:15
18:55
18:20
19:00
41
c-d
18:18
19:08
18:25
19:15
26
c-b
18:30
19:30
18:34
19:34
48
d-c
17:47
18:37
17:55
0:00
49
d-c
18:13
19:03
18:15
0:00Table 6
Timetable for inserting DH trips.
DH Trip
Travel Route
Departure time
Arrival time
DH
b-a
18:02
18:20In Figure6, the red dotted line indicates the DF step diagram after the insertion of DH and SDT. The arrow from station b to station a indicates the inserted DH. The optimized DF values for the four terminals are d(a,t)∗=6, d(b,t)∗=5, d(c,t)∗=8, and d(d,t)∗=5, respectively. The minimum number of vehicles required to complete all the trips in the driving plan is equal to the sum of all maximum inverse differences, i.e., N∗=∑k∈Kmaxt∈[17:00,19:00]⁡d(k,t)∗=24. Figure 8 shows the number of vehicles operating at the same time in the regional bus network of the four lines. The lower limit of the number of vehicles required for the four stations is G∗=maxt∈[17:00,19:00]⁡g(t)=24. According to Eq. (11), G∗=N∗ holds, so it is impossible to reduce the fleet size by inserting empty buses. Meanwhile, by adjusting the departure time of some buses, the passenger’s waiting time is controlled within 20 minutes to improve the bus service.Figure 8
Sum of deficit functions after inserting DH and SDT.Before the SDT and the DH processes, the fleet size was 28 and the target function value was 2154.57. Considering the passenger waiting cost, the departure times of some buses are adjusted and one empty bus is inserted. The fleet size reduces to 24, and the objective function value becomes 1793.22, which has saved 16.90%.


## 5.1. Data Collection

City bus in Beijing is the most widely used and affordable amongst all means of public transportation, although it can be very crowded and may meet a traffic jam. In 2016, the entire public bus network has 876 routes with 22688 buses [2]. Since 2013, in an effort to reduce urban air pollution, Beijing has been converting regular bus routes to trolleybus routes by installing overhead power lines on several corridors. Public bus service in the city began in 1921. Today there are two operators. The city’s primary public bus operator, the state-owned Beijing Public Transport Holdings, Ltd., operates most routes and the Beijing Xianglong Bus Co., Ltd., an independent operator, provides service on 32 Yuntong bus routes [2].Public buses are identified either by numbers or by Chinese characters. Lines 1-751 are downtown regular ones and bus routes are mostly in the city’s urban core district. They start running at 05:00-05:30 and stop at 22:00-23:00.Public transport along Chang’an Avenue, a major thoroughfare in Beijing, China, was selected for data collection during the evening peak hours (17:00-19:30 pm). We recorded the passenger flows generated from these sites. The survey lasted for 2 months from May 2015 to June 2015, and more than 30 undergraduate students were recruited. Direct observation and video tape recording were simultaneously employed. Moreover, bus smart card data were obtained from a bus company. All field works were finished on weekdays with good weather conditions.Three bus lines including lines 1, 57, and 52 are selected since they all belong to the same bus company. Among them, Line 1 is one of the busiest bus routes in Beijing and is known as “the city boat on Chang’an Street.” Moreover, overlapped or parallel routes help to reschedule vehicles, as shown in Figure5. The first and last stations of Line 1 are Laoshan Bus Station (a) and Sihui Hub Station (b). And the first and last stations of Line 57 are Sihui Hub Station (b) and Dianchang Village Station (c). The first and last stations of Line 52 are Dianchang Village Station (c) and Peace Park Station (d). The lengths of lines 1, 57, and 52 are 25.31km, 23.5km, and 22.0km, respectively.Figure 5
Bus routes of Line1, Line 57, and Line 52.The schedulesS between 17:00 and 19:00 with the four terminals (a, b, c, d) were collected. A 20-trip schedule is shown in Table 2. The passenger demands at the four terminals are shown in Table 3 and the average DH travel times for all trips are shown in Table 4.Table 2
A 20-trip schedule with the four terminals.
Trip Number
Route
Departure time
Arrival time
1
a-b
17:03
17:43
2
a-b
17:15
17:55
3
a-b
17:18
17:58
4
a-b
17:22
18:02
5
a-b
17:40
18:20
6
a-b
17:55
18:35
7
a-b
18:03
18:43
8
a-b
18:20
19:00
9
a-b
18:25
19:05
10
a-b
18:47
19:23
11
b-a
17:20
18:00
12
b-a
17:35
18:15
13
b-a
17:50
18:30
14
b-a
18:00
18:40
15
b-a
18:15
18:55
16
b-a
18:32
19:12
17
b-a
18:45
19:25
18
c-b
17:00
18:00
19
c-b
17:13
18:13
20
c-b
17:20
18:20Table 3
Passenger demands at the four terminals.
Time
Terminal
a
b
c
d
17:00-18:00
294
153
297
72
18:00-19:00
293
115
238
46
Total
587
268
535
118Table 4
Average DH travel time (minutes) matrix.
DH Trip
a-b
b-c
c-d
DH Time (minute)
18
20
25It is assumed that passengers will board the first feasible transfer connecting trip (i.e., the vehicle capacity is sufficient). And the waiting weights at the four terminals are assumed to be equal. Namely,αpa=0.25, αpb=0.25, αpc=0.25, and αpd=0.25 hold. Other data are from the field surveys of previous studies [29–31] or the government report [32]. The waiting cost of each passenger Cn is assumed to be 25 yuan/h (Cn=25) [29]. The operating cost of each vehicle Cm is 1.4 yuan/km (Cm=1.4) [30, 31]. According to the government report [32], the average bus speed in Beijing is 22 km/h and the average bus operating cost is 50 yuan/h during evening peak hours.


## 5.2. Results

Based on the data in Table2, the DF technology can be used to obtain the required fleet size for each terminal. As shown in the blue solid line ladder diagram in Figure 6, the initial DF values of the four terminals a, b, c, and d are, respectively, d(a,t)=7, d(b,t)=7, d(c,t)=9, and d(d,t)=5. Then the minimum number of vehicles required to complete all the trips is equal to the sum of all the maximum inverse differences, i.e., min⁡N=∑k∈Kmaxt∈[17:00,19:00]⁡d(k,t)=28. Figure 7 shows the number of vehicles operating simultaneously for the four lines. The lower limit of the number of vehicles required for the four stations is G=maxt∈[17:00,19:00]⁡g(t)=26. According to Eq. (11), G=maxt∈[17:00,19:00]⁡g(t)=26, and the fleet size can be further reduced.Figure 6
DF values at four terminals.Figure 7
Sum of deficit functions (of vehicles in service).Since the passenger waiting time is very critical to judge the bus service, this paper makes endeavor to keep it within 20 minutes. The DH trips are inserted to reduce the fleet size. As shown in Figure6, the insertion of the DH trips reduces the peak of the solid line diagram. The passengers waiting at a station are assumed to be not affected by the adjustment of the departure time. The time for the 39th trip to the right is 14min, and the range for the left/right adjustment for other adjustments is 8min, i.e., Δ=±8min. The number of the vehicles for adjusting the departure time is shown in Table 5 and the time to insert a DH trip is shown in Table 6.Table 5
SDT for the twelve trips.
Trip No.
Travel Route
Original Time
Time After SDT
Departure time
Arrival time
Departure time
Arrival time
10
a-b
18:47
19:23
18:45
19:25
12
b-a
17:35
18:15
17:43
18:23
31
b-c
17:54
18:54
17:55
18:55
13
b-a
17:50
18:30
17:58
18:38
39
c-d
17:46
18:36
18:00
18:50
24
c-b
18:05
19:05
18:10
19:10
32
b-c
18:05
19:05
18:13
19:13
15
b-a
18:15
18:55
18:20
19:00
41
c-d
18:18
19:08
18:25
19:15
26
c-b
18:30
19:30
18:34
19:34
48
d-c
17:47
18:37
17:55
0:00
49
d-c
18:13
19:03
18:15
0:00Table 6
Timetable for inserting DH trips.
DH Trip
Travel Route
Departure time
Arrival time
DH
b-a
18:02
18:20In Figure6, the red dotted line indicates the DF step diagram after the insertion of DH and SDT. The arrow from station b to station a indicates the inserted DH. The optimized DF values for the four terminals are d(a,t)∗=6, d(b,t)∗=5, d(c,t)∗=8, and d(d,t)∗=5, respectively. The minimum number of vehicles required to complete all the trips in the driving plan is equal to the sum of all maximum inverse differences, i.e., N∗=∑k∈Kmaxt∈[17:00,19:00]⁡d(k,t)∗=24. Figure 8 shows the number of vehicles operating at the same time in the regional bus network of the four lines. The lower limit of the number of vehicles required for the four stations is G∗=maxt∈[17:00,19:00]⁡g(t)=24. According to Eq. (11), G∗=N∗ holds, so it is impossible to reduce the fleet size by inserting empty buses. Meanwhile, by adjusting the departure time of some buses, the passenger’s waiting time is controlled within 20 minutes to improve the bus service.Figure 8
Sum of deficit functions after inserting DH and SDT.Before the SDT and the DH processes, the fleet size was 28 and the target function value was 2154.57. Considering the passenger waiting cost, the departure times of some buses are adjusted and one empty bus is inserted. The fleet size reduces to 24, and the objective function value becomes 1793.22, which has saved 16.90%.


## 6. Conclusion and Further Studies

This work develops a methodology for the multidepot vehicle scheduling problem considering the passenger waiting cost. The purpose of this methodology is to minimize the fleet size and reduce the passenger waiting times. The deficit function (DF) approach is applied to realize the shifting departure time (SDT) and the deadheading (DH) to minimize the fleet size. An optimization function is introduced to minimize both the bus operating cost and the passenger waiting cost. Finally, this methodology is applied to a PT network in Beijing, China. Results show that the total cost can be reduced by 16.90% compared with the current timetables.A limitation in this study is need of more accurate calculations of time-dependent passenger demands, which have important impacts on the vehicle scheduling optimization. With the development of modern technology, real-time passenger information is easily obtained and collected. The mobile phone can be used as a tracking device, which can be used to query the line, the vehicle arrival times, and the vehicle locations, etc. It can also collect the passenger’s precise origin-destination information to evaluate the passenger’s path selection preferences. In addition, the following studies are advised:(a) Studying more accurate weight factors for passengersαpk(k=a,b,c,d), since PT users have different travel components of their trip(b) Investigating the effect of different vehicle size to meet the needs of passengers at different departure times(c) Considering transfers for passengers in their trips(d) If large-size vehicles are allowed to operate on those trips designed for small vehicles, the fleet size can be reduced. This problem also involves issues such as departure intervals and operating costs, which need to be further discussed in detail in subsequent studies



---

*Source: 4212631-2019-05-02.xml*