# An Optimization Method of Passenger Assignment for Customized Bus

Authors: Yang Cao; Jian Wang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This study proposes an optimization method of passenger assignment on customized buses (CB). Our proposed method guarantees benefits to passengers by balancing the elements of travel time, waiting time, delay, and economic cost. The optimization problem was solved using a Branch and Bound (B&B) algorithm based on the shortest path for the selected stations. A simulation-based evaluation of the proposed optimization method was conducted. We find that a CB service can save 38.33% in average travel time, 38.33% in average waiting time, and 27.78% in delay penalties, all at an acceptable ticket price. The variations are caused by different degrees of busload. A detailed investigation revealed that a CB can significantly reduce travel time, waiting time, and delays, with the degree of benefits showing a decreasing trend with corresponding increases in busload. This finding indicates that CBs with smaller busloads can more flexibly transport passengers and provide a greater level of benefits. At the same time, a small busload strategy can be implemented more easily and in the near future on a test basis in urban China areas.


---

## Body

## 1. Introduction

In recent years, one emerging mode of demand-responsive transport systems (namely, the customized bus (CB)) has been developed to provide advanced, convenient, and comfortable service to commuters. Online information platforms (e.g., Internet and databases) can classify passengers with similar travel demands and arrange specific CB services for the different passenger classifications. Especially in China, CB services have become very popular. CBs are found to be more human-friendly, more comfortable, and more reliable than traditional bus transport systems. In addition, CB services have the ability to attract more private car owners to using public transport systems. Currently, several successful CB operations are being run in 22 Chinese cities. A further eight cities have CB services under construction. Thus, CB is regarded as a successful mode of transport, one which can improve road use efficiency, reduce urban congestion, and improve traffic safety.Though CB is an emerging transport system, research into car-sharing has already taken place. The earliest car-sharing system was found in Zurich, where car-sharing started in 1948 [1]. Kirby and Bhatt [2, 3] discussed the subscription bus service (which is similar to a CB service) in America. Kirby and Bhatt’s study provided guidelines on the planning, organization, and operation of such subscription bus services. McCall [4] discussed the evolution and operations of a subscription commuter-bus-service system, named COM-BUS. Chang and Schonfeld [5] proposed analytical optimization models to compare traditional and subscription bus systems, where each system provided a feeder service to a single transportation terminal. Potts et al. [6] provided a decision-making framework and conducted a comprehensive review of six main types of flexible public transport systems. These systems were neither fully demand-responsive nor fixed route systems, and they had been operating in America and Canada for the past 10 years. In China, Qingdao launched the first CB system. Cao and Wang [7] analyzed the background, definition, operation planning process, characteristics, and the key contributing factors of the CB service. Subsequently, a CB service was operated in Beijing. Xu et al. [8] discussed the advantages and potential applications of a CB service in Beijing. Most recently, Liu [9, 10] analyzed the background of CB, its temporal and spatial distribution in China, and the CB operation planning process. The latter study demonstrated that CB services can effectively meet the mobility needs of large populations on a nationwide basis.In addition, the CB system is also a subproblem of transport network analysis. The structural transit analysis was initiated by Byrne [11] for radial lines, by Newell [12] for a hub-and-spoke network, and by Vaughan [13] for ring and radial routes. Recently the continuous approximation literature has proposed the strategic evaluation of transit technologies [14, 15]. Moccia and Laporte [16] review and extend technoeconomic analytical models for the technology choice in a transit corridor with fixed demand. In these models the demand is fixed and uniformly distributed in a given area, and a composite objective function reflecting user and agency costs is minimized. In our paper, the passengers’ demand is obtained in advance, and the route of CB system is preset according to the shortest path selecting algorithm; we only focus on the passenger assignment and its impact on the construction cost.Passenger assignment is extended from the issue of traffic assignment, which some relevant studies have also addressed over the past few decades. Wardrop [17] first proposed a famous theory, which dealt with user equilibrium and system optimization as a means of addressing the traffic assignment problem. This theory has since been used for several decades. Beckman et al. [18] proposed a mathematical model for user equilibrium. This model laid the foundation for traffic assignment solutions. Subsequent to Beckman’s study, more researchers tried to consider more realistic solutions to traffic assignment (e.g., elastic demand, stochastic user equilibrium, multioptimization, and dynamic demand). The first time any researcher used a traffic assignment solution in public transport was in 1971, when Dial [19] proposed a Logit model applied to the multipath traffic assignment problem. Daganzo [20] proposed a probability distribution model of passenger assignment. However, their model is not suitable for large traffic networks, because of the enumeration method they used. Friedrich and Wekech [21] first used a Branch and Bound (B&B) method in a transit traffic assignment model and formulated the model in VISUM. Poon et al. [22] presented a transit network assignment problem with a FIFO principle under crowded conditions. Poon et al. proposed an assignment model based on a timetable. The concept of passenger assignment has been developed for several years. However, most research until now has focused on macroscopic passenger assignment. Therefore, finding a mathematical model for CB passenger assignment is difficult. According to the characteristics of a CB, we first find the shortest path between fixed stations. We then use a B&B method to obtain passenger assignment optimization. Finally, we use a simulation platform based on Excel, Matlab, and Vissim to test the effectiveness of our method and compare our service with normal public bus services.The reminder of this paper is organized as follows: Section2, entitled “Material and Methods,” presents problem formulation and the associated solution. Section 3, entitled “Results and Discussions,” describes our simulation set-up and associated results. In Section 4, our conclusions are summarized.


