# Mathematical Analysis and an Exact Solution Combined with Preprocessing Method for Resynchronizing of Bus Timetable Problem

Authors: Yinghui Wu; Yifan Zhu; Tianyu Cao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Bus timetabling is a subproblem of bus network planning, and it determines departure time of each trip of lines to make vehicles from different lines synchronously arrive at transfer stations. Due to the well-designed coordination of bus timetables, passengers can make a smooth transfer without waiting a long time for connecting buses. This paper addresses the planning level of resynchronizing of bus timetable problem allowing modifications to initial timetable. Timetable modifications consist of shifts in the departure times and headways. A single-objective mixed-integer programming model is proposed for this problem to maximize the number of total transferring passengers benefiting from smooth transfers. We analyze the mathematical properties of this model, and then a preprocessing method is designed to reduce the solution space of the proposed model. The numerical results show that the reduced model is effectively solved by branch and bound algorithm, and the preprocessing method has the potential to be applied for large-scale bus networks.


---

## Body

## 1. Introduction

Bus network planning has been known for long as a complex problem including several subproblems, i.e., line planning, timetable design, vehicle scheduling, and crew scheduling [1–3]. The bus timetabling is a principal stage, and it determines the departure time of each trip of all lines in the bus network in order to maximize the service quality of bus transit system [4].With a synchronized bus timetable, passengers can immediately transfer to another line after getting down from the feeder line at stations. However, if the bus network timetable is not well synchronized, passengers have to wait longer for the connecting bus when they get down from the feeder line [5]. A well-designed bus timetable with good coordination of bus departure times at transfer stations is very important for the bus operation attracting more travelers choosing transit service. In China, line-by-line timetabling approach is often used to generate bus network timetables. This method does not consider the synchronization of bus departure times among different lines at the same transfer station. In order to provide bus schedule coordination service, schedulers intend to synchronize timetables of different lines at the transfer nodes to facilitate passengers transferring by slightly modifying the departure times and headways of initial bus timetable. Regarding this situation, this paper addresses the planning level of BSC problem through small timetable modifications to given an initial timetable. Timetable modifications consist of shifts in initial departure times of vehicles from the depot. Headway-sensitive passenger demand is also considered in this problem.In the literature, several studies have proposed solutions to the synchronization of bus timetabling (SBT) problem to maximize the number of synchronized bus arrivals at transfer nodes [6–8]. For instance, Ibarra-Rojas et al. [8] extended the work of Ceder et al. [6] and Eranki [7] to address a flexible SBT problem with oriented synchronization, almost evenly spaced departures and preventing bus bunching. Shafahi and Khani [9], and Cevallos and Zhao [10] focused on constant headways in the SBT problem to minimize the total transfer waiting time experienced by passengers. Mollanejad et al. [11] developed a MIP model for the SBT problem with uneven headways and trips before and after a planning horizon. Parbo et al. [12] studied a bilevel timetable optimization problem, aimed at minimizing the weighted transfer waiting time. Wu Y. et al. [13] studied a stochastic version of SBT. Slack time was inserted into the timetable to mitigate the randomness of travel times to reduce the rate of transfer failures. A recent paper studied by Wu et al. [14] used integrated real-time holding control and slacks to improve the reliability and efficiency of schedule coordination. Tilahun and Ong [15] formulated bus timetabling just for single frequency routes not multiple trips for each route. A fuzzy multiobjective optimization model was formulated and solved using preference-based genetic algorithm by assigning appropriate fuzzy preference to the need of the customers.Timetable coordination of railway network was also studied to minimize the waiting time cost (or reduce the chances of missing the connecting trains) of passengers. Wong et al. [16] investigated the synchronization of railway timetabling problem to minimize the total transfer waiting time by adjusting train’s run times and dwell times at stations. In the case of high-speed rail lines under given time-dependent origin-destination demand, Niu et al. [17] proposed a synchronization approach for the train schedule. Wang et al. [18] proposed an event-driven model for the train-scheduling problem with the consideration of time-varying passenger demand. Kang et al. [19–21] focused on the coordination of last trains aimed at reducing the number of cases in which passengers miss the connecting trains within one headway time. Meanwhile, Kang et al. [22] and Guo et al. [23] proposed the timetable coordination of first trains for the railway network of Beijing. A multiperiod timetabling problem for metro transit networks was studied by Guo et al. [24], in which passenger travel demand varies in the transitional period.The above-mentioned papers of timetable synchronization issues mainly focused on designing a new timetable for the transit network studied. However, large deviations from the initial timetable destroy regular timetable service and following vehicle and crew scheduling plan [3]. Recently, Wu Y. et al. [25] studied the biobjective resynchronizing of bus timetable problem with the consideration of impact on the initial timetable and proposed a nondominated sorting genetic based algorithm to solve this problem, not an exact solution.Compared to the above papers, the main contributions of this paper are as follows:(1) A resynchronizing of bus timetable (SRSBT) problem that allowing modifications to the initial timetable in tactical planning level is proposed. Timetable modifications consist of shifts in the departure times and headways. And, headway-sensitive passenger demand was also considered in the proposed problem. (2) We formulate this problem as a single-objective mixed-integer programming model maximizing the number of total transferring passengers benefiting from smooth transfers. The mathematical properties of this model were analyzed. (3) Based on these properties of the model, we design a preprocessing method to reduce the solution space of the proposed model, which means that large-scale SRSBT problems can be solved by an exact solution combined with the preprocessing method. For small-cases study, the preprocessing method is effective and reduces the solution spaces of SRSBT model to at least 56%.The remainder of the paper is organized as follows. Section2 formulates the SRSBT problem and explores several properties of the single-objective SRSBT model. Based on the properties of the SRSBT, Section 3 describes the preprocessing method to reduce the solution space. In Section 4, the effectiveness of the preprocessing method is evaluated through small instances. Finally, Section 5 concludes this paper.


