# Multiperspective Bus Route Planning in a Stackelberg Game Framework

Authors: Xinyu Liu; Jie Yu; Xiaoguang Yang; Weijie Tan
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Bus route planning is a challenging task due to multiple perspective interactions among passengers, service providers, and government agencies. This paper presents a multidimensional Stackelberg-game-based framework and mathematical model to best trade off the decisions of multiple stakeholders that previous literature rarely captures, i.e., governments, service providers, and passengers, in planning a new bus route or adjusting an existing one. The proposed model features a bilevel structure with the upper level reflecting the perspective of government agencies in subsidy allocation and the lower level representing the decisions of service providers in dispatching frequency and bus fleet size design. The bilevel model is framed as a Stackelberg game where government agencies take the role of “leader” and service providers take the role of “follower” with social costs and profits set as payoffs, respectively. This Stackelberg-game-based framework can reflect the decision sequence of both participants as well as their competition or collaboration relationship in planning a bus route. The impact of such decisions on the mode and route choices of passengers is captured by a Nested Logit model. A partition-based bisection algorithm is developed to solve the proposed model. Results from a case study in Shanghai validate the effectiveness and performance of the proposed model and algorithm.


---

## Body

## 1. Introduction

Traffic congestion is a main concern for urban transportation systems across the world. Among diverse means of transportation, public transit is widely developed in most countries as an efficient, reliable, accessible, and ecological travel mode, which plays an essential role in establishing a sustainable urban transportation system. Governments and transit providers have made great efforts to improve transit service performance, which will eventually improve passengers’ travel experience, attract more transit users, and increase the market share of public transit. Route planning is essential for developing a well-operated transit system towards high efficiency and convenience of future operation, which usually involves multiple stakeholders, including passengers on the demand side and government agencies and transit providers on the supply side. In practice, transit providers operate the bus service under the supervision of governments. Although governments endeavor to guarantee transit services to the general public, the goal of transit providers is to make profits. Therefore, governments often allocate subsidies to operators in order to improve transit performance. Travelers can then make their trip decisions by comparing the available transit and other transportation options. However, the role of governments and the threefold interactions among governments, transit operators, and passengers are often neglected at the planning stage. Failure to capture the multidimensional nature of route planning may lead to an imbalance between demand and supply, causing degraded service to passengers, undesirable service profits, and social costs.This paper proposed a Stackelberg game framework and a bilevel model in planning a single bus route which contribute to the existing literature by revealing the comprehensive relationships and interactions among governments, transit operators, and passengers. The role of governments is particularly considered in the planning framework. Decisions of transit companies and government agencies were described with the Stackelberg game, where governments take the role of the “leader” and transit companies react as the “follower.” Mode and route choice behavior of passengers, affected by the decisions of transit providers, were analyzed based on Nested Logit models. A bilevel analytical model was established to optimize decisions of both transit providers and governments. In the lower level, transit providers optimize frequency and fleet size to maximize their profits. In the upper-level model, governments determine the amount of subsidy for transit providers with the objective of minimizing total social cost. The proposed modelling framework works for either planning a new bus route or adjusting an existing route. A partition-based bisection algorithm was further developed to solve the mathematical optimization model.The remainder of the paper is organized as follows: Section2 presents the review of previous studies. Section 3 describes the formulation of the proposed Stackelberg-game-based framework and the optimization model. Section 4 develops a partition-based-bisection algorithm to solve the optimization model. Section 5 applies the proposed framework and model in a real-world case in Shanghai. Conclusions are summarized in Section 6.


## 2. Literature Review

Tremendous efforts have been made in macroscopic transit network planning that decides large scales of transit route networks. Researchers tend to optimize route network in a sequential order, including route network design, frequency setting, timetabling, vehicle scheduling, and crew scheduling [1], although some studies also address route design and frequency simultaneously. Several researchers provided comprehensive reviews of relevant studies in the past six decades. Guihaire and Hao [2] classified transit network problems into three basic categories: network design, frequency setting, and timetabling. Kepaptsoglou and Karlaftis [3] reviewed network design problems from objectives, decision variables, network structure, demand patterns, demand characteristics, and methodological approaches, followed by Farahani et al. [4] who summarized transit network design in the context of urban transportation network design. More recently, Ibarra-Rojas et al. [5] identified five major planning problems as strategic planning (network design), tactical planning (frequency setting and timetabling), and operational planning (vehicle scheduling, driver scheduling, and driver rostering).Network planning parameters are generally optimized to reach a goal through analytical methods or heuristic solutions under certain constraints. Users and operators are the two main perspectives considered in the planning framework. User benefits include travel, access and waiting cost minimization, minimization of transfers, maximization of coverage, and maximization of consumer surplus; operator benefits include maximum utilization and quality of service, minimization of operating costs, maximization of profits, and minimization of the fleet size [3]. Most researchers developed planning strategies by setting one single objective as user benefits [6–15], operator benefits [16–21], or total welfare combining these two perspectives to simplify the problem [19, 22–53]. There are also new perspectives incorporated in a few recent studies, such as safety [54] and sustainability [47, 55]. Although studies on network-level restructuring of transit systems provide comprehensive methods for planners to follow, these methods cannot fit well in practice because the planning framework did not reflect the complicated roles and goals of multiple stakeholders. Other studies simultaneously trade off the benefits of users and operators by setting multiple objectives and find a set of optimal solutions [56–66], but they failed to capture the roles and activities of governments in the network planning process.On the other hand, network-level planning strategies are practically intractable due to financial and political reasons and, in most cases, adjustments are made at the microscopic and route-by-route level. At the route level, Chien et al. [67] proposed a genetic algorithm to determine the optimal feeder bus route location and headway with minimizing the total user and operator cost. In a later study, Chien et al. [68] proposed a heuristic method to optimize bus routes, headway, and fleet size together for a many-to-one commuter travel pattern with the objective of minimizing the total of operator and user costs. Some studies also explored the optimal scheduling of a single transit route [69–73]. In addition, simulation methods have been applied to optimize a bus route. Andersson et al. [74] established a simulation model of an urban bus route to help reduce bus operation irregularities and delays during peak hours in Stockholm and further generalized the mathematical model in a relevant study [75]. Wu et al. [76] proposed a simulation framework integrating the response surface methodology to optimize stop-skipping bus service with the objective of minimizing total user and operator cost.Bus route planning is an inherently multiobjective problem [56]. However, the previous studies rarely capture multidimensional perspectives of stakeholders and their interactions with respect to route planning and the resulting performance, particularly the role of governments. To address the impact and interactions of multiperspective decisions in the transportation system, game theory approaches have been widely adopted. For example, Fisk [77] introduced basic concepts of the Nash equilibrium game and Stackelberg game and explained the idea of using a Nash game to study mode choices of travelers in a multimodal transportation network and using a Stackelberg game in signal optimization problems involving providers and travelers. Related research falls into three categories, games between travelers and operators, games between operators, and games among travelers, providers, and governments. Most studies on games between travelers and operators aim to estimate mode and route choices of travelers in the transportation network with Logit-based stochastic user equilibrium assignment [78–82]. For the competition between operators, Williams and Abdulaal [83] used a Nash-Cournot equilibrium to study the market behavior of multiple operators for a single route’s service and further extended their model [84]. In games considering these three stakeholders, Gong and Jin [85] built a trilateral game among governments, public transport enterprises, and passengers in public transit pricing adjustment. Ma and Zhang [86] established a three-stage Stackelberg game model among governments, automobile enterprises, and consumers in advocating the purchase of electric vehicles. Ling [87] used a bilevel programming model to decide the best subsidy amount provided to both transit providers and passengers in China. Limited efforts have been made to develop such a framework for transit route planning with mode and route choice behavior of travelers and decisions of governments and providers both taken into consideration.This study adds to the existing literature by proposing a modelling framework incorporating the roles and interactions of governments, operators, and travelers in bus route planning. The route frequency, fleet size, and subsidy are simultaneously optimized through a heuristic algorithm with the objectives of satisfying all three participants.