## 2. Material and Methods

The goal of proposed passenger assignment optimization method is saving the cost for the CB passengers. The framework of the proposed optimization method is presented in Figure1.Figure 1
Framework of passenger assignment optimization method.This optimization method is a combination of two modules, which are based on the passenger information, road network, and CBs. First, the various passenger demands are presented, such as origin, destination, and timetable. Then, Module 1 is activated to select the shortest path in the road network for those passengers who have the same destination. After that, Module 2 is activated to optimize passenger assignment. This optimization takes into account the factors of minimizing the average cost per person in terms of the overall combination of travel time, waiting time, penalty of delay, and ticket price. Finally, the information pertaining to passenger assignments and bus departure times is sent to the CBs and passengers. In the future, we would like to establish a CB system management platform for demand analysis, shortest path selecting, passenger assignment, and ticket price making; thus the framework of proposed method would be integrated in the platform.


### 2.1. Problem Statement

This section presents the formulation of the passenger assignment optimization method in detail. The information of road network is entailed in Section2.1.1; the parameters and measurements of the optimization problem are proposed in Section 2.1.2.


#### 2.1.1. Road Network

Referring to [23], we use a diagraph GN,L to present the road traffic network; N and L are a set of nodes and links, respectively. N=n is the number of nodes, and L=m is the number of links. Then, we use link travel time cij of link l=i,j∈L to represent the cost of an individual from node i to node j.


#### 2.1.2. Problem Setting

(
1) ParametersCB Station
(
S
). The number of stations among the path is denoted by S1 (i.e., the origin So), S2⋯SS (i.e., the destination Sd).CB Number
(
B
). The total number of CB: each bus is denoted by b.Busload
(
B
L
). The busload of CB b is BLb.Demand
(
D
). The expected number of people from station i to station j is Dij.Actual People
(
A
). The actual number of people from station i to station j by CB b is Aijb.(
2) MeasurementsAverage Travel Time
(
A
T
T
). The total travel time for CBs spent on the path is TT, travel time is the main cost in a trip, and most passengers will choose a shorter path with less TT.For CBb, the travel time is TTb:(1)TTb=∑i=1S-1Aidbcidb.The average travel time per person isATT:(2)ATT=∑b=1BTTbA.Average Waiting Time
(
A
W
T
). Waiting time is important for passengers which will affect their mood, and it depends on the arriving time of passengers and CBs.The time for people waiting for the CBb is WTb:(3)WTb=∑i=1S-1∑a=1AidbTia-tib,where Tia is the expected arriving time of passenger a at station i; it follows a Poisson distribution; tib is the expected arriving time of CB b at station i.And then(4)ti+1b=tib+Δtib+ci,i+1b,where Δtib is the waiting time of CB b at station i.The average waiting time per person isAWT:(5)AWT=∑b=1BWTbA.Average Penalty of Delay
(
A
P
D
). The penalty of delay is associated with the salary of passengers; most of them want to be early rather than late.The punishment of delay for passengera arriving destination d at time t is PDa,tdb, including the early penalty and the late penalty. Thus, the following model is utilized to calculate this value:(6)PDb=∑a=1∑i=1S-1AidbPDa,tdb,PDa,tdb=βtd∗a-Δd-tdb,iftd∗a-Δd>tdbγtdb-td∗a-Δd,iftd∗a+Δd<tdb0,else,where β is the unit time value rate of early penalty, γ is the unit time value rate of late penalty, and td∗a-Δd,td∗a+Δd is the expected time range for arriving d, tdb is actual time for arriving d, from (3), and tdb=tib+Δtib+cidb is obtained.Thus, the average penalty of delay per person is(7)APD=∑b=1BPDbA.Average Ticket Price
(
A
T
P
). Ticket price is the visible cost for passengers that makes it more concerned.The ticket price at stationi is tpi. To simplify the problem, tpi is set to be constant. Thus, the ticket price of CB b is TPb:(8)TPb=∑i=1S-1Aidbtpi.The average ticket price per person isATP:(9)ATP=∑b=1BTPbA.Total Cost
(
T
C
). The total cost including above measurements is(10)TC=∑b=1BωTTTb+ωWWTb+ωDPDb+ωPTPb,where ωT is the weight of travel time, ωW is the weight of waiting time, ωD is the weight of penalty of delay, and ωP is the weight of ticket price, and all of them are constant value.Average Cost
(
A
C
). The average cost per person including above measurements is(11)AC=TCA.In order to simplify the problem without loss of the reality, several assumptions are made as follows.Assumption 1.
All the stations excepting the destination only allow getting on and not getting off, thus meaning the expected number of people from stationi to station d is Did, which follows the Poisson distribution, and the amount of demand D is assumed to be distributed uniformly among all stations; thus D1d=D2d=⋯=DS-1d=D/S-1.Assumption 2.
All the buses have the same busload; thusBL1=BL2=⋯=BLB=BL; BL is a constant value. Thus, the total number of buses can be calculated as B=D/BL.Assumption 3.
Same as Assumption1, the actual number of people from station i to station d by CB b is Aidb.Assumption 4.
The departure time of the CBs depends on the number of assignment passengers; once passenger assignment is finished, the departure time is defined,t1b=T1A1b,b=1,2,…,B.Assumption 5.
All passengers have the same expected working timetd∗a=td∗. Thus,(12)PDa,tdb=PDtdb=βtd∗-Δd-tdb,iftd∗-Δd>tdbγtdb-td∗-Δd,iftd∗+Δd<tdb0,else,PDb=PDtdb∑i=1S-1Aidb.And due to Assumptions1 and 5, the demand of each passenger will not be abnormal, so that it is possible to meet all the passengers’ demands in the CB system.