## 2. Problem Formulation

In large bus transit systems, passengers often transfer from one bus line to another at a transfer station in order to complete their trips. As an example, Figure1 shows a transfer opportunity between line i and line j, at station b. Passengers are assumed to transfer from an arriving trip of a feeder linei to the first available trip of their desired linej. The transfer opportunity of passengers transferring from trip p of line i to line j depicted in Figure 2 requires a small time, for example, 2 minutes for passengers to disembark the vehicle of trip p and walk to the area for embarking the vehicle of line j. In the current timetable, trip p of line i arrives at 9:30 leaving 10 minutes transfer time to the next departing line j trip q+1 at 9:40, thus resulting in 8 minutes of excess transfer time.Figure 1
Geographic representation of two bus lines, linei and line j, and station b, where passengers can transfer.Figure 2
Example of passenger transfer from tripp of line i to line j at station b under a given timetable.If the departure time of tripq is adjusted from 9:30 to 9:32, the excess transfer time for the trip p of line i would be removed. Figure 3 depicts the change in the departure time of trip q. The modification in the departure time of trip q at the transfer station can be realized by adjusting the departure time trip q from the depot. However, such change in the departure time of trip q could also influence the departure times of other trips of this line due to limited range of headway times (interval of time between two consecutive trips on the same line). Alternatively, the required shift in the departure time of trip can be limited if the trip p of line i would be adjusted to arrive earlier at 9:28 (see Figure 4).Figure 3
Representation of change in the departure time of tripq.Figure 4
Representation of change in the arrival time of tripp.The SRSBT problem is how to modify the departure times and headways in the initial timetable with limited range to maximize the number of passengers benefiting from smooth transfers.


### 2.1. Notations

We introduce notations necessary to formulate the SRSBT problem.Sets I: set of lines in the bus network, i∈I J i: set of lines that have transfer nodes with line i, j∈Ji B i j: set of transfer nodes for line i and j, b∈BijParameters f i: number of trips for line i in the planning period of interest h i: headway of line i in the existing timetable; hi=T/fi,∀i∈I h i m i n: minimum headway of line i allowed for synchronized timetable; himin=hi-δi,∀i∈I h i m a x: maximum headway of line i allowed for synchronized timetable; himax=hi+δi,∀i∈I n ^ i b j: estimated number of passengers, each transferring from line i to line j at transfer node b when the initial timetable is used n i p b j: actual number of passengers benefiting from a smooth transfer for p-th trip of line i to line j at node b when synchronized timetable is used γ: the maximal value of deviation allowed from the departure times T: length of planning period in minutes; the planning period can be standardized as 0,T t i b: travel time from depot of line i to node b in the planning period w b m i n: minimum separation time between synchronized bus arrivals at node b w b m a x: maximum separation time between synchronized bus arrivals at node b x ^ i p: departure time of the p-th trip of line i in the initial timetable; x^ip=p-1hi,∀i∈I,p∈1,…,fi δ i: a given headway amplitude factor for synchronized timetable.Decision Variables x i p: departure time of the p-th trip of line i y i p b j q: 0-1 if or not the p-th trip of line i arrives first at node b and synchronizes with the q-th trip of line j within time window wbmin,wbmax.


