Multi-Objective Optimization of University Bus Based on Passenger Probability Density Estimation

Jingcheng Zhao, Yang Liu, Yufeng Gui^*

College of Science, Wuhan University of Technology, Wuhan, China.

DOI: 10.4236/am.2017.85048                

Abstract

In this paper, a multi-objective optimization model is presented, based on Parzen Window method which can make a theoretical analysis of the probability density function of passengers and determine the demand over a corresponding period by integration. This model can minimize the total of waiting time of passengers and the running cost of school buses with several constrains including the passengers’ numbers and the longest endurance time. Moreover, the data from Wuhan University of Technology, used as an example, verify the feasibility of the model. At last, the whole results are calculated by the Particle Swarm Optimization.

Keywords

School Bus, Parzen Window, Multi-objective Optimization, Particle Swarm Optimization

1. Introduction

With the development of education, there are more colleges establishing some new campuses which need school buses back and forth to meet students’ demand their daily life. However, because of the unreasonable arrangement of buses’ sites, timetable and routes, there exists the waste of the spending and the oil resources. Moreover, students are now wasting too much time waiting for the buses. Therefore, solving these problems of school bus in time is very essential and the interest of this work is two-fold.

In the past, early models of school bus problem mainly concerned on the route and sites setting, such as Zhang Fu, Zhu Taiying (2012) [1] , Hao Zhongna (2016) [2] , Zhang Miao (2008) [3] . Recently, there are some researches focusing on the timetable like Zhao Shasha, Xiong Wei (2015) [4] . They analyzed the congestion time and gave a time schedule and the departure number of the school bus. Unfortunately, due to the lack of real-time data, the paper couldn’t give the specific departure time of each vehicle. However, with the emerging of travel credit card, it becomes much easier to collect the demanding data. Hence, to cope with the problem, we now use the real-time data to estimate the distribution of passengers by the non-parametric estimation method and then establish a multi-objective optimization model to specify the timetable and departure bus numbers.

Realistically, the advantages of the optimization of the school buses’ timetable and departure numbers are the following:

1) On one hand, it can cut down the waste of resource and reduce the school investment when demands vacant by shortening the total operating time. On the other hand, it can shorten the waiting time of students which can bring a great convenience.

2) The optimization model can provide some theoretical and practical guidance to the arrangement of transportation in other field, for example, the city bus.

3) As a branch of vehicle target planning, the research has further developed the theory and practice of vehicle target planning.

2. Preliminary Data Processing

2.1. Advantages of Prazen Window Estimation

It is tough to get the real-time number of passengers when students take a school bus. In order to easily obtain the real-time data, we utilize the school bus charge card system. Every student can only pay the fee through the machine when they need to take the bus. By recording “1” when someone get on at a moment or recording “0” contrarily, the numbers of passengers can be known. In the actual situation, it is not determined whether there will be passengers show up. A student who took the school bus at 12:35:01 is possible to take the school bus at 12:36:59 the next time. The possibility is influenced by many conditions. Hence, it is required to take all the sample points into consideration by using the Parzen Window estimation method and then figure out the number of passengers.

2.2. Calculate the Window Function and Window Width

Assuming that the data $x_1,x_2,\cdots ,x_n$ are taken from a continuous distribution [5] . A kernel density estimate at any point x is defined as:

${\hat{p}}_n\left(x\right)=\frac{1}{nh}{\displaystyle \underset{i=1}{\overset{n}{\sum }}K\left(\frac{x-x_i}{h}\right)}$ (1)

where n is the sample size, $K(\cdot )$ is defined as Window function, h is the bandwidth. In order to ensure the rationality of the probability density function, it is necessary to ensure its value the non-negative and the total results of integration will add up to 1. And those conditions can be obtained by requiring the kernel function $K\left(x\right)$ the distribution density.

Generally, it can choose square window, normal window to be the window function. But considering that the smoothness of the normal function will make the estimation function changes smoothly and changes only with one parameter change, the normal window is decided to be the kernel function.

So the kernel function is:

$K\left(x,x_i\right)=\frac{1}{\sqrt{2\text{π}}h}\exp \left\{-\frac{{\left(x-x_i\right)}^2}{2h^2}\right\}$ (2)

The window width h is the only parameter needed to be adjusted. If the width h is too long, then the resolution will be very low. But if the width h is too short, the statistic change will be too high. Generally as long as the width h can minimize AMISE (Asymptotic Mean Integrated Squared Error), it is the optimal window width. However, in this way, the bandwidth can only be used as a starting point to explore the optimal estimation. From the practical point of view, Rudemo (1982) and Bowman (1984) propose a recursive method to determine the final bandwidth by cross validation method [5] .