### 2.2. Selecting the Shortest Path

Before assignment optimization, the shortest path is selecting through the branch pruning algorithm to obtain the minimum total travel time. Here, we just list the procedure of the search algorithm; the detailed algorithm can be found in [23].The procedure of the branch pruning shortest path selecting algorithm is described as follows.Step 1.
Seti=o;  TTi=0;  TTj=∞  ∀j≠i;  Pi=NULL. Define the scan eligible node set  Q=i.Step 2.
Select and remove the node with the lowest travel time fromQ. This is node i; if  TTi+ei,d>Eo,d, then go to Step  4.Step 3.
Scan each link corresponding to nodei. For each link l=i,j, if TTi+cl<TTj, then TTj=TTi+cl;  Pj=l; insert node j into Q.Step 4.
IfQ≠⌀, then STOP; otherwise, go to Step  2.
Here,Pi represents the preceding link on the shortest path to node i; Q denotes the scan eligible node set which manages the nodes to be examined during the search procedure.


### 2.3. Optimization of Passenger Assignment

After obtaining the shortest path fromo to d, another problem arises which is about the optimization of passenger assignment. The passenger assignment optimization problem is to optimally assign the actual number of passengers among bus stations S1,S2,…,SS, according to the demand of each station. According to Section 2.1, this problem is formulated as follows.The subject is to minimize the average cost among the shortest path:(13)minAC=min⁡∑b=1BωTATTb+ωWAWTb+ωDAPDb+ωPATPb=min⁡1A∑b=1BωT∑i=1S-1Aidbcidb+ωW∑i=1S-1∑a=1AidbTia-tib+ωDPDtdb∑i=1S-1Aidb+ωP∑i=1S-1Aidbtpi.Due to the assumptions in Section2.1.2 and ∑b=1B∑i=1S-1Aidb=D, ∑b=1B∑i=1S-1Aidbcidb and ∑b=1B∑i=1S-1Aidbtpi are constant value. Thus, the subject of the optimization problem is only concerned with waiting time and penalty of delay, and (13) can be revised as(14)min⁡AC=min1A∑b=1BωW∑i=1S-1∑a=1AidbTia-tib+ωDPDtdb∑i=1S-1Aidb(15)s.t.:1≤b≤B,b,B∈Z,(16)1≤i≤S,i,S∈Z,(17)∑i=1S-1Aidb≤BLb,∀b,Aidb∈Z,(18)∑b=1BAidb≤Did,∀i,(19)∑i=1S-1cii+1b=codb,∀b,(20)cod1=cod2=⋯=codB,(21)Δtib≤Tib-tib≤Δtib,∀b,∀i,(22)PDtdb=PDtib=βtd∗-Δd-tib+Δtib+cidb,iftd∗-Δd>tib+Δtib+cidbγtib+Δtib+cidb-td∗-Δd,iftd∗+Δd<tib+Δtib+cidb0,else,(23)tpi=ki,∀i.Here, for this problem,Aidb, i=1,2,…,S, b=1,2,…,B, are the integral variables. And constraint (15) means the number of CBs is B which is a constant value. Constraint (16) means the number of stations is S. Constraint (17) means the total actual number of passengers for each CB should follow the bus load of the CB. Constraint (18) means the total actual number of passengers for each CB should not beyond the demand. Constraint (19) means the path from origin to destination should go through the middle stations (i.e., excepting stations S1 and SS); thus the total travel time of path o,d consists of the travel time of links, 1,2,2,3,…,S-1,S. Constraint (20) means the total travel time for each CB is the same. Constraint (21) means all passengers would arrive at the nearby station within a limit time windows, and Δtim is a constant value. Constraint (22) means all passengers follow the penalty function, and td∗ and Δd are constant value. Constraint (23) means the ticket price of each station is a constant value, and ki is a constant value for station i.From the above, this problem is an integer programming optimization problem, which can be solved by mature algorithm so as to avoid the complex calculation process and reduce the computational burden [23]. Branch and Bound (B&B) algorithm was utilized to find the optimal solution. The goal of a B&B algorithm is to find a value x (here, x=AidbS×B is a matrix) that maximizes or minimizes the value of a real-valued function fx (here, fx=TC, and the goal is to minimize the function), called an objective function, among some set S of admissible or candidate solutions. The set S is called the search space or feasible region. A B&B algorithm operates according to two principles.(1) It recursively splits the search space into smaller spaces, then minimizing fx on these smaller spaces; the splitting is called branching.(2) Branching alone would amount to brute-force enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find and uses these bounds to “prune” the search space, eliminating candidate solutions, that is, can prove not containing an optimal solution.The following is the skeleton of a B&B algorithm for minimizing the objective functionTC. In the process of the algorithm, all the candidates are stored into the set of active_set, and the observed optimal value is put into the set of U.Step 1 (initializing step).
SetU=∞ and eliminate the obviously nonoptimal value; put others into the set of active_set.Step 2 (branching step).
Chose a valueY from active_set; if it is easy to calculate, then turn to Step  3; else, decompose it to several subvalues and put it into active_set; turn to Step  2.Step 3 (bounding step).
Calculate the lower boundLY.Step 4 (fathoming step).
IfLY≥U or there is any feasible solutions in Y, then eliminate Y from the feasible region; else, calculate minx∈Y⁡fx, then consider the local optimal value x∗ as the best value and set U=fx∗.Step 5 (stopping step).
If there is no value needed to be solute, that is,active_set∈⌀, then stop the algorithm, and the observed local optimal value is the global optimal value; otherwise, turn to Step  2.