## 3. Model Formulation

In this study, interactions between transit providers and governments in bus route planning are described with a Stackelberg leader-follower game, where mode and route choices of travelers are captured based on Nested Logit models. Notations of key variables used in the model formulations are summarized in Table1.Table 1
Notation of key model parameters.
Sets and parametersO, DSets of origins and destinationsa, bModes of transportation in the studied network (a—car, b—bus)(r, s)An O-D pair (r∈O,s∈D)KrsaSet of car routes for O-D pair (r, s), with route k∈KrsaqrsTravel demand of O-D pair (r, s) (p/h)qrsbBus travel demand in O-D pair (r, s) (p/h)qrsa,kCar travel demand choosing routek in O-D pair (r, s) (p/h)crsb,trsbUnit monetary cost (RMB/p) and time cost (min/p) of O-D pair (r, s) for choosing the target bus route scrsa,k,trsa,k,drsa,kUnit monetary cost (RMB/p), time cost (min/p), and travel distance (km/p) of O-D pair (r, s) for choosing car route k, k∈KrsaWSocial cost (RMB/h)πProfit of the bus route (RMB/h)rRevenue of the bus route (RMB/h)ctTravel cost of all travelers (RMB/h)cbTotal cost of the bus route (RMB/h)caTotal cost of cars (RMB/h)ZTotal subsidy for the bus route (RMB/h)β1,γ1Unit fixed cost of buses and cars (RMB/veh/h)β2,γ2Unit labor cost of buses and cars (RMB/veh/h)β3,γ3Fuel cost of buses and cars for every kilometer (L/km)tRound trip time of the bus route (h)Decision variablesNFleet size of the bus route (veh), frequency of the bus routef=N/t (veh/h), and departure headway h=60/f (min)zUnit subsidy per passenger of the bus route (RMB/p)


### 3.1. The Stackelberg-Game-Based Modelling Framework

As shown in Figure1, decisions of the government and transit providers are described in a leader-follower Stackelberg game. The leader expects to learn how the follower responds to its decisions; that is, the leader’s decisions are optimized with the prediction of the follower’s reaction. For the target bus route, the amount of subsidy decided by the government as a leader would influence decisions of the transit provider as a follower. The government seeks to minimize social cost (including cost of travelers, bus transit, and cars along with total subsidy), while the transit provider intends to maximize its profit (including revenue, total subsidy, and cost). Decisions of fleet size and frequency by the transit provider would change the cost of the bus route and influence mode and route choices of travelers, resulting in changes of objectives for transit providers and the government accordingly.Figure 1
The leader-follower Stackelberg game between transit providers and government.Based on the leader-follower Stackelberg-game-based framework, a bilevel programming model is proposed to solve this problem, given by(1)minWz,f,Ns.t.0≤z≤zmax,where f,N solves(2)maxπz,f,Ns.t.N=1,2,…,Nmax.The lower-level decision variable is fleet sizeN (veh), while frequency of the bus route f can be calculated from N/t (veh/h). The upper-level decision variable z (RMB/p) is the unit subsidy per passenger of the bus route. Nmax and zmax are the highest frequency that transit operators can provide (veh/h) and the available unit budget of the government (RMB/p) for subsidy, respectively.


### 3.2. The Upper Level: Minimization of Social Cost

For the target bus route, the upper level reflects the perspective of the government to minimize the social cost with respect to the decision of subsidy allocation. The social cost includes the cost of travelers, bus transit, and cars, as well as the total subsidy allocated by governments, given by(3)Wz,f,N=ctf+cbf,N+caf+Zz,f,where Z, representing the total subsidy allocated to the bus route, can be calculated with(4)Zz,f=z⋅∑r∈O∑s∈Dqrsb.cbf,N is the cost of transit providers on the bus route and can be calculated with equations (8)–(11) in the lower level.ctf is the travel cost of travelers and caf represents the cost of cars, given by(5)ctf=∑r∈O∑s∈Dqrs⋅−Prsb⋅ursb−∑k∈KrsaPrsa,k⋅ursa,k,caf=∑r∈O∑s∈D∑k∈Krsaqrsa,kdrsa,kγ3Fa+γ1+γ2qrsa,k,where ursb and Prsb represent the deterministic components of the utility functions and the percentage of O-D pair (r, s) choosing the target bus route, calculated in equations (14) and (18); ursa,k and Prsa,k represent the deterministic components of the utility functions and the percentage of O-D pair (r, s) choosing car route k, calculated in equations (15) and (19). Fa is the unit fuel price of cars (RMB/L).


### 3.3. The Lower Level: Maximization of Profits

