# Optimal Adjustment Schemes on the Long Through-Type Bus Lines considering the Urban Rail Transit Network.

1. IntroductionBus and urban rail transit play very important roles in public transport network in most big cities and there are both competition and cooperation between them. On one hand, it reflects their competitive relationship that the passengers could choose one of these two transportation modes to reach their destinations. On the other hand, that the passengers sometimes transfer from one of these two transportation modes to the other in one trip reflects their cooperative relationship. The function of bus lines in the comprehensive network may change with the development of the urban rail transit network in mega cities. The form of bus lines and their operation schemes should be optimized considering the impacts of urban rail transit network to achieve better cooperation between bus lines and urban rail lines.

Many researchers have investigated the optimization methods of the solo bus network over the past few decades and most of them focused on the optimization of bus lines and timetabling [1-3]. However, they did not consider the changes of passengers' travel mode from single-mode to multimode and it will affect the bus network design. In the public transport network, there is a strong complementary and alternative relationship between bus transit and urban rail transit. The studies of the optimization methods of bus lines considering the rail transit network mainly involve three aspects. Firstly, they studied the regulation means on existing bus network coordinating with one or a few new urban rail lines. Sun et al. [4] studied the optimization method of bus network design considering a new urban rail line. Secondly, they discussed the optimization methods of the feeder bus network connecting with urban rail stations. Chien et al. and Dijoseph et al. [5, 6] considered different influence factors in the optimization of feeder buses. Shrivastava et al. and Verma et al. [7, 8] built models to attain the feeder routes to urban railway stations, respectively. Also, Deng et al. and Wong et al. [9, 10] studied the feeder bus network design problem and proposed feeder bus network design models, from different angles. Besides, some researchers [11-13] studied the optimization methods of public transportation network consisting of more than one mode. These studies only considered the impacts of one urban rail station or a new urban rail line in the optimization, and the impacts of entire urban rail network on the long through-type bus line in the competitive trip mode were not considered.

Meanwhile, the designs of bus network and urban rail network are both based on passenger demand, and the imbalance of passenger demand is inevitable [14]. Ouyang et al. [15] formulated a methodological framework with the continuum approximation techniques to design bus networks for cities where travel demand varies gradually over space. For the bus or urban rail lines, the imbalance of demand is embodied in the imbalance of load factors of sections. Zhu et al. [16] proposed a bilevel model to solve the timetable design problem for an urban rail line considering the section loading-rates of trains. Xu et al. [17, 18] proposed that, for operating enterprises, considering the fairness of services for the passengers and the equality degree of train utilization rates, the unbalance of load factors should be avoided on the basis of meeting the demand of passengers. Thus, the imbalance of passenger demand should be considered in the optimization of bus network.

In this paper, a bilevel programming model is set up to optimize the long through-type bus lines with full consideration of the impacts of the rail transit network. At the same time, the load factors of associated bus routes are guaranteed in a reasonable range. The objective of upper level model is to minimize the passengers' average trip cost and maximize the benefits of the bus operators, and the lower level model is a passenger flow assignment model based on Logit-SUE which takes the crowding perception of passengers in bus vehicles into account. Then a genetic algorithm is designed to obtain optimized form of bus line based on the proposed model.

The remainder of this paper is organized as follows. Section 2 describes the bilevel programming model for the long through-type bus lines. Based on the proposed model, the genetic algorithm and MSA algorithm are developed in Section 3. In Section 4, a numerical experiment is conducted to show the application of the proposed model and algorithm, followed by the sensitivity analyses of the weight coefficients of two subgoals of the upper level model and the time value of passengers. The final section concludes the paper and discusses future research issues.

2. Bilevel Programming Model of Bus Line Design

2.1. Problem Description. This paper focuses on the optimization of the long through-type bus lines which are located in the dense area of rail transit network, as shown in Figure 1. This type of bus lines is usually long, most of which pass through the center area of the city. Usually, these bus lines have two crossing transfer points with the dense area of rail transit network and the bus stops between the two crossing transfer points are all located in the rail transit network. There is a competitive relationship between the bus line and the urban rail line between the two crossing transfer points. The bus line is composed of N stops, and the bus line sections are sequentially numbered as a, a = 1, 2 ... N - 1. The passengers considered in this study include the ones who only take bus and the ones who take both the bus and the train in one trip.

The setting decision of a stop station determines whether the stop station is cancelled or reserved or the bus line is disconnected here. If the setting decisions of stop stations change, the trip choices of passengers may vary accordingly. For each OD, if and only when the bus line from O to D is not reachable, the passengers may transfer to another bus line. For each OD, the bus route that the passengers may transfer to is defined as the associated bus route (as shown in Figure 2) and it is the shortest one of other bus routes which can replace the bus route of original bus line from O to D.

The adjustment schemes of bus line involve the adjustment of the bus line form and the corresponding headways. The optimization model proposed in this paper is based on the following assumptions.

Assumption 1. The waiting time of each passenger at the bus stop is half the vehicle headway of the bus line.

Assumption 2. The passengers are not willing to transfer more than twice in urban rail systems in one trip.

Assumption 3. O and D points are all located at the stops of bus lines and the stations of rail transit network.

Assumption 4. For the passengers who choose the original bus line, if the bus line from O to D is still reachable after optimization, the passengers will choose the urban rail line or the optimized bus line; otherwise, the passengers will choose the urban rail line or the associated bus routes.

Assumption 5. The bus line can be broken down only at the bus stops which have the setting conditions for the initial and terminal stops.

2.2. Definitions and Notations. The following definitions and notations are used throughout the paper.

[Z.sub.1]: it is the average travel cost of all the passengers.

[z.sup.1]: it is the total cost of the passengers who do not transfer to associated bus routes.

[z.sup.2]: it is the total cost of the passengers who transfer to associated bus routes.

[Z.sub.2]: it is the benefits of the bus operators.

