In this paper, we consider a public transport departure time prediction problem. The problem is considered in twonotations: estimation of the mean expected departuretime and estimation of the time interval required to ensurae predefined probability to depart on-time. We propose departure time estimation algorithms based on a real-time monitorindgata, schedule and operation strategies for the public transport management. We consider a schedule-based holding strategy and a bus bunching prevention strategy. We also propose an algorithm for departure time intervalestimation. Numerical tests based on real bursoutes in Samara, Russia are used for a comparative study of dierent departure time prediction algorithms.
It is a challenge for public transportation agencies to provide reliable service because public transport often operates under conditions of high uncertainty. Variation in travel time caused by di erent factors of uncertainty, such as real-time tra c situation and tra c congestion, weather conditions, change of passenger ow, driver behavior [1]. The unreliability of the transport schedule reduces the e ciency of the transport infrastructure because road users have to take into account risks of arriving late while planning the route. This is especially important for the passenger transport, where the discrepancy with the schedule can accumulate and lead to the bus bunching problem.
variables. Non-parametric regression (NPR) models is a relatively simple method for prediction without the need to estimate parameters. K nearest neighbor (k-NN) methods are one of the most popular NPR methods. Bus travel time prediction models using k-NN was developed in [3, 4].
Machine learning models, including arti cial neural networks (ANN) and support vector machine (SVM) models. ANN has been reported to be especially useful for nding solutions for complex non-linear problems. In [8] authors proposed two ANN-based models to predict bus arrival time: the link-based ANN and the stop-based ANN. The paper [6] proposed a dynamic algorithm that integrated the ANN model and a Kalman lter-based algorithm. In [9] authors used Bayesian inference theory to combine neural networks. Their results showed that the ANN model outperformed the historical data based model and the regression model in terms of prediction accuracy. SVM is a very speci c type of learning algorithm characterized by the capacity control of the decision function, the use of the kernel functions, and the sparse solution. The SVM-based models to predict bus arrival time was developed in [10{12].
design and operational management of the public transport [15]. The use of operational control strategies makes it possible to reduce the discrepancy between the scheduled time and the real time of arrival at the control points and prevent the bus bunching on the route. One of the most popular control strategies is the schedule-based holding control strategy: if a bus arrives at a stop earlier than the scheduled time, it is held until the scheduled departure time is reached [16]. Although this strategy can improve schedule adherence, it delays the operation of early buses and causes impatient among passengers on board. Another strategy is a driver schedule recovery strategy that proposes to adjust speed over segments between two consecutive control points to arrive on-time [17, 18]. However, this strategy requires that drivers highly exible response to the tra c situation and can be limited by tra c conditions.
The structure of this paper is organized as follows: the second section introduces the basic notations and the problem formulation, describes the departure time prediction algorithms based on real-time tra c data and schedule. In this section, we propose an algorithm based on the operation control strategies. The third section presents the problem formulation of the departure time interval estimation and describes a base algorithm for solving this problem. In the fourth section, we present an experimental study of the algorithms. Lastly, we present our conclusions and recommendations for future work.
Ir be the bus run numbers on the route r 2 R; DTi be the departure time from the starting station of the bus with the run number i 2 Ir on the route r 2 R; DTisch be the scheduled departure time from the starting station of the bus i 2 Ir; ATi be the arrival time at the ending terminal of the bus i 2 Ir; ATisch be the scheduled arrival time at the ending terminal of the bus i 2 Ir.
runs).
Denote the deviation of the real observed arrival time of the bus with the run number i 2 Ir from the scheduled arrival time as iarr:
iwait:
DTjsch + min;
iarr; >:DTjsch + max (0; arr i wait < 0; arr < 0; i iwait); otherwise; where 2 [0; 1] are the control strategy coe cients.
where (i; j); i 2 Ir; j 2 Ir is the numbers of consecutive runs of the bus v 2 V on the route r 2 R.
following assessment construction:
In the next subsections, we describe algorithms for estimation the departure time D^Ti based on the real-time monitoring information, schedule, and operation control strategies: a holding control strategy and a bus bunching prevention strategy.
The monitoring data based departure time prediction algorithm uses the real-time monitoring data taking into account the planned schedule. The main assumption of the algorithm is that the deviation of the arrival time at the ending terminal from the scheduled arrival time will be maintained when the vehicle departs from the starting station. The departure time estimation based on the monitoring data can be described as follows
DT^jM = DTjsch + iarr:
The schedule-based holding control strategy is one of the most popular strategies in the bus route schedule design problem. In this strategy, if a bus arrives early at the timing point, it will be held until the scheduled departure time is reached. If the bus is already late, it will depart from the timing point immediately after passenger pickup. We use the similar approach to adapt schedule-based holding strategy to estimate the departure time from the starting terminal.
time iarr and the waiting (recovery) time iwait to control the departure time in the following way: arr = ATi i
ATisch: iwait = DTjsch
ATisch; D^Ti; 8i 2 Ir; 8r 2 R: (1) (2) (3) if the vehicle arrived at the terminal stop later than the scheduled departure time of the next run, then shorten the waiting time to a minimum; if the vehicle arrived earlier than the scheduled arrival time, then reduce the deviation from the scheduled departure time by the recovery time increasing; otherwise, reduce the deviation from the scheduled departure time by reducing the recovery time.
The operation strategy based algorithm considers a minimum delay between departure times of the di erent buses on the same route to prevent bus bunching.
Denote the minimum delay between the departure times as rroute; r 2 R.
Then the departure time estimation for the run number j 2 R of the vehicle v 2 V on the route r 2 R can be expressed as follows:
DT^jOS = max(D^TjS; DTk + route); r where k is the last run number, D^TjS is the departure time estimation obtained using the schedule-based algorithm.
In the previous section, we describe the mean expected departure time estimation problem. Sometimes this formulation cannot be suitable for passengers. Often it is desirable to know not a time instant of the departure, but a departure time interval required to ensure a prede ned probability of departing on-time.
(4) (5) (6) P (
dep < DTi < ) > p; where DTi is the departure time,
dep is the estimated departure time interval. The base departure time dep estimation algorithm uses tra c statistics. Let rd = fDTi; i 2 Irg be the dataset with the departure time of the vehicles v 2 V on the routes r 2 R in the selected d N day d, r = f r gd=1 be the statistics for N days.
p(d; ; ) = (1; 9DTi 2 0; othewise; rd : < DTi < ;
end dep =
; Algorithm 1: Departure time interval estimation p^ = 0;
= 0; while p^ < p do
= + step; // step - increment step p^ = PN
d=1 p(d; ; )=N ;
An experimental study of the algorithms was carried out on the public transport data in Samara. To estimate the departure time, we chose the 1070 runs of di erent bus routes, for which the departure / arrival times to the control points according to the schedule are known.
Firstly, we estimate the deviation of the real observed arrival time to the terminal stop from the scheduled arrival time. Figure 1 shows the histogram of the arrival time deviation. The positive deviation indicates the delay in the arrival, and the negative deviation means that the vehicle arrives ahead of schedule. As can be seen from the histogram, vehicles often arrive at the ending terminal later than the scheduled time.
350 300 re250 b um200 n lse150 c i eh100 V 50 0 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
Devia!on, min
selected criteria. Using bus bunching prevention control strategy do not improve the departure time estimation precision.
At the nal stage of the experimental study, we estimate the deviation of the real observed departure time from the estimated departure time. Figure 2 depicts the histogram of the departure time deviation. A positive deviation means that the vehicle departed after the estimated departure time.
300 250 r eb200 m u n150 s e l ich100 e V 50 0 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24
Devia!on, min
In this paper, we considered the problem of public transport departure time estimation. We compared the algorithm based on the real-time monitoring, the schedule-based algorithm with the holding operation strategy, and the operation strategy based algorithm with bus bunching prevention strategy. The schedule-based algorithm with the holding control strategy showed the best results by mean absolute error criteria. Using bus bunching prevention strategy did not decrease the error of the estimation.
problem is considered in two notations: estimation of the mean expected departure time and estimation of the time interval required to ensure a prede ned probability to depart on-time. We compare algorithms based on a real-time tra c data and public transport schedule. The paper proposes an original prediction algorithm based on the operation strategies of the public transport management. Numerical tests based on real bus routes in Samara, Russia are used for a comparative study of di erent departure time prediction algorithms.