## 2.1. Problem Statement

This section presents the formulation of the passenger assignment optimization method in detail. The information of road network is entailed in Section2.1.1; the parameters and measurements of the optimization problem are proposed in Section 2.1.2.


### 2.1.1. Road Network

Referring to [23], we use a diagraph GN,L to present the road traffic network; N and L are a set of nodes and links, respectively. N=n is the number of nodes, and L=m is the number of links. Then, we use link travel time cij of link l=i,j∈L to represent the cost of an individual from node i to node j.


### 2.1.2. Problem Setting

(
1) ParametersCB Station
(
S
). The number of stations among the path is denoted by S1 (i.e., the origin So), S2⋯SS (i.e., the destination Sd).CB Number
(
B
). The total number of CB: each bus is denoted by b.Busload
(
B
L
). The busload of CB b is BLb.Demand
(
D
). The expected number of people from station i to station j is Dij.Actual People
(
A
). The actual number of people from station i to station j by CB b is Aijb.(
2) MeasurementsAverage Travel Time
(
A
T
T
). The total travel time for CBs spent on the path is TT, travel time is the main cost in a trip, and most passengers will choose a shorter path with less TT.For CBb, the travel time is TTb:(1)TTb=∑i=1S-1Aidbcidb.The average travel time per person isATT:(2)ATT=∑b=1BTTbA.Average Waiting Time
(
A
W
T
). Waiting time is important for passengers which will affect their mood, and it depends on the arriving time of passengers and CBs.The time for people waiting for the CBb is WTb:(3)WTb=∑i=1S-1∑a=1AidbTia-tib,where Tia is the expected arriving time of passenger a at station i; it follows a Poisson distribution; tib is the expected arriving time of CB b at station i.And then(4)ti+1b=tib+Δtib+ci,i+1b,where Δtib is the waiting time of CB b at station i.The average waiting time per person isAWT:(5)AWT=∑b=1BWTbA.Average Penalty of Delay
(
A
P
D
). The penalty of delay is associated with the salary of passengers; most of them want to be early rather than late.The punishment of delay for passengera arriving destination d at time t is PDa,tdb, including the early penalty and the late penalty. Thus, the following model is utilized to calculate this value:(6)PDb=∑a=1∑i=1S-1AidbPDa,tdb,PDa,tdb=βtd∗a-Δd-tdb,iftd∗a-Δd>tdbγtdb-td∗a-Δd,iftd∗a+Δd<tdb0,else,where β is the unit time value rate of early penalty, γ is the unit time value rate of late penalty, and td∗a-Δd,td∗a+Δd is the expected time range for arriving d, tdb is actual time for arriving d, from (3), and tdb=tib+Δtib+cidb is obtained.Thus, the average penalty of delay per person is(7)APD=∑b=1BPDbA.Average Ticket Price
(
A
T
P
). Ticket price is the visible cost for passengers that makes it more concerned.The ticket price at stationi is tpi. To simplify the problem, tpi is set to be constant. Thus, the ticket price of CB b is TPb:(8)TPb=∑i=1S-1Aidbtpi.The average ticket price per person isATP:(9)ATP=∑b=1BTPbA.Total Cost
(
T
C
). The total cost including above measurements is(10)TC=∑b=1BωTTTb+ωWWTb+ωDPDb+ωPTPb,where ωT is the weight of travel time, ωW is the weight of waiting time, ωD is the weight of penalty of delay, and ωP is the weight of ticket price, and all of them are constant value.Average Cost
(
A
C
). The average cost per person including above measurements is(11)AC=TCA.In order to simplify the problem without loss of the reality, several assumptions are made as follows.Assumption 1.
All the stations excepting the destination only allow getting on and not getting off, thus meaning the expected number of people from stationi to station d is Did, which follows the Poisson distribution, and the amount of demand D is assumed to be distributed uniformly among all stations; thus D1d=D2d=⋯=DS-1d=D/S-1.Assumption 2.
All the buses have the same busload; thusBL1=BL2=⋯=BLB=BL; BL is a constant value. Thus, the total number of buses can be calculated as B=D/BL.Assumption 3.
Same as Assumption1, the actual number of people from station i to station d by CB b is Aidb.Assumption 4.
The departure time of the CBs depends on the number of assignment passengers; once passenger assignment is finished, the departure time is defined,t1b=T1A1b,b=1,2,…,B.Assumption 5.
All passengers have the same expected working timetd∗a=td∗. Thus,(12)PDa,tdb=PDtdb=βtd∗-Δd-tdb,iftd∗-Δd>tdbγtdb-td∗-Δd,iftd∗+Δd<tdb0,else,PDb=PDtdb∑i=1S-1Aidb.And due to Assumptions1 and 5, the demand of each passenger will not be abnormal, so that it is possible to meet all the passengers’ demands in the CB system.