[[??].sup.1]: it is the operation cost of the bus line.

[[??].sup.2]: it is the imbalance of the load factors of bus line sections.

[??]: it is the function to normalize a variable.

k: it is the total number of the bus lines after the optimization.

[chi]: it is the serial number of the bus lines after the optimization.

[I.sub.[chi]]([J.sub.[chi]]): it is the collection of O (D) points in the line [chi] ([chi] = 1 ... k).

[R.sub.ij]: it is the collection of paths from i [member of] I to j [member of] J, [R.sub.ij] = [R.sub.ij,1] [union] [R.sub.ij,2] [union] [R.sub.ij,3] [union] [[??].sub.ij], [R.sub.ij,1] is the collection of paths each of which contains only the bus line, [R.sub.ij,2] is the collection of paths each of which contains rail lines and one part of the bus line, [R.sub.ij,3] is the collection of paths each of which contains rail lines and two parts of the bus lines, and [[??].sub.ij] is the associated bus route.

[r.sub.ij]: it is the path number, numbered the paths in [R.sub.ij] in order of [R.sub.ij,1], [R.sub.ij,2], [R.sub.ij,3], and [[??].sub.ij], [r.sub.ij] = 1, 2 ... [m.sub.ij], [m.sub.ij] + 1, [m.sub.ij] is the number of the paths except the associated bus routes.

Q: it is the total number of passengers in the public transit network, [mathematical expression not reproducible].

[t.sub.1]: it is the total waiting time of the passengers at bus stops and rail transit stations.

[t.sub.2]: it is the total transfer time of passengers.

[c.sup.r.sub.ij,1] ([c.sup.r.sub.ij,2], [c.sup.r.sub.ij,3]): it is the transfer times between the transfer bus stop and rail transit station (between the nontransfer bus stop and rail transit station, in the rail transit network).

[l.sub.1]([l.sub.2]): it is the average transfer distance between a transfer bus stop and a rail transit station (between a nontransfer bus stop and a rail transit station), m.

[[bar.t].sub.rail]: it is the average transfer time between two urban rail lines in peak hours, min.

[v.sub.1]: it is the average walking speed for the passengers, m/s.

[v.sub.2]: it is the travelling speed of the bus line, m/s.

[v.sub.3]: it is the travelling speed of urban rail transit, m/s.

[t.sub.3]: it is the total time of passengers in the bus.

[l.sup.r.sub.ij,bus]([l.sup.r.sub.ij,rail]): it is the length of the bus (urban rail) line in path [r.sub.ij], m.

[DELTA][l.sub.1]([DELTA][l.sub.2]): it is the length of each section of original bus line (urban rail lines), m. u: it is the total ticket price of the passengers, yuan.

[[delta].sup.r.sub.ij,bus]([[delta].sup.r.sub.ij,rail]): it is the ticket price of bus (rail) line in path [r.sub.ij], yuan.

[[phi].sub.1]([[phi].sub.2], [[phi].sub.3]): it is the penalty coefficient of the waiting time (the transfer time, the time in the bus vehicle).

[omega]: it is the conversion coefficient of time value, yuan/s.

[mathematical expression not reproducible]: it is the headway of the urban rail lines (associated bus routes [r.sub.ij] = [[??].sub.ij]), min.

N: it is the total number of the stops of target bus line.

e: it is the serial number of the bus stops, e = 1, 2 ... N.

S: it is the collection of the bus stops located in the dense area of rail transit network.

n: it is the total number of the bus stops in S.

[e.sup.r.sub.ij,2]: it is the serial number of the bus stop in path [r.sub.ij] ([r.sub.ij] [member of] [R.sub.ij,2] [union] [R.sub.ij,3]) where the passenger transfers to the rail transit stations.

[e.sup.r.sub.ij,3]: it is the serial number of the bus stop in path [r.sub.ij] ([r.sub.ij] [member of] [R.sub.ij,3]) which the passenger transfers from the rail transit stations to.

