#  Reconstructing Transit Vehicle Trajectory Using High-Resolution GPS Data
††thanks: ©2023 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other uses, in any current or future media,
including reprinting/republishing this material for advertising or promotional
purposes, creating new collective works, for resale or redistribution to
servers or lists, or reuse of any copyrighted component of this work in other
works.

Yuzhu Huang1, Awad Abdelhalim2, Anson Stewart2, Jinhua Zhao2, Haris
Koutsopoulos3 1 Department of Civil and Environmental Engineering,
Massachusetts Institute of Technology<EMAIL_ADDRESS>Department of Urban
Studies and Planning, Massachusetts Institute of Technology<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Civil and Environmental
Engineering, Northeastern University<EMAIL_ADDRESS>
###### Abstract

High-resolution location (“heartbeat”) data of transit fleet vehicles is a
relatively new data source for many transit agencies. On its surface, the
heartbeat data can provide a wealth of information about all operational
details of a recorded transit vehicle trip, from its location trajectory to
its speed and acceleration profiles. Previous studies have mainly focused on
decomposing the total trip travel time into different components by vehicle
state and then extracting measures of delays to draw conclusions on the
performance of a transit route. This study delves into the task of
reconstructing a complete, continuous, and smooth transit vehicle trajectory
from the heartbeat data that allows for the extraction of operational
information of a bus at any point in time into its trip. Using only the
latitude, longitude, and timestamp fields of the heartbeat data, the authors
demonstrate that a continuous, smooth, and monotonic vehicle trajectory can be
reconstructed using local regression in combination with monotonic cubic
spline interpolation. The resultant trajectory can be used to evaluate transit
performance and identify locations of bus delays near infrastructure such as
traffic signals, pedestrian crossings, and bus stops.

##  I Introduction

###  I-A Background

As more sensors and devices are installed on transit vehicles for monitoring
various aspects of transit fleet operations, higher quality and more granular
data become available to transit agencies. One recent data source addition is
the high-resolution GPS data of vehicle location, often called “second-by-
second data” (referred to as “heartbeat data” hereinafter), that records the
historical location and other metadata of each transit vehicle at almost every
second.

While analysts can use operational metrics obtained from analyzing stop-level
Automatic Vehicle Location (AVL) data to identify areas with poor performance,
it is difficult to determine what exactly contributes to the poor performance
in each area. As an example, an analyst may find that the average speed of
buses is particularly low within one stop-to-stop segment, but the low average
speed could be caused by slow-moving traffic due to congestion, or by stopping
delays incurred by traffic signals. The average speed information alone is not
enough to determine which one of the two is the primary source of delay, thus
making it challenging to pinpoint the most effective traffic intervention or
transit improvement strategy.

In comparison, the heartbeat data offers timestamps of vehicles not only at
bus stops, but also at locations in between them. Therefore, the heartbeat
data contains a richer set of data than AVL and would allow analysts to
understand the exact behaviors of vehicles at any location along its route.
Such detailed information offers an opportunity to uncover the interactions
between buses and other road infrastructure and points of conflict besides bus
stops that could impede bus movement such as traffic signals, pedestrian
crossings, etc.

###  I-B Motivation

At first glance, the heartbeat data seems to provide information about the
exact location of each vehicle in such detail that it should be able to tell
everything an analyst would wish to know about a vehicle’s trip. However,
closer examination of the data would show that the coordinate data can be
noisy and vehicles may appear to straddle the road network, and the data
recorded can have inconsistent frequency, making it difficult to directly read
the exact location and speed of the vehicle from the heartbeat data at every
point of interest.

The task of extracting operational information from the heartbeat data would
be easier if a complete transit vehicle trajectory could be reconstructed from
raw heartbeat data. Such a trajectory would provide reliable information about
the location, speed, and acceleration of the transit vehicle at any time and
distance into the trip, thus offering valuable information to analysts trying
to understand how transit vehicles interact with the built environment at a
very granular level.

This research features the following contributions:

  * •

A concise definition for an ideal transit vehicle trajectory is proposed;

  * •

A process for how noisy and intermittent heartbeat data can be converted to a
series of discrete timestamped location data is demonstrated;

  * •