## 2.1.1. Road Network

Referring to [23], we use a diagraph GN,L to present the road traffic network; N and L are a set of nodes and links, respectively. N=n is the number of nodes, and L=m is the number of links. Then, we use link travel time cij of link l=i,j∈L to represent the cost of an individual from node i to node j.


## 2.1.2. Problem Setting

(
1) ParametersCB Station
(
S
). The number of stations among the path is denoted by S1 (i.e., the origin So), S2⋯SS (i.e., the destination Sd).CB Number
(
B
). The total number of CB: each bus is denoted by b.Busload
(
B
L
). The busload of CB b is BLb.Demand
(
D
). The expected number of people from station i to station j is Dij.Actual People
(
A
). The actual number of people from station i to station j by CB b is Aijb.(
2) MeasurementsAverage Travel Time
(
A
T
T
). The total travel time for CBs spent on the path is TT, travel time is the main cost in a trip, and most passengers will choose a shorter path with less TT.For CBb, the travel time is TTb:(1)TTb=∑i=1S-1Aidbcidb.The average travel time per person isATT:(2)ATT=∑b=1BTTbA.Average Waiting Time
(
A
W
T
). Waiting time is important for passengers which will affect their mood, and it depends on the arriving time of passengers and CBs.The time for people waiting for the CBb is WTb:(3)WTb=∑i=1S-1∑a=1AidbTia-tib,where Tia is the expected arriving time of passenger a at station i; it follows a Poisson distribution; tib is the expected arriving time of CB b at station i.And then(4)ti+1b=tib+Δtib+ci,i+1b,where Δtib is the waiting time of CB b at station i.The average waiting time per person isAWT:(5)AWT=∑b=1BWTbA.Average Penalty of Delay
(
A
P
D
). The penalty of delay is associated with the salary of passengers; most of them want to be early rather than late.The punishment of delay for passengera arriving destination d at time t is PDa,tdb, including the early penalty and the late penalty. Thus, the following model is utilized to calculate this value:(6)PDb=∑a=1∑i=1S-1AidbPDa,tdb,PDa,tdb=βtd∗a-Δd-tdb,iftd∗a-Δd>tdbγtdb-td∗a-Δd,iftd∗a+Δd<tdb0,else,where β is the unit time value rate of early penalty, γ is the unit time value rate of late penalty, and td∗a-Δd,td∗a+Δd is the expected time range for arriving d, tdb is actual time for arriving d, from (3), and tdb=tib+Δtib+cidb is obtained.Thus, the average penalty of delay per person is(7)APD=∑b=1BPDbA.Average Ticket Price
(
A
T
P
). Ticket price is the visible cost for passengers that makes it more concerned.The ticket price at stationi is tpi. To simplify the problem, tpi is set to be constant. Thus, the ticket price of CB b is TPb:(8)TPb=∑i=1S-1Aidbtpi.The average ticket price per person isATP:(9)ATP=∑b=1BTPbA.Total Cost
(
T
C
). The total cost including above measurements is(10)TC=∑b=1BωTTTb+ωWWTb+ωDPDb+ωPTPb,where ωT is the weight of travel time, ωW is the weight of waiting time, ωD is the weight of penalty of delay, and ωP is the weight of ticket price, and all of them are constant value.Average Cost
(
A
C
). The average cost per person including above measurements is(11)AC=TCA.In order to simplify the problem without loss of the reality, several assumptions are made as follows.Assumption 1.
All the stations excepting the destination only allow getting on and not getting off, thus meaning the expected number of people from stationi to station d is Did, which follows the Poisson distribution, and the amount of demand D is assumed to be distributed uniformly among all stations; thus D1d=D2d=⋯=DS-1d=D/S-1.Assumption 2.
All the buses have the same busload; thusBL1=BL2=⋯=BLB=BL; BL is a constant value. Thus, the total number of buses can be calculated as B=D/BL.Assumption 3.
Same as Assumption1, the actual number of people from station i to station d by CB b is Aidb.Assumption 4.
The departure time of the CBs depends on the number of assignment passengers; once passenger assignment is finished, the departure time is defined,t1b=T1A1b,b=1,2,…,B.Assumption 5.
All passengers have the same expected working timetd∗a=td∗. Thus,(12)PDa,tdb=PDtdb=βtd∗-Δd-tdb,iftd∗-Δd>tdbγtdb-td∗-Δd,iftd∗+Δd<tdb0,else,PDb=PDtdb∑i=1S-1Aidb.And due to Assumptions1 and 5, the demand of each passenger will not be abnormal, so that it is possible to meet all the passengers’ demands in the CB system.