The lower-level problem aims to maximize the profit of transit providers for operating the target bus route,π, given by(6)πz,N,f=rf+Zz,f−cbf,N,where Z is the total subsidy allocated to the target bus route given by equation (4) and r is the revenue of transit providers for operating the bus route, given by(7)rf=∑r∈O∑s∈Dcrsbqrsb.The total cost of transit providers on the bus route,cb, is given by(8)cbN,f=cbpN+CblN+Cbef,(9)cbpN=β1N,(10)cblN=β2N,(11)cbef=β3Fbvbft,where cbpN, cblN, and cbeN represent the fixed cost of purchasing buses (RMB/h), labor cost (RMB/h), and fuel cost (RMB/h), respectively;Fb is the unit fuel price of buses (RMB/L); vb is the average bus travel speed (km/h); vbft is the total hourly travel distance of buses (km/h).In the proposed framework, transit providers need to consider how their decisions on bus frequency and fleet size would influence the choice of travelers and the resulting social cost and profit, as illustrated in Figure1. In this study, a two-level Nested Logit model is employed to represent mode and route choices of travelers in response to the decisions of transit operators, where travelers make mode choices at the first level and decide routes of the chosen mode in the second level. For simplicity of illustration, the target bus route is considered as the only available one between O-D pairs; that is, travelers will not make route decisions in the second level if they choose to take buses in the first level.Utilities of travelers are comprised of time and monetary cost. The utilities of O-D pair (r, s) choosing the target bus route and car route k are given by(12)Ursb=ursb+εrsb,(13)Ursa,k=ursa,k+εrsa,k,(14)ursb=−crsb−αtrsb,(15)ursa,k=−crsa,k−αtrsa,k,where ursb and ursa,k are the deterministic components of the utility functions; α is the value of time of travelers (RMB/min); trsb is the time cost of O-D pair (r, s) taking the target bus route (min), comprised of the walking time to bus stops trsb,p, in-vehicle time trsb,v, and waiting time at bus stops trsb,w, given by(16)trsb=trsb,p+trsb,v+trsb,w.According to Larson and Odoni [88], the mean waiting time of passengers at bus stops trsb,w can be described in the following equation:(17)trsb,w=ξ⋅60f,where ξ is given in three different situations: ξ=1/2 when buses arrive with perfect headways; ξ=1 when buses arrive according to a Poisson process; ξ=3/4 when buses clumped in pairs 50 percent of the time.Therefore, the percentages of travelers choosing the target bus route and car routek are given by(18)Prsb=expθursbexpθursb+expθursa,(19)Prsa,k=expθursaexpθursb+expθursa⋅expλaursa,k∑k∈Krsaexpλaursa,k,(20)ursa=1λaln∑k∈Krsaexpλaursa,k,where θ is a scale parameter associated with the choice between buses and cars with θ>0; ursa is the overall expected utility of O-D pair (r, s) choosing the car mode, given by equation (20), where λa is a scale parameter for choosing between different car routes, λa>0 and θ/λa≤1.Thus, the total number of passengers traveling with the target bus route for O-D pair (r, s) is given by(21)qrsb=qrs⋅expθursbexpθursb+expθursa.The total number of travelers using car routek for O-D pair (r, s) is given by(22)qrsa,k=qrs⋅expθursaexpθursb+expθursa⋅expλaursa,k∑k∈Krsaexpλaursa,k.


## 3.1. The Stackelberg-Game-Based Modelling Framework

As shown in Figure1, decisions of the government and transit providers are described in a leader-follower Stackelberg game. The leader expects to learn how the follower responds to its decisions; that is, the leader’s decisions are optimized with the prediction of the follower’s reaction. For the target bus route, the amount of subsidy decided by the government as a leader would influence decisions of the transit provider as a follower. The government seeks to minimize social cost (including cost of travelers, bus transit, and cars along with total subsidy), while the transit provider intends to maximize its profit (including revenue, total subsidy, and cost). Decisions of fleet size and frequency by the transit provider would change the cost of the bus route and influence mode and route choices of travelers, resulting in changes of objectives for transit providers and the government accordingly.Figure 1
The leader-follower Stackelberg game between transit providers and government.Based on the leader-follower Stackelberg-game-based framework, a bilevel programming model is proposed to solve this problem, given by(1)minWz,f,Ns.t.0≤z≤zmax,where f,N solves(2)maxπz,f,Ns.t.N=1,2,…,Nmax.The lower-level decision variable is fleet sizeN (veh), while frequency of the bus route f can be calculated from N/t (veh/h). The upper-level decision variable z (RMB/p) is the unit subsidy per passenger of the bus route. Nmax and zmax are the highest frequency that transit operators can provide (veh/h) and the available unit budget of the government (RMB/p) for subsidy, respectively.


## 3.2. The Upper Level: Minimization of Social Cost

For the target bus route, the upper level reflects the perspective of the government to minimize the social cost with respect to the decision of subsidy allocation. The social cost includes the cost of travelers, bus transit, and cars, as well as the total subsidy allocated by governments, given by(3)Wz,f,N=ctf+cbf,N+caf+Zz,f,where Z, representing the total subsidy allocated to the bus route, can be calculated with(4)Zz,f=z⋅∑r∈O∑s∈Dqrsb.cbf,N is the cost of transit providers on the bus route and can be calculated with equations (8)–(11) in the lower level.ctf is the travel cost of travelers and caf represents the cost of cars, given by(5)ctf=∑r∈O∑s∈Dqrs⋅−Prsb⋅ursb−∑k∈KrsaPrsa,k⋅ursa,k,caf=∑r∈O∑s∈D∑k∈Krsaqrsa,kdrsa,kγ3Fa+γ1+γ2qrsa,k,where ursb and Prsb represent the deterministic components of the utility functions and the percentage of O-D pair (r, s) choosing the target bus route, calculated in equations (14) and (18); ursa,k and Prsa,k represent the deterministic components of the utility functions and the percentage of O-D pair (r, s) choosing car route k, calculated in equations (15) and (19). Fa is the unit fuel price of cars (RMB/L).


## 3.3. The Lower Level: Maximization of Profits