Several smoothing algorithms that convert the discrete data to a continuous
trajectory function are explored and evaluated.

To the authors’ best knowledge, this research is the first of its kind that
attempts to understand bus operations by reconstructing complete vehicle
trajectories from heartbeat data.

###  I-C Related Work

Researchers have explored various uses of transit heartbeat data to understand
bus operations. Hall and Vyas calculated the average segment speeds of transit
vehicles by dividing segment length by non-dwell travel times and evaluated
how well transit vehicle speeds can represent the congestion state of general
traffic [1]. Colghlan et al. calculated the average speed of the entire trip
by dividing the total trip length by the total trip time and compared the
result to an ideal speed to draw a conclusion about queueing delay [2]. Aemmer
et al. used high-resolution GTFS-RT data to calculate vehicle speeds by taking
the slope between two time-distance data points and used the difference
between the said speed and free-flow speed to categorize vehicle delays [3].
Lind and Reid calculated vehicle speeds similarly and made conclusions about
local and rapid bus services by comparing the speed and reliability patterns
[4]. These researchers have relied on drawing conclusions about bus operations
by calculating an average vehicle speed within a segment or between data
records rather than attempting to reconstruct a complete speed profile of the
vehicle. Cathey and Deiley constructed speed profiles of transit vehicles on
freeways using the Kalman Filter and concluded that granular AVL data gathered
from buses can serve as an additional data source for freeway performance
monitoring, but did not address the issue of negative speeds resulting from
the filtering process [5].

As reviewed by Li et al., researchers in the non-transit space have proposed
smoothing algorithms and imputation methods to reconstruct complete vehicle
trajectories using vehicle location data of general-purpose vehicles [6].
Toledo et al. proposed the use of local regression as the smoothing algorithm
to minimize the measurement errors of vehicle location data and to construct a
smooth and monotonic high-order polynomial as the vehicle trajectory[7].
Venthuruthiyil et al. further discussed the strategies for selecting the
optimal window size and polynomial order in reconstructing the trajectory
function [8]. Although the researchers demonstrated the applicability of local
regression in retrieving complete vehicle trajectories, they did not address
the lack of guarantee for the differentiability of high-order polynomials.
Rafati Fard et al. presented a method for reconstructing the trajectories of
vehicles captured in aerial photography using a two-step wavelet analysis
technique that reduces measurement errors but did not discuss whether the
reconstructed location trajectory is guaranteed to be non-decreasing [9]. Wu
et al. explored reconstructing traffic-related spatial-temporal datasets by
imputing missing values with Graphical Neural Networks but presented
applications only in reconstructing complete speed profiles rather than
location profiles [10].

Therefore, this research attempts to address the gap in the literature by
presenting methods to reconstruct a continuous, smooth, and monotonic transit
vehicle trajectory directly from high-resolution GPS coordinate data to enable
the extract of the location, speed, and acceleration of a bus at any point in
time into its trip.

##  II From Raw Coordinates to Time-Distance Data

###  II-A Notation and Formulation

The goal in reconstructing the vehicle trajectory using heartbeat data is to
convert the series of timestamped coordinates into a continuous function that
maps every point in time into a bus trip, i.e. “time into trip”, to a
“distance into trip” value. With classic vehicle kinematics equations, the
time-to-distance mapping offered by the trajectory function will then allow
for the derivation of the vehicle speed and acceleration profiles.

Suppose the heartbeat data of a bus trip contains a series of $n$ timestamped
coordinates, i.e.

$C=[C_{1},C_{2},...,C_{n}]^{T}$ (1)

recorded at timestamps

$S=[S_{1},S_{2},...,S_{n}]^{T},$ (2)

where for each $i\in\\{1,2,...,n\\}$, $C_{i}$ is a pair of latitude and
longitude values $(lat_{i},lon_{i})$ and timestamp $S_{i}$ is the date and
time at which the location of the bus is recorded as coordinate $C_{i}$ by the
onboard device.

Through a map-matching process, the series of raw coordinates, $C$, is
converted to a series of map-matched coordinates, $M$. Using information about
the characteristics of the road network, the series of timestamps $S$ and the
map-matched coordinates $M$ can be converted to time into trip values

$T=[t_{1},t_{2},...,t_{n}]^{T},$ (3)