Determine h to minimize the $ISE\left(h\right)$ :

$ISE\left(h\right)=n^{-2}{h}^{-1}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}K\cdot K\left(\frac{X_i-X_j}{h}\right)}}-2n^{-1}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\hat{p}}_{-i}\left(X_i\right)}$ (3)

where $K\cdot K\left(\frac{X_i-X_j}{h}\right)$ is the convolution, ${\hat{p}}_{-i}\left(X_i\right)$ is the estimation of pro-

bability density after removing the point $X_i$ .

2.3. Calculate the Specific Numbers of Passengers over the Corresponding Period

According to the data from the card management center, the record of passenger’s at every second is “1”or “0”. So with the record in the total time T, the Parzen Window method can figure out the probability density function: $p\left(x\right)$ , which have the features:

$\{\begin{array}{l}p\left(x\right)\ge 0;\\ {\displaystyle {\int }_0^{T}p\left(x\right)\text{d}x=1}\end{array}$ (4)

To visually represent the probability value of having a passengers arriving at the parking site per second, $p\left(x\right)$ needs to be disposed as following:

$p_t={p\left(x\right)|}_{x=t}\cdot N$ (5)

which N indicates the total number of passengers in the whole day at the school bus-stops. Then integrate $p_t$ which in the section of $\left[T_1,T_2\right]$ , and the number of passengers during the time slot $\left[T_1,T_2\right]$ which is remarked as $N_{T_1}^{T_2}$ can be calculated:

$N_{T_1}^{T_2}={\displaystyle {\int }_{T_1}^{T_2}{p}_t\text{d}t}={\displaystyle {\int }_{T_1}^{T_2}{p\left(x\right)|}_{x=t}\cdot N\text{d}t}=N\cdot {\displaystyle {\int }_{T_1}^{T_2}p\left(x\right)\text{d}x}$ (6)

3. Model Analysis and Assumptions

3.1. Model Analysis

This paper intends to draw a conclusion about the reasonable timetable and number of the departure school bus Firstly, based on the real-time data, Parzen Window method can figure out the demanding number of passengers at any different time. Then, establish multi-objective optimization model and calculate the rational allocation of the school bus.

Considering the objective function, firstly from the perspective of students, the aim is to minimize the waiting and travelling time; secondly from the perspective of school, the aim is to minimize the total travelling cost and the loss due to the empty seat during the travelling. Moreover, considering the constraints, one constraint is the capacity of the school buses. Their real carrying number can’t beyond the maximum capacity. Besides, another constraint is the waiting time, each student staying in the parking site or staying in the bus has a maximum endurable waiting time, so every school bus no matter in which station should have a maximum time to stop and cannot overstay.

3.2. Model Assumptions

In order to facilitate the establishment and solution of the model, this paper makes the corresponding assumptions based on the actual situation:

1) Assuming that the school bus is always at a constant speed during travelling.

2) Assuming that there is no overload during travelling.

3) Assuming that all the school buses are operating properly without any maintenance and emergency situations.

4. The Mathematical Model

4.1. Establishment of Objective Function I

The shorter the total waiting time of students spend, the better. The student arrives at the stop at the time t_i in the probability of P_i and takes the bus at the time t_j. The total time for all students to take the school bus notes as W_T. The time section that the school bus running from the starting time T₁ to the ending time T₂ is divided into seconds from second 0 ~ second N_T.

So the objective function is as following [6] :

$\min W_T={\displaystyle \underset{i=0}{\overset{N_T}{\sum }}{P}_i\left(t_j-t_i\right)}j\ge i$ (7)

4.2. Establishment of Objective Function II

The less the total cost of the school bus is, the better. With reasonable scheduling as the main target, the model only considers the cost and loss of the school bus seat rates, regardless of the bus purchase cost and school staff salaries and other expenses. Assuming that the school bus only consider the distance cost when it reaches its maximum capacity.

Assuming that the university has N_C school buses and N_S school bus-stop sites, then the other objective function is represented as shown below:

$\min C_T={\displaystyle \underset{k=1}{\overset{N_C}{\sum }}{\displaystyle \underset{i=1}{\overset{N_S}{\sum }}{\displaystyle \underset{j=1}{\overset{N_S}{\sum }}\left(D_{kij}+E_{kij}\right)}}}$ (8)

$D_{kij}=N_{kij}\times d_{kij}$ (9)

where $C_T$ is total costs of the school bus operation, $D_{kij}$ is travel costs that school bus k travel from the site i to the site j, $E_{kij}$ is costs that school bus k travel from site i to site j due to empty seats, $N_{kij}$ is driving times that school bus k travel from site i to site j, $d_{kij}$ is the cost of a single trip that school bus k travel from site i to site j.