## 2.2. Selecting the Shortest Path

Before assignment optimization, the shortest path is selecting through the branch pruning algorithm to obtain the minimum total travel time. Here, we just list the procedure of the search algorithm; the detailed algorithm can be found in [23].The procedure of the branch pruning shortest path selecting algorithm is described as follows.Step 1.
Seti=o;  TTi=0;  TTj=∞  ∀j≠i;  Pi=NULL. Define the scan eligible node set  Q=i.Step 2.
Select and remove the node with the lowest travel time fromQ. This is node i; if  TTi+ei,d>Eo,d, then go to Step  4.Step 3.
Scan each link corresponding to nodei. For each link l=i,j, if TTi+cl<TTj, then TTj=TTi+cl;  Pj=l; insert node j into Q.Step 4.
IfQ≠⌀, then STOP; otherwise, go to Step  2.
Here,Pi represents the preceding link on the shortest path to node i; Q denotes the scan eligible node set which manages the nodes to be examined during the search procedure.


## 2.3. Optimization of Passenger Assignment

After obtaining the shortest path fromo to d, another problem arises which is about the optimization of passenger assignment. The passenger assignment optimization problem is to optimally assign the actual number of passengers among bus stations S1,S2,…,SS, according to the demand of each station. According to Section 2.1, this problem is formulated as follows.The subject is to minimize the average cost among the shortest path:(13)minAC=min⁡∑b=1BωTATTb+ωWAWTb+ωDAPDb+ωPATPb=min⁡1A∑b=1BωT∑i=1S-1Aidbcidb+ωW∑i=1S-1∑a=1AidbTia-tib+ωDPDtdb∑i=1S-1Aidb+ωP∑i=1S-1Aidbtpi.Due to the assumptions in Section2.1.2 and ∑b=1B∑i=1S-1Aidb=D, ∑b=1B∑i=1S-1Aidbcidb and ∑b=1B∑i=1S-1Aidbtpi are constant value. Thus, the subject of the optimization problem is only concerned with waiting time and penalty of delay, and (13) can be revised as(14)min⁡AC=min1A∑b=1BωW∑i=1S-1∑a=1AidbTia-tib+ωDPDtdb∑i=1S-1Aidb(15)s.t.:1≤b≤B,b,B∈Z,(16)1≤i≤S,i,S∈Z,(17)∑i=1S-1Aidb≤BLb,∀b,Aidb∈Z,(18)∑b=1BAidb≤Did,∀i,(19)∑i=1S-1cii+1b=codb,∀b,(20)cod1=cod2=⋯=codB,(21)Δtib≤Tib-tib≤Δtib,∀b,∀i,(22)PDtdb=PDtib=βtd∗-Δd-tib+Δtib+cidb,iftd∗-Δd>tib+Δtib+cidbγtib+Δtib+cidb-td∗-Δd,iftd∗+Δd<tib+Δtib+cidb0,else,(23)tpi=ki,∀i.Here, for this problem,Aidb, i=1,2,…,S, b=1,2,…,B, are the integral variables. And constraint (15) means the number of CBs is B which is a constant value. Constraint (16) means the number of stations is S. Constraint (17) means the total actual number of passengers for each CB should follow the bus load of the CB. Constraint (18) means the total actual number of passengers for each CB should not beyond the demand. Constraint (19) means the path from origin to destination should go through the middle stations (i.e., excepting stations S1 and SS); thus the total travel time of path o,d consists of the travel time of links, 1,2,2,3,…,S-1,S. Constraint (20) means the total travel time for each CB is the same. Constraint (21) means all passengers would arrive at the nearby station within a limit time windows, and Δtim is a constant value. Constraint (22) means all passengers follow the penalty function, and td∗ and Δd are constant value. Constraint (23) means the ticket price of each station is a constant value, and ki is a constant value for station i.From the above, this problem is an integer programming optimization problem, which can be solved by mature algorithm so as to avoid the complex calculation process and reduce the computational burden [23]. Branch and Bound (B&B) algorithm was utilized to find the optimal solution. The goal of a B&B algorithm is to find a value x (here, x=AidbS×B is a matrix) that maximizes or minimizes the value of a real-valued function fx (here, fx=TC, and the goal is to minimize the function), called an objective function, among some set S of admissible or candidate solutions. The set S is called the search space or feasible region. A B&B algorithm operates according to two principles.(1) It recursively splits the search space into smaller spaces, then minimizing fx on these smaller spaces; the splitting is called branching.(2) Branching alone would amount to brute-force enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find and uses these bounds to “prune” the search space, eliminating candidate solutions, that is, can prove not containing an optimal solution.The following is the skeleton of a B&B algorithm for minimizing the objective functionTC. In the process of the algorithm, all the candidates are stored into the set of active_set, and the observed optimal value is put into the set of U.Step 1 (initializing step).
SetU=∞ and eliminate the obviously nonoptimal value; put others into the set of active_set.Step 2 (branching step).
Chose a valueY from active_set; if it is easy to calculate, then turn to Step  3; else, decompose it to several subvalues and put it into active_set; turn to Step  2.Step 3 (bounding step).
Calculate the lower boundLY.Step 4 (fathoming step).
IfLY≥U or there is any feasible solutions in Y, then eliminate Y from the feasible region; else, calculate minx∈Y⁡fx, then consider the local optimal value x∗ as the best value and set U=fx∗.Step 5 (stopping step).
If there is no value needed to be solute, that is,active_set∈⌀, then stop the algorithm, and the observed local optimal value is the global optimal value; otherwise, turn to Step  2.