The lower-level problem aims to maximize the profit of transit providers for operating the target bus route,π, given by(6)πz,N,f=rf+Zz,f−cbf,N,where Z is the total subsidy allocated to the target bus route given by equation (4) and r is the revenue of transit providers for operating the bus route, given by(7)rf=∑r∈O∑s∈Dcrsbqrsb.The total cost of transit providers on the bus route,cb, is given by(8)cbN,f=cbpN+CblN+Cbef,(9)cbpN=β1N,(10)cblN=β2N,(11)cbef=β3Fbvbft,where cbpN, cblN, and cbeN represent the fixed cost of purchasing buses (RMB/h), labor cost (RMB/h), and fuel cost (RMB/h), respectively;Fb is the unit fuel price of buses (RMB/L); vb is the average bus travel speed (km/h); vbft is the total hourly travel distance of buses (km/h).In the proposed framework, transit providers need to consider how their decisions on bus frequency and fleet size would influence the choice of travelers and the resulting social cost and profit, as illustrated in Figure1. In this study, a two-level Nested Logit model is employed to represent mode and route choices of travelers in response to the decisions of transit operators, where travelers make mode choices at the first level and decide routes of the chosen mode in the second level. For simplicity of illustration, the target bus route is considered as the only available one between O-D pairs; that is, travelers will not make route decisions in the second level if they choose to take buses in the first level.Utilities of travelers are comprised of time and monetary cost. The utilities of O-D pair (r, s) choosing the target bus route and car route k are given by(12)Ursb=ursb+εrsb,(13)Ursa,k=ursa,k+εrsa,k,(14)ursb=−crsb−αtrsb,(15)ursa,k=−crsa,k−αtrsa,k,where ursb and ursa,k are the deterministic components of the utility functions; α is the value of time of travelers (RMB/min); trsb is the time cost of O-D pair (r, s) taking the target bus route (min), comprised of the walking time to bus stops trsb,p, in-vehicle time trsb,v, and waiting time at bus stops trsb,w, given by(16)trsb=trsb,p+trsb,v+trsb,w.According to Larson and Odoni [88], the mean waiting time of passengers at bus stops trsb,w can be described in the following equation:(17)trsb,w=ξ⋅60f,where ξ is given in three different situations: ξ=1/2 when buses arrive with perfect headways; ξ=1 when buses arrive according to a Poisson process; ξ=3/4 when buses clumped in pairs 50 percent of the time.Therefore, the percentages of travelers choosing the target bus route and car routek are given by(18)Prsb=expθursbexpθursb+expθursa,(19)Prsa,k=expθursaexpθursb+expθursa⋅expλaursa,k∑k∈Krsaexpλaursa,k,(20)ursa=1λaln∑k∈Krsaexpλaursa,k,where θ is a scale parameter associated with the choice between buses and cars with θ>0; ursa is the overall expected utility of O-D pair (r, s) choosing the car mode, given by equation (20), where λa is a scale parameter for choosing between different car routes, λa>0 and θ/λa≤1.Thus, the total number of passengers traveling with the target bus route for O-D pair (r, s) is given by(21)qrsb=qrs⋅expθursbexpθursb+expθursa.The total number of travelers using car routek for O-D pair (r, s) is given by(22)qrsa,k=qrs⋅expθursaexpθursb+expθursa⋅expλaursa,k∑k∈Krsaexpλaursa,k.


## 4. Solution Algorithm

Generally speaking, the optimal solution for a bilevel programming problem is reached when the lower-level objective is optimized under the given upper-level variables, and the upper-level objective also reaches its optimal value with the prediction of the lower-level decisions. This study develops a partition-based-bisection algorithm to solve the proposed model based on identifying the unique response pattern of the lower-level transit providers to the upper-level decisions of government, detailed as follows.


### 4.1. Lower-Level Decisions in response to the Upper Level

For simplicity of illustration, assuming a uniform monetary cost of taking buses for all O-D pairs, that is,crsb=η,∀r∈O,s∈D, in this model, reactions of the lower-level local optimal N (or f) when considered as a continuous variable can be captured with changes of the upper level z in a certain direction. In other words, the lower-level local optimal points of N increase or no longer exist as z increases, which is further proved in the Appendix. The response pattern of the lower-level local optimal fleet size to the upper-level subsidy provides the direction on how to search the optimal value of lower-level decision variables when the subsidy is increasing, which can be used to design the solution algorithm.


### 4.2. The Partition-Based-Bisection Algorithm

A partition-based-bisection algorithm is proposed to solve the model with the overall procedure divided into a main algorithm consisting of three general steps (Steps 1, 3, and 4) and a bisection algorithm fulfilling a major intermediate step (Step 2). The algorithm is summarized in Figure2 and each step is illustrated in Figure 3. The first step is to find the initial starting points of the fleet size from the beginning of subsidy at 0. In the second step, bisection methods are used to define the partitioned rectangular-shaped and ladder-shaped areas as shown in Figure 3(b). For each area with the same fleet size, points with the smallest subsidy are considered as candidates for the lower level because the upper-level function value increases as z increases when f and N are fixed, as indicated in equations (3) and (4). Furthermore, comparisons between these candidate points and the lower and upper bounds of the fleet size are made to further decide the optimal decisions of the lower level in Step 3. Finally, the best solution for both levels is identified in the fourth step.Figure 2
The overall procedure of the proposed partition-based-bisection algorithm.Figure 3
Steps of the solution algorithm. (a) Step 1. (b) Step 2. (c) Step 3. (d) Step 4.
(a)(b)(c)(d)Step 1.
Find the set of initial fleet size pointsLc0=N0i|i=1,…,I for subsidy z=z0, identified by πz0,N0i,N0i/t>πz0,N0i−1,N0i−1/t and πz0,N0i,N0i/t>πz0,N0i+1,N0i+1/t. Start from z0=0, and increase z0 with 0.1 RMB/p each time until an initial point is found or the maximal subsidy is reached. If the maximal subsidy is reached, that is, no initial point is found, compare the lower and upper limits of the fleet size and the subsidy and identify the optimal value for both levels. Otherwise, for each point N0i, do Step 2 to find the lower-level candidate set. The detailed process is described in Step 1 of Figure 2. The expected examples of the initial fleet size and the subsidy starting points are illustrated as the red dots in Figure 3(a).Step 2.
Use the bisection method to find all the partition points of the subsidy and the fleet size for eachN0i∈Lc0, as suggested in Step 2 of Figure 2 (bisection algorithm).(a)
N=N0i. Take z0 for N as the lower boundary of the bisection interval.(b)
Set step length of subsidyωz = 1; find zu where N are no longer local optimal, which can be identified by πzu,N,N/t <πzu,N+1,N+1/t. Then the initial interval z0,zu is defined.(c)
Calculate the midpointzmid of z0,zu.(d)
Ifπzmid,N,N/t<πzmid,N+1,N+1/t, zu=zmid. If πzmid,N,N/t≥πzmid,N+1,N+1/t, z0=zmid.(e)
Repeat (c) and (d). If the convergence criterion (zu−z0≤0.001) is met, z0+zu/2 is the partition point for N and N+1.(f)
Ifπz0,N+1,N+1/t <πz0,N+2,N+2/t, there is no longer a possible candidate point in z0,zmax. N=N0i+1. Take z0 for N as the lower boundary of the bisection interval. Skip to (b).
Else if the maximal subsidyzmax is reached. N=N0i+1. Take z0 for N as the lower boundary of the bisection interval. Skip to (b).
ElseN=N+1. Take z0=z0+zu/2 for N as the lower boundary of the bisection interval. Repeat (b) to (f) to get the partition point of the subsidy for the new N.
For eachN0i, a ladder-shaped or rectangular-shaped candidate area is obtained (see Figure 3(b)). Solution candidates for each initial point N0i include the left point of the rectangular-shaped area or the left point and partition points of the ladder-shaped area. Identify the candidate set Lc=zji,Nji|i=1,…,I,j=1,…,Ji, where Ji is the total number of partition points for each starting point N0i.Step 3.
For eachzji in Lc, compare πzji,Nji,Nji/t with πzji,Nmin,Nmin/t and πzji,Nmax,Nmax/t. If there are two or more partition points with the same value of subsidy zji, comparisons between the fleet sizes of these points along with the lower and upper limits of the fleet size on the lower-level function are also necessary. Therefore, the lower-level optimal set Lcmax=zlk,Nlk,flk|k=1,…,K is identified (i.e., the red triangles in Figure 3(c)), where K is the total number of the partition points with different values of the subsidy.Step 4.
Calculate the upper-level function value for each point and select the optimal point with optimal value. Then the optimal solution for both levels is obtained, indicated as the red star in Figure3(d).