[x'.sub.e]: it is the 0-1 variable to indicate whether the bus vehicle stops at this stop; it is determined by the decision variable of the upper level model [x.sub.e].

[w.sup.r.sub.ij]: it is defined as the travel cost of passengers who choose the path [r.sub.ij].

[[eta].sub.ij]: it is the increase coefficient of path cost, [[eta].sub.ij] [member of] [0, 1], and it can be obtained through practical investigation.

[[??].sub.[chi]]: it is the number of original sections involved in line [chi].

[[??].sub.[chi]]: it is the number of actual sections involved in line [chi].

[[pi].sub.[chi]]: it is the serial number of actual sections of the bus line [chi], [[pi].sub.[chi]] = 1, 2 ... [[??].sub.[chi]].

[mathematical expression not reproducible]: it is the number of the initial point (terminal point) of section [[pi].sub.[chi]].

[Z.sub.a]: it is the seating capacity of bus vehicles.

[[??].sub.ijr]: it is the total number of the passengers who choose the path [[??].sub.ij] before optimization.

[[bar.[lambda]].sub.min]: it is the permissible minimum average load factor of the bus line sections.

[bar.[lambda]]: it is the average load factor of the bus line sections.

[[theta].sub.1]([[theta].sub.2]): it is the weight coefficients of [Z.sub.1]([Z.sub.2]) in the upper level model.

[[??].sub.1]([[??].sub.2]): it is the weight coefficients of [[??].sub.1]([[??].sub.2]).

[f.sub.min]([f.sub.max]): it is the maximum (minimum) headway of bus line.

[[lambda].sub.max]([[lambda].sub.min]): it is the maximum (minimum) load factor of bus line sections.

[q.sub.max]: it is the bus maximum transect volume of passengers.

[kappa]: it is the passengers perception coefficient for path costs.

[Q.sub.ij]: it is the number of the passengers from i to j.

[g'.sub.a]: it is the number of the passengers of section a.

[[rho].sup.ar.sub.ij]: it is the 0-1 variable, if section a is in the path [r.sub.ij], [[rho].sup.ar.sub.ij] = 1, otherwise, [[rho].sup.ar.sub.ij] = 0.

[w.sup.r(rail).sub.ij]: it is the cost of urban rail transit in [w.sup.r.sub.ij].

[w.sup.r(bus).sub.ij]: it is the cost of bus transit in [w.sup.r.sub.ij].

[p.sub.rail]: it is the mode choice probability of urban rail transit.

M: it is the total number of the possible line forms of target bus line.

[??]: it is the minimum number of original sections of each bus line.

E: it is the number collection of the stops which have the setting conditions for the initial and terminal stops.

The decision variables in the model are shown as follows:

(1) The decision variables of the upper level model are as follows:

[f.sub.[chi]]: the headway of the bus line [chi], min.

[x.sub.e]: the setting decision of the bus stop e. When e [member of] S, if the stop is cancelled, [x.sub.e]=1; if the stop is reserved, [x.sub.e]=2; if the bus line is disconnected at this stop, [x.sub.e]=0. When e [not member of] S, [x.sub.e]=2.

(2) The decision variables of the lower level model are as follows:

[g.sub.ijr]: the number of the passengers who choose the paths in [r.sub.ij] from i to j.

2.3. Objective. The optimization on the adjustment schemes of the bus lines in the integrated public transport network involves both the service provider and the passengers. In order to describe the interplay between the two sides, a bilevel programming model is presented here.

2.3.1. The Upper Level Model. The objective function of the upper level model consists of the following parts.

(1) The Minimization of Average Passenger Travel Cost [Z.sub.1]. According to Assumption 4, the total travel cost of the passengers can be divided into two parts: one is the total cost of the passengers who do not transfer to associated bus routes [z.sup.1], and the other is the total cost of ones who transfer to the associated bus routes [z.sup.2].

(1) The Description of [z.sup.1]

[z.sup.1] mainly includes the following:

(a) The waiting time of passengers [t.sub.1]:

[mathematical expression not reproducible] (1)

(b) The transfer time of passengers [t.sub.2]:

[mathematical expression not reproducible] (2)

(c) The time of passengers in bus vehicles [t.sub.3]:

[mathematical expression not reproducible] (3)

(d) The total ticket price u:

[mathematical expression not reproducible] (4)

Therefore, the total travel cost of the passengers who do not transfer to associated bus routes [z.sup.1] is

[z.sup.1] = ([[phi].sub.1][t.sub.1] + [[phi].sub.2][t.sub.2] + [[phi].sub.3][t.sub.3])[omega] + u (5)

(2) The Description of [z.sup.2]

[z.sup.2] is the travel cost of the passengers who transfer to the associated bus routes. When the line form of the target bus line alters, the trip mode choices of the passengers may change accordingly.

[x'.sub.e] is defined as the 0-1 variable to indicate whether a stop station will be set here, so

[mathematical expression not reproducible] (6)

When [x'.sub.i][x'.sub.j] = 0, [r.sub.ij] [member of] [R.sub.ij,1], the bus line from i to j is not accessible, the passengers who have originally chosen the bus line will make the trip choices again, and they will transfer to the urban rail line or the associated bus route from i to j. [w.sup.r.sub.ij] is defined as the travel cost of passengers who choose the path [r.sub.ij], according to the first principle of Wardrop, for the passengers, [mathematical expression not reproducible]. Thus, [mathematical expression not reproducible] is defined as

[mathematical expression not reproducible] (7)

Therefore, [z.sup.2] is obtained as follows:

[z.sup.2] = [summation over (i[member of]I)] [summation over (j[member of]J)] [summation over (r=[[??].sub.ij])] (1 - [x'.sub.i][x'.sub.j])[w.sup.r.sub.ij][g.sub.ijr] (8)

In summary, [Z.sub.1] is described as

[Z.sub.1] = [??] ([p[z.sup.1] + [z.sup.2]]/Q) (9)

(2) The Maximization of the Benefits of the Bus Operators [Z.sub.2]. In order to describe the benefits that the bus operators concern, the operation cost of the bus line [[??].sup.1] and the imbalance of load factors of bus line sections [[??].sup.2] are considered. More operation cost of the bus line leads to fewer benefits to the bus operators. Meanwhile, the imbalance of load factors of bus line sections results in the inequality of vehicle utilization rates which leads to a decrease in the service life of the vehicles, and it also causes the unfairness of services for the passengers which brings about the reduction of the bus line's competitiveness. Thus, the increment of the imbalance of load factors will also lead to a decrease in [Z.sub.2].

Accordingly, the function that describes their connections is set as follows:

[mathematical expression not reproducible] (10)

Then [[??].sup.1] and [[??].sup.2] are gotten as follows:

(1) The Description of [[??].sup.1]

If the number of the operating company's bus vehicles is fixed, it will not affect the optimization results. Meanwhile, the operation parameters of urban rail transit are fixed, so the operation cost of urban rail transit is fixed. Therefore, according to paper [4], the bus line operation cost is directly proportional to the operation time. Then [[??].sup.1] is obtained:

[mathematical expression not reproducible] (11)

(1) The Description of [[??].sup.2]

The standard deviation of load factors of bus line sections is used to describe the imbalance of them, so we have the following equation:

[mathematical expression not reproducible] (12)

where [mathematical expression not reproducible] is the average load factor of the bus line.

In conclusion, the upper level model is formulated as follows:

min Z = [[theta].sub.1] min[Z.sub.1] - [[theta].sub.2] max[Z.sub.2] (13)

s.t. [g.sub.ijr] [greater than or equal to] 0, [for all]i [member of] I, j [member of] J, i < j, [r.sub.ij] [member of] [R.sub.ij] (13a)

[mathematical expression not reproducible] (13b)

[f.sub.min] [less than or equal to] [f.sub.[chi]] [less than or equal to] [f.sub.max] (13c)

[f.sub.[chi]] [less than or equal to] [q.sub.max]/[Z.sub.a][f.sub.max] (13d)

[mathematical expression not reproducible] (13e)

[mathematical expression not reproducible] (13f)

[mathematical expression not reproducible] (13g)

[c.sup.r.sub.ij,3] [less than or equal to] 2 (13h)

[mathematical expression not reproducible] (13i)

[l.sup.r.sub.ij,bus] [less than or equal to] [DELTA][l.sub.1] (N - 1) (13j)

[mathematical expression not reproducible] (13k)

[mathematical expression not reproducible] (13l)

[x.sub.e] [member of] {0, 1, 2} , e = 1, 2 ... N (13m)

[mathematical expression not reproducible] (13n)

2.3.2. The Lower Level Model. The lower level model is a passenger flow assignment model of public transport network based on Logit-SUE. According to the previous studies [19], the lower level model is established as follows:

[mathematical expression not reproducible] (14a)

s.t. [[m.sub.ij].summation over (r=1)] [g.sub.ijr] = [Q.sub.ij] (14b)

[summation over (i[member of]I)][summation over (j[member of]J)] [Q.sub.ij] = Q (14c)

[g'.sub.a] = [summation over (i[member of]I)] [summation over (j[member of]J)] [[m.sub.ij].summation over ([r.sub.ij]=1)] [g.sub.ijk][[rho].sup.ar.sub.ij] (14d)

[mathematical expression not reproducible] (14e)

a = 1, 2 ... N - 1 (14f)

[g.sub.ijk] [greater than or equal to] 0 (14g)

[x.sub.i,] [x.sub.j] [member of] {0, 1} (14h)

k = 1, 2 ... [m.sub.ij] (14i)

i, j = 1, 2 ... N, i < j (14j)

[[rho].sup.ar.sub.ij] = 0,1 (14k)

The equivalence between the model and the SUE condition is proved as follows.

Firstly, the generalized Lagrange function of the model is constructed:

L (g, [psi]) = Y(g) - [summation over (i)] [summation over (j)] [[psi].sub.ij] ([[m.sub.ij].summation over (r=1)] [g.sub.ijr] - [Q.sub.ij]) (14l)

Afterward, the Kuhn-Tucker conditions of the optimization model are listed:

[g.sub.ijr] [partial derivative]L/[partial derivative][g.sub.ijr] = 0, [partial derivative]L/[partial derivative][g.sub.ijr] [greater than or equal to] 0 (14m)

Then we get

[mathematical expression not reproducible] (14n)

Formula (14n) can be simplified as follows:

[g.sub.ijr] ([w.sup.r.sub.ij] + 1/[kappa] (ln [g.sub.ijr] + 1) - [[psi].sub.ij]) = 0 (14o)

[w.sup.r.sub.ij] + 1/[kappa] (ln [g.sub.ijr] + 1) - [[psi].sub.ij] [greater than or equal to] 0 (14p)

[[m.sub.ij].summation over (r=1)] [g.sub.ijr] = [Q.sub.ij] (14q)

[g.sub.ijr] [greater than or equal to] 0 (14r)

Among them, [[psi].sub.ij] is the K-T multiplier corresponding to (14b).

When [g.sub.ijr] > 0, formula (14o) can be simplified as

[w.sup.r.sub.ij] + 1/[kappa] (ln [g.sub.ijr] + 1) - [[psi].sub.ij] = 0, [for all]i, j (14s)

Then we get

[g.sub.ijr] = exp ([kappa] ([[psi].sub.ij] - [w.sup.r.sub.ij]) - 1) (14t)

[[psi].sub.ij] = [w.sup.r.sub.ij] + 1/[kappa] (ln [g.sub.ijr] + 1) (14u)

If we replace formulas (14t) and (14u) into formula (14b), the following Logit model can be obtained:

[mathematical expression not reproducible] (14v)

At this point, the equivalence between the model and the SUE condition is proved.

3. Solution Algorithm

The upper level model is solved by genetic algorithm (GA), and the lower level model is solved by Method of Successive Average algorithm (MSA).

3.1. The Genetic Algorithm Design. Genetic algorithm (GA) is one of evolutionary algorithms in artificial intelligence approaches. Different from traditional optimization approaches, GA does not rely on the special characteristics of the problems and thus has no requirement on convexity and smoothness of functions and constraints [20]. It is widely applied in solving bus line planning optimization problems due to its extensive generality, strong robustness, high efficiency, and practical applicability. The main steps of GA are given as below.

(1) Chromosome Encoding. In this paper, each chromosome is composed of two parts. For the first part, the genes are the setting decisions of the bus stops, and the 0-1-2 encoding is used. When the code is 2, it indicates that the bus stop is reserved; when the code is 1, it indicates that the bus stop is cancelled; when the code is 0, the line is disconnected at this stop. For the second part, 0-1 binary encoding is used, and the variations of headways of every possible form of bus lines are chosen as genes. The expression of chromosome is shown in Figure 3 according to constraints (13m) and (13c).

(2) Generate Initial Individuals.

(1) The setting decisions of the bus stops: according to [g.sub.ijr] obtained from the lower level model, the choice probability of each bus stop [p.sub.e](e [member of] S) which reflects its competitiveness is defined as

[mathematical expression not reproducible] (15)

where [mathematical expression not reproducible] is the times that stop e is used by the passengers, and 2Q is the times that all the stops belonging to the bus line are used by the passengers. Identify [c.sub.1] and [c.sub.2] as the threshold values of bus stop choice probabilities; if [p.sub.e] [less than or equal to] [c.sub.1], mark stop e as "0"; if [c.sub.1] < [p.sub.e] < [c.sub.2], mark stop e as "1"; if [p.sub.e] [greater than or equal to] [c.sub.2], mark stop e as "2".

Generate the genes according to the following principles:

For the stops whose number belonging to E, assign the stops which are marked "0" equal probability to the genes of "0" or "1" randomly; assign the stops which are marked "1" equal probability to the genes of "0" or "1" or "2" randomly; the stops which are marked "2" have the genes of "2".

For other stops, assign the stops which are marked "0" to the genes of "1"; assign the stops which are marked "1" equal probability to the genes of "1" or "2" randomly; the stops which are marked "2" have the genes of "2".

(2) The headway of each possible shape of the bus line: assign the genes of the headway randomly according to constraints (13c).

(3) Chromosome Adjustment. The chromosomes of headways are decoded into real solutions. Specifically, if the genes of first part of the chromosome are beyond constraints (13i), they will be replaced by the genes which are corresponding with the original shape of the bus line. Besides, if the gene "1" is adjacent to gene "0", the chromosome becomes infeasible. Then the two continuous genes "01" will be replaced by genes "02" and the two continuous genes "10" will be replaced by genes "20". These steps are repeated until the solution satisfies all constraints.

(4) Fitness Calculation. It is necessary to transform the objective function (14a)-(14v) into a maximization problem since the GA is designed for solving maximization problem. The following equation is used to transform the fitness values.

fitness = -[[theta].sub.1] min [Z.sub.1] + [[theta].sub.2] max [Z.sub.2] + [[bar].[omega]] (16)

where [[bar].[omega]] is a constant to keep the fitness value as a positive value, and it is generally taken as the maximum value of the objective function.

(5) Crossover and Mutation Operations. The fitness of the chromosome is sorted, and the largest two chromosomes are recorded before crossover and mutation. Single-point crossover and mutation operations are used in this step. The new children will be adjusted to feasible solutions according to step "Chromosome Adjustment".

Other detailed steps and approaches of GA are similar to the standard GA. The procedure for GA in this problem includes the following steps:

Step 1. Generate initial individuals.

Step 2. Adjust chromosomes to a feasible solution.

Step 3. Calculate fitness of each individual and record the optimal solution.

Step 4. Terminate when the maximum number of generations is reached; otherwise, turn to Step 5.

Step 5. Obtain new chromosomes applying the operators like selection, crossover, and mutation; turn to Step 2.

3.2. The MSA Algorithm Design. The lower level model is solved by MSA algorithm, which has been widely used in traffic distribution. The MSA algorithmis designed as follows:

Step 1. Define G as the collection of passenger flow in each path, [G.sup.[0]] = 0. Then the cost of each path under [G.sup.[0]] is calculated and the collection of each path cost is defined as W([G.sup.[0]]). The passenger flow from i to j in path r, which is defined as [g.sub.ijr], is then obtained through Logit model. Let k' = 1, [g.sub.ijr.sup.[1]] = [g.sub.ijr], then the new passenger flow collection [G.sup.[1]] is obtained.

Step 2. W([G.sup.[k']]) can be calculated when [G.sup.[k']] is obtained, and then the passenger flow from i to j in path r is obtained as [g.sub.ijr2.sup.[k']], which is calculated by the same method as Step 1. And the additional passenger flow is obtained as [G.sup.[k'].sub.2].

Step 3. Convergence judgment: terminate when W[([G.sup.[k']]).sup.T]([G.sup.k'] - [G.sup.k'.sub.2])/W[([G.sup.[k']]).sup.T] [G.sup.k'] [less than or equal to] [epsilon]; otherwise, let [G.sup.[k'+1]] = (1/(k' + 1))(k'[G.sup.[k']] + [G.sup.[k'].sub.2]), k' = k' + 1; then turn to Step 2.

4. Case Study

4.1. Model Parameters and Optimization Result

4.1.1. The Network. The public transportation network in a region of a Chinese city is taken as an example in this section. As shown in Figure 4, the network consists of 10 urban rail lines and 1 long through-type bus line. The target bus line has 32 stops, 21 of which are located in the dense area of rail transit network. The scope of the study includes 496 OD pairs and 471 associated bus routes.

4.1.2. The Parameters. The values of the parameters involved in the optimization model are shown in Table 1. Among them, the values of parameter 1 to parameter 12 are set according to the actual surveys and the references, and others are set according to the existing studies.

Besides, [[theta].sub.1]: [[theta].sub.2] is 1:1 and [[??].sub.1]: [[??].sub.2] is 1:1. At the same time, the value of [[phi].sub.3] is connected with the standing-passenger density of the bus vehicles, according to paper [22]; if [mathematical expression not reproducible] is defined as the load factor of the section [[pi].sub.[chi]], then

[mathematical expression not reproducible] (17)

4.1.3. Result Analysis

(1)Optimization Result. The model and algorithm were implemented on Matlab 2014b. The population size is 400, crossover probability is 0.9, mutation probability is 0.2, and maximum generation is 150, [epsilon] is 0.05. The objective function value of each generation is shown in Figure 5. The result shows that the GA has good convergence to solve the proposed model, and the algorithm began to converge after the 116th generation.

(2) Performance Indicators. The line form of the bus line before and after optimization is shown in Figure 6. After the optimization, the long through-type bus line is split into two separate lines. Table 2 indicates that, after the optimization, the value of the objective function is improved by 27.2% in comparison with the original scheme. Even though the passengers' average travel cost has a 4.7% increase, the operation cost is decreased by 46.1%. The result is consistent with the existing argument that operation cost is strongly associated with the form of the bus line [23]. Meanwhile, the imbalance degree of load factors of the bus line sections is decreased by 18.6%. The optimization results validate the feasibility and effectiveness of the model.

The bus line to be optimized shown in Figure 4 has 32 bus stops and 31 sections. We number the bus line sections from 1 to 31 according to the running direction of the bus, as shown in Figure 7.

The load factors of the bus line sections before and after optimization are incarnated in the form of gradient map, as shown in Figure 8. For each section, the filling color of a rectangle is used to reflect the load factor of the section: the lighter the filling color, the higher the load factor.

Then, the following conclusions can be drawn according to Figure 8:

Before optimization, the sections with load factor less than 30% account for about 45.2% of the total. The sections with high load factors are mostly located in the area between the suburbs and the dense urban rail network with the direction from suburbs to the city center. The high load factors result in a large operating pressure. After optimization, the sections with load factor less than 30% account for about only 22.6% of the total. A feeder bus line connecting the suburbs and the dense urban rail network with a smaller headway contributes to reducing the operating pressure. Similarly, a longer bus line situated in the dense urban rail network with a larger headway is conducive to improve the load factors of the sections which are very low before optimization. The promotion of load factors of sections within a reasonable range will help to improve the equality of bus vehicle utilization rates and reduce the operation costs of bus companies.

4.2. Sensitivity Analysis. Different values of parameters involved in the optimization may lead to different optimization results. Most of the parameters can be confirmed to relatively reasonable values according to the actual surveys and the references. However, some important parameters are influenced by many factors that are difficult to quantify, and they cannot be easily confirmed. Accordingly, the impacts of their changes on optimization results are necessary to discuss here.

4.2.1. Weight Coefficients of Subgoals [[theta].sub.1] and [[theta].sub.2]. The weight coefficients of [Z.sub.1] and [Z.sub.2] in the upper level model are closely related to the government consideration and the benefits of the bus operators; their changes may lead to different optimization results. Accordingly, [[theta].sub.1] stands for the attention that the government consideration gets, and [[theta].sub.2] stands for the attention that the bus company's benefits get.

When [[theta].sub.1]/[[theta].sub.2] takes for different values, which are set as 5 scenarios shown in Table 3, the analysis of the change law of the optimization results was given as follows, which are shown in Table 3 and Figure 9.

Figure 9 indicates that when the value of [[theta].sub.1]/[[theta].sub.2] changes, it is better to divide the long through-type bus line into several separate bus lines under the condition of unbalanced passenger flow distribution.

(1) For the feeder buses connecting the suburbs and the dense urban rail network with the direction from suburbs to the city center, the changes of the value of [[theta].sub.1]/[[theta].sub.2] do not have significant impacts on their headways. Considering the limitation of the load factors of bus line sections and the passengers' trip cost, their headways can never be too small or too large, and they are set as 4 min in the optimization results in the case.

(2) When the bus operation cost becomes more important in the model, the bus operation cost will decrease, but its reduction is limited due to the randomness of [[??].sup.2]. At the same time, more importance on bus operation cost will lead to larger headways of the longer bus line and bigger average load factor.

(3) When the value of [[theta].sub.1]/[[theta].sub.2] decreases to 1:3 (scenario 5), the bus line is divided into three separate bus lines with independent operation, respectively, and the operation cost is still being reduced. Reasonable optimization of the bus line form can effectively reduce its operation cost. For the unbalanced passenger flow distribution, the more attention the bus operation cost is paid on, the more conducive the multiple bus lines with independent operation are to reduce operation cost compared with the long through-type bus line

Generally, for the supply side, when the average load factor of the bus line sections is constrained and the imbalance of each load factor of bus line sections is considered during the optimization, multiple bus lines with independent operation, respectively, will be better than the long through-type bus line under the condition of unbalanced passenger flow distribution. Meanwhile, the degree of the attention to the supply side and the demand-side will not have a significant impact on the headways of the feeder buses with the direction from suburbs to the city center. Also, reasonable optimization of the bus line form can effectively reduce its operation cost, and the more attention the bus operation cost is paid on, the better the multiple bus lines are under the condition of unbalanced passenger flow distribution.

4.2.2. Time Value That Passengers Perceive [omega]. Cities with different levels of urban construction, economic development, and employment have different average values of [omega] for the commuters, especially in different countries. However, the changes of [omega] may lead to the changes of passengers' tripmode choices. When [omega] is increased from 4 yuan /h to 16 yuan /h, the optimization results are shown in Table 4 and the forms of the optimized bus line are shown in Figure 10.

Table 4 indicates that higher time value that passengers perceive leads to the higher average travel cost, and passengers then prefer to choose faster trip mode. The choice probability of urban rail transit increases gradually, and the bus line operation cost decreases.

As to the form of the optimized bus line, shown in Figure 10, when the value of [omega] is low, the bus mode plays a very important role in the public transit network because of its low trip cost, and the form of long bus line with more stop stations is better for passengers' travel demand. When the value of [omega] is higher, the passengers prefer to choose faster trip mode and the rapidity and punctuality of urban rail transit are more prominent. Thus, the feeder bus lines with the functions of gathering and dispersing the passengers of urban rail transit are better for passengers' travel demand. At the same time, the headways of the feeder buses starting from the suburbs to the center of the city are generally small enough to meet the large passenger demand during peak hours. However, the headways of the feeder buses which have the opposite direction are relatively large.

The load factors of bus line sections corresponding to the lines shown in Figure 10 are given in Figure 11. It indicates the following:

(1) When the value of [omega] is low(4 yuan/h in the case), more passengers choose the bus tripmode, and the form of long bus line is better. Considering the bus line's average load factor can never be beyond the constraints (13g), the headway of the bus line cannot be set too small. Thus, the load factors of the sections located in the line from the suburbs to urban rail network are usually high ([omega] = 4, from section 1 to section 5 in Figure 10). However, the load factors of the sections located in the line from urban rail network to the suburbs are usually low ([omega]=4, from section 25 to section 30 in Figure 10).

(2) As the increment of [omega] (8~12 yuan/h in the case), the long bus line is divided into two bus lines, which consist of a feeder bus line and a longer bus line, and the headway of the feeder bus is usually small.

(3) When the value of [omega] increases to 16 yuan/h, the long bus line is divided into three bus lines, which consist of two feeder bus lines and a longer bus line. Then fewer passengers choose the bus mode, especially the feeder bus line from the city center to the suburbs. Accordingly, setting the feeder bus line from the city center to the suburbs a larger headway will help to reduce the bus line operation cost.

5. Conclusions

In this paper, a bilevel optimization model on the adjustment schemes of long through-type bus lines considering the impacts of the rail transit network and the influences on other associated bus routes was presented to minimize the integrated target value, including the average passenger travel cost and the benefits of the bus operators. A genetic algorithm is developed to solve the proposed model and the effectiveness is tested by a numerical example.

The results show that the proposed model is effective and efficient to improve the quality of the long through-type bus line, which reflects not only in the reduction of the bus operation cost, but also in the reasonable distribution of passengers in different sections, and the low load factors of the bus line sections have also been improved. At the same time, it is better to divide the long through-type bus line into several bus lines with independent operation, respectively, under the condition of unbalanced passenger flow distribution. Moreover, reasonable optimization of the bus line form can effectively reduce its operation cost. For the unbalanced passenger flow distribution, the more importance the operator benefits are attached to, the more apt the long through-type bus line is to be divided into several separate bus lines with independent operation, respectively. Besides, the higher time value that the passengers perceive leads more passengers to choose faster trip mode, and the combination of feeder bus lines and a longer bus line is more suitable for passengers' travel demand.

The passengers who transfer to the target bus line from other bus lines due to the changes of its operation scheme have not been considered due to the complexity of the problem in this study. Future research will attempt to take this part of the passengers into consideration in order to make the model more realistic.

https://doi.org/10.1155/2018/8029137

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This research was funded by the Fundamental Research Funds for the Central Universities (2018YJS091) and the National Natural Science Foundation of China (71621001-3, 71390332).

References

[1] M. Bielli, M. Caramia, and P. Carotenuto, "Genetic algorithms in bus network optimization," Transportation Research Part C: Emerging Technologies, vol. 10, no. 1, pp. 19-34, 2002.

[2] C. L. Zhao and H. J. Huang, "Modeling the equilibriumbus line choice behavior and transit system design with oblivious users," Discrete Dynamics in Nature and Society, vol. 2014, Article ID 173876, 5 pages, 2014.

[3] J. C. Chu, "Mixed-integer programming model and branch-and-price-and-cut algorithm for urban bus network design and timetabling," Transportation Research Part B: Methodological, vol. 108, pp. 188-216, 2018.

[4] Y. Sun, X.-N. Sun, Q.-F. Kong, R. Song, and S.-W. He, "Methodology of bus network optimization and adjustment under operation of newurban rail transit line," Tiedao Xuebao/Journal of the China Railway Society, vol. 36, no. 3, pp. 1-8, 2014.

[5] S. I. Chien, L. N. Spasovic, S. S. Elefsiniotis, and R. S. Chhonkar, "Evaluation of feeder bus systems with probabilistic time-varying demands and nonadditive time costs," Transportation Research Record, no. 1760, pp. 47-55, 2001.

[6] P. Dijoseph and S. I.-J. Chien, "Optimizing sustainable feeder bus operation considering realistic networks and heterogeneous demand," Journal of Advanced Transportation, vol. 47, no. 5, pp. 483-497, 2013.

[7] P. Shrivastav and S. L. Dhingra, "Development of feeder routes for Suburban railway stations using heuristic approach," Journal of Transportation Engineering, vol. 127, no. 4, pp. 334-341, 2001.

[8] A. Verma and S. L. Dhingra, "Feeder bus routes generation within integrated mass transit planning framework," Journal of Transportation Engineering, vol. 131, no. 11, pp. 822-834, 2005.

[9] L. Deng, W. Gao, Y. Fu, and W. Zhou, "Optimal design of the feeder-bus network based on the transfer system," Discrete Dynamics in Nature and Society, vol. 2013, Article ID 483682, 10 pages, 2013.

[10] J.-J. Lin and H.-I. Wong, "Optimization of a feeder-bus route design by using a multiobjective programming approach," Transportation Planning and Technology, vol. 37, no. 5, pp. 430-449, 2014.

[11] W. Fan and R. B. Machemehl, "Tabu search strategies for the public transportation network optimizations with variable transit demand," Computer-Aided Civil and Infrastructure Engineering, vol. 23, no. 7, pp. 502-520, 2008.

[12] W. Fan and R. B. MacHemehl, "Bi-level optimization model for public transportation network redesign problem," Transportation Research Record, no. 2263, pp. 151-162, 2011.

[13] I. Bakas, R. Drakoulis, N. Floudas, P. Lytrivis, and A. Amditis, "A flexible transportation service for the optimization of a fixed-route public transport network," Transportation Research Procedia, vol. 14, pp. 1689-1698, 2016.

[14] D. Horcher and D. J. Graham, "Demand imbalances and multiperiod public transport supply," Transportation Research Part B: Methodological, vol. 108, pp. 106-126, 2018.

[15] Y. Ouyang, S. M. Nourbakhsh, and M. J. Cassidy, "Continuum approximation approach to bus network design under spatially heterogeneous demand," Transportation Research Part B: Methodological, vol. 68, pp. 333-344, 2014.

[16] Y. Zhu, B. Mao, Y. Bai, and S. Chen, "A bi-level model for single-line rail timetable design with consideration of demand and capacity," Transportation Research Part C: Emerging Technologies, vol. 85, pp. 211-233, 2017.

[17] D. J. Xu, Optimization for train plan of full-length and short-turn routing in urban rail transit, Beijing Jiaotong University, 2016.

[18] D. J. Xu, B. H. Mao, and L. G. Lei, "Optimization for train plan of full-length and short-turn routing in urban rail transit," Journal of Transportation Systems Engineering and Information Technology, vol. 17, no. 1, pp. 120-126, 2017.

[19] Y. Li, B. F. Si, X. B. Yang et al., "A stochastic user equilibrium model and algorithm for urban transit network with transfer cost," Systems Engineering-Theory & Practice, vol. 34, no. 8, pp. 2127-2134, 2014.

[20] R.-J. Shi, B.-H. Mao, Y. Ding, Y. Bai, and Y. Chen, "Timetable optimization of rail transit loop line with transfer coordination," Discrete Dynamics in Nature and Society, vol. 2016, Article ID 4627094, 11 pages, 2016.

[21] Urban Construction Design & Research Institute, Standard for Classification of Urban Public Transportation, China building industry press, Beijing, China, 2007.

[22] M. Shao, T. Li, and L. Sun, "Survey method and model of passengers' cost perception of crowding level in bus," Tongji Daxue Xuebao/Journal of Tongji University, vol. 40, no. 7, pp. 1031-1034, 2012.

[23] V. Guihaire and J. K. Hao, "Transit network design and scheduling: a global review," Transportation Research Part A: Policy and Practice, vol. 42, no. 10, pp. 1251-1273, 2008.

Si-Jia Zhang (iD), (1,2) Shun-Ping Jia (iD), (1,2) Yun Bai (iD), (1,2) Bao-Hua Mao, (1,2) Cun-Rui Ma (iD), (1,2) and Tong Zhang (1,2)

(1) MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China

(2) School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Correspondence should be addressed to Shun-Ping Jia; shpjia@bjtu.edu.cn

Received 8 May 2018; Accepted 28 August 2018; Published 30 September 2018

Academic Editor: Emilio Jimenez Macias

Caption: Figure 1: The long through-type bus line.

Caption: Figure 2: An example of passengers choosing the associated bus route.

Caption: Figure 3: The expression of chromosomes.

Caption: Figure 4: The public transport competition network in the case.

Caption: Figure 5: Optimization process of GA.

Caption: Figure 6: The comparison of the bus line form between the optimized and original one.

Caption: Figure 7: The long through-type bus line.

Caption: Figure 8: The load factors of the optimized bus line and the original one.

Caption: Figure 9: The optimal line forms of the bus line in different scenarios.

Caption: Figure 10: The optimal forms of the target bus line under different values of [omega].

Caption: Figure 11: The load factor of bus line under different values of [omega].

Table 1: The parameter values in the model. No. The parameters value unit 1 [DELTA][l.sub.1] 600 m 2 [DELTA][l.sub.2] 1000 m 3 [l.sub.1] 400 m 4 [l.sub.2] 1000 m 5 [f.sub.2] 2 min 6 [[bar.t].sub.rail] 5 min 7 [f.sub.min] 2 min 8 [f.sub.max] 20 min 9 [[bar.[lambda]].sub.min] 0.371 -- 10 [c.sub.1] 0.02 -- 11 [c.sub.2] 0.05 -- 12 E [6, 7, 8, -- 9, 10, 14, 15, 16, 17, 18, 23, 24, 25, 26] 13 [v.sub.1] 1.5 [4] m/s 14 [v.sub.2] 4.7 [4] m/s 15 [v.sub.3] 9.7 [4] m/s 16 [[phi].sub.1] 1.5 [4] -- 17 [[phi].sub.2] 1.3 [4] -- 18 [omega] 0.0333 [4] yuan/s 19 [Z.sub.a] 75 [21] -- 20 [[lambda].sub.min] 0.15 [4] -- 21 [[lambda].sub.max] 1.0 [4] -- 22 [kappa] 10 [19] -- Table 2: The comparison of important values between optimized bus line and the original one. ([z.sup.1] + [z.sup.2])/ Z Q (yuan) [[??].sup.1] (h) [[??].sup.2] Before 0.419 6.551 28.704 0.2039 After 0.305 6.856 15.462 0.1660 [f.sub.[chi]] (min) [bar.[lambda]] Line1 Line2 [p.sub.rail] (%) Before 0.3706 6 53.7 After 0.3746 4 15 57.1 Table 3: The different scenarios and the optimal [f.sub.[chi]]. ([z.sup.1] + [z.sup.2])/ Scenario Q (yuan) [[??].sup.1] (h) [[??].sup.2] 1 6.650 18.561 0.209 2 6.770 18.561 0.186 3 6.856 15.462 0.166 4 6.951 13.671 0.186 5 6.909 11.112 0.171 [[theta].sub.1]: Scenario [bar.[lambda]] [[theta].sub.2] 1 0.4259 1:0.0 2 0.3898 1:0.5 3 0.3746 1:1.0 4 0.4962 1:2.0 5 0.4563 1:3.0 Optimized [f.sub.[chi]] (min) Scenario Line1 Line2 Line3 1 4 11 -- 2 4 11 3 4 15 -- 4 4 19 -- 5 4 17 20 Table 4: The important values of the model under different values of [omega]. ([z.sup.1] + [omega] [z.sup.2])/ (yuan/h) Q (yuan) [[??].sup.1] (h) [[??].sup.2] 4 2.78 24.60 0.230 8 4.97 18.36 0.238 12 6.86 15.46 0.166 16 9.10 8.43 0.227 [f.sub.[chi]] (min) [omega] (yuan/h) Line1 Line2 Line3 [p.sub.rail] (%) 4 7 -- -- 38.17 8 6 19 -- 51.49 12 4 15 -- 57.10 16 5 11 16 57.41

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Zhang, Si-Jia; Jia, Shun-Ping; Bai, Yun; Mao, Bao-Hua; Ma, Cun-Rui; Zhang, Tong |

Publication: | Discrete Dynamics in Nature and Society |

Geographic Code: | 9CHIN |

Date: | Jan 1, 2018 |

Words: | 8587 |

Previous Article: | Distributed Robust Kalman Filtering with Unknown and Noisy Parameters in Sensor Networks. |

Next Article: | A Metaheuristic Method for the Task Assignment Problem in Continuous-Casting Production. |

Topics: |