### 2.2. SRSBT Model

For the SRSBT problem, we propose a single-objective mathematical model (i.e., SRSBT model) as below.(1)maxF=∑i∈I∑j∈Ji∑b∈Bij∑p=1fi∑q=1fjnipbjyipbjq(2)s.t.xi1≤himax,∀i∈I(3)T-himax≤xifi≤T,∀i∈I(4)himin≤xip-xip-1≤himax,∀i∈I,p∈2,…,fi(5)-γ≤xip-x^ip≤γ,∀i∈I,p∈1,…,fi(6)nipbj=n^ibj+n^ibjhixip-xip-1-hi,∀i∈I,j∈Ji,p∈2,…,fi(7)xjq+tjb-xip+tib≥wbmin-M1-yipbjq,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈Bij(8)xjq+tjb-xip+tib≤wbmax+M1-yipbjq,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈Bij(9)∑q=1fjyipbjq≤1,∀i∈I,j∈Ji,p∈1,…,fi,b∈Bij(10)xip∈0,1,…,T,∀i∈I,j∈Ji,p∈1,…,fi(11)yipbjq∈0,1,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈BijEquation (1) is the objective to maximize the total number of passengers whose excess transfer time is limited to wbmin,wbmax. Constraint (2) ensures that the first trip of each line departs at the beginning of the planning period. Similarly, Constraint (3) forces the last trip of each line to depart at the end of the planning period. Constraint (4) guarantees that the headways between consecutive trips of each line i is in the range of himin,himax. Constraint (5) defines the maximal value of deviation of departure times, relative to that of initial timetable. Equation (6) is the actual number of passengers transferring from the p-th trip of line i to line j at node b which depends on the actual headways for the feeder line i. Constraints (7) and (8) ensure that yipbjq equals one if the difference between the arrivals of two trips at node b is within time window wbmin,wbmax, in which M is a large constant. Constraint (9) ensures that each passenger makes less than one smooth transfer at one time. Constraints (10) and (11) are the domains of xip and yipbjq, respectively.Two main differences made by this paper relative to Ibarra-Rojas et al. [8] are emphasized here. On the one hand, in view of the studied problems, this paper studied a resynchronizing of bus timetable problem with the consideration of initial timetable which is very different from the problem proposed in Ibarra-Rojas et al. [8], in which a completely new timetable was generated by their model without considering the initial timetable. In our paper, timetable modifications consist of shifts in the departure times and headways of initial timetable. On the other hand, the objective function in our proposed model is also different from the objective function of Ibarra-Rojas et al. [8]. In our model, we considered a uniform-distributed passenger demand for transferring, and the number of transferring passengers reflects the importance of transfer nodes and variation in headways. The passenger demand is sensitive to the realized headways. In Ibarra-Rojas et al. [8] the transferring demand is not considered, which is a special case of our model.


### 2.3. Properties of the SRSBT Model