## 4.1. Lower-Level Decisions in response to the Upper Level

For simplicity of illustration, assuming a uniform monetary cost of taking buses for all O-D pairs, that is,crsb=η,∀r∈O,s∈D, in this model, reactions of the lower-level local optimal N (or f) when considered as a continuous variable can be captured with changes of the upper level z in a certain direction. In other words, the lower-level local optimal points of N increase or no longer exist as z increases, which is further proved in the Appendix. The response pattern of the lower-level local optimal fleet size to the upper-level subsidy provides the direction on how to search the optimal value of lower-level decision variables when the subsidy is increasing, which can be used to design the solution algorithm.


## 4.2. The Partition-Based-Bisection Algorithm

A partition-based-bisection algorithm is proposed to solve the model with the overall procedure divided into a main algorithm consisting of three general steps (Steps 1, 3, and 4) and a bisection algorithm fulfilling a major intermediate step (Step 2). The algorithm is summarized in Figure2 and each step is illustrated in Figure 3. The first step is to find the initial starting points of the fleet size from the beginning of subsidy at 0. In the second step, bisection methods are used to define the partitioned rectangular-shaped and ladder-shaped areas as shown in Figure 3(b). For each area with the same fleet size, points with the smallest subsidy are considered as candidates for the lower level because the upper-level function value increases as z increases when f and N are fixed, as indicated in equations (3) and (4). Furthermore, comparisons between these candidate points and the lower and upper bounds of the fleet size are made to further decide the optimal decisions of the lower level in Step 3. Finally, the best solution for both levels is identified in the fourth step.Figure 2
The overall procedure of the proposed partition-based-bisection algorithm.Figure 3
Steps of the solution algorithm. (a) Step 1. (b) Step 2. (c) Step 3. (d) Step 4.
(a)(b)(c)(d)Step 1.
Find the set of initial fleet size pointsLc0=N0i|i=1,…,I for subsidy z=z0, identified by πz0,N0i,N0i/t>πz0,N0i−1,N0i−1/t and πz0,N0i,N0i/t>πz0,N0i+1,N0i+1/t. Start from z0=0, and increase z0 with 0.1 RMB/p each time until an initial point is found or the maximal subsidy is reached. If the maximal subsidy is reached, that is, no initial point is found, compare the lower and upper limits of the fleet size and the subsidy and identify the optimal value for both levels. Otherwise, for each point N0i, do Step 2 to find the lower-level candidate set. The detailed process is described in Step 1 of Figure 2. The expected examples of the initial fleet size and the subsidy starting points are illustrated as the red dots in Figure 3(a).Step 2.
Use the bisection method to find all the partition points of the subsidy and the fleet size for eachN0i∈Lc0, as suggested in Step 2 of Figure 2 (bisection algorithm).(a)
N=N0i. Take z0 for N as the lower boundary of the bisection interval.(b)
Set step length of subsidyωz = 1; find zu where N are no longer local optimal, which can be identified by πzu,N,N/t <πzu,N+1,N+1/t. Then the initial interval z0,zu is defined.(c)
Calculate the midpointzmid of z0,zu.(d)
Ifπzmid,N,N/t<πzmid,N+1,N+1/t, zu=zmid. If πzmid,N,N/t≥πzmid,N+1,N+1/t, z0=zmid.(e)
Repeat (c) and (d). If the convergence criterion (zu−z0≤0.001) is met, z0+zu/2 is the partition point for N and N+1.(f)
Ifπz0,N+1,N+1/t <πz0,N+2,N+2/t, there is no longer a possible candidate point in z0,zmax. N=N0i+1. Take z0 for N as the lower boundary of the bisection interval. Skip to (b).
Else if the maximal subsidyzmax is reached. N=N0i+1. Take z0 for N as the lower boundary of the bisection interval. Skip to (b).
ElseN=N+1. Take z0=z0+zu/2 for N as the lower boundary of the bisection interval. Repeat (b) to (f) to get the partition point of the subsidy for the new N.
For eachN0i, a ladder-shaped or rectangular-shaped candidate area is obtained (see Figure 3(b)). Solution candidates for each initial point N0i include the left point of the rectangular-shaped area or the left point and partition points of the ladder-shaped area. Identify the candidate set Lc=zji,Nji|i=1,…,I,j=1,…,Ji, where Ji is the total number of partition points for each starting point N0i.Step 3.
For eachzji in Lc, compare πzji,Nji,Nji/t with πzji,Nmin,Nmin/t and πzji,Nmax,Nmax/t. If there are two or more partition points with the same value of subsidy zji, comparisons between the fleet sizes of these points along with the lower and upper limits of the fleet size on the lower-level function are also necessary. Therefore, the lower-level optimal set Lcmax=zlk,Nlk,flk|k=1,…,K is identified (i.e., the red triangles in Figure 3(c)), where K is the total number of the partition points with different values of the subsidy.Step 4.
Calculate the upper-level function value for each point and select the optimal point with optimal value. Then the optimal solution for both levels is obtained, indicated as the red star in Figure3(d).


## 5. Case Study

### 5.1. The Studied Route

This study selects an existing bus route (Route 85) in Shanghai, China, for a case study. Model parameters are calibrated through automatically collected Bus GPS data, Smart Card data, and taxi operation data, using 7:00–9:00 am on August 1st, 2016, as the study period. Current passenger volume of the bus route is obtained from Smart (IC) Card data. In addition, 6,853 taxi operation records around the bus route during the study period are selected to extract O-D (Origin-Destination), travel time, trip distance, and taxi fare as both travel demand and taxi operation parameters. To estimate the bus operation parameters, 163,898 GPS records of the study bus route on Aug 1st, 2016, are processed. The distribution of O-D pairs and trajectories of the studied bus route are shown in Figure4.Figure 4
Case study bus route and demand distribution.Table2 summarizes the key parameters of the target bus route extracted from real-world Smart Card and GPS data.Table 2
Parameters of the studied bus route in current operational condition.
ParameterValuefe13 veh/hqbe1004 p/hNe30 vehze3.15 RMB/pvb19.71 km/ht1.42 hβ110.27 RMB/veh/hβ26.94 RMB/veh/hβ30.4 L/kmη2 RMB/pFb6.88 RMB/Lγ12.28 RMB/veh/hγ28.33 RMB/veh/hγ30.12 L/kmFa10 RMB/Lθ0.8α2.6 RMB/mincrsa,k can be estimated with the taxi fare structure in Shanghai, given by(23)crsa,k=14,drsa,k≤3km,14+2.4⋅drsa,k−3,3km<drsa,k≤10km,14+2.4⋅10−3+3.6⋅drsa,k−10,drsa,k>10km.The cost per km varies in three different levels of trip distance. A fixed 14 RMB is required when the trip distance is smaller than 3 km. If the distance exceeds 3 km but no more than 10 km, the ride exceeding 3 km is charged with 2.4 RMB/km (total cost would be 14 RMB for the first 3 km ride plus 2.4 times the distance exceeding 3 km). If the distance exceeds 10 km, 3.6 RMB/km is the unit price for the ride exceeding 10 km (total cost would be 14 RMB for the first 3 km ride, 16.8 RMB for the second 7 km ride, and 3.6 times the distance exceeding 10 km).


