Proposing an approach to calculate headway intervals to improve bus fleet scheduling using a data mining algorithm

Document Type : Research Paper


Iran University of Science and Technology


The growth of AVL (Automatic Vehicle Location) systems leads to huge amount of data about different parts of bus fleet (buses, stations, passenger, etc.) which is very useful to improve bus fleet efficiency. In addition, by processing fleet and passengers’ historical data it is possible to detect passenger’s behavioral patterns in different parts of the day and to use it in order to improve fleet plans. In this research, a new approach is developed to use AVL data to investigate relationship between headway change and passenger downfall rate. For this purpose, a new method is developed that is called Intelligent Headway Selection (IHS) approach. The aim of this approach is finding similar days from passengers’ behavior perspective in the dataset and by focusing on unusual patterns of each group, headway changes effects on passenger downfall rate is being studied. In this approach, in the first step, each day is classified into specific time periods (like half of hours) and the passengers’ behavior pattern is detected for each day during the specified time periods. Then, in the K-Means algorithm, Euclidian distance measure is replaced with Dynamic Time Warping (DTW) algorithm to enable the K-Means to compare time series. The modified K-Means algorithm is used to compare days in the dataset and categorize similar days in the same clusters. Then, headway – passenger per minute plot is created for each time period to detect unusual patterns. Then, a Headway Interval Detection Procedure (HIDP) is developed to use these unusual patterns to find suitable headway values for each time period.  Afterwards, these plots merged and the final headways are calculated.


Main Subjects

Lobel, A., 1999. Solving large-scale multiple-depot vehicle scheduling problems. In: Wilson, N.H.M. (Ed.), Computer-Aided Transit Scheduling. Lecture Notesin Economics and Mathematical Systems, vol. 471. Springer-Verlag, pp. 193–220.447–458.
Kwan, R.S.K., Rahin, M.A., 1999. Object oriented bus vehicle scheduling – the BOOST system. In: Wilson, N.H.M. (Ed.), Computer-Aided Transit Scheduling.Lecture Notes in Economics and Mathematical Systems, vol. 471. Springer-Verlag, pp. 177–191.
Mesquita, M., Paixao, J.M.P., 1999. Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow typeformulations. In: Wilson, N.H.M. (Ed.), Computer-Aided Transit Scheduling Lecture Notes in Economics and Mathematical Systems, vol. 471. Springer-Verlag, pp. 221–243.
Banihashemi, M., Haghani, A., 2000. Optimization model for large-scale bus transit scheduling problems. Transportation Research Record 1733, 23–30.
Freling, R., Wagelmans, A.P.M., Paixao, J.M.P., 2001. Models and algorithms for single-depot vehicle scheduling. Transportation Science 35 (2), 165–180.
Haghani, A., Banihashemi, M., 2002. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints.Transportation Research 36A, 309–333.
Haghani, A., Banihashemi, M., Chiang, K.H., 2003. A comparative analysis of bus transit vehicle scheduling models. Transportation Research 37B, 301–322.(Eds.), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430. Springer-Verlag, pp. 115–129.
Huisman, D., Freling, R., Wagelmans, A.P.M., 2004. A robust solution approach to the dynamic vehicle scheduling problem. Transportation Science 38 (4),447–458.
Shangyao Yan,2007, Intercity Bus Scheduling Model Incorporating Variable Market Share, Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions,Volume: 37, Issue: 6,921 – 932
Zhu Chang-sheng,2010, the research in public transit scheduling based on the improved genetic simulated annealing algorithm, Computational Intelligence and Natural Computing Proceedings (CINC), Second International Conference on, Volume 2, 273 – 276
Zhiwei Yang,2008, Research on Bus Scheduling Based on Artificial Immune Algorithm, Wireless Communications, Networking and Mobile Computing. WiCOM '08. 4th International Conference on, 1 - 4
Matias, L ,2010, Validation of both number and coverage of bus schedules using AVL data , Intelligent Transportation Systems (ITSC), 2010 13th International IEEE Conference, 131 - 136
O. Adebisi, 1986,a mathematical model for headway variance of fixed-route buses,Transportation Research Part B: Methodological, Volume 20, Issue 1, Pages 59–70
P. Furth, B. Hemily, T. Muller, J. Strathman, Uses of archived AVL–APC data to improve transit performance and management: review and potential, Transport. Res. Board (2003).
Ming-Jun Liua, b, Bao-Hu Mao, Shao-Kuan Chen, Li-Ping Gao, Quan-Xin Sun ,2010, An Exploratory Hazard-based Analysis of the First Discharge Headway,Procedia - Social and Behavioral Sciences, 6th International Symposium on Highway Capacity and Quality of Service, Volume 16, Pages 536–547
Chuanjiao SUN, Wei ZHOU, Yuanqing WANG,2008, Scheduling Combination and Headway Optimization of Bus Rapid Transit,Journal of Transportation Systems Engineering and Information Technology, Volume 8, Issue 5, Pages 61–67
J. Patnaik, S. Chien, A. Bladikas, Using data mining techniques on apc data to develop effective bus scheduling, J. System. Cybernet. Inform. 4 (1) (2006)
Bin Yu, Zhongzhen Yang, Xueshan Sun, Baozhen Yao, Qingcheng Zeng, Erik Jeppesen ,2011,Parallel genetic algorithm in bus route headway optimization,Applied Soft Computing, Volume 11, Issue 8, Pages 5081–5091
Yanhong Li, Wangtu Xu, Shiwei He,2013,Expected value model for optimizing the multiple bus headways, Applied Mathematics and Computation, Volume 219, Issue 11, Pages 5849–5861
Yang Hairong, Changsha, 2009, Optimal Regional Bus Timetables Using Improved Genetic Algorithm,Intelligent Computation Technology and Automation. ICICTA '09. Second International Conference on  (Volume: 3), 10-11 Oct. 2009, 213 – 216
Dirk L. van Oudheusden, William Zhub, 1995, Trip frequency scheduling for bus route management in Bangkok, European Journal of Operational Research, Volume 83, Issue 3, Pages 439–451
Sho-Hsien Liao, Pei-Hui Chu, Pei-Yuan Hsiao, 2012, Data mining techniques and applications – a  decade review from 2000 to 2011, Expert Systems with Applications, Volume 39, Issue 12, Pages 11303,11311
Tak-Chun Fu, 2011, A review on time series data mining, Engineering Applications of Artificial Intelligence, Volume 24, Issue 1, Pages 164-181
B. Barabino, M. Di Francesco, S. Mozzoni, Regularity diagnosis by automatic vehicle location raw data, Public Transport 4 (3) (2013) 187–208
Mandelzys M, Hellinga B (2010) Identifying causes of performance issues in bus schedule adherence with automatic vehicle location and passenger count data. Transp Res Rec 2143:9–15
Ruan M, Lin J (2009) An investigation of bus headway regularity and service performance in Chicago bus transit system. Paper presented at the Transport Chicago, annual conference
M. Chen, X. Liu, J. Xia, S. Chien, A dynamic bus-arrival time prediction model based on apc data, Comput.-Aid. Civil Infrastruct. Eng. 19 (5) (2004) 364– 376.
Q. Chen, E. Adida, J. Lin, Implementation of an iterative headway-based bus holding strategy with real-time information, Public Transport 4 (3) (2013) 165–186.
A. El-Geneidy, J. Horning, K. Krizek, Analyzing transit service reliability using detailed data from automatic vehicular locator systems, J. Adv. Transport. 45 (1) (2011) 66–79.