We can see that the SRSBT model is a mixed-integer quadratic programming model. To find effective algorithms solving the SRSBT model, we analyze the mathematical model.Property 1.
The feasible departure time window ofxip can be expressed by expression (12).(12)xip∈maxp-1himin,T-fi-p-1himax,x^ip-γ,minphimax,T-fi-phimin,x^ip+γProof.
Without considering small timetable modifications, Wu Y. H. et al. [25] and Ibarra-Rojas et al. [8] have derived the departure time window of xip as (13). We thus obtain expression (14). Considering constraint (5), we could get expression (12).(13)p-1himin,minT,phimax∩max0,T-fi-p-1himax,T-fi-phimin(14)xip∈maxp-1himin,T-fi-p-1himax,minphimax,T-fi-phimin
Defining the departure time window asDpi (p∈1,…,fi), let Dpi=Dpi←,Dpi→, where Dpi←=maxp-1himin,T-fi-p-1himax,x^ip-γ and Dpi→=minphimax,T-fi-phimin,x^ip+γ. The arrival time window Apbi of any trip p of line i can thus be expressed as expression (15). We thus define a synchronization window Spbi for any trip p of line i at node b as expression (16).(15)Apbi=Dpi←+tib,Dpi→+tib(16)Spbi=Dpi←+tib+wbmin,Dpi→+tib+wbmax
Thus, whenAqbj∉Spbi, yipbjq equals zero; i.e., passengers from trip p of line i cannot transfer to trip q of line j at node b.Property 2.
The value range of parameterγ is 0,maxi∈I⁡fi/2himax-himin/2+hi.Proof.
Obviously, when the initial timetable is not allowed to be modified, the lower bound ofγ is zero. The notations in Section 2.1 define hi=T/fi, himin=hi-δi, himax=hi+δi, δi=himax-himin/2, and x^ip=p-1hi. Combining with property 1, we obtain expression (17) and (18).(17)xip-x^ip∈maxp-1himin-hi,T-fihimax+p-1himax-hi,minp-1himax-hi+himax,T-fihimin+p-1himin-hi+himin=max-p-1δi,-fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin(18)⇒xip-x^ip=max⁡max-p-1δi,-fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin=max⁡minp-1δi,fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin
From expression (18), it can be seen that fi/2 and fi/2+1 are the watershed lines for discussing the value of xip-x^ip.fi is even or not. We discuss three situations as follows.(I)
p≤fi/2,∀i∈I(19)xip-x^ip=maxp-1δi,p+1δi+himin=p+1δi+himin=pδi+hi≤fi2δi+hi(II)
fi/2<p≤fi/2+1,∀i∈I(20)xip-x^ip=maxp-1δi,fi-p-1δi+himin=maxfi2δi,fi2δi+himin=fi2δi+himin(III)
fi/2+1<p≤fi,∀i∈I(21)xip-x^ip=maxfi-p-1δi,fi-p-1δi+himin=fi-p-1δi+himin<fi2δi+himin
wherefi/2 is the largest integer not greater than fi/2. Therefore, the value of xip-x^ip is not larger than fi/2δi+hi.
Based on the discussion above, we can obtain the upper bound ofγ denoted by γmax=maxi∈I,p∈1,…,fi⁡xip-x^ip≤maxi∈I⁡fi/2δi+hi=maxi∈I⁡fi/2himax-himin/2+hi. Therefore, the value range of parameter γ is 0,maxi∈I⁡fi/2himax-himin/2+hi.Property 3.
∑ q = 1 f j y i p b j q ≤ 1 is a valid inequality for trip p of line i synchronizing with line j as hjmin>wbmax-wbmin.Proof.
Constraint (9) ∑q=1fjyipbjq≤1 means that the maximum number of smooth transfers that passengers make between one trip of line i and all trips of line j is 1. Let us suppose ∑q=1fjyipbjq=n(n>1) so that trip p of line i can synchronize with trips q1<q2<⋯<qn of line j. According to constraints (7) and (8), the arrival times of trips that synchronize with trip p of line i must be within the time window xip+tib+wbmin,xip+tib+wbmax. Therefore, the difference between xjqn+tjb and xjq1+tjb must be less than wbmax-wbmin; i.e., xjqn-xjq1≤wbmax-wbmin. According to constraint (4), we obtain xjqn-xjq1≥n-1hjmin. We then have hjmin≤wbmax-wbmin/n-1(n>1), which is in conflict with hjmin>wbmax-wbmin.Property 4.
According to constraints (7) ~ (9), the matrix formed by the synchronization variables yipbjq has following typical structure as shown in Figure 5.Figure 5
Typical structure of the matrix formed by the synchronization variablesyipbjq.Proof.
According to constraints (7) and (8), when yipbjq=1, we can obtain yipbj(q+1)=1,yipbj(q+2)=1,…,yipbjfj=1. When yipbjq=0, we can obtain yipbj1=0,yipbj2=0,…,yipbj(q-1)=0. With constraint (9), i.e., ∑q=1fjyipbjq≤1, trip p of line i at most synchronizes with one trip of line j. We thus get the typical structure of the matric formed by the synchronization variables yipbjq, which is different from that of Ibarra-Rojas et al. [8].Property 5.
The SRSBT problem is NP-hard.Proof.
Using a polynomial reduction from monotone NAE-3SAT, Ibarra-Rojas et al. [8] have proved that the SBT problem is NP-hard. Ibarra-Rojas et al. [8] proposed a MIP model for the SBT problem without considering passenger demand and the limited range of departure times. In other words, the MIP model assumes that the number of transferring passengers for each trip of all lines at each transfer node is one. It is quite clear that the MIP model is a special case of the model consisting of expressions (1)~(4), (7)~(8) and (10)~(11) in Section 2.2. Therefore, the SRSBT model is also NP-hard.