## 3. Results and Discussions

### 3.1. Simulation Evaluation

The proposed optimization method is evaluated through a simulation platform. The framework of the integrated simulation platform is shown in Figure2. This simulation platform is composed of Excel, Matlab, and Vissim. Excel is the master control program of the integrated simulation platform, which can directly call Vissim and Matlab through the COM Interface of Vissim and the Spreadsheet Link EX of Excel, respectively. Matlab is programmed for the traffic optimization model with a powerful toolbox, library function, and the advantage of analyzing the matrix. Vissim can simulate traffic flow and then output the performance index. The proposed integrated simulation platform provides an effective solution which validates the traffic optimization model.Figure 2
Framework of the integrated simulation platform.After building the integrated simulation platform, we will use it to simulate the optimization problem of CB. Here, take Harbin as an example. And the parameters are set as follows: the total stations numberS=4; the total demand is D=∑i=13Did=120 people, the demand of each station is D1d=D2d=D3d=40 people; BL=40 people/bus; B=D/BL=3 buses; c1o2=5 min, c23=4 min, c34d=6 min, and cod=15 min; T1a=34a/a!e-34, T2a=41a/a!e-41, and T3a=47a/a!e-47; Δt=2 min; a=1,2,…,40; β=0.3 and γ=1; tp1=2, tp2=1.5 and tp3=1; ωw=0.1 and ωD=1. For the optimization problem, we have the following: tib depends on the time of the last passenger of the expected assignment plan for bus b=1, 2, 3 and station i=1, 2, 3, 4, and ti+1b≥tib+cii+1, i=1,2,3.The road network of Harbin in simulation platform is shown in Figure3.Figure 3
Road network, for example, of Harbin in simulation platform.As shown in Figure3, the origin (i.e., Station 1) is set as the first campus of the Harbin Institute of Technology. The destination is set as the second campus of the Harbin Institute of Technology. In addition, immediate Station 2 is set at the intersection between Wenchang Street and Wenfu Road. Immediate Station 3 is set at the intersection between Wenchang Street and Xuanhua Street. According to Section 2.2, we find the shortest path from the origin to the destination between Station 2 and Station 3. Next, to simplify this, we extract the road network from the original map, which is shown in Figure 4.Figure 4
Simplified road network, for example, of Harbin.


### 3.2. Results Analysis

In this section, we use a simulation platform to evaluate the optimization method, compare the results of CB services with the traditional bus services, and make a sensitive analysis.Table1 shows the optimal results compared to traditional bus. The results of traditional bus come from the data of Route 84 bus as the compared traditional bus which has the same routes as we designed for the CB. The optimal passenger assignment is optimized as the matrix Aidb in Table 1, and the optimal AC is 1.5083 which decreases 32.95% passenger cost compared to traditional bus (AC=2.25).Table 1
The optimal results compared to traditional bus.
Optimal CB
Traditional bus
Difference (%)
A
i
d
b
p
b
=
1
2
3
i
=
1
15
15
10
2
10
15
15
3
15
10
15
NaN
NaN
A
C
(
Ұ
/
person)
1.5083
2.2500
32.95Figure5 shows the results of the comparison between CB and traditional bus services for different, separate measurements. From Figure 5, we can see that the CB has a better performance than the traditional bus. A CB can save 38.33% in average travel time, 38.33% in average waiting time, and 27.78% in terms of penalty of delay. These savings occur because traditional buses must stop at every station (unlike a CB). As such, traditional buses will cost more in terms of longer travel times and more penalties of delay. Also, because a traditional bus will try to serve every passenger who wants to get on the bus, long waiting times and a crowded environment are inevitable. We also note that, due to the advantages offered by a CB, a CB ticket price will be higher than the ticket price on a traditional bus.Figure 5
Average cost for each measurement between CB and traditional bus.Figure6 shows our sensitivity analysis results with variations in the degree of busload. Busload is an important parameter, as the degree of busload can affect the number of available CBs and, in turn, the passenger assignments. Ultimately, these factors can then affect the overall cost to the passenger. With an increase in busload from 20 to 60 passengers, the AWT cost rises and the APD cost decreases, respectively. In addition, the passenger cost (AC including AWT and APD) goes down. Also, when the busload is 40 passengers, AC is at the minimum. That is to say, the busload can obviously affect the passenger cost. A smaller busload means that more CBs are available for service. As such the service itself can be more flexible in terms of meeting passenger demands. This flexibility will lead to a lower AWT but will also lead to a higher APD. Moreover, AC will tend to be stable when busloads increase.Figure 6
Sensitivity analysis with the effect of busload.


## 3.1. Simulation Evaluation