and distance into trip values

$D=[d_{1},d_{2},...,d_{n}]^{T}.$ (4)

Detailed information about how the map-matching process can be carried out is
described in Section II-B.

The series of discrete time-distance data can be used to infer the location of
the vehicle at time points in the complement set $T^{C}=\\{t\in T_{R}:t\notin
T\\}$, where $T_{R}$ is the set of real values within the time range
$[0,t_{n}]$. To do so, an interpolation method or smoothing method is needed
in order to impute the distance into trip values at time points in $T^{C}$.
The algorithm takes $T$ and $D$ as input, and depending on the assumption
around the error term associated with each value in $D$, outputs a function
$f:T_{R}\to X$, where $X$ is a real set of true distance into trip values
corresponding to each time into trip value in $T_{R}$.

The continuous function $f$ provides a mapping from time $T_{R}$ to distance
$X$, and can be alternatively expressed as

$x(t)=f(t).$ (5)

The speed profile of the vehicle can then be derived as

$v(t)=\frac{d}{dt}x(t)=f^{\prime}(t),$ (6)

and the acceleration profile is

$a(t)=\frac{d^{2}}{dt^{2}}x(t)=f^{\prime\prime}(t).$ (7)

The entire process of reconstructing a complete vehicle trajectory from
timestamped raw coordinates given by the heartbeat data is illustrated in the
flow chart in Figure 1.

Figure 1: Flow chart of data processing.

###  II-B Map Matching

The raw coordinates recorded in the heartbeat data sometimes land in areas
beyond the road network rather than within actual road segments. To mitigate
the issue, a map-matching process is needed to “snap” each coordinate point to
the closest road segment to restore the location information as much as
possible.

The map-matching tool used by the authors is the Valhalla map engine, which
offers the “trace attributes” service that allows for the conversion of raw
coordinates $C$ to map-matched coordinates $M$ [11, 12]. The service also
returns the ID of the specific road segment, $r_{i}$, along the inferred path
that each matched coordinate $M_{i}$ lies on, as well as the most probable
normalized position, $p_{i}$, along the road segment $r_{i}$. The normalized
position value $p_{i}$ is given so that $0\leq p_{i}\leq 1$. $p_{i}=0$ means
the coordinate $M_{i}$ is at the beginning of the segment $r_{i}$, while
$p_{i}=1$ means the end.

For each bus trip, the vehicle is expected to run on a predefined and fixed
route, so the ordered list of possible road segments that make up the pattern
of the bus trip is known and denoted by

$\mathbf{R}=\langle R_{1},R_{2},...,R_{s}\rangle,$ (8)

where $s$ is the total number of road segments in the list, and segment
$R_{b}$ is downstream of $R_{a}$ for $b>a$. The map matched coordinate $M_{i}$
is considered valid only if $r_{i}\in\mathbf{R}$.

When analyzing the heartbeat data of a single bus trip, the trip is recorded
to start at timestamp $S_{1}$ and ends at timestamp $S_{n}$. Therefore, each
timestamp $S_{i}$ can be converted to a “time into trip” value $t_{i}$ through
the simple calculation:

$t_{i}=S_{i}-S_{1}.$ (9)

For every road segment in $\mathbf{R}$, its features including length are
available from OpenStreetMap [12]. With this information, each matched
coordinate of the bus can be converted to a distance value relative to the
starting location of the trip. Denote the length of segment $R_{j}$ by $L_{j}$
and the index of the road segment $r_{i}$ in the set $\mathbf{R}$ by $id_{i}$
(i.e. $r_{i}=R_{id_{i}}$), then a “distance into trip” value can be calculated
as follows:

$d_{i}=\sum\limits_{j=1}^{id_{i}-1}L_{j}+L_{id_{i}}\times
p_{i}-L_{id_{1}}\times p_{1}$ (10)

Note that the last term in Equation 10 is needed to ensure that $d_{1}=0$ and
that every distance into trip value is measured with respect to the first data
point.

Combining the time into trip and distance into trip information calculated
using Equations 9 and 10, a discrete series of time-distance data can be
obtained from the map-matched coordinates.

###  II-C Properties of An Ideal Bus Trajectory