## 2.1. Notations

We introduce notations necessary to formulate the SRSBT problem.Sets I: set of lines in the bus network, i∈I J i: set of lines that have transfer nodes with line i, j∈Ji B i j: set of transfer nodes for line i and j, b∈BijParameters f i: number of trips for line i in the planning period of interest h i: headway of line i in the existing timetable; hi=T/fi,∀i∈I h i m i n: minimum headway of line i allowed for synchronized timetable; himin=hi-δi,∀i∈I h i m a x: maximum headway of line i allowed for synchronized timetable; himax=hi+δi,∀i∈I n ^ i b j: estimated number of passengers, each transferring from line i to line j at transfer node b when the initial timetable is used n i p b j: actual number of passengers benefiting from a smooth transfer for p-th trip of line i to line j at node b when synchronized timetable is used γ: the maximal value of deviation allowed from the departure times T: length of planning period in minutes; the planning period can be standardized as 0,T t i b: travel time from depot of line i to node b in the planning period w b m i n: minimum separation time between synchronized bus arrivals at node b w b m a x: maximum separation time between synchronized bus arrivals at node b x ^ i p: departure time of the p-th trip of line i in the initial timetable; x^ip=p-1hi,∀i∈I,p∈1,…,fi δ i: a given headway amplitude factor for synchronized timetable.Decision Variables x i p: departure time of the p-th trip of line i y i p b j q: 0-1 if or not the p-th trip of line i arrives first at node b and synchronizes with the q-th trip of line j within time window wbmin,wbmax.


## 2.2. SRSBT Model

For the SRSBT problem, we propose a single-objective mathematical model (i.e., SRSBT model) as below.(1)maxF=∑i∈I∑j∈Ji∑b∈Bij∑p=1fi∑q=1fjnipbjyipbjq(2)s.t.xi1≤himax,∀i∈I(3)T-himax≤xifi≤T,∀i∈I(4)himin≤xip-xip-1≤himax,∀i∈I,p∈2,…,fi(5)-γ≤xip-x^ip≤γ,∀i∈I,p∈1,…,fi(6)nipbj=n^ibj+n^ibjhixip-xip-1-hi,∀i∈I,j∈Ji,p∈2,…,fi(7)xjq+tjb-xip+tib≥wbmin-M1-yipbjq,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈Bij(8)xjq+tjb-xip+tib≤wbmax+M1-yipbjq,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈Bij(9)∑q=1fjyipbjq≤1,∀i∈I,j∈Ji,p∈1,…,fi,b∈Bij(10)xip∈0,1,…,T,∀i∈I,j∈Ji,p∈1,…,fi(11)yipbjq∈0,1,∀i∈I,j∈Ji,p∈1,…,fi,q∈1,…,fj,b∈BijEquation (1) is the objective to maximize the total number of passengers whose excess transfer time is limited to wbmin,wbmax. Constraint (2) ensures that the first trip of each line departs at the beginning of the planning period. Similarly, Constraint (3) forces the last trip of each line to depart at the end of the planning period. Constraint (4) guarantees that the headways between consecutive trips of each line i is in the range of himin,himax. Constraint (5) defines the maximal value of deviation of departure times, relative to that of initial timetable. Equation (6) is the actual number of passengers transferring from the p-th trip of line i to line j at node b which depends on the actual headways for the feeder line i. Constraints (7) and (8) ensure that yipbjq equals one if the difference between the arrivals of two trips at node b is within time window wbmin,wbmax, in which M is a large constant. Constraint (9) ensures that each passenger makes less than one smooth transfer at one time. Constraints (10) and (11) are the domains of xip and yipbjq, respectively.Two main differences made by this paper relative to Ibarra-Rojas et al. [8] are emphasized here. On the one hand, in view of the studied problems, this paper studied a resynchronizing of bus timetable problem with the consideration of initial timetable which is very different from the problem proposed in Ibarra-Rojas et al. [8], in which a completely new timetable was generated by their model without considering the initial timetable. In our paper, timetable modifications consist of shifts in the departure times and headways of initial timetable. On the other hand, the objective function in our proposed model is also different from the objective function of Ibarra-Rojas et al. [8]. In our model, we considered a uniform-distributed passenger demand for transferring, and the number of transferring passengers reflects the importance of transfer nodes and variation in headways. The passenger demand is sensitive to the realized headways. In Ibarra-Rojas et al. [8] the transferring demand is not considered, which is a special case of our model.