### 5.2. Results

Given the studied route, the proposed model optimizes and adjusts its frequency, fleet size, and subsidy from 13 veh/h to 13.38 veh/h, from 30 veh to 19 veh, and from 3.15 RMB/p to 3.29 RMB/p, respectively. The resulting changes of profit and cost structures at the upper and lower levels are illustrated in Figures5 and 6. At the lower level, as shown in Figure 5, the revenue of the target bus route increases 77% (318.75 RMB/h versus 565.35 RMB/h) with the proposed model, due to the increased revenue (713.41 RMB/h versus 727.54 RMB/h), increased subsidy (1123.62 RMB/h versus 1195.75 RMB/h), and decreased cost (1518.28 RMB/h versus 1357.94 RMB/h).Figure 5
Lower-level transit profit structure before and after the adjustment with the proposed model.Figure 6
Upper-level social cost structure before and after the adjustment with the proposed model.At the upper level, from the perspective of the government that takes social cost as its main consideration, except for the increased total subsidy as a cost of governments, the cost of travelers, taxi operation, and bus transit all decrease, resulting in an overall decrease of the social cost after the adjustment (65954.46 RMB/h versus 65699.2 RMB/h, as shown in Figure6). The results of both levels validate the effectiveness of the proposed model and algorithm for both transit providers and the government with respect to increasing transit profit and reducing social cost.


### 5.3. Sensitivity Analyses

In this section, sensitivity analyses of the model performance with respect to the value of time (VOT) of travelers and government budget for subsidy are further conducted to better guide the application of the proposed model.


#### 5.3.1. Value of Time (VOT)

Variations of the number of transit users with VOT (from 0.4 RMB/min to 6.0 RMB/min) under different budget levels (1.0 RMB/p to 6.0 RMB/p) are illustrated in Figure7. At each budget level, it is interesting to observe a threshold value (i.e., 2.5 RMB/min when budget = 1.0 RMB/p; 2.9 RMB/min when budget = 2.0 RMB/p; 3.2 RMB/min when budget = 3.0 RMB/p; 3.3 RMB/min when budget = 4.0 RMB/p; 3.6 RMB/min when budget = 5.0 RMB/p; 3.8 RMB/min when budget = 6.0 RMB/p) after which the number of transit users drops off to 0. A similar pattern of threshold value could also be found in Figures 8 and 9, which exhibit the changes of transit profit structure and social cost structure with increasing VOT under different budget levels, respectively. Transit operation revenue (Figure 8(a)), cost (Figure 8(b)), and profit (Figure 8(d)), along with government subsidies (Figures 8(c) and 9(b)) and taxi operation cost (Figure 9(d)), would reach 0 beyond the threshold, indicating that travelers with a relatively higher VOT would no longer consider bus transit as a choice no matter what decisions are made from transit operators and the government side. Such findings are critical for the government agencies and transit operators to target potential groups of travelers and areas of interests when planning a bus route.Figure 7
Variation of transit users with VOT under different budget levels.Figure 8
Variation of transit profit structure with VOT under different budget levels.
(a)(b)(c)(d)Figure 9
Variation of social cost components with VOT under different budget levels.
(a)(b)(c)(d)(e)Increase of VOT within the threshold value leads to more people using cars instead of buses (see Figure7). Therefore, transit operators need to raise their inputs on frequency and fleet size to improve the competitiveness of buses, resulting in more cost (see Figure 8(b)). Meanwhile, revenue of transit operators is reduced as a result of fewer transit users, as shown in Figure 8(c). Therefore, the overall transit operator’s profit decreases (see Figure 8(d)), along with certain fluctuations caused by optimizing government subsidy allocation decisions (see Figure 8(c) or Figure 9(b)). The largest transit profit is reached where VOT is around 0.8 RMB/min. From the perspective of governments, social cost increases (Figure 9(e)) with VOT as a result of the increasing user cost, transit cost, and taxi cost (see Figures 9(a), 9(c), and 9(d)), and the increment becomes linear after the threshold value is reached. Therefore, the government and transit operators should consider VOT as a crucial factor when evaluating the profit and cost of a bus route.


#### 5.3.2. Government Budget

A higher budget level leads to more transit users, revenue, cost, subsidies, and less car operation cost would be observed with the same VOT, as shown in Figures7–9. However, it is notable that, at each VOT level, budget would not make a difference on results of the model when it is relatively high. This could be further validated in Figure 10, which summarizes the optimal unit subsidy per passenger from the proposed model with different given unit budgets. One can observe that the optimal subsidy increases with the budget and remains stable when the available budget reaches a threshold value (i.e., 1.2 RMB/p when VOT = 1.2 RMB/min; 2 RMB/p when VOT = 1.8 RMB/min; 2.8 RMB/p when VOT = 2.4 RMB/min; 3.6 RMB/p when VOT = 3.0 RMB/min; 4.8 RMB/p when VOT = 3.6 RMB/min). The threshold value increases accordingly when VOT grows larger, indicating that there exists an appropriate subsidy budget for the government to reserve given the VOT to optimize the operation of the target bus route. A larger budget for a subsidy may not help to improve the operational performance of the bus route and when the VOT is very low (e.g., 0.6 RMB/min), subsidies are not necessary. Therefore, observations of the optimal subsidy budget would benefit the government to reserve an appropriate level of budget for subsidy allocation to achieve the best transit operational performance.Figure 10
Variation of optimal subsidies with the budget.


## 5.1. The Studied Route