The goal of data smoothing is to obtain a trajectory that resembles the real-
world behavior of the bus as realistically as possible. Therefore, a few
properties must be considered for the result to be representative of an actual
transit vehicle trip. These properties include:

  * •

The trajectory should be non-decreasing, i.e. the distance into trip at a
later time point should not be smaller than the distance into trip at a
previous time point.

  * •

The trajectory is made up of composite cubic polynomials. The position of the
vehicle is a result of control inputs and follows vehicle kinematics, and as
Nagy et al. reported, cubic polynomials are the lowest order curves that can
be used to generate the trajectory of car-like robots [13].

  * •

The trajectory function should be continuous and at least once differentiable
so that the speed profiles are also continuous and can be easily retrieved
from the function.

Since a suitable smoothing algorithm is the backbone of the process of
constructing a continuous trajectory function from discrete time-distance data
points, discussions around the exploration and evaluation of the algorithms
are carried out in the following section separately.

##  III Trajectory Smoothing

###  III-A Linear Interpolation

The simplest method to construct a continuous curve on the time-space diagram
using the discrete time-distance data obtained from the previous steps is
through linear interpolation, or equivalently, connecting adjacent data points
using line segments (LSEG).

An example snippet of the trajectory obtained from linear interpolation is
shown in Figure 2(a). Considering the three properties of an ideal bus
trajectory introduced above, it can be noticed that the trajectory is
continuous and monotonic but not smooth or differentiable. An approximated
speed profile can be obtained, however, through forward differentiation of the
time-distance function. An acceleration profile can then be similarly produced
from the speed profile.

###  III-B Polynomial Cubic Interpolation

To address the non-differentiability issue of linear interpolation, the
Piecewise Cubic Hermite Interpolant (PCHIP) algorithm developed by Fritsch et
al. is explored [14]. The PCHIP algorithm connects adjacent data points in $T$
and $D$ with a cubic polynomial function and enforces a smooth trajectory by
ensuring that the first derivative is equal for the connecting polynomial
functions on each side of a data point [15]. This maintains the cubic
polynomial and monotonic properties of the trajectory.

Figure 2(b) shows an example of the trajectory obtained using PCHIP. While the
PCHIP algorithm guarantees a continuous first derivative, it does not ensure a
continuous second derivative, resulting in a continuous speed profile but not
a continuous acceleration profile.

###  III-C Local Regression

Although the PCHIP algorithm allows for the construction of a trajectory that
satisfies all three properties of an ideal trajectory, one of the fundamental
assumptions that have to be made is that all the discrete distance into trip
data points that serve as the input to the algorithm are the true distances
and that there is no error associated with each distance value. Such an
assumption may not be valid, however, if the measurement error of the onboard
device is taken into consideration.

A local regression process (LOCREG) can be used to estimate the true distance
into trip of the bus vehicle at each recorded timestamp by weighing the
importance of nearby data points based on their distance from the timestamp of
interest, consequently smoothing out the transit vehicle trajectory [16].

Suppose the true distance of the vehicle at each time point $t_{i}$ is $x_{i}$
such that

$x_{i}=d_{i}+\varepsilon_{i},$ (11)

where $d_{i}$ is the measured distance at time $t_{i}$, and $\varepsilon_{i}$
is the measurement error for $d_{i}$. The objective of the local regression
algorithm is to find a function $f:t\to x$ such that it solves the following
minimization problem at each data point $(t_{i},d_{i})$:

$\min\sum_{j=1}^{n}w_{i,j}(d_{i}-f(t_{i}))^{2},$ (12)

where the value of each weight term $w_{i,j}$ is determined by the selected
bandwidth and kernel function. In this study, cubic polynomials, the tricube
kernel proposed by Cleveland and a bandwidth of 20 data points are selected
empirically in the estimation of each true distance $x_{i}$ [16].

An example snippet of the trajectory obtained from local regression is shown
in Figure 2(c). LOCREG is superior to LSEG and PCHIP in that it produces a
continuous trajectory that takes into account the measurement error of each
measured distance, but it does not necessarily guarantee differentiability or
monotonicity of the overall function. This can result in negative speed values
when taking the first derivative of the LOCREG trajectory and also presents
challenges in deriving speed and acceleration profiles.