## 2.3. Properties of the SRSBT Model

We can see that the SRSBT model is a mixed-integer quadratic programming model. To find effective algorithms solving the SRSBT model, we analyze the mathematical model.Property 1.
The feasible departure time window ofxip can be expressed by expression (12).(12)xip∈maxp-1himin,T-fi-p-1himax,x^ip-γ,minphimax,T-fi-phimin,x^ip+γProof.
Without considering small timetable modifications, Wu Y. H. et al. [25] and Ibarra-Rojas et al. [8] have derived the departure time window of xip as (13). We thus obtain expression (14). Considering constraint (5), we could get expression (12).(13)p-1himin,minT,phimax∩max0,T-fi-p-1himax,T-fi-phimin(14)xip∈maxp-1himin,T-fi-p-1himax,minphimax,T-fi-phimin
Defining the departure time window asDpi (p∈1,…,fi), let Dpi=Dpi←,Dpi→, where Dpi←=maxp-1himin,T-fi-p-1himax,x^ip-γ and Dpi→=minphimax,T-fi-phimin,x^ip+γ. The arrival time window Apbi of any trip p of line i can thus be expressed as expression (15). We thus define a synchronization window Spbi for any trip p of line i at node b as expression (16).(15)Apbi=Dpi←+tib,Dpi→+tib(16)Spbi=Dpi←+tib+wbmin,Dpi→+tib+wbmax
Thus, whenAqbj∉Spbi, yipbjq equals zero; i.e., passengers from trip p of line i cannot transfer to trip q of line j at node b.Property 2.
The value range of parameterγ is 0,maxi∈I⁡fi/2himax-himin/2+hi.Proof.
Obviously, when the initial timetable is not allowed to be modified, the lower bound ofγ is zero. The notations in Section 2.1 define hi=T/fi, himin=hi-δi, himax=hi+δi, δi=himax-himin/2, and x^ip=p-1hi. Combining with property 1, we obtain expression (17) and (18).(17)xip-x^ip∈maxp-1himin-hi,T-fihimax+p-1himax-hi,minp-1himax-hi+himax,T-fihimin+p-1himin-hi+himin=max-p-1δi,-fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin(18)⇒xip-x^ip=max⁡max-p-1δi,-fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin=max⁡minp-1δi,fi-p-1δi,minp+1δi+himin,fi-p-1δi+himin
From expression (18), it can be seen that fi/2 and fi/2+1 are the watershed lines for discussing the value of xip-x^ip.fi is even or not. We discuss three situations as follows.(I)
p≤fi/2,∀i∈I(19)xip-x^ip=maxp-1δi,p+1δi+himin=p+1δi+himin=pδi+hi≤fi2δi+hi(II)
fi/2<p≤fi/2+1,∀i∈I(20)xip-x^ip=maxp-1δi,fi-p-1δi+himin=maxfi2δi,fi2δi+himin=fi2δi+himin(III)
fi/2+1<p≤fi,∀i∈I(21)xip-x^ip=maxfi-p-1δi,fi-p-1δi+himin=fi-p-1δi+himin<fi2δi+himin
wherefi/2 is the largest integer not greater than fi/2. Therefore, the value of xip-x^ip is not larger than fi/2δi+hi.
Based on the discussion above, we can obtain the upper bound ofγ denoted by γmax=maxi∈I,p∈1,…,fi⁡xip-x^ip≤maxi∈I⁡fi/2δi+hi=maxi∈I⁡fi/2himax-himin/2+hi. Therefore, the value range of parameter γ is 0,maxi∈I⁡fi/2himax-himin/2+hi.Property 3.
∑ q = 1 f j y i p b j q ≤ 1 is a valid inequality for trip p of line i synchronizing with line j as hjmin>wbmax-wbmin.Proof.
Constraint (9) ∑q=1fjyipbjq≤1 means that the maximum number of smooth transfers that passengers make between one trip of line i and all trips of line j is 1. Let us suppose ∑q=1fjyipbjq=n(n>1) so that trip p of line i can synchronize with trips q1<q2<⋯<qn of line j. According to constraints (7) and (8), the arrival times of trips that synchronize with trip p of line i must be within the time window xip+tib+wbmin,xip+tib+wbmax. Therefore, the difference between xjqn+tjb and xjq1+tjb must be less than wbmax-wbmin; i.e., xjqn-xjq1≤wbmax-wbmin. According to constraint (4), we obtain xjqn-xjq1≥n-1hjmin. We then have hjmin≤wbmax-wbmin/n-1(n>1), which is in conflict with hjmin>wbmax-wbmin.Property 4.
According to constraints (7) ~ (9), the matrix formed by the synchronization variables yipbjq has following typical structure as shown in Figure 5.Figure 5
Typical structure of the matrix formed by the synchronization variablesyipbjq.Proof.
According to constraints (7) and (8), when yipbjq=1, we can obtain yipbj(q+1)=1,yipbj(q+2)=1,…,yipbjfj=1. When yipbjq=0, we can obtain yipbj1=0,yipbj2=0,…,yipbj(q-1)=0. With constraint (9), i.e., ∑q=1fjyipbjq≤1, trip p of line i at most synchronizes with one trip of line j. We thus get the typical structure of the matric formed by the synchronization variables yipbjq, which is different from that of Ibarra-Rojas et al. [8].Property 5.
The SRSBT problem is NP-hard.Proof.
Using a polynomial reduction from monotone NAE-3SAT, Ibarra-Rojas et al. [8] have proved that the SBT problem is NP-hard. Ibarra-Rojas et al. [8] proposed a MIP model for the SBT problem without considering passenger demand and the limited range of departure times. In other words, the MIP model assumes that the number of transferring passengers for each trip of all lines at each transfer node is one. It is quite clear that the MIP model is a special case of the model consisting of expressions (1)~(4), (7)~(8) and (10)~(11) in Section 2.2. Therefore, the SRSBT model is also NP-hard.