This study selects an existing bus route (Route 85) in Shanghai, China, for a case study. Model parameters are calibrated through automatically collected Bus GPS data, Smart Card data, and taxi operation data, using 7:00–9:00 am on August 1st, 2016, as the study period. Current passenger volume of the bus route is obtained from Smart (IC) Card data. In addition, 6,853 taxi operation records around the bus route during the study period are selected to extract O-D (Origin-Destination), travel time, trip distance, and taxi fare as both travel demand and taxi operation parameters. To estimate the bus operation parameters, 163,898 GPS records of the study bus route on Aug 1st, 2016, are processed. The distribution of O-D pairs and trajectories of the studied bus route are shown in Figure4.Figure 4
Case study bus route and demand distribution.Table2 summarizes the key parameters of the target bus route extracted from real-world Smart Card and GPS data.Table 2
Parameters of the studied bus route in current operational condition.
ParameterValuefe13 veh/hqbe1004 p/hNe30 vehze3.15 RMB/pvb19.71 km/ht1.42 hβ110.27 RMB/veh/hβ26.94 RMB/veh/hβ30.4 L/kmη2 RMB/pFb6.88 RMB/Lγ12.28 RMB/veh/hγ28.33 RMB/veh/hγ30.12 L/kmFa10 RMB/Lθ0.8α2.6 RMB/mincrsa,k can be estimated with the taxi fare structure in Shanghai, given by(23)crsa,k=14,drsa,k≤3km,14+2.4⋅drsa,k−3,3km<drsa,k≤10km,14+2.4⋅10−3+3.6⋅drsa,k−10,drsa,k>10km.The cost per km varies in three different levels of trip distance. A fixed 14 RMB is required when the trip distance is smaller than 3 km. If the distance exceeds 3 km but no more than 10 km, the ride exceeding 3 km is charged with 2.4 RMB/km (total cost would be 14 RMB for the first 3 km ride plus 2.4 times the distance exceeding 3 km). If the distance exceeds 10 km, 3.6 RMB/km is the unit price for the ride exceeding 10 km (total cost would be 14 RMB for the first 3 km ride, 16.8 RMB for the second 7 km ride, and 3.6 times the distance exceeding 10 km).


## 5.2. Results

Given the studied route, the proposed model optimizes and adjusts its frequency, fleet size, and subsidy from 13 veh/h to 13.38 veh/h, from 30 veh to 19 veh, and from 3.15 RMB/p to 3.29 RMB/p, respectively. The resulting changes of profit and cost structures at the upper and lower levels are illustrated in Figures5 and 6. At the lower level, as shown in Figure 5, the revenue of the target bus route increases 77% (318.75 RMB/h versus 565.35 RMB/h) with the proposed model, due to the increased revenue (713.41 RMB/h versus 727.54 RMB/h), increased subsidy (1123.62 RMB/h versus 1195.75 RMB/h), and decreased cost (1518.28 RMB/h versus 1357.94 RMB/h).Figure 5
Lower-level transit profit structure before and after the adjustment with the proposed model.Figure 6
Upper-level social cost structure before and after the adjustment with the proposed model.At the upper level, from the perspective of the government that takes social cost as its main consideration, except for the increased total subsidy as a cost of governments, the cost of travelers, taxi operation, and bus transit all decrease, resulting in an overall decrease of the social cost after the adjustment (65954.46 RMB/h versus 65699.2 RMB/h, as shown in Figure6). The results of both levels validate the effectiveness of the proposed model and algorithm for both transit providers and the government with respect to increasing transit profit and reducing social cost.


## 5.3. Sensitivity Analyses

In this section, sensitivity analyses of the model performance with respect to the value of time (VOT) of travelers and government budget for subsidy are further conducted to better guide the application of the proposed model.


### 5.3.1. Value of Time (VOT)

Variations of the number of transit users with VOT (from 0.4 RMB/min to 6.0 RMB/min) under different budget levels (1.0 RMB/p to 6.0 RMB/p) are illustrated in Figure7. At each budget level, it is interesting to observe a threshold value (i.e., 2.5 RMB/min when budget = 1.0 RMB/p; 2.9 RMB/min when budget = 2.0 RMB/p; 3.2 RMB/min when budget = 3.0 RMB/p; 3.3 RMB/min when budget = 4.0 RMB/p; 3.6 RMB/min when budget = 5.0 RMB/p; 3.8 RMB/min when budget = 6.0 RMB/p) after which the number of transit users drops off to 0. A similar pattern of threshold value could also be found in Figures 8 and 9, which exhibit the changes of transit profit structure and social cost structure with increasing VOT under different budget levels, respectively. Transit operation revenue (Figure 8(a)), cost (Figure 8(b)), and profit (Figure 8(d)), along with government subsidies (Figures 8(c) and 9(b)) and taxi operation cost (Figure 9(d)), would reach 0 beyond the threshold, indicating that travelers with a relatively higher VOT would no longer consider bus transit as a choice no matter what decisions are made from transit operators and the government side. Such findings are critical for the government agencies and transit operators to target potential groups of travelers and areas of interests when planning a bus route.Figure 7
Variation of transit users with VOT under different budget levels.Figure 8
Variation of transit profit structure with VOT under different budget levels.
(a)(b)(c)(d)Figure 9
Variation of social cost components with VOT under different budget levels.
(a)(b)(c)(d)(e)Increase of VOT within the threshold value leads to more people using cars instead of buses (see Figure7). Therefore, transit operators need to raise their inputs on frequency and fleet size to improve the competitiveness of buses, resulting in more cost (see Figure 8(b)). Meanwhile, revenue of transit operators is reduced as a result of fewer transit users, as shown in Figure 8(c). Therefore, the overall transit operator’s profit decreases (see Figure 8(d)), along with certain fluctuations caused by optimizing government subsidy allocation decisions (see Figure 8(c) or Figure 9(b)). The largest transit profit is reached where VOT is around 0.8 RMB/min. From the perspective of governments, social cost increases (Figure 9(e)) with VOT as a result of the increasing user cost, transit cost, and taxi cost (see Figures 9(a), 9(c), and 9(d)), and the increment becomes linear after the threshold value is reached. Therefore, the government and transit operators should consider VOT as a crucial factor when evaluating the profit and cost of a bus route.


### 5.3.2. Government Budget

A higher budget level leads to more transit users, revenue, cost, subsidies, and less car operation cost would be observed with the same VOT, as shown in Figures7–9. However, it is notable that, at each VOT level, budget would not make a difference on results of the model when it is relatively high. This could be further validated in Figure 10, which summarizes the optimal unit subsidy per passenger from the proposed model with different given unit budgets. One can observe that the optimal subsidy increases with the budget and remains stable when the available budget reaches a threshold value (i.e., 1.2 RMB/p when VOT = 1.2 RMB/min; 2 RMB/p when VOT = 1.8 RMB/min; 2.8 RMB/p when VOT = 2.4 RMB/min; 3.6 RMB/p when VOT = 3.0 RMB/min; 4.8 RMB/p when VOT = 3.6 RMB/min). The threshold value increases accordingly when VOT grows larger, indicating that there exists an appropriate subsidy budget for the government to reserve given the VOT to optimize the operation of the target bus route. A larger budget for a subsidy may not help to improve the operational performance of the bus route and when the VOT is very low (e.g., 0.6 RMB/min), subsidies are not necessary. Therefore, observations of the optimal subsidy budget would benefit the government to reserve an appropriate level of budget for subsidy allocation to achieve the best transit operational performance.Figure 10
Variation of optimal subsidies with the budget.