###  III-D Interpolation and Regression

To address the issue with monotonicity from using local regression, an
exploratory algorithm is experimented with. This algorithm, named LOCREG-
PCHIP, combines the desired properties of both PCHIP and LOCREG, removes the
non-monotonic sections of the LOCREG data, and fills in the now missing
intervals by passing the remaining data through a monotonic interpolation
algorithm such as PCHIP.

A complete workflow that starts from data smoothing and ends with filling in
data to obtain a smooth and monotonic trajectory is detailed in Algorithm 1.

Algorithm 1 LOCREG-PCHIP

Input: an $1\times n$ vector $T$ of time into trip values
$t_{1}<t_{2}<...<t_{n}$, an $1\times n$ vector $D$ of distance into trip
values $d_{1}\leq d_{2}\leq...\leq d_{n}$ for $i=1,...,n$ and $n>2$.

1:X = []

2:$f_{locreg}=LOCREG(T,D)$

3:for i = 1, 2, …, n do

4: $x_{i}=f_{locreg}(t_{i})$

5: if $i>1$ and $x_{i}<x_{i-1}$ then

6: $x_{i}=x_{i-1}$

7: end if

8: $X.append(x_{i})$

9:end for

10:$f=PCHIP(T,X)$

11:return $f$

An example snippet of the trajectory obtained from local regression is shown
in Figure 2(d). The trajectory obtained using LOCREG-PCHIP preserves the true
distance values estimated from local regression at all time points except for
those where the monotonicity principle is violated, in which case the distance
value is chosen to be equal to the largest distance value observed prior to
the said time points. Since the algorithm ends with constructing a PCHIP
function using the modified distance values, the resultant trajectory function
is both monotonic and differentiable.

(a) Linear interpolation

(b) PCHIP

(c) LOCREG

(d) LOCREG-PCHIP

Figure 2: Trajectory constructed from different algorithms.

##  IV Evaluation and Validation

The ground truth location, speed and acceleration data of a bus is not often
available. The following sections offer some alternative validation
strategies. The discussion uses a sample trajectory that is considered
representative of a typical bus trip as described in Section V-A, thus the
conclusions are assumed to be applicable to other bus trips as well.

###  IV-A Validation of the Speed Profile

One way to validate the accuracy of the speed profile is to check if the speed
from the calculated trajectory is indeed zero when the transit vehicle was
recorded as having doors open at a bus stop in the AVL data. The speed
profiles obtained from all aforementioned algorithms can be displayed over
color bands of door-open intervals in the AVL data as illustrated in Figure 3.

Figure 3: Comparison of all speed profiles.

In order to measure how well the speed trajectory aligns with the AVL stop
events, the number of integer seconds within AVL door-open intervals that
correspond to a zero speed on the speed profile can be calculated. The notion
of “zero speed” is loosely defined as a speed below which a vehicle is
considered not traveling to account for the additional errors in the distance
values that were not accounted for in the smoothing process.

As summarized in Table I, if the “stop speed” is defined as below 5 mph, the
speed at over 90% of the integer timestamps labeled as door-open in the AVL
data are correctly captured using the LOCREG, LOCREG-PCHIP, and PCHIP
algorithms. A more intuitive plot comparing the percentage of stop speed
correctly captured by each algorithm is shown in Figure 4.

TABLE I: Percentage of AVL door-open integer timestamps at which speeds are correctly captured by each algorithm. Algorithm | Stop-Speed Threshold (mph)
---|---
|  0 |  3 |  5
LSEG |  0 |  77 |  86
LOCREG |  7 |  77 |  100
LOCREG-PCHIP |  0 |  84 |  92
PCHIP |  0 |  92 |  98
Figure 4: Percentage of AVL door-open instances at which speeds are correctly
captured vs. the “stop speed” threshold.

###  IV-B Validation of the Acceleration Profile