## 3. Preprocessing Method

According to Properties1 and 3, we design a preprocessing method to reduce the solution space of the SRSBT by eliminating useless variables and constraints. Algorithm 1 describes the preprocessing method.Algorithm 1:The procedure of preprocessing method.
Input: SRSBT model Output: Reduced SRSBT model 1:for  (i∈I,j∈Ji,b∈Bij,p∈1,...,fi,q∈1,…,fj)  do 2:Calculate Aqbj and Spbi by Expression (15) and (16) 3:if  (Aqbj∩Spbi=⌀)  then 4:if  (Dqj→+tjb<Dpi←+tib+wbmin)  then 5:Eliminate yipbjq and constraints (6)~(7) and (9) with indexes i,j,b,p and q. 6:end if 7:if  (Dqj←+tjb>Dpi→+tib+wbmax)  then 8:for  (q′∈q,…,fj)  do 9:Eliminate yipbjq′ and constraints (6)~(7) and (9) with indexes i, j, b, p and q′ 10:end for 11:break 12:end if 13:end if 14:end for


## 4. Numerical Examples

In this section, a simple bus network used in Wu Y. H. et al. [25] is adopted to illustrate the effectiveness of the preprocessing method. Figure 6 and Table 1 depict the structure of simple bus network and its initial timetable used. For other operational parameters for these two instances, please refer to Wu Y. H. et al. [25]. Under the initial timetable, the average number of passengers for each transferring between different lines is given in Table 2. Other operational parameters are described in Section 2.Table 1
Initial timetable for the simple bus network used by Wu Y. H. et al. [25].
Trip number Line 1 2 1 0 0 2 15 15 3 30 30 4 45 45Table 2
Transferring passengers of the network illustrated in Wu Y. H. et al. [25].
Transfer nodeb From linei To linej Number of transferring passengers (n^ibj) 1 1 2 15 2 1 20 2 1 2 25 2 1 15Figure 6
A simple bus network in Wu Y. H. et al. [25].We firstly use the preprocessing approach to reduce the solution space of SRSBT model. Then, a branch and bound (B&B) algorithm is used to solve the reduced SRSBT model. The B&B algorithm and preprocessing method used in this section are coded in C# and all tests are executed on an Intel Core (TM) i3 processor at 2.27 GHz under Windows 7 using 2.00 G of RAM.According to property 2, the maximal value of parameterγ is 17 for this case. Under each given value of γ, there is corresponding solution and one optimal value of objective (i.e., the number of passengers benefiting from smooth transfers). It can be observed from Figure 7 that when γ equals zero, nonpassengers can take a smooth transfer. The optimal value of objective increases slightly as γ takes value range from 0 to 4. However, the optimal value of objective increases rapidly as γ takes value range from 5 to 7. The optimal value of objective reaches its maximal value as γ takes 10. When γ takes a value larger than 10, the optimal value of objective remains unchanged. According to Figure 7 we can select appropriate value of γ under given service level.Figure 7
Optimal value of the objective function in SRSBT with differentγ.Table3 gives the optimal solutions for the adjusted timetable under γ taking the value range from 0 to 10. The optimal solutions for γ taking the value from 11 to 17 are the same as γ equals 10. We can see that from Table 3 the optimal solutions are sensitive to the departure time modifications.Table 3
The adjusted departure times of trips of lines obtained for the simple bus network in Figure6.
γ Departure number Line 1 2 0 1 0 0 2 15 15 3 30 30 4 45 45 1 1 1 0 2 16 15 3 31 29 4 46 45 2 1 1 0 2 16 15 3 31 30 4 47 44 3 1 1 0 2 16 14 3 32 29 4 48 45 4 1 1 0 2 17 15 3 33 31 4 49 47 5 1 4 0 2 20 14 3 35 28 4 50 44 6 1 6 0 2 21 14 3 35 28 4 51 44 7 1 7 0 2 21 14 3 36 29 4 52 45 8 1 7 0 2 23 15 3 38 30 4 53 46 9 1 7 0 2 23 16 3 38 31 4 54 47 10 1 7 0 2 23 16 3 39 32 4 55 48Table4 shows the results of solving instances of SRSBT model and reduced SRSBT model using a B&B algorithm. Column one shows different himin,himax consisting of different instances. Columns two and four show the relative gap (difference between the best feasible solution and the best upper) for SRSBT and reduced SRSBT, respectively. Columns three and five show the computational time needed by B&B algorithm solving SRSBT model and reduced SRSBT model. The computational time of preprocessing method is neglected since it is less than 0.1 second. Column six shows the percentage of solution space eliminated from SRSBT to obtain the reduced SRSBT model.Table 4
Results of solving instances of SRSBT model and reduced SRSBT model using a B&B algorithm.
h i m i n , h i m a x SRSBT Reduced SRSBT Reduction (%) Gap (%) Time (s) Gap (%) Time (s) 14,16 0 1.91 0 0.10 72.8 13,17 0 3.54 0 0.91 67.4 12,18 0 5.60 0 2.35 60.2 11,19 0 10.9 0 5.46 56.0From Table4, we can see that there are high levels of eliminated variables using the preprocessing method. Therefore, the solving times of reduced SRSBT are less than that of SRSBT, which illustrates that the preprocessing method is effective. The variation in headway generates large instances which need more time to be solved. In particular, we see that high percentage levels of eliminated variables for instances with small headway deviation. For the instances, the preprocessing method can reduce the solution spaces of SRSBT model to at least 56%. It will be useful to solve large SRSBT problems using the preprocessing method, which is our following work.