4.3. Establishment of Constraint I: School Bus Capacity Constraint

According to the actual situation, we take school bus safety and operating costs into consideration, that is to say the number of students must reach a certain number and cannot exceed its capacity whenever the school bus leaves the station. This constraint can be represented as follows:

$0.5Q_k\le L_{ik}\le Q_k$ (10)

where $Q_k$ is the maximum capacity of the school bus k while $L_{ik}$ is the number of students that school bus k have accumulated at the site i.

4.4. Establishment of Constraint II: Waiting Time Constraint

Due to the limited time of students after class and normal endurable waiting, the sum of the time $T_{kij}$ required for school bus k to arrive at site j from the other station i and the residence time $B_{kj}$ of the school bus k at the i site cannot exceed the waiting limit $T_c$ , which is determined by the questionnaire inferred. We set the speed of each school bus is equal and the number of station is P. The constraint is listed below [7] :

${\displaystyle \underset{\left(j=1,2,\cdots ,P\right)}{\sum }{T}_{kij}+B_{kj}\left(i\ne j\right)}\le T_c$ (11)

$0\le T_{kij}\le T_1$ (12)

$0\le B_{kj}\le T_2$ (13)

In summary, the multi - objective optimization model is as follows:

Objective functions:

$\{\begin{array}{l}\min W_T={\displaystyle \underset{i=0}{\overset{N_T}{\sum }}{P}_i\left(t_j-t_i\right)}j\ge i\\ \min C_T={\displaystyle \underset{k=1}{\overset{N_C}{\sum }}{\displaystyle \underset{i=1}{\overset{N_S}{\sum }}{\displaystyle \underset{j=1}{\overset{N_S}{\sum }}\left(D_{kij}+E_{kij}\right)}}}\end{array}$ (14)

Constraints:

$\{\begin{array}{l}0.5Q_k\le L_{ik}\le Q_k\\ {\displaystyle \underset{\left(j=1,2,3,4\right)}{\sum }{T}_{kij}+B_{kj}\left(i\ne j\right)}\le T_c\\ 0\le T_{kij}\le T_1\\ 0\le B_{kj}\le T_2\end{array}$ (15)

5. Model Solution and Example

5.1. Model Solution

The traditional multi-objective optimization method solves the multi-objective problem by weighted all the targets and summed them into single objective problems. Since this method requires a priori knowledge of the problem, so in the realistic issues, it is really complicated to determine the weight of each object. It could be more appropriate to use a new way called evolving calculation to solve the multi-objective problem. Particle swarm optimization algorithm (particle swarm optimization, PSO) is a kind of optimization algorithm proposed by Kennedy and Eberhart in 1995, because of its easiness to understand and implement, has been successfully applied in many optimization problems.

The minimum of student’s waiting time and the running costs is in conflicted with each other. Practically, if we enable students to get on the bus as soon as possible, the bus needs to launch frequently. However, by this way, the driving time and distance of the bus would be boosted, so the cost will increased relevantly. This particularity makes the problem difficult to be solved by the traditional weighted sum into a single objective, so we use the particle swarm optimization algorithm to solve the problem.

The flow chart of multi-objective search algorithm [8] [9] which based on the particle swarm optimization is shown in Figure 1.

Where the module of population initialization will initialize the position and velocity of the particle randomly; when calculating the value of fitness, each individual has two fitness value including the student’s waiting time and the school buses’ operation cost, besides, each individual are required to meet all the constraints; the particle update optimization means to update the individual optimal particle according to the new particle position; updating the non-inferior solution set is to filter the non-inferior solution according to the now particle dominance relation.

The particle velocity and position update formula is as follow:

$\begin{array}{l}{V}^{k+1}=w{V}^k+c_1{r}_1\left(P_{id}^k-X^k\right)+c_2{r}_2\left(P_{gd}^k-X^k\right)\\ X^{k+1}=X^k+V^{k+1}\end{array}$ (16)

Figure 1. The flow chart of multi-objective search algorithm.

where w is the inertia weight, r and r₂ is the random numbers between $\left[0,1\right]$ , k is times of current iteration, $P_{id}^k$ is the best location of individual particle, $P_{gd}^k$ is the best global optimal particle position, c₁ and c₂ are the constant, V is the particle speed, X is the particle position. When the particle adjusts its position depending on the speed, it will be limited to the maximum speed V_max. When V_i exceeds V_max, V_i are still be valued as V_max. In other way, V_max is the width of the search space [8] .

Among all the parameters, w, c₁ and c₂ account greatly on the performance of the algorithm. There are many scholars have studied their setting and adjustment. In terms of choosing parameters, the literature review [10] , through the simulation of different parameters on the particle exploration ability, algorithm and the successful rate of the algorithm performance, recommend a fixed set of parameters: $w=0.7298$ , $c_1=2.0434$ , $c_2=0.9487$ .

5.2. Case Study

Since the founding of Wuhan University of Technology, there exists many problems sin the school bus operating because of the much too distributed campus. Those issues have already affect students’ daily life. Hence, we take Wuhan University of Technology as the research object. To understand students’ demand in different period for different school buses, we did a survey on students through questionnaire both online and offline and collect the real-time data from the center of bus data.

5.2.1. Data Collection

In order to ensure the rationality and practicability of the scheme, the data source must be true and reliable, we collected sufficient raw data through questionnaire and investigated the data from center of school bus. We know that the total number of school bus N_C now is 15. There are three types of the school bus including large bus (L), medium-sized bus (M), small bus (S) whose maximum capacity is 60, 35, 15 respectively. Besides, the total number of the school bus-stop N_S is 4. And the longest residence time of the school bus T₁ is 10 minutes and the longest running time between two stops T₂ is 15 minutes. And the longest endurable waiting time of a student T_c is 10 minutes.

5.2.2. Data Processing

The probability distribution of the student passengers in South Lake campus on Monday which is estimated by the Parzen Window method is shown in Figure 2.

Where the plot represents the time whose unit is 10⁴ seconds, and the ordinate represent the probability whose unit is 10⁻³. According to the distribution, we can figure out that the peak probability usually distribute at the moment about 7:30, 9:40, 11:50, 13:30, 15:40, 17:40 which are the time of just finishing classes. So we can draw the conclusion that the result of the Parzen window is credible because the probability distribution is consistent with students’ actual travel rules.

Figure 2. The probability density estimation.

5.2.3. PSO Parameter Setting

In the last part of 5.1 Model Solution, the PSO parameter setting is: w = 0.7298, c₁ = 2.0434, c₂ = 0.9487, the size of initial population N = 50, V_max = 4.9 × 10⁴.

5.2.4. Result

Through the MATLAB programming solution, we can get the best scheduling of the school bus for every campus within a week. Because of the limited space, we now only show the Monday schedule of each campus as follow:

6. Conclusion

In this paper, we use the non-parametric estimation called the Parzen Window Method instead of a simple estimate of the probability distribution to estimate the probability distribution of students’ taking school bus every day. This method takes all the sample points’ influences into consideration rather than a part of them, so the estimated probability is more realistic. Next, according to the demand of student passengers, a multi-objective programming model is established, which can be adjusted and allocated to different time periods, different school districts, different types of school bus and the number of buses they own. Through the modeling of the Wuhan University of Technology, the model can get the detailed timetable. However, because we did not consider that the congestion period will have influences on the time of school bus travelling between two bus-stop stations, the final result is a little bit ideal. If the following research can fix this drawback, the model can be more consummative.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Zhang, F. and Zhu, T.Y. (2012) Optimization of School Bus Station and Line. Mathematics in Practice and Cognition, 4, 141-146.
[2]	Hao, Z.N. (2016) Study on Optimization Model and Algorithm of School Bus Route. Journal of Chongqing Jiaotong University (Natural Science Edition), 2, 126-130, 162.
[3]	Zhang, M. (2008) Research on Multi-Objective Routing Problem Optimization Based on Bi-level Programming. Southwest Jiaotong University.
[4]	Zhao, S.S., Xiong, W., Yu, W.Y., Wang, Z. and Lu, Q. (2015) Optimal Dispatching and Arrangement of University Buses—Taking Three Gorges University as an Example. Science and Technology Innovation and Application, 32, 7-9.
[5]	Wang, X. (2005) Nonparametric Statistics. Renmin University of China Press, Beijing, 213-218.
[6]	Zhou, Q., Zheng, Z. and Su, R.S. (2008) Research on Optimization of School Bus Dispatching. Journal of Hebei University of Technology (Social Science Edition), 23, 32-35.
[7]	Liu, W. (2013) Research on Optimal Scheduling Algorithm and Model of School Bus. Journal of Tsinghua University, Natural Science Edition, 2, 247-251.
[8]	Zhang, L.B., Zhou, C.G. and Ma, M. (2004) Solving Multi-Objective Optimization Problem Based on Particle Swarm Optimization. Journal of computer research and development, 41, 1286-1291.
[9]	Wen, Y., Liao, W.Z. and Be, I.Z. (2010) An Adaptive Particle Swarm Optimization Algorithm for Solving Multi-Objective Optimization Problems. Computer engineering and application, 46, 38-40.
[10]	Wang, D.F. and Meng, L. (2016) Performance Analysis and Parameter Selection of Particle Swarm Optimization. Automation, 10, 1552-1561.