Another way to check the performance of the algorithm is to examine the
percentage of accelerations that are beyond a reasonable threshold. Based on
the research by Kirchner et al., the maximum bus acceleration is $0.17g=3.7$
miles-per-hour-per-second (mphps) and maximum deceleration is $-0.24g=-5.3$
mphps [17]. As indicated by the acceleration profiles shown in Figure 5,
LOCREG and LOCREG-PCHIP produce acceleration profiles that are more reasonable
than the other two methods. This is verified by the percentage of unreasonable
accelerations summarized in Table II, where the authors find that only 1.3% of
the accelerations from LOCREG-PCHIP and none from LOCREG are beyond the
reasonable threshold, whereas 2.1% and 5.3% of accelerations from LSEG and
PCHIP, respectively, are unreasonable.

TABLE II: Percentage of trajectory data of which accelerations are beyond the $[-5.3,3.7]$ mphps threshold. Algorithm |  % unreasonable acceleration
---|---
LSEG |  2.1
LOCREG |  0.0
LOCREG-PCHIP |  1.3
PCHIP |  5.3
Figure 5: Comparison of all acceleration profiles.

Given the discussion above, the trajectories produced by LOCREG, LOCREG-PCHIP,
and PCHIP are better compared to those from LSEG when validated against stop-
level AVL data and reasonable acceleration thresholds.

###  IV-C Selection of the Best Algorithm

The “best algorithm” should produce trajectories that not only perform
reasonably well in the evaluation of speed and acceleration profiles but also
satisfy all three characteristics of an ideal trajectory. As shown in Table
III, the algorithms that satisfy these criteria are LOCREG-PCHIP and PCHIP.

TABLE III: Evaluation of algorithms.

Algorithm | Evaluation Criteria
---|---
|  MON1 |  CUB2 |  DIFF3 |  ERR4 |  AVL (%)5 |  ACC (%)6 |  Best
LSEG |  ✓ |  ✗ |  ✗ |  ✗ |  86 |  98 |
LOCREG |  ✗ |  ✗ |  ✗ |  ✓ |  100 |  100 |
LOCREG-PCHIP |  ✓ |  ✓ |  ✓ |  ✓ |  92 |  99 |  ✓
PCHIP |  ✓ |  ✓ |  ✓ |  ✗ |  98 |  95 |

  * 1

MON: the trajectory is non-decreasing

  * 2

CUB: the trajectory is made up of cubic polynomials

  * 3

DIFF: the trajectory is once differentiable

  * 4

ERR: minimizes measurement error

  * 5

AVL (%): the percentage of AVL dwell activities correctly captured

  * 6

ACC (%): the percentage of accelerations within a reasonable threshold

Comparing the LOCREG-PCHIP algorithm with PCHIP, LOCREG-PCHIP is preferable
because it is able to predict the true distances from observed distances using
the information provided by adjacent data points by taking advantage of the
LOCREG algorithm, rather than trusting each observation a hundred percent.
Therefore, it is decided that LOCREG-PCHIP is the best overall algorithm for
reconstructing bus trajectories.

##  V Case Study

To demonstrate how a complete bus trajectory can be reconstructed using
heartbeat data, a case study using real-world data is provided in the
following section. The case study aims at providing a concrete example of the
data processing procedures discussed in the previous sections and offers
insight into how analysts can utilize the complete bus trajectories
constructed using methods provided in this research to draw insight into
transit operations.

###  V-A Data Source

The heartbeat data analyzed in this study are archived snapshots of the GTFS-
RT data taken from the public-facing API made available by the Massachusetts
Bay Transportation Authority (MBTA). Each heartbeat data point records a
timestamped location of the transit vehicle during its trip. An examination of
the heartbeat data recorded over 12 weekdays of outbound Route 1 operated by
the MBTA reveals that most data is recorded in intervals shorter than 10
seconds with a median frequency of 6 seconds, mode of 3 seconds and mean of 9
seconds.

For the purpose of this case study, the heartbeat data of one outbound Route 1
trip operated on a weekday morning (Monday, April 25, 2022, at 8 AM) is
analyzed.

###  V-B Reconstructing Vehicle Trajectory

The heartbeat data of the analyzed trip contains 328 timestamped raw
coordinates, a subset of which is shown in the $S$ and $C$ columns in Table
IV. The raw coordinates are passed into the map-matching engine Valhalla [11],
which returns the corresponding matched coordinates shown in column $M$, the
ID of the road segment in column $r$, and the position of each matched
coordinate along its segment in column $p$.