## 5. Conclusions

In this paper, we have studied a SRSBT problem by adjusting the departure times of initial bus timetable in a limited range. For this problem, we proposed a mixed-integer programming model with the objective of maximizing the number of total transferring passengers benefiting from smooth transfers. By analyzing the mathematical properties of this model, we developed a preprocessing method to reduce the synchronization variables and constraints of the SRSBT model. The preprocessing method proved to be effective in terms of the solving time and reduced solution spaces. For the instances studied in Section4, the reduced SRSBT has at least 56% fewer solution spaces than that of SRSBT. Obtaining a high quality solutions for SBT problems in a reasonable time is beneficial to large bus transit networks in real life. Combined with B&B algorithm, the preprocessing method proposed in this paper has the potential to solve large SRSBT problems in a reasonable time.Besides using the preprocessing method with exact algorithms to solve large bus networks, several aspects should be considered for future studies. In real cases, the travel times of bus are often stochastic. Recent studies deal with multiperiod transit timetabling, robust timetable coordination, and integrated timetabling and vehicle-scheduling problems [3, 14, 24, 26]. These topics also should be paid more attention to in future studies. Finally, it would be interesting to consider the use of preprocessing method combined with mathematics to solve large real cases.



---

*Source: 7832638-2018-09-23.xml*