## 5.3.1. Value of Time (VOT)

Variations of the number of transit users with VOT (from 0.4 RMB/min to 6.0 RMB/min) under different budget levels (1.0 RMB/p to 6.0 RMB/p) are illustrated in Figure7. At each budget level, it is interesting to observe a threshold value (i.e., 2.5 RMB/min when budget = 1.0 RMB/p; 2.9 RMB/min when budget = 2.0 RMB/p; 3.2 RMB/min when budget = 3.0 RMB/p; 3.3 RMB/min when budget = 4.0 RMB/p; 3.6 RMB/min when budget = 5.0 RMB/p; 3.8 RMB/min when budget = 6.0 RMB/p) after which the number of transit users drops off to 0. A similar pattern of threshold value could also be found in Figures 8 and 9, which exhibit the changes of transit profit structure and social cost structure with increasing VOT under different budget levels, respectively. Transit operation revenue (Figure 8(a)), cost (Figure 8(b)), and profit (Figure 8(d)), along with government subsidies (Figures 8(c) and 9(b)) and taxi operation cost (Figure 9(d)), would reach 0 beyond the threshold, indicating that travelers with a relatively higher VOT would no longer consider bus transit as a choice no matter what decisions are made from transit operators and the government side. Such findings are critical for the government agencies and transit operators to target potential groups of travelers and areas of interests when planning a bus route.Figure 7
Variation of transit users with VOT under different budget levels.Figure 8
Variation of transit profit structure with VOT under different budget levels.
(a)(b)(c)(d)Figure 9
Variation of social cost components with VOT under different budget levels.
(a)(b)(c)(d)(e)Increase of VOT within the threshold value leads to more people using cars instead of buses (see Figure7). Therefore, transit operators need to raise their inputs on frequency and fleet size to improve the competitiveness of buses, resulting in more cost (see Figure 8(b)). Meanwhile, revenue of transit operators is reduced as a result of fewer transit users, as shown in Figure 8(c). Therefore, the overall transit operator’s profit decreases (see Figure 8(d)), along with certain fluctuations caused by optimizing government subsidy allocation decisions (see Figure 8(c) or Figure 9(b)). The largest transit profit is reached where VOT is around 0.8 RMB/min. From the perspective of governments, social cost increases (Figure 9(e)) with VOT as a result of the increasing user cost, transit cost, and taxi cost (see Figures 9(a), 9(c), and 9(d)), and the increment becomes linear after the threshold value is reached. Therefore, the government and transit operators should consider VOT as a crucial factor when evaluating the profit and cost of a bus route.


## 5.3.2. Government Budget

A higher budget level leads to more transit users, revenue, cost, subsidies, and less car operation cost would be observed with the same VOT, as shown in Figures7–9. However, it is notable that, at each VOT level, budget would not make a difference on results of the model when it is relatively high. This could be further validated in Figure 10, which summarizes the optimal unit subsidy per passenger from the proposed model with different given unit budgets. One can observe that the optimal subsidy increases with the budget and remains stable when the available budget reaches a threshold value (i.e., 1.2 RMB/p when VOT = 1.2 RMB/min; 2 RMB/p when VOT = 1.8 RMB/min; 2.8 RMB/p when VOT = 2.4 RMB/min; 3.6 RMB/p when VOT = 3.0 RMB/min; 4.8 RMB/p when VOT = 3.6 RMB/min). The threshold value increases accordingly when VOT grows larger, indicating that there exists an appropriate subsidy budget for the government to reserve given the VOT to optimize the operation of the target bus route. A larger budget for a subsidy may not help to improve the operational performance of the bus route and when the VOT is very low (e.g., 0.6 RMB/min), subsidies are not necessary. Therefore, observations of the optimal subsidy budget would benefit the government to reserve an appropriate level of budget for subsidy allocation to achieve the best transit operational performance.Figure 10
Variation of optimal subsidies with the budget.


## 6. Conclusion

This study contributes to developing a multidimensional Stackelberg game framework for bus route planning or replanning by capturing multiple stakeholders’ perspectives and interactions. In this framework, decisions of transit providers and the government are based on the leader-follower Stackelberg game theory. Transit providers determine the frequency and fleet size from the perspective of optimizing profits under the given subsidy, while the government seeks to minimize the social cost by allocating a certain amount of subsidies to the bus route with predicting decisions of transit providers. Mode and route choice behavior of travelers are captured with the Nested Logit models, which are also affected by the decisions of transit providers. This framework is further described in a bilevel optimization model, where the upper-level function represents the objective of the government and the lower-level function represents the benefits of transit providers. A unique partition-based-bisection algorithm is further developed to solve the bilevel optimization model based on identifying the unique response of lower-level decisions of transit operators to the upper-level government decisions.A case study in Shanghai, China, is conducted to validate the performance of the proposed framework and model, with parameters calibrated using real-world GPS and Smart Card data. Objectives of both the government and transit providers are improved through the adjustment, which indicates that the proposed model and algorithm are efficient for planning a new bus route or adjusting an existing one. Sensitivity analyses under different VOTs (value of time of travelers) and levels of government budget subsidies indicate the existence of critical thresholds of VOT and budget subsidies beyond which the optimal decisions of government and transit operators would remain unchanged. Such findings are critical to target potential groups of travelers and areas of interests when governments and transit providers are planning a bus route and to provide guidance for government budget decisions when multiple bus routes are within their considerations.In the case study, Bus GPS data, Smart Card data, and taxi operation data are used to calibrate the parameters. These automated data are easy to collect, which helps governments and transit operators to adjust bus routes on a regular basis. However, other possible methods (e.g., manual survey data) could also be applied to collect required parameters in the proposed framework. Several factors need to be carefully examined when using automated data: (i) The accuracy of GPS/AVL and Smart Card data is highly dependent on data acquisition systems. Failure to maintain the data collection process may lead to unreliable results. (ii) Smart Card data cannot represent all the transit demand, since there is still a proportion of passengers using other payment methods or evading fares [89]. Therefore, methods to address these issues should be considered before implementing the framework in practice.Future work along the line will be extending the framework into the planning of multiple transit routes, under which traffic route assignment will be considered through the stochastic user equilibrium. Applications and evaluation of the proposed model in a real-world study area with various modes of transportation included will also be performed in the next step.



---

*Source: 1801320-2020-11-26.xml*