TABLE IV: An example map-matched coordinate table. $i$ |  $S$ |  $C$ |  $M$ |  $r$ |  $p$
---|---|---|---|---|---
0 |  2022-04-25 08:24:45 |  (42.372642, -71.119048) |  (42.372660, -71.119108) |  0 |  0.639
1 |  2022-04-25 08:24:50 |  (42.372365, -71.119241) |  (42.372373, -71.119267) |  0 |  0.940
2 |  2022-04-25 08:24:57 |  (42.372246, -71.119324) |  (42.372252, -71.119319) |  2 |  0.463
… |  |  |  |  |

Using Equations 9 and 10, the time into trip $T$ and distance into trip $D$
values of each data point can be calculated and passed to the LOCREG-PCHIP
algorithm, a continuous vehicle trajectory color-coded by vehicle speed is
obtained and shown in the time-space diagram in Figure 6. The location of road
infrastructure such as bus stops, traffic signals, and pedestrian crossings
can also be identified through the map matching process and plotted in the
same figure.

Figure 6: A snippet of a LOCREG-PCHIP trajectory used for the operational
analysis of a sample weekday PM inbound trip of Route 1 operated by the MBTA.

The time-space diagram of a complete vehicle trajectory, in combination with
AVL data, can provide a wealth of information regarding the bus operation and
lend insight into the movement of the bus throughout its trip.

###  V-C Qualitative Analysis of A Vehicle Trajectory

Several observations of the operations of the sample bus trip are described
below to showcase the information that a complete bus trajectory can provide.

####  V-C1 Stop Dwelling Activities

As shown by the sections of the trajectory labeled $A$ in Figure 6, the
trajectory captures the bus stopping at the far-side bus stop at Massachusetts
Ave & Albany St after it waits at the traffic signal just upstream of the bus
stop.

The sections labeled $B$ show that the bus opened its door once upstream of
the bus stop at 84 Massachusetts Avenue and once at the bus stop.
Interestingly, this behavior could be due to the Massachusetts State
regulation which requires bus drivers to stop and open the doors before a
railroad track [18]. Both of these stopping activities are validated by the
door-open intervals recorded in the AVL data.

####  V-C2 Vehicle Speed

The section labeled $C$ in Figure 6 shows that the bus traveled at a speed of
approximately 25-30 mph 1.9-2.2 miles into the trip (Harvard Bridge), faster
than its speed at most other sections of the trip.

####  V-C3 Stopping at a Pedestrian Crossing

From the section labeled $D$ in Figure 6, one can see that the vehicle stopped
before a pedestrian crossing prior to stopping at the bus stop at
Massachusetts Ave opposite the Christian Science Center.

####  V-C4 Stopping at A Traffic Signal

The section labeled $E$ shows that the bus stopped at a traffic signal
upstream of the far-side stop at Massachusetts Ave & Tremont St. Besides
clearly showing the existence of the stopping activity at the traffic signal,
the trajectory also shows the duration that the bus stopped at the signal.
Such information about how long buses stop at a signal can be valuable for the
decision-making related to transit signal priority projects.

##  VI Conclusion and Discussion

This study developed methodologies to reconstruct continuous, monotonic, and
differentiable bus trajectories from noisy heartbeat data. The trajectory
smoothing algorithm LOCREG-PCHIP was identified as the best algorithm that
produces a trajectory satisfying ideal properties while performing well
against expected speed and acceleration data. The continuous bus trajectories
allow for the extraction of location, speed, and acceleration at any point in
time into a trip.

Several limitations are present with the methodologies that could be addressed
in future research. First, this study only explored using heartbeat data with
an average frequency of below 10 seconds. Further research may be needed to
determine how the algorithm will perform on data with larger time intervals.
Secondly, none of the smoothing algorithms presented in this study guarantees
that the trajectory is twice-differentiable, therefore the acceleration
profile is not guaranteed to be smooth. Lastly, the validation method used in
this study to evaluate the performance of the algorithm is merely checking
whether the speed and acceleration values fall within acceptable thresholds.
An ideal method, however, is to compare the location, speed, and acceleration
of vehicles with ground-truth data collected from telematics devices.

Further research will explore how the analysis of multiple bus trajectories
can be analyzed in batches to allow for the categorization and quantification
of different types of delays encountered by buses of specific routes or
corridors.

