IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 11, NO. 3, SEPTEMBER 2010 753
[8] P. Viola and M. Jones, “Robust real-time face detection,” Int. J. Comput.
Vis., vol. 57, no. 2, pp. 137–154, May 2004.
[9] M. Carrasco, L. Pizarro, and D. Mery, Bimodal Biometric Person Identifi-
cation System Under Perturbations. Berlin, Germany: Springer-Verlag,
2007, p. 114.
[10] W. Zhao, R. Chellappa, P. Phillips, and A. Rosenfeld, “Face recognition:
A literature survey,” ACM Comput. Surv. (CSUR), vol. 35, no. 4, pp. 399–
458, Dec. 2003.
[11] G. García-Busnter and M. Torres-Torriti, “Effective pedestrian detection
and counting at bus stops,” in Proc. IEEE Latin Amer. Robot. Symp.,
Oct. 2008, pp. 158–163.
[12] F. Delgado, J. C. Muñoz, R. Giesen, and A. Cipriano, “Real-time control
of buses in a transit corridor based on vehicle holding and boarding limits,”
in Proc. 88th Annu. Meeting Transp. Res. Board, Jan. 2009, pp. 59–67.
[13] C. Cortés, D. Sáez, E. Sáez, A. Núñez, and A. Tirachini, “Hybrid predic-
tive control strategy for a public transport system with uncertain demand,”
in Proc. 6th TRISTAN, Jun. 2007, 6 p.
[14] Poynting, RFID UHF Patch Antenna (PATCH-A0025), 2008. [Online].
Available: http://www.poynting.co.za/
[15] INfinity 510 Reader Datasheet, Sirit, Toronto, ON, Canada, 2008.
[16] Altelicon, CA-240 Coaxial Cable. [Online]. Available: http://www.
altelicon.com/
[17] Laitan Holding Corp. [Online]. Available: http://www.laitan.ca/
[18] ALN-9534 2 × 2 Inlay—Product Overview, Alien Technology, Morgan
Hill, CA, 2008. [Online]. Available: http://www.alientechnology.com/
docs/products/
[19] S. M. Ross, Introduction to Probability and Statistics for Engineers and
Scientists. Amsterdam, The Netherlands: Elsevier, 2004.
Modeling and Algorithms of GPS Data Reduction
for the Qinghai–Tibet Railway
Dewang Chen, Member, IEEE, Yun-Shan Fu, Baigen Cai,
and Ya-Xiang Yuan
Abstract—Satellites are currently being used to track the positions
of trains. Positioning systems using satellites can help reduce the cost
of installing and maintaining trackside equipment. This paper develops
a nonlinear combinatorial data reduction model for a large amount of
railway Global Positioning System (GPS) data to decrease the memory
space and, thus, speed up train positioning. Three algorithms are proposed
by employing the concept of looking ahead, using the dichotomy idea,
or adopting the breadth-first strategy after changing the problem into a
shortest path problem to obtain an optimal solution. Two techniques are
developed to substantially cut down the computing time for the optimal
algorithm. The surveyed GPS data of the Qinghai–Tibet railway (QTR)
are used to compare the performance of the algorithms. Results show
that the algorithms can extract a few data points from the large amount
of GPS data points, thus enabling a simpler representation of the train
tracks. Furthermore, these proposed algorithms show a tradeoff between
the solution quality and computation time of the algorithms.
Index Terms—Data reduction, Global Positioning System (GPS), heuris-
tic algorithms, Qinghai–Tibet railway (QTR), shortest path problem.
I. INTRODUCTION
As satellite positioning has many advantages (e.g., low cost, real
time, and no cumulative errors) [1], it is often used in car-navigation
systems [2] or in generating electronic maps [3]. Furthermore, satel-
lites are currently used to track the positions of trains instead of
using radio frequency systems [4] or track circuits. Positioning sys-
tems using satellites can help in reducing the cost of installing and
maintaining trackside equipment [5]. Recently, the European Union
has launched many projects (e.g., GADEROS [6] and RUNE [7])
using satellite positioning for low-density railways. In the United
States, an incremental train control system using GPS positioning was
employed in a Michigan railway [8]. The results of these projects
showed that satellite positioning has a better performance–cost ratio
for low-density railways. In China, GPS positioning was first adopted
in the train-control system for the Qinghai–Tibet railway (QTR) in
Manuscript received March 7, 2008; revised January 1, 2009 and June 22,
2009; accepted March 30, 2010. Date of publication May 24, 2010; date of
current version September 3, 2010. This work was supported in part by the
National Natural Science Foundation (NSFC) of China under Grant NSFC
60776833, Grant NSFC 60634010, and Grant NSFC 60736047. Some of the
work presented in this paper was completed during the visit of D. Chen with
the Institute of Computational Mathematics, Chinese Academy of Sciences,
Beijing, China, in 2008 and with the Berkeley Initiative in Soft Computing
Program, Department of Electrical Engineering and Computer Science, Univer-
sity of California, Berkeley, in 2009. The Associate Editor for this paper was
S. Sun.
D. Chen and B. Cai are with the State Key Laboratory of Rail Traffic
Control and Safety, Beijing Jiaotong University, Beijing 100044, China (e-mail:
dwchen@bjtu.edu.cn; bgcai@bjtu.edu.cn).
Y.-S. Fu and Y.-X. Yuan are with the State Key Laboratory of Scientific and
Engineering Computing, Chinese Academy of Sciences, Beijing 100080, China
(e-mail: fuys@lsec.cc.ac.cn; yyx@lsec.cc.ac.cn).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TITS.2010.2048030
1524-9050/$26.00 © 2010 IEEE