The proposed optimization method is evaluated through a simulation platform. The framework of the integrated simulation platform is shown in Figure2. This simulation platform is composed of Excel, Matlab, and Vissim. Excel is the master control program of the integrated simulation platform, which can directly call Vissim and Matlab through the COM Interface of Vissim and the Spreadsheet Link EX of Excel, respectively. Matlab is programmed for the traffic optimization model with a powerful toolbox, library function, and the advantage of analyzing the matrix. Vissim can simulate traffic flow and then output the performance index. The proposed integrated simulation platform provides an effective solution which validates the traffic optimization model.Figure 2
Framework of the integrated simulation platform.After building the integrated simulation platform, we will use it to simulate the optimization problem of CB. Here, take Harbin as an example. And the parameters are set as follows: the total stations numberS=4; the total demand is D=∑i=13Did=120 people, the demand of each station is D1d=D2d=D3d=40 people; BL=40 people/bus; B=D/BL=3 buses; c1o2=5 min, c23=4 min, c34d=6 min, and cod=15 min; T1a=34a/a!e-34, T2a=41a/a!e-41, and T3a=47a/a!e-47; Δt=2 min; a=1,2,…,40; β=0.3 and γ=1; tp1=2, tp2=1.5 and tp3=1; ωw=0.1 and ωD=1. For the optimization problem, we have the following: tib depends on the time of the last passenger of the expected assignment plan for bus b=1, 2, 3 and station i=1, 2, 3, 4, and ti+1b≥tib+cii+1, i=1,2,3.The road network of Harbin in simulation platform is shown in Figure3.Figure 3
Road network, for example, of Harbin in simulation platform.As shown in Figure3, the origin (i.e., Station 1) is set as the first campus of the Harbin Institute of Technology. The destination is set as the second campus of the Harbin Institute of Technology. In addition, immediate Station 2 is set at the intersection between Wenchang Street and Wenfu Road. Immediate Station 3 is set at the intersection between Wenchang Street and Xuanhua Street. According to Section 2.2, we find the shortest path from the origin to the destination between Station 2 and Station 3. Next, to simplify this, we extract the road network from the original map, which is shown in Figure 4.Figure 4
Simplified road network, for example, of Harbin.


## 3.2. Results Analysis

In this section, we use a simulation platform to evaluate the optimization method, compare the results of CB services with the traditional bus services, and make a sensitive analysis.Table1 shows the optimal results compared to traditional bus. The results of traditional bus come from the data of Route 84 bus as the compared traditional bus which has the same routes as we designed for the CB. The optimal passenger assignment is optimized as the matrix Aidb in Table 1, and the optimal AC is 1.5083 which decreases 32.95% passenger cost compared to traditional bus (AC=2.25).Table 1
The optimal results compared to traditional bus.
Optimal CB
Traditional bus
Difference (%)
A
i
d
b
p
b
=
1
2
3
i
=
1
15
15
10
2
10
15
15
3
15
10
15
NaN
NaN
A
C
(
Ұ
/
person)
1.5083
2.2500
32.95Figure5 shows the results of the comparison between CB and traditional bus services for different, separate measurements. From Figure 5, we can see that the CB has a better performance than the traditional bus. A CB can save 38.33% in average travel time, 38.33% in average waiting time, and 27.78% in terms of penalty of delay. These savings occur because traditional buses must stop at every station (unlike a CB). As such, traditional buses will cost more in terms of longer travel times and more penalties of delay. Also, because a traditional bus will try to serve every passenger who wants to get on the bus, long waiting times and a crowded environment are inevitable. We also note that, due to the advantages offered by a CB, a CB ticket price will be higher than the ticket price on a traditional bus.Figure 5
Average cost for each measurement between CB and traditional bus.Figure6 shows our sensitivity analysis results with variations in the degree of busload. Busload is an important parameter, as the degree of busload can affect the number of available CBs and, in turn, the passenger assignments. Ultimately, these factors can then affect the overall cost to the passenger. With an increase in busload from 20 to 60 passengers, the AWT cost rises and the APD cost decreases, respectively. In addition, the passenger cost (AC including AWT and APD) goes down. Also, when the busload is 40 passengers, AC is at the minimum. That is to say, the busload can obviously affect the passenger cost. A smaller busload means that more CBs are available for service. As such the service itself can be more flexible in terms of meeting passenger demands. This flexibility will lead to a lower AWT but will also lead to a higher APD. Moreover, AC will tend to be stable when busloads increase.Figure 6
Sensitivity analysis with the effect of busload.


## 4. Conclusions

In this paper, a passenger assignment optimization method is proposed. The proposed method (a CB service) improves the overall passenger cost in terms of waiting time and penalty of delay, while at the same time decreasing traffic congestion, compared to traditional bus services. Our study overcomes the shortcomings of existing published studies pertaining to CB. (1) Our paper is able to quantify the passenger assignment optimization problem, which can in turn save costs in real-world implementation. From our evaluation results, we find that the travel time, waiting time, and penalty of delay are all improved with a CB service, compared to traditional bus services. Thus, our system can help convince more private car owners to change to using public transport, thus easing the current amount of traffic congestion. (2) By analyzing the effect of busload, we were able to find that the cost becomes stable when the busload is beyond 40 passengers. In our study, 40 passengers are the optimum choice of busload. Any future research should consider different modes of CB services, such as several OD pairs. Also, we will try to optimize the ticket price for corporate CB services.



---

*Source: 7914753-2017-06-04.xml*