## References

  * [1] R. W. Hall and N. Vyas, “Buses as a traffic probe: Demonstration project,” _Transportation Research Record_ , vol. 1731, no. 1, pp. 96–103, 2000.
  * [2] C. Coghlan, S. Dabiri, B. Mayer, M. Wagner, E. Williamson, M. Eichler, and N. Ramakrishnan, “Assigning bus delay and predicting travel times using automated vehicle location data,” _Transportation Research Record_ , vol. 2673, no. 3, pp. 624–636, 2019.
  * [3] Z. Aemmer, A. Ranjbari, and D. MacKenzie, “Measurement and classification of transit delays using gtfs-rt data,” _Public Transport_ , pp. 1–23, 2022\.
  * [4] E. Lind and J. Reid, “Diagnosing obstacles to speed and reliability with high-resolution automatic vehicle locator data: bus time budgets,” _Transportation research record_ , vol. 2675, no. 12, pp. 464–474, 2021.
  * [5] F. W. Cathey and D. J. Dailey, “Transit vehicles as traffic probe sensors,” _Transportation Research Record_ , vol. 1804, no. 1, pp. 23–30, 2002.
  * [6] L. Li, R. Jiang, Z. He, X. M. Chen, and X. Zhou, “Trajectory data-based traffic flow studies: A revisit,” _Transportation Research Part C: Emerging Technologies_ , vol. 114, pp. 225–240, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0968090X19312987
  * [7] T. Toledo, H. N. Koutsopoulos, and K. I. Ahmed, “Estimation of vehicle trajectories with locally weighted regression,” _Transportation research record_ , vol. 1999, no. 1, pp. 161–169, 2007.
  * [8] S. P. Venthuruthiyil and M. Chunchu, “Trajectory reconstruction using locally weighted regression: A new methodology to identify the optimum window size and polynomial order,” _Transportmetrica A: Transport Science_ , vol. 14, pp. 1–19, 03 2018.
  * [9] M. Rafati Fard, A. Shariat Mohaymany, and M. Shahri, “A new methodology for vehicle trajectory reconstruction based on wavelet analysis,” _Transportation Research Part C: Emerging Technologies_ , vol. 74, pp. 150–167, 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0968090X16302261
  * [10] Y. Wu, D. Zhuang, A. Labbe, and L. Sun, “Inductive graph neural networks for spatiotemporal kriging,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 5, pp. 4478–4485, May 2021. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/16575
  * [11] Valhalla. Valhalla - open source routing engine for openstreetmap. [Online]. Available: github.com/valhalla
  * [12] OpenStreetMap contributors. OpenStreetMap. [Online]. Available: https://www.openstreetmap.org
  * [13] B. Nagy and A. Kelly, “Trajectory generation for car-like robots using cubic curvature polynomials,” in _Proceedings of 3rd International Conference on Field and Service Robotics (FSR ’01)_ , June 2001, pp. 479 – 490.
  * [14] F. N. Fritsch and R. E. Carlson, “Monotone piecewise cubic interpolation,” _SIAM Journal on Numerical Analysis_ , vol. 17, no. 2, pp. 238–246, 1980\. [Online]. Available: http://www.jstor.org/stable/2156610
  * [15] F. N. Fritsch and J. Butland, “A method for constructing local monotone piecewise cubic interpolants,” _SIAM Journal on Scientific and Statistical Computing_ , vol. 5, no. 2, pp. 300–304, 1984. [Online]. Available: https://doi.org/10.1137/0905021
  * [16] W. S. Cleveland, “Robust locally weighted regression and smoothing scatterplots,” _Journal of the American Statistical Association_ , vol. 74, no. 368, pp. 829–836, 1979. [Online]. Available: http://www.jstor.org/stable/2286407
  * [17] M. Kirchner, P. Schubert, and C. T. Haas, “Characterisation of real-world bus acceleration and deceleration signals,” _Journal of Signal and Information Processing_ , vol. 2014, 2014.
  * [18] Massachusetts State Department of Public Utilities. Code of Massachusetts Regulations (CMR). [Online]. Available: https://www.mass.gov/files/220˙cmr˙155.00˙final˙8˙7˙09.pdf