arXiv:1511.04810v1 [math.OC] 16 Nov 2015

Parsimonious shooting heuristic for trajectory control of
connected automated traffic part I: Theoretical analysis with
generalized time geography
Fang Zhoua , Xiaopeng Lia ∗, Jiaqi Mab
a. Department of Civil and Environmental Engineering,
Mississippi State University, MS 39762, USA
b. Transportation Solutions and Technology Applications Division,
Leidos, Inc., Reston, VA 20190, USA

Abstract
This paper studies a problem of controlling trajectories of a platoon of vehicles on a highway section
with advanced connected and automated vehicle technologies. This problem is very complex because each
vehicle trajectory is essentially an infinite-dimensional object and neighboring trajectories have complex
interactions (e.g., car-following behavior). A parsimonious shooting heuristic algorithm is proposed to
construct vehicle trajectories on a signalized highway section that comply with the boundary condition for
vehicle arrivals, vehicle mechanical limits, traffic lights and vehicle following safety. This algorithm breaks
each vehicle trajectory into a few segments that each is analytically solvable. This essentially decomposes
the original hard trajectory control problem to a simple constructive heuristic. Then we slightly adapt
this shooting heuristic algorithm to one that can efficiently solve the leading vehicle problem on an
uninterrupted freeway. To study theoretical properties of the proposed algorithms, the time geography
theory is generalized by considering finite accelerations. With this generalized theory, it is found that
under mild conditions, these algorithms can always obtain a feasible solution to the original complex
trajectory control problem. Further, we discover that the shooting heuristic solution is a generalization
of the solution to the classic kinematic wave theory by incorporating finite accelerations. We identify
the theoretical bounds to the difference between the shooting heuristic solution and the kinematic wave
solution. Numerical experiments are conducted to verify the theoretical results and to draw additional
managerial insights into the potential of trajectory control in improving traffic performance. In summary,
this paper provides a methodological and theoretical foundation for advanced traffic control by optimizing
the trajectories of connected and automated vehicles. Built upon this foundation, an optimization
framework will be presented in a following paper as Part II of this study.

1

Introduction

1.1

Background

As illustrated by the trajectories in the time-space diagram in Figure 1(a), traffic on a signalized arterial is
usually forced to decelerate and accelerate abruptly as a result of alternating green and red lights. When
traffic density is relatively high, stop-and-go traffic patterns will be formed and propagated backwards along
so-called shock waves. Similar stop-and-go traffic also occurs frequently on freeways even without explicit
signal interruptions. Such stop-and-go traffic imposes a number an adverse impacts to highway performance.
Obviously, vehicles engaged in abrupt stop-and-go movements are exposed to a high crash risk (Hoffmann
∗ Corresponding

author. Tel: 662-325-7196, E-mail: xli@cee.msstate.edu.

1

Space

Space

Time
(a)

Time
(b)

Figure 1: Vehicle trajectories along a highway section upstream of an signalized intersection: (a) benchmark
manual vehicle trajectories; (b) smoothed automated vehicle trajectories.
and Mortimer, 1994), not to mention extra discomfort to drivers (Beard and Griffin, 2013). Also, frequent
decelerations and accelerations cause excessive fuel consumption and emissions (Li et al., 2014), which pose
a severe threat to the urban environment. Further, when vehicles slow down or stop, the corresponding
traffic throughput decreases and the highway capacity drops (Cassidy and Bertini, 1999), which can cause
excessive travel delay.
Although stop-and-go traffic has been intensively studied in the context of freeway traffic with either
theoretical models (e.g., Herman et al. (1958); Bando et al. (1995); Li and Ouyang (2011)) or empirical
observations (e.g., Kuhne (1987); Kerner and Rehborn (1996); Mauch and Cassidy (2002); Ahn (2005); Li
and Ouyang (2011); Laval (2011a)), few studies had investigated how to smooth traffic and alleviate corresponding adverse consequences on signalized highways until the advent of vehicle-based communication
(e.g., connected vehicles or CV) and control (e.g., automated vehicles or AV) technologies. CV basically enables real-time information sharing and communications among individual vehicles and infrastructure control
units1 . AV aims to replacing a human driver with a robot that constantly receives environmental information via various sensor technologies (as compared to human eyes and ears) and consequently determines
vehicle control decisions (e.g., acceleration and braking) with proper computer algorithms (as compared to
human brains) and vehicle control mechanics (as compared to human limbs)2 . The combination of these two
technologies, which is referred as connected and automated vehicles (CAV), essentially enables disaggregated
control (or coordination) of individual vehicles with real-time vehicle-to-vehicle and vehicle-to-infrastructure
communications. Before these technologies, highway vehicle dynamics was essentially determined by microscopic human driving behavior. However, there is not even a universally accepted formulation of human
driving behavior (Treiber et al., 2010) due to the unpredictable nature of humans (Kerner and Rehborn, 1996)
and limited empirical data to comprehensively describe such behavior (Daganzo et al., 1999). Therefore,
it was very challenging, if not completely impossible, to perfectly smooth vehicle trajectories with traditional infrastructure-based controls (e.g., traffic signals) that are designed to accommodate human behavior.
Whereas CAV enables replacing (at least partially) human drivers with programmable robots whose driving
algorithms can be flexibly customized and accurately executed. This opens up a range of opportunities to
control individual vehicle trajectories in ways that cooperate with aggregated infrastructure-based controls
so as to optimize both individual drivers’ experience and overall traffic performance. These opportunities
inspired several pioneering studies to explore how to utilize CAV to improve mobility and safety at intersections (Dresner and Stone, 2008; Lee and Park, 2012a) and reduce environmental impacts along highway
segments (Ahn et al., 2013; Yang and Jin, 2014). However, these limited studies mostly focus on controlling
1 http://www.its.dot.gov/connected_vehicle/connected_vehicle.htm.
2 http://en.wikipedia.org/wiki/Autonomous_car

2

one or very few vehicles at a particular highway facility (e.g., either an intersection or a segment) to achieve
a certain specific objective (e.g., stability, safety or fuel consumption) rather than smoothing a stream of
vehicles to improve its overall traffic performance. Mos of the developed control algorithms require sophisticated numerical computations and their real-time applications might be hindered by excessive computational
complexities.
This study aims to propose a new CAV-based traffic control framework that controls detailed trajectory
shapes of a stream of vehicles on a stretch of highway combining a one-lane section and a signalized intersection. As illustrated in Figure 1(b), the very basic idea of this study is smoothing vehicle trajectories and
clustering them to platoons that can just properly occupy the green light windows and pass the intersection
at a high speed. Note that a higher passing speed indicates a larger intersection capacity, and thus we see
that the CAVs in Figure 1(b) not only have much smoother trajectories but also spend much less travel
times compared with the benchmark manual vehicles in Figure 1(a). Further, smoother trajectories imply
safer traffic, less fuel consumption, milder emissions, and better driver experience. While the research idea
is intuitive, the technical development is quite sophisticated, because this study needs to manipulate continuous trajectories that not only individually have infinite control points but also have complex interactions
between one another due to the shared rights of way. In order to overcome these modeling challenges, we first
partition each trajectory into a few parabolic segments that each is analytically solvable. This essentially
reduces an infinite-dimensional trajectory into a few set of parabolic function parameters. Further, we only
use four acceleration and deceleration variables that are nonetheless able to control the overall smoothness
of the whole stream of vehicle trajectories while assuring the exceptional parsimony and simplicity of the
proposed algorithm. With these treatments, we propose an efficient shooting heuristic algorithm that can
generate a stream of smooth and properly platooned trajectories that can pass the intersection efficiently
and safely yielding minimum environmental impacts. Also, note that this algorithm can be easily adapted to
freeway speed harmonization as well because the freeway trajectory control problem is essentially a special
case of the investigated problem with an infinite green time. We investigate a lead vehicle problem to study
this freeway adaption. After generalizing the concept of time geography (Miller, 2005) by allowing finite
acceleration and deceleration, we discover a number of elegant properties of these algorithms in the feasibility
to the original trajectory control problem and the connection with classic traffic flow models.
This Part I paper focuses construction of parsimonious feasible algorithms and analysis of related theoretical properties. We want to note that the ultimate goal of this whole study is to establish a methodology
framework that determines the best trajectory vectors under several traffic performance measures, such as
travel time, fuel consumption, emission and safety surrogate measures. While this paper also qualitatively
discusses optimality issues with visual patterns in trajectory plots, we leave the detailed computational issues
and the overall optimization framework to the Part II paper (Ma et al., 2015).

1.2

Literature Review

Freeway traffic smoothing has drawn numerous attentions from both academia and industry in the past
several decades. Numerous studies have been conducted in attempts to characterize stop-and-go traffic on
freeway (Herman et al., 1958; Chandler et al., 1958; Kuhne, 1987; Bando et al., 1995; Kerner and Rehborn,
1997; Bando et al., 1998; Kerner, 1998; Mauch and Cassidy, 2002; Ahn, 2005; Li and Ouyang, 2011; Laval,
2011a) Herman et al. (1958); Bando et al. (1995); Li and Ouyang (2011). However, probably due to the
lack of high resolution trajectory data (Daganzo et al., 1999), no consensus has been formed on fundamental
mechanisms of stop-and-go traffic formation and propagation, particularly at the microscopic level (Treiber
et al., 2010). To harmonize freeway traffic speed, scholars and practitioners have proposed and tested a
number of infrastructure-based control methods mostly targeting at aggregated traffic (rather than individual
vehicles), including variable speed limits (Lu and Shladover, 2014), ramp metering(Hegyi et al., 2005),
and merging traffic control (Spiliopoulou et al., 2009). While theoretical results show that these speed
harmonization methods can drastically improve traffic performance in all major performance measures, e.g.,
safety, mobility and environmental impacts (Islam et al., 2013; Yang and Jin, 2014), field studies show
the performances of these methods exhibit quite some discrepancies (Bham et al., 2010). Probably due to
limited understandings of microscopic behavior of highway traffic, these field practices of speed harmonization
3

are mostly based on empirical experience and trial-and-error approaches without taking full advantage of
theoretical models. Also, drivers may not fully comply with the speed harmonization control and their
individual responses may be highly stochastic, which further comprises the actual performance of these
control strategies. Therefore, these aggregated infrastructure-based traffic smoothing measures may not
perform as ideally as theoretical model predictions.
With the advance of vehicle-based communication (i.e., CV) and control (i.e., AV) technologies, researcher
started exploring ways of freeway traffic smoothing by controlling individual vehicles. Schwarzkopf and
Leipnik (1977) analytically solved the optimal trajectory of a single vehicle on certain grade profiles with
simple assumptions of vehicle characteristics based on Pontryagin’s minimum principle. Hooker (1988)
instead proposed a simulation approach that capture more realistic vehicle characteristics. Van Arem et al.
(2006) finds that traffic flow stability and efficiency at a merge point can be improved by cooperative adapted
cruise control (a longitudinal control strategy of CAV) that smooths car-following movements. Liu et al.
(2012) solved an optimal trajectory for one single vehicle and used this trajectory as a template to control
multiple vehicles with variable speed limits. Ahn et al. (2013) proposed an rolling-horizon individual CAV
control strategy that minimizes fuel consumption and emission considering roadway geometries (e.g., grades).
Yang and Jin (2014) proposed a vehicle speed control strategy to mitigate traffic oscillation and reduce vehicle
fuel consumption and emission based on connected vehicle technologies. They found with only a 5 percent
compliance rate, this control strategy can reduce traffic fuel consumption by up to 15 percent. Wang et. al.
(2014a; 2014b) proposed optimal control models based on dynamic programming and Pontryagin’s minimum
principle that determine accelerations of a platoon of AVs or CAVs to minimize a variety of objective cost
functions. Li et al. (2014) revised a classic manual car-following model into one for CAV following by
incorporating CAV features such as faster responding time and shared information. They found the CAV
following rules can significantly reduce magnitudes of traffic oscillation, emissions and travel time. Despite
relatively homogenous settings and complex algorithms, these adventurous developments have demonstrated
a great potential of these advanced technologies in improving freeway mobility, safety and environment.
Despite these fruitful developments on the freeway side, traffic smoothing on interrupted highways (i.e.,
with at-grade intersections) is a relative recent concept. This concept is probably motivated by recent CAV
technologies that allow vehicles paths to be coordinated with signal controls. The existing traffic smooth
studies for interrupted highways can be in general categorized into two types. The first type assumes that
CAVs can communicate with each other to pass an intersection in a self-organized manner (e.g., like a school
of fish) even without conventional traffic signals. For example, Dresner and Stone (2008) proposes a heuristic control algorithm that process vehicles as a queuing system. While this development probably performs
excellently when traffic is light or moderate, its performance under dense traffic is yet to be investigated.
Further, Lee and Park (2012b) proposes a nonlinear optimization model to test the limits of a non-stop intersection control scheme. They show that ideally, the optimal non-stop intersection control can significantly
outperform classic signalized control in both mobility and environmental impacts at different congestion levels. Zohdy and Rakha (2014) integrates an embedded car-following rule and an intersection communication
protocol into an nonlinear optimization model that manages a non-stop intersection. This model considers
different weather conditions, heterogeneous vehicle characteristics and varying market penetrations. Overall,
these developments on non-stop unsignalized control usually only focus on the operations of vehicles in the
vicinity of an intersection and require complicated control algorithms and simulation. How to implement
this complex mathematical programming model in real-time application might need further investigations.
The second type of studies for interrupted traffic smoothing consider how to design vehicles trajectories
in compliance with existing traffic signal controls at intersections. The basic ideal is that a vehicle shall
slow down from a distance when it is approaching to a red light so that this vehicle might be able to
pass the next green light following a relatively smooth trajectory without an abrupt stop. Trayford et al.
(1984a; 1984b) tested using speed advice to vehicles approaching to an intersection so as to reduce fuel
consumption with computer simulation. Later studies extend the speed advice approach to car-following
dynamics (Sanchez et al., 2006), in-vehicle traffic light assistance (Iglesias et al., 2008; Wu et al., 2010)
multi-intersection corridors (Mandava et al., 2009; Guan and Frey, 2013; De Nunzio et al., 2013), scaled-up
simulation (Tielert et al., 2010), and electric vehicles (Wu et al., 2015). These approaches mainly focused

4

on the bulky part of a vehicle’s trajectory with constant cruise speeds without much tuning its microscopic
acceleration. However, acceleration detail actually largely affects a vehicle’s fuel consumption and emissions
(Rakha and Kamalanathsharma, 2011). To address this issue, Kamalanathsharma et al. (2013) proposes
an optimization model that considers a more realistic yet more sophisticated fuel-consumption objective
function in smoothing a single vehicle trajectory at an signalized intersection. While such a model captures
the advantage from microscopically tuning vehicle acceleration, it requires a complicated numerical solution
algorithm that takes quite some computation resources even for a single trajectory.
In summary, there have been increasing interests in vehicle smoothing using advanced vehicle-based technologies in recent years. However, most relevant studies only focus on controlling one or a few individual
vehicles. Most studies either ignore acceleration detail and allow speed jumps to assure the model computational tractability or capture acceleration in very sophisticated algorithms that are difficult to be simply
implemented in real time. Further, few studies investigated theoretical properties of the proposed controls
and their relationships with classic traffic flow theories. Without such theoretical insights, we would miss
the great opportunity of transferring the vast elegant developments on existing manual traffic in the past
few decades to future CAV traffic.
This proposed trajectory optimization framework aims to fill these research gaps. We investigate a general
trajectory control problem that optimizes individual trajectories of a long stream of interactive CAVs on a
signalized highway section. This problem is general such that the lead vehicle problem on a freeway can be
represented as its special case (e.g., by setting the red light time to zero). This problem is a very challenging
infinite-dimension nonlinear optimization problem, and thus it is very hard to solve its exact optimal solution.
We instead propose a heuristic shooting algorithm to solve an near-optimum solution to this problem. This
algorithm can be easily extended to the freeway lead vehicle problem. While the proposed algorithms can
flexibly control trajectory shapes by tuning acceleration across a broad range, it is extremely parsimonious:
it compresses a trajectory into a very few number of analytical segments, and includes only a few acceleration
levels as control variables. With such parsimony and simplicity, these algorithms expect to be quite suitable
for real-time applications and further adaptations. The simple structure of these algorithms also allows us
to analyze its theoretical properties. By extending the traditional time-geography theory to a second-order
version that considers finite acceleration, we are able to analytically investigate the feasibility of the proposed
algorithms and the implication to the feasibility of the original problem. This novel extension also allows us
to relate the trajectories solved by the lead vehicle problem algorithm to those generated by classic traffic flow
models. This helps us reveal the fundamental commonalities between these two highway traffic management
paradigms based on completely different technologies.
This paper is organized as follows. Section 2 states the studied CAV trajectory optimization problem on
a signalized highway section and its variant for the lead vehicle problem on a freeway segment. Section 3
describes the proposed shooting heuristic algorithms for the original problem and its variant, respectively.
Section 4 analyzes the theoretical properties of the proposed algorithms based on an extended time-geography
theory. Section 5 demonstrates the proposed algorithms and their properties with a few illustrative examples.
Section 6 concludes this paper and briefly discusses future research directions.

2
2.1

Problem Statement
Primary Problem

This section describes the primary problem of trajectory construction on a signalized one-lane highway
segment, as illustrated in Figure 2. The problem setting is described below.
Roadway Geometry: We consider a single-lane highway section of length L. Location on this segment
starts from 0 at the upstream and ends at L at the downstream. We use location set [0, L] to denote this
highway section. Traffic goes from location 0 to L on this section. A fixed-time traffic light is installed at
location L. The effective green phase starts at time 0 with an duration of G, followed by an effective red
phase of duration R, and this pattern continues all the way. This indicates the signal cycle time is always

5

≥τ
≥s

Space

L

(vn− , t−
n)
0

Time

Figure 2: Illustration of the studied problem.
C := R + G. We denote the set of green time intervals as G := {[gm := mC, rm := mC + G)}m∈Z+
where Z+ is the non-negative integer set. We define function
G(t) = min{t′ ∈ G, t′ > t}, ∀t ∈ [−∞, ∞],
which identifies the next closest green time to t. Note that G(t) = t if t ∈ G or G(t) > t if t ∈
/ G.
Vehicle Characteristics: We consider a stream of N identical automated vehicles indexed as n ∈ N :=
{1, 2, · · · , N }. Each vehicle’s acceleration at any time is no less than deceleration limit a < 0 and no
greater than acceleration limit a > 0. The speed limit on this segment is v̄, and we don’t allow a
vehicle to back up, thus a vehicle’s speed range is [0, v].
We want to design a set of trajectories for these vehicles to follow on this highway section. A trajectory is
formally defined below.
Definition 1. A trajectory is defined as a second-order semi-differentiable function p(t), ∀t ∈ (−∞, ∞) such
that its first order differential (or velocity) ṗ(t) is absolutely continuous and its second-order right-differential
p̈(t) (or acceleration) is Riemann integrable over any t ∈ (−∞, ∞). We denote the set of all trajectories by
T̄ . We call the subsection of p between times t− and t+ (−∞ ≤ t− < t+ ≤ ∞) a trajectory section, denoted
by p (t− : t+ ).
We let function pn denote the trajectory of vehicle n, ∀n ∈ N . At any time t, pn (t) essentially denotes
the location of vehicle n’s front bumper. Collectively we denote all vehicle trajectories by trajectory vector
p := [pn (t)]n∈N . The trajectories in vector p shall satisfy the following constraints.
Kinematic Constraints: Trajectory p is kinetically feasible if ṗ(t) ∈ [0, v̄] and p̈(t) ∈ [a, ā] , ∀t ∈ (−∞, ∞).
We denote the set of all kinetically feasible trajectories as

T := p ∈ T̄ |0 ≤ ṗ(t) ≤ v̄, a ≤ p̈(t) ≤ ā, ∀t ∈ (−∞, ∞) .
(1)

−
Entry Boundary Condition: Let t−
n and vn denote the time and the speed when vehicle n arrives at the
−
−
entry of this segment (or location 0), ∀n ∈ N . We require t−
1 < t2 < · · · < tN and separation between
tn−1 and tn is sufficient for the safety requirement, ∀n ∈ N \{1}. Define the subset of trajectories in
T that are consistent with vehicle n’s entry boundary condition as

−
−
Tn− := p ∈ T p(t−
, ∀n ∈ N .
(2)
n ) = 0, ṗ(tn ) = vn

6

Exit Boundary Condition: Due to the traffic signal at location L, vehicles can only exit this section
during a green light. Denote the set of trajectories in T that pass location L during a green signal
phase by

T + := p ∈ T p−1 (L) ∈ G , ∀n ∈ N ,
(3)
where the generalized inverse function is defined as p−1 (l) := inf {t |p(t) ≥ l } , ∀l ∈ [0, ∞) , p ∈ T . Note
that function p−1 (·) shall satisfy the following properties:

P1: Function p−1 (l) is increasing with l ∈ (−∞, ∞);
P2: Due to speed limit v̄, p−1 (l + δ) ≥ p−1 (l) + δ/v̄, ∀l ∈ (−∞, ∞) , δ ∈ [0, ∞).
Further, let Tn denote
T the set of trajectories that satisfy both vehicle n’s entry and exit boundary
conditions, i.e., Tn = Tn− T + .
Car-following Safety: We require that the separation between vehicle n’s location at any time and its
preceding vehicle (n − 1)’s location a communication delay τ ago is no less than a jam spacing s (which
usually includes the vehicle length and a safety buffer), ∀n ∈ N \{1}. For a genetic trajectory p ∈ T ,
a safely following trajectory of p is a trajectory p′ ∈ T such that p′ (t − τ ) − p(t) ≥ s, ∀t ∈ (−∞, ∞).
We denote the set of all safely following trajectories of p as F (p), i.e.,

{p′ |p′ (t − τ ) − p(t) ≥ s, ∀t ∈ (−∞, ∞) } , ∀p
∈
T . (4)
T
With this, we define Tn (pn−1 ) := F (pn−1 ) Tn that denotes the set of feasible trajectories for vehicle
n that are safely following given vehicle (n − 1)’s trajectory pn−1 .
F (p)

:=

In summary, a feasible lead vehicle’s trajectory p1 has to fall in T1 , and any feasible following vehicle
trajectory pn has to belong to Tn (pn−1 ), ∀n ∈ N \{1} . We say a trajectory vector p is feasible if it satisfies
all above-defined constraints. Let P denote the set of all feasible trajectory vectors, i.e.,
P := {p := [pn ] n∈N |p1 ∈ T1 , pn ∈ Tn (pn−1 ) , ∀n ∈ N \1 } .

(5)

The primary problem (PP) investigated in this paper is finding and analyzing feasible solutions to P.
Remark 1. Although a realistic vehicle trajectory only has a limited length, we set a trajectory’s time horizon
to (−∞, ∞) to make the mathematical presentation convenient without loss of generality. In our study, we
−1
are only interested in trajectory sections between locations 0 and L, i.e., pn t−
n , pn (L) . Therefore, we
−
can just view pn (−∞, tn ) as the given trajectory history that leads to the entry boundary condition, and
pn p−1
n (L), ∞ as some feasible yet trivial projection above location L (e.g., accelerating to v̄ with rate ā
and then cruising at v̄). Further, with this extension, safety constraint (4) also ensures that vehicles did not
collide before arriving location 0 and will not collide after exiting location L.
Remark 2. This study can be trivially extended to static yet time-variant signal timing; i.e., the signal
timing plan is pre-determined, yet different cycles could have different green and red durations,
e.g., alPm
(G
+ Ri ) ,
ternating
like
G
,
R
,
G
,
R
,
·
·
·
.
In
this
case,
define
signal
timing
switch
points
g
=
i
1
1
2
2
m
i=1
P
+
rm = m
(G
+
R
)
+
G
,
∀m
∈
Z
and
G
becomes
{[g
,
r
)}
where
r
:=
0,
and
all
the
following
i
i
i
m
m
0
i=1
∀m=1,2
results shall remain valid.

2.2

Problem Variation: Lead-Vehicle Problem

In the classic traffic flow theory, the lead-vehicle problem (LVP) is a well-known fundamental problem
that predicts traffic flow dynamics on one-lane freeway given the lead vehicle’s trajectory and the following
vehicles’ initial states (Daganzo, 2006). We notice that PP (5) can be easily adapted to LVP by relaxing
exit boundary condition (3) yet fixing trajectory p1 . The LVP is officially formulated as follows. Given lead
vehicle’s trajectory p1 ∈ T , the set of feasible trajectories for LVP is
o
n
\
(6)
P LVP (p1 ) := p := [pn ] n∈N pn ∈ F (pn−1 ) Tn− , ∀n ∈ N \1 .

The LVP investigated in this paper is finding and analyzing feasible solutions to P LVP .
7

3

Shooting Heuristic Algorithms

This section proposes customized heuristic algorithms to solve feasible trajectory vectors to PP and LVP.
Although a trajectory is defined over the entire time horizon (−∞, ∞), these algorithms only focus on the
trajectory sections from the entry time t−
n for each vehicle n ∈ N , because the trajectory sections before
t−
should
be
trivial
given
history
and
do
not affect the algorithm results. Therefore, in the following
n
presentation, we view a trajectory and the corresponding trajectory section over time [t−
n , ∞) the same.

3.1

Shooting Heuristic for PP

This section presents a shooting heuristic (SH) algorithm that is able to construct a smooth and feasible
trajectory vector to solve P in PP very efficiently. Traditional methods for trajectory optimization include
analytical approaches that can only solve simple problems with special structures and numerical approaches
that can accommodate more complex settings yet may demand enormous computation resources (Von Stryk
and Bulirsch, 1992). Since a vehicle trajectory is essentially an infinite-dimensional object along which the
state (e.g. location, speed, acceleration) at every point can be varied, it is challenging to even construct one
single trajectory, particularly under nonlinear constraints. Note that our problem deals with a large number of
trajectories for vehicles in a traffic stream that constantly interact with each other and are subject to complex
nonlinear constraints (1)-(5). Therefore we deem that it is very complex and time-consuming to tackle this
problem with a traditional approach. Therefore, we opt to devise a new approach that circumvents the need
for formulating high-dimensional objects or complex system constraints. This leads to the development of
a shooting heuristic (SH) algorithm that can efficiently construct a smooth feasible trajectory vector with
only a few control parameters.
Figure 3 illustrates the components in the proposed SH algorithm. Basically, for each vehicle n ∈ N , SH
first constructs a trajectory, denoted by pfn , with a forward shooting process that conforms with kinematic
constraint (1), entry boundary constraint (2) and safety constraint (4) (if n > 1). As illustrated in Figure
3(a), if trajectory pfn (dashed blue curve) turns out far enough from preceding trajectory pn−1 (red solid
curve) such that safety constraint (4) is even not activated (or if n = 1 and pfn is already the lead trajectory),
−
pfn basically accelerates from its entry boundary condition (t−
n , vn ) at location 0 with a forward acceleration
f
rate of ā ∈ (0, ā] until reaching speed limit v̄ and then cruises at constant speed v̄. Otherwise, as illustrated
in Figure 3(b), if trajectory pfn is blocked by pn−1 due to safety constraint (4), we just let pfn smoothly merge
into a safety bound (the red dotted curve) translated from pn−1 that just keeps spatial separation s and
temporal separation τ from pfn . The transitional segment connecting pfn with the safety bound decelerates at
a forward deceleration rate of af ∈ [a, 0). If trajectory pfn from the forward shooting process is found to violate
exit boundary constraint (3) (or run into the red light), as illustrated in Figure 3(c), a backward shooting
process is activated to revise pfn to comply with constraint (3). The backward shooting process first shifts
the section of pfn above location L rightwards to the start of the next green phase to be a backward shooting
b
b
trajectory pb
n . Then pn shoots backwards from this start point at a backward acceleration rate ā ∈ (0, ā]
until getting close enough to merge into pfn , which may require pb
n stops for some time if the separation
between the backward shooting start point and pfn is long relative to acceleration rate āb . Then, pb
n shoots
b
backwards a merging segment at a backward deceleration rate of a ∈ [a, 0) until getting tangent to pfn .
Finally, merging pfn and pb
n yields a feasible trajectory pn for vehicle n. Such forward and backward shooting
processes are executed from vehicle 1 through vehicle N consecutively, and then SH concludes
withoa feasible
n
f
f
b
trajectory vector p = [pn ] n∈N ∈ P. Note that SH only uses four control variables ā , a , ā , ab that are
yet able to control the overall smoothness of all trajectories (so as to achieve certain desired objectives).
Further, the constructed trajectories are composed of only a few quadratic (or linear) segments that are all
analytically solvable. Therefore, the proposed SH algorithm is parsimonious and simple to implement.
To formally state SH, we first define the following terminologies in Definitions 2-4 with respect to a single
trajectory, as illustrated in Figure 4(a).
8

Time

n

pn

ab

pb

1

pnf

ā b

(a)

af

af

ā f

ā f

ā f
−
(t−
n , vn )

s

Space

n

pn−

1

pf

τ

s

Space

pnf

pn−

1

pn−

τ

s

Space

τ

−
(t−
n , vn )

Time

(b)

−
(t−
n , vn )

Time

(c)

Figure 3: Components in the proposed shooting heuristic: (a) forward shooting process without activating
safety constraint (4); (b) forward shooting process with activating safety constraint (4); and (c) backward
shooting process. .
Definition 2. We define a state point by a three-element tuple (l, v, t′ ) , which represents that at time t′ ,
the vehicle is at location l and operates at speed v. A feasible state point (l, v, t′ ) should satisfy v ∈ [0, v̄].
Definition 3. We use a four-element tuple (l, v, a, t′ ) to denote the quadratic function that passes location
l at time t′ with velocity v and acceleration a; i.e., 0.5a(t − t′ )2 + v(t − t′ ) + l with respect to time variable
t ∈ (−∞, ∞). Note that this quadratic function definition also includes a linear function (i.e., a = 0). For
simplicity, we can use a boldface letter to denote a quadratic function, e.g., f := (l, v, a, t′ ) and f (t) :=
0.5a(t − t′ )2 + v(t − t′ ) + l.
Definition 4. We use a five-element tuple s := (l, v, a, t′ , t′′ ) to denote a segment of quadratic function
f = (l, v, a, t′ ) between time min {t′ , t′′ } and max {t′ , t′′ }. We call this tuple a quadratic segment. Define
s(t) := f (t), ∀t ∈ [min {t′ , t′′ } , max {t′ , t′′ }]. If the speed and the acceleration on every point along this
segment satisfy constraint (1), we call it a feasible quadratic segment.
Remark 3. In Definitions 2-4, if one or more elements in a tuple are unknown or variable, we use “·” to hold
their places (e.g., (l, ·, t′ ), (l, v, ·, t′ , ·) ).
Definition 5. For a trajectory p ∈ T̄ composed by a vector of consecutive quadratic segments sk :=
[(lk , vk , ak , tk , tk+1 )]k=1,2,··· ,k̄ with −∞ = t1 < t2 < · · · < tk̄+1 = ∞, we denote p = [sk ]k=1,2,··· ,k̄ . Without
loss of generality, we assume that any trajectory in this study can be decomposed into a vector of quadratic
segments.
During the forward shooting process, we need to check safety constraints (4) at every move for any
vehicle n ≥ 2. As illustrated in Figure 4(b), we basically create a shadow (or safety bound) of the preceding
trajectory pn−1 by shifting pn−1 downwards by s and rightwards by τ . Then safety constraint (4) is simply
equivalent to that pn does not exceed this shadow trajectory at any time. The following definition specifies
the shadow trajectory and its elemental segments.
Definition 6. For a trajectory pn (t), ∀t ∈ (−∞, ∞), we define its shadow trajectory psn as psn (t) := pn (t−τ )−
+
s
s, ∀t ∈ (−∞, ∞). It is obvious that t− (psn ) = t−
n + τ and t (pn ) = ∞. Note that if the following trajectory
−
s
pn+1 (t) initiated at time tn+1 satisfies pn+1 (t) ≤ pn , ∀t ∈ (−∞, ∞), then pn and pn+1 satisfies safety
constraint (4). Further, a shadow segment of s := (l, v, a, t′ , t′′ ) is simply ss := (l−s, v, a, t′ +τ, t′′ +τ ). We also
m
generalize this definition to the mth -order shadow trajectory of pn as psn (t) := pn (t−mτ )−sm, ∀t ∈ (−∞, ∞)
m
and mth -order shadow segment ss := (l − ms, v, a, t′ + mτ, t′′ + mτ ), which are essentially the results of
repeating the shadow operation by m times.
9

t )′
a,

pn

(l,

v,

s
pn
′

)
′ ,t
,t

v,
(l,
τ

′′

v
(l,

,a

t
a,

′′

,t

)
′′

s
(l −

(l, v, t′ )

s,

(a)

v, a

′ +
,t

τ, t

+

s1 =

τ)

a 1,
v 1,
(l 1,

′′ )
t′ 1, t 1

D(s1 − s2 )

)
′
, t 2, t 2
′′

s2 =

, a2
( l 2, v 2

(b)

(c)

Figure 4: Illustrations of definitions (x-axis for time elapsing rightwards and y-axis for location increasing
upwards): (a) state point, quadratic function and segment; (b) shadow trajectory and shadow segment; and
(c) segment distance. .
The following definitions specify an analytical function that checks the distance between two segments
(e.g., the current segment to be constructed and a reference shadow segment in forward shooting), as illustrated in Figure 4(c).
Definition 7. Given two segments s1 := (l1 , v1 , a1 , t′1 , t′′1 ), s2 := (l2 , v2 , a2 , t′2 , t′′2 ), define segment distance
from s1 to s2 as
(
mint∈[t− ,t+ ] s1 (t) − s2 (t), if t− ≤ t+ ;
D (s1 − s2 ) :=
∞,
otherwise,
where t− := max {min{t′1 , t′′1 }, min{t′2 , t′′2 }} and t+ := min {max{t′1 , t′′1 }, max{t′2 , t′′2 }}. If t− ≤ t+ , D (s1 − s2 )
can be solved analytically as

D (s1 − s2 ) :=

(

s1 (t∗ (s1 − s2 )) − s2 (t∗ (s1 − s2 )) , if a1 − a2 > 0 and t∗ (s1 − s2 ) ∈ (t− , t+ )
min {s1 (t− ) − s2 (t− ) , s1 (t+ ) − s2 (t+ )} ,
otherwise.

where
t∗ (s1 − s2 ) :=

v1 − a1 t′1 − v2 + a2 t′2
.
a2 − a1

(7)

We also extend the distance definition to trajectory sections and trajectories below. Given two trajectory
sections p(t− : t+ ) and p′ (t′− : t′+ ), the distance from p(t− : t+ ) to p′ (t′− : t′+ ) is defined as
D(p(t− : t+ ) − p′ (t′− : t′+ )) :=

min

t∈[max(t− ,t′− ),min(t+ ,t′+ )]

p(t) − p′ (t)

if max(t− , t′− ) ≤ min(t+ , t′+ ) or D(p(t− : t+ ) − p′ (t′− : t′+ )) := ∞. Suppose these two sections can be
partitioned into quadratic segments, i.e., p(t− : t+ ) = [sk ]k=1,2,··· ,k̄ and p′ (t′− : t′+ ) = [s′k′ ]k′ =1,2,··· ,k̄′ , then

D p(t− : t+ ) − p′ (t′− : t′+ ) =

min

k=1,··· ,k̄,k′ =1,··· ,k̄′ ,

D(sk − s′k′ ).

Note that function D(·) has a transitive relationship; i.e., D(A − B) ≥ DAB and D(B − C) ≥ DBC indicates
D(A − C) ≥ DAB + DBC .

10

Definition 8. Next, we define an analytical operation that determines how we take a move in the forward
shooting process, as illustrated in Figure 5(a). Given a quadratic segment s′ := (l′ , v ′ , a′ , t′− , t′+ ) with
t′− < t′+ , a feasible state point (l, v, t− ) with t− < t′+ , acceleration rate a+ ≥ 0 and deceleration rate
a− < 0 (and a− ≤ a′ ), we want to construct a forward shooting segment s := (l, v, a+ , t− , tm ) followed by a
forward merging segment sm := (lm , v m , a− , tm , t+ ) where v m := v + a+ (tm − t− ), lm := p + v(tm − t− ) +
0.5a+ (tm − t− )2 with t+ ≥ tm ≥ t− in the following way. We basically select t− and tm values to make s
and sm satisfy the following conditions. First, we want to keep s′ above s and the segment extended from
sm to time ∞, i.e.,


D [s′ − s] ≥ 0, and D s′ − pm , v m , a− , tm , ∞ ≥ 0.
(8)
m
+
m
−
Further, the exact values of t and t shall be determined in the following three cases: (I) if no t ∈ [t , ∞)

can be found to satisfy constraint (8), this shooting operation is infeasible and return tm = t+ = −∞; (II)
otherwise, we try to find t+ ∈ [max {t′− , t− } , t′+ ] and tm ∈ [t− , t+ ] such that s′ and sm get tangent at time
t+ ; and (III) if this trial fails, set tm = t+ = ∞. Fortunately, since these segments are all simple quadratic
segments, tm and t+ can be solved analytically in the following forward shooting operation (FSO) algorithm,
where the final solutions to tm and t+ are denoted by tmf (s′ , (l, v, t− , a+ ) , a− ) and t+f (s′ , (l, v, t− , a+ ) , a− ),
respectively.
FSO-1: If D (s′ − s̄) < 0 where s̄ := (l, v, a− , t− , ∞), there is no feasible solution, and we just set tm =
t+ = −∞ (Case I). Go to Step FSO-3.
FSO-2: Shift the origin to time t− and denote t̂′− := t′− − t− , t̂′+ := t′+ − t− , t̂m := tm − t− , t̂+ :=
m m − m
t+ − t− and t̂− := max{t̂′− , 0}. Then get
 a quadratic function q by subtracting (l , v , a , t ) from
(l′ , v ′ , a′ , t′− ), i.e., q := l̂, v̂, a′ − a− , 0 where
l̂ := 0.5a′ t̂′−

and

2

+ 0.5 a+ − a−

 m 2
t̂
− a′ t̂′− + l′ − l,


v̂ = v ′ − v − a′ t̂′− − a+ − a− t̂m .

−
FSO-2-1: If a′ = a− , test whether we can make q(t)
whether lˆ = 0 with t̂m =
 − =′+0, ∀t ∈ [t̂ , ∞), i.e.,
′
′ ′−
+
−
m
m
v − v − a t̂
/ (a − a ). If yes and t̂ ∈ t̂ , t̂
(Case II), set t = t− + t̂m and t+ = t′+ .
Otherwise (Case III), set t+ = tm = ∞. Go to Step FSO-3.
2
′
FSO-2-2: If a > a− ,then q is a convex quadratic function, and we need to solve α t̂m + β t̂m + γ = 0

2
+
where
− a− ) (a+ − a′ ), β := −2 (a+ − a− ) v ′ − v − a′ t̂′− and γ := v ′ − v − a′ t̂′− − (a′ −
 α := (a
2
a− ) a′ t̂′− − 2v ′ t̂′− + 2l′ − 2l . In case of α = β = 0 (Case III), set t+ = tm = ∞, and go to
Step FSO-3. Otherwise, we need to try candidate solutions to t̂m and t̂+ , denoted by t̂mc and t̂+c ,
respectively. In case of α = 0 but β 6= 0, solve t̂mc = −γ/β and

t̂+c =

v ′ − v − a′ t̂′− − (a+ − a− ) t̂mc
.
a− − a′

Otherwise, we should have α 6= 0, and then solve both candidate solutions
p
−β ± β 2 − 4αγ
mc
t̂
=
2α

(9)

(10)

and the corresponding t̂+c with equation(9). If the candidate solutions are not real numbers, then
we just set t̂+c = t̂mc = ∞. Otherwise, try both sets of solutions and select the set satisfying
t̂+c ≥ t̂mc ≥ 0. For either of these two cases, if t̂+c ∈ t̂− , t̂′+ (Case II) , we set tm = t− + t̂mc and
t̂+ = t̂+c . Otherwise, set t+ = tm = ∞ (Case III). Go to Step FSO-3.
11

′+

a,

t

,t

)

t′+

t+

,
,v
′

′

(p

(l ′
,v ′
,a ′
, t ′−
, t ′+
)

(p m
,v m
,a −
,t m
,t +
)

′

′−

tm

+

(p

,v

,a +
,t −
,t m
)

tm

t′−

m ,t
− ,t
+
t
m ,a
ml , v
(

(l,

t−

v

t−
+,
,a

m)
,t

)

−

t

(a)

(b)

Figure 5: Illustrations of shooting operations: (a) a forward shooting operation, and (b) a backward shooting
operation. .
FSO-3: Finally, we return tmf (s′ , (l, v, t− , a+ ) , a− ) = tm and t+f (s′ , (l, v, t− , a+ ) , a− ) = t+ .
Definition 9. We extend one forward shooting operation to the following
 forward shooting process
 (FSP)
that generates a whole trajectory. Given a shadow trajectory ps := ssh := lhs , vhs , ash , tsh , tsh+1 h=1,··· ,h̄ .
(with ts1 = −∞ and tsh̄+1 = ∞) and a feasible entry state point (l, v, t− ), we basically want to construct a
forward shooting trajectory pf ((l, v, t− ), ps ) that starts from (l, v, t− ) and maintains acceleration āf or speed
v̄ until being bounded by ps . We consider a template trajectory starting at (l, v, t− ) and composed by these
a
two candidate
āf , t− , ta := t−+ (v̄ − v)/āf ) (which accelerates from v to v̄ given v < v̄)
 segments s := (l, v,
 f
∞
a
2
2
and s := l := l + 0.5 v̄ − v /ā , v̄, 0, ta, ∞ (which maintains maximum speed v̄ all the way), i.e.,
pt :=

(

[sa , s∞ ] , if v < v̄;
[s∞ ] ,
if v = v̄.

Then
pf ((l, v, t− ), ps ), if bounded
by ps , shall first follow pt and then merge into ps with a merging segment


pt (tm ), ṗt (tm ), af , tm , t+ . This can be solved analytically with the following FSP algorithm.

FSP-1: Initiate h = 1, t+ = tm = ∞, pf = ∅ and iterate through the segments in ps as follows.


FSP-2: If v < v̄, apply the FSO algorithm to solve candidate time points tmc := tmf ssh , (l, v, āf , t− ), af


and t+c := t+f ssh , (l, v, āf , t− ), af . If tmc > ta , revise tmc := (tmf ssh , (la , v̄, 0, ta ), af ) and t+c :=
t+f (ssh , (la , v̄, 0, ta ), af ). If v = v̄, solve tmc := tmf (ssh , (l, v̄, 0, t− ), af ) and t+c := (t+f ssh , (l, v̄, 0, t− ), af ).
If tmc = −∞, the algorithm cannot find a feasible solution and return pf ((l, v, t− ), ps ) = ∅, tmf ((l, v, t− ), ps ) =
−∞ and t+f ((p, v, t− ), ps ) = −∞. If t+c ∈ [tsh , tsh+1 ], set tm = tmc and t+ = t+c , and go to the Step
FSP-3. Otherwise, t+c shall be ∞. Then if h < h̄, set h = h + 1 and repeat this step.
FSP-3: If v < v̄ and ta > t− , append segment (l, v, āf , t− , min(tm , ta )) to pf (appending means adding this
segment as the last element of pf ). If tm > ta , append (la , v̄, 0, ta , tm ) to pf . If t+ < tsh̄+1 , which
indicates t+ ∈ [tsh , tsh+1 ], we first append segment (lhs + vhs (t+ − tsh ) + 0.5ash (t+ − tsh )2 , vhs + ash (t+ −
ts ), as , t+ , ts ) to pf , and then append all segments [ss ′ ] ′
to pf .
h

h

h h =h+1,··· ,h̄

h+1

12

FSP-4: Finally, return pf ((l, v, t− ), ps ) = pf , tmf ((l, v, t− ), ps ) = tm and t+f ((p, v, t− ), ps ) = t+ .
Definition 10. This definition further specifies how we take a symmetric move in the backward shooting, as
illustrated in Figure 5(b). Given a quadratic segment s′ := (l′ , v ′ , a′ , t′− , t′+ ) with t′− < t′+ (e.g., a segment
generated from the forward shooting process), a feasible state point (l, v, t− ) with t− > t′− , acceleration
rate a+ ≥ 0 and deceleration rate a− < 0 (and a− ≤ a′ ), we construct a backward shooting segment
s := (l, v, a+ , t− , tm ) preceded by a backward merging segment sm := (lm , v m , a− , tm , t+ ) where again
v m := v+a+ (tm −t− ), lm := l+v(tm −t− )+0.5a+(tm −t− )2 , and t+ ≤ tm ≤ t− , such that again condition (8)
is satisfied (and thus s′ is above s and sm ). And again there are three cases in determining t− and tm values:
(I) if no tm ∈ (−∞, t− ] can be found to satisfy constraint (8), this shooting operation is infeasible and return
tm = t+ = ∞; (II ) otherwise we try to find t+ ∈ [t′+ , min {t− , t′− }] and tm ∈ [t+ , t− ] such that s′ and sm get
tangent at time t+ (as Figure 5(b) indicates); and (III) if no such t+ is found, set tm = t+ = −∞. Solutions
tm and t− are denoted as functions tmb (s′ , (l, v, t− ) , a+ , a− ) and t-b (s′ , (l, v, t− ) , a+ , a− ), respectively, and
they can be solved analytically in the following backward shooting operation (BSO) algorithm.
BSO-1: If D[s′ − (l, v, a− , t− , −∞)] < 0, there is no feasible solution, and we just return tm = t+ = −∞
(Case I). Go to Step BSO-3.
BSO-2: Again shift the origin point to t− and denote t̂′− := t′− − t− , t̂′+ := t′+ − t− , t̂m := tm − t− ,
t̂+ := t+ − t− and t̂− := min{t̂′+ , 0}. And obtain q by subtracting (lm , v m , a− , tm ) from (l′ , v ′ , a′ , t′− ),
which is formulated the same as that in Step FSO-2.



′
BSO-2-1: If a = a− , test whether ˆ
l = 0 with t̂m = v ′ − v − a′ t̂′− / (a+ − a− ). If yes and t̂m ∈ t̂− , t̂′−
(Case II),

set tm = t− + t̂m and t+ = t′− ; Otherwise, return t̂m = t̂+ = −∞ (Case III). Go to BSO-3.
2
′
BSO-2-2: If a > a− , we need to again solve α t̂m + β t̂m + γ = 0 formulated in Step FSO-2-2. In case of
α = β = 0 (Case III), set t+ = tm = −∞, and go to Step FSO-3. Otherwise, we again try candidate
solutions t̂mc and t̂+c . In case of α = 0 but β 6= 0, solve t̂mc = −γ/β and t̂+c with equation (9). In
case of α 6= 0, then we solve two sets of solutions t̂mc and t̂+c with equations (10) and (9) respectively.
if the candidate solutions are not real numbers, then we just set t̂+c = t̂mc = ∞. Otherwise, try
 both
sets of solutions and select the set satisfying t̂+c ≤ t̂mc ≤ 0. With this, if we obtain t̂+c ∈ t̂− , t̂′−
(Case II), we set tm = t− + t̂mc and t̂+ = t̂+c . Otherwise, set t+ = tm = ∞. Go to Step BSO-3.
BSO-3: Finally, we return tmb (s′ , (l, v, t− , a+ ) , a− ) = tm and t+b (s′ , (l, v, t− , a+ ) , a− ) = t+ .
Definition 11. Symmetric to Definition 9, we extend one backward move BSO to the following backward
shooting process (BSP). We consider a backward shooting template trajectory starting at a feasible entry
state point (l, v, t− ) composed by one or both of s−a := (l, v, āf , t− , t−a := t− − v/āb ) (which decelerates
backward from v to 0 given v > 0) and s−∞ := l-a := l − 0.5v 2 /āb , 0, 0, t-a , −∞ (which denotes the

vehicle is stopped prior to time t-a ), i.e.,

pt :=

(

[s−∞ , s-a ] , if v > 0;
[s−∞ ] ,
if v = 0.

Further, we are given the original trajectory (e.g., those generated from FSP)
pf := {sh := {lh , vh , ah , th , th+1 }} h=1,··· ,h̄ .
We will find
section pb ((l, v, t− ), p) that is to merge into pf with a merging
 a backward shooting trajectory

segment pt (tm ), ṗ(tm ), ab , tm , t+ and does not exceed (i.e., going left of) pf at any time. This can be
solved analytically with the following BSP algorithm.
13

BSP-1: Initiate h being the largest segment index of pf such that th < t− , set t+ = tm = −∞, pb = ∅ and
iterate through the segments in pf .




BSP-2: If v > 0, apply BSO to solve tmc := tmb sh , (l, v, āb , t− ), ab and t+c := tmf sh , (l, v, āb , t− ), ab .




If tmc < t−a , revise tmc := tmb sh , (l-a , 0, 0, t-a ), ab and t+c := t+b sh , (l-a , 0, 0, t-a ), ab with




BSO. If v = 0, directly solve tmc := tmb sh , (l, 0, 0, t− ), ab and t+c := t+b sh , (l, 0, 0, t−), ab
with BSO. If tmc = ∞, the algorithm cannot find a feasible solution
 (because any
 trajectory through
−
f
b
−
eb
−
f
(l, v, t ) will go above p ) and thus returns p ((l, v, t ), p) = p
(l, v, t ), p = ∅. If t+c = −∞
f
and h = 1, the algorithm
 a feasible backward trajectory that can touch p and thus return
 cannot find
+c
s
s
m
mc
+
−
f
b
−
eb
∈ [th , th+1 ], set t = t
and t = t+c and go to
(l, v, t ), p = ∅. If t
p ((l, v, t ), p) = p
Step BSP-3. Otherwise, if h > 1, set h = h − 1 and repeat this step.


BSP-3: If v > 0 and t-a < t− , insert segment l−ma , v −ma , āb , t−ma , t− to pb (inserting means adding
this segment before the head of pb ), where t−ma := max(tm , t-a ), v −ma := v − āb (t− − t−ma ) and
l−ma := l − v(t− − t−ma ) + 0.5āb (t− − t−ma )2 . If tm < t−a , insert (l-a , 0, 0, tm , t-a ) to pb . Then we
insert merging segment (lm , v m āb , t+ , tm ) to pb where lm := lh + vh (t+ − tsh ) + 0.5ah (t+ − tsh )2 , and
v m := v + a (t+ − t ).
h

h

h



BSP-4: Now we have obtained a backward shooting trajectory section pb (l, v, t− ), pf = pb (tm : t− ) (or pb


for simplicity). We further extend pb (tm : t− ) by inserting pf (t1 : tm ) and appending pf (l, v, t− ) , pf


generated from an auxiliary FSP, and construct the extended backward shooting trajectory peb (l, v, t− ), pf




i

h
:= pf (t1 : tm ), pb (tm : t− ) , pf (l, v, t− ) , pf . Return pb (l, v, t− ), pf and peb (l, v, t− ), pf .


Now we are ready to present the proposed shooting algorithm that yields a trajectory vector P āf , af , āb , āb
as a functional of these four acceleration rates.
SH-1: Initialize control variables āf , af , āb and ab . Set n = 1, trajectory vector P = ∅.


s
SH-2: Apply the FSP to obtain pfn = snk = lnk , vnk , ank , tnk , tn(k+1) k=1,··· ,k̄n = pf ((0, vn− , t−
n ), pn−1 )
s
(define p0 := ∅). We call this process the primary FSP (to differentiate from the auxiliary FSP in the
BSP). If pfn = ∅, whichmeans that this algorithm cannot find a feasible solution for trajectory platoon
P , set P āf , af , āb , āb := P = ∅ and return.


SH-3: This steps checks the need for the BSP. Find the segment index knL such that L ∈ lnkL , ln(kL +1)
and solve the time tL
n when vehicle n passes location L as follows
q

2
 −vnkL + vnk
L +2ankL (L−lnkL )
, if ankL 6= 0;
L
ankL
tn := tnkL +
 L−lnkL ,
if ankL = 0.
v L
nk


L
f
If tL
n = G tn , which means that pn does not violate the exit boundary constraint (3) (or does not
run into the red light), we set pn = pfn and go to SH4. Otherwise, pfn violates constraint (3) and we
need to apply BSP to revise it in the following
step. Set vnL := vnkL + ankL tL
n − tnkL , apply the


b
b
L
L
f
b
BSP to solve p = p
L, v , G t
, p . If the start location of obtain p is no less than 0, set
n

n

n

n

n

14


 f 
f
, pn . Otherwise, pb
pn = peb L, vnL , G tL
n can not meet pn on this highway section, and return
n


P āf , af , āb , āb := ∅ .



SH-4: Append pn to P . Return P SH af , āf , ab , āb := P if n = N , or otherwise set n = n + 1 and go to
SH-2.

Although FSO (Definition 8) and BSO (Definition 10) do not explicitly impose speed limits to the generated
trajectory segments, as long as a non-empty trajectory vector P is returned by the SH algorithm, P shall
satisfy all constraints defined in Section 2 (or P ∈ P), as proven in the following proposition.


Proposition 1. If the SH algorithm successfully generates a vector of trajectories P af , āf , ab , āb with
af , ab ∈ [a, 0) and āf , āb ∈ (0, ā], they shall fall in the feasible trajectory vector set P defined in (5).
Proof. Since the acceleration of each segment generated from the SH algorithm is either explicitly specified
within [a, ā] (i.e., one of af , āf , ab , āb and 0) or just following a shadow trajectory’s acceleration that shall
fall in [a, ā] as well. So the constraint with respect to acceleration in (1) is satisfied.
Then, we will use mathematical induction to exam the remaining constraints in (1)-(4). First for vehicle
1, FSP can generate p1 with at maximum 2 segments, which apparently falls in T1− (and thus both constraints
(1)-(2). are satisfied). If BSP is not needed, exit constraint (3) is automatically satisfied and thus p1 ∈ T1 .
Otherwise, the new segments generated from BSP below L start from a speed no greater than v̄ and decelerate
backwards to a value no less than 0 and then increase the speed and merge into the forward shooting trajectory
at a speed no greater than v̄. During this process, the speed shall always stay within [0, v̄] and therefore
constraint (1) remains valid. The auxiliary FSP is similar to the primary FSP and thus will not violate
constraint (1) as well. Further, the BSP step SH3 does not affect the entry boundary condition (2) and
makes exit condition (3) feasible in addition. Therefore we obtain p1 ∈ T1 .
Then we assume that pn−1 ∈ Tn−1 , ∀n = 2, · · · , N , and we will prove that pn ∈ Tn (pn−1 ). If pn is not
blocked by pn−1 during the FSP, then the construction of pn is similar to that of p1 and thus pn should
automatically satisfy constraints (1)-(3) and thus pn ∈ Tn . Further, pn shall be always below psn−1 and
therefore pn shall satisfy safety constraint (4), i.e., pn ∈ Tn (pn−1 ). Otherwise, if pn is blocked by pn−1 , the
construction of pn would generate some more segments that merge the forward trajectory into psn−1 (e.g., as
Figure 5(a) illustrates) and then follow psn−1 , as compared with the construction of p1 . Due to the induction
assumption, the segments following psn−1 shall satisfy kinematic constraint (1) the same as the corresponding
segments in pn−1 . For the merging segment, since it starts from a forward shooting segment and ends at a
shadow segment and therefore its speed range should be bounded by [0, v̄]. Therefore, we obtain pn ∈ T .
Again, the primary FSP ensures that pn satisfies the entry boundary (2) and BSP ensures that pn satisfy
exit constraint (3). This yields pn ∈ Tn . Further we see that any segment generated from FSP shall be either
below or on psn−1 . If the BSP generates new segments, they shall be
 to the forward shooting
 strictly right
f
b
f
b
trajectory. Therefore, p shall fall in T (p
). This proves that P a , ā , a , ā ∈ P.
n

3.2

n

n−1

Shooting Heuristic for the Lead Vehicle Problem

The above proposed SH algorithm can be easily adapted to solve LVP (6). The only modifications are to
fix p1 and to set G = [−∞, ∞] (and therefore no BSP is needed). We denote this adapted SH for LVP by
SHL. More importantly, we further find that SHL can be alliteratively implemented in a parallel manner.
Each trajectory can be calculated directly from the input parameters without its preceding trajectory’s
information. We denote this parallel alternative of SHL with PSHL. Apparently, PSHL allows further
improved computational efficiency with parallel computing. This section describes PSHL and validates that
PSHL indeed solves LVP. We first introduce an extended forward shooting operation (EFSO) that merges
two feasible trajectories.

15

EFSO-1: Given two feasible trajectories p := [sj := (lj , vj , aj , tj , tj+1 )]j=1,2,··· ,J and p′ = s′k := [(lk′ , vk′ , a′k ,

t′k , t′k+1 k=1,2,··· ,K ∈ T , and deceleration rate a− < 0. Set iterators j = 1 and k = 1 .

mf (s′ , (l , v , t , a ) , a− ) and t+ = t+f (s′ , (l , v , t , a ) , a− ). If tm = −∞, return
EFSO-2: Solve tm
j j j
j
j j j
j
k
k
jk
jk := t
jk
m
m ′
−
m
tm (p′ , p, a− ) = t+ (p′ , p, a− ) = −∞. If tm
jk < ∞ and tjk ∈ [tj , tj+1 ], return t (p , p, a ) = tjk ,
+
+
′
−
t (p , p, a ) = tjk . If k < K, set k = k + 1 and repeat this step; otherwise, go to the next step.

EFSO-2: If j < J, set j = j + 1 and k = 1 and go to Step EFSO-2. Otherwise, return tm (p′ , p, a− ) =
t+ (p′ , p, a− ) = ∞.
Based on EFSO, we devise the following extended forward shooting process (EFSP) that generates a forward
shooting trajectory constrained by a series of upper bound trajectories.
EFSP-1: Given a feasible state point (l, v, t), and a set of trajectories {pm ∈ T }m=1,··· ,M . Initiate m = 1
and p = pf ((l, v, t), ∅) with FSP.




EFSP-2: Call EFSO to solve tm := tm pm , p, af and t+ := t+ pm , p, af . If tm = −∞, return


h


pf (l, v, t), {pm }m=1,··· ,M = ∅. If tm < ∞, revise p := p (t− (p) : tm ) , p (tm ) , ṗ (tm ) , af , tm , t+ ,
pm (t+ : ∞)].



EFSP-3: If m < M , set m = m + 1 and go to PSFP-2; otherwise return pf (l, v, t), {pm }m=1,··· ,M = p.
Then we are ready to present the PSHL algorithm as follows.

PSHL-1: Given lead trajectory p1 ∈ T and boundary condition [vn− , t−
n ]n∈N \{1} . Initialize acceleration
f
f
− −
f
parameters ā and a . Set p̄ := p , p̄ := p ((0, v , t ), ∅) , ∀n ∈ N \{1}. Set initial trajectory platoon
1

1

n

n

n

P = [p1 ],n = 2.

n n−m o
f
s
PSHL-2: Solve pn := p (0, vn− , t−
n ) , p̄m

m=1,··· ,n−1



with EFSP.





PSHL-3: If pn = ∅, return P PSH af , āf := ∅. Otherwise, append pn to P . If n = N , return P PSH af , āf :=
P ; otherwise, set n = n + 1 and go to PSHL-2.




Proposition 2. P PSH af , āf obtained from PSHL is identical to P SH af , āf , ab , āb when p1 ∈ T is
fixed and G = (−∞, ∞).


Proof. We first consider the cases that P PSH af , āf 6= ∅. We will prove this proposition via induc

tion with the iterator being vehicle index n. Let [p1, p2 , · · · , pN ] denote the trajectories in P PSH af , āf




and p′1, p′2 , · · · , p′N denote the trajectories in P SH af , āf , ab , āb . Apparently, when n = 1,p′1 = p1

′
since the lead vehicle’s htrajectory is fixed.
on the defi
 Assume that when n = k, pk ′ = pk . Based

−
s
+
f
m
+
m
m
m
′
, p̄k+1 (t ) , p̄˙ k+1 (t ) , a , t , t , pk (t : ∞) where p̄k+1 :=
inition of SH, pk+1 = p̄k+1 tk+1 : t





′
−
s (t) := p′ (t − τ ) − s, tm := tm p′ s , p̄
f , t+ := t+ p′ s , p̄
f . Based on the
pf (0, vk+1
, t−
),
∅
,
p
,
a
,
a
k+1
k+1
k
k
k
k
k+1
n k+1−m o
′
s
s
as
induction assumption, pk = pk can be obtained by repeatedly calling EFSO to merge p̄sm
m=1,··· ,k
n k+1−m o
and thus p′k+1 = pk+1 .
in PSHL-2. Therefore, p′k+1 is obtained by merging p̄sm
m=1,··· ,k+1


When P PSH af , āf = ∅, from the above discussion that shows the equivalence of generating pk and p′k ,


it is obvious that P SH af , āf = ∅ as well. This completes the proof.

16

−

2

(l

+

v
2 −
v̄ 2ā

, v̄

,t

+

v
v̄− ā

+

)

+

+

+

+

l

p̄

(l −

v2
−
2ā , 0, t

− āv )

v̄
v− a

2

v̄
2 −
v 2a

(l

,
, v̄

t−

(l −

v2
−
2a , 0, t

− av )
t−
−,
v
−,
(l

)

−

,v

)

t̄+

t̄m

−)

,t
(l, v

+ t
v − t−
v
l−

(l

,t

t+
+

)

+ t
v −
l − v− t
pl
+

tm

−

(a)

(b)

Figure 6: Illustrations of the generalized time geography theory in : (a) quadratic cone; and (b) quadratic
prism.


Corollary 1. Given lead trajectory p1 ∈ T , PSHL yields P PSH af , āf ∈ P LVP (p1 ) if af , āf ∈ [a, ā].

4

Theoretical Property Analysis

This section analyze theoretical properties of the proposed SH algorithms, including their solution feasibility
and relationship with the classic traffic flow theory. It is actually quite challenging to analyze such properties
because the original problem defined in Section 2 involves infinite-dimensional trajectory variables and highly
nonlinear constraints. Fortunately, the concept of time geography (Miller, 2005) is found related to the
bounds to feasible trajectory ranges. We generalize this concept to enable the following theoretical analysis.

4.1

Quadratic Time Geography

We first generalize the time geography theory considering acceleration range [ā, a] in additional to speed range
[0, v̄]. These generalized theory, which we call the quadratic time geography (QTG) theory, are illustrated in
Figure 6 and discussed in detail in this subsection.
Definition 12. We call the set of feasible trajectories (i.e., in T ) passing a common feasible state point
(l, v, t− ) the quadratic cone of (l, v, t− ), denoted by Clvt− , illustrated as the shaded area in Figure 6(a) and
formulated below:

Clvt− = p p ∈ T , p(t− ) = l, ṗ(t− ) = v, ∀t ∈ (−∞, ∞) ,

where the upper bound trajectory p̄lvt− of (l, v, t− ), illustrated as the top boundary of the shade in Figure
6(a), is formulated as


v2

if t ∈ −∞, t− − vā ;
l − 2ā ,


;
p̄lvt− (t) := l + v(t − t− ) + 0.5ā(t − t− )2 , if t ∈ t− − vā , t− + v̄−v
ā

 − v̄−v


(v̄−v)2
−
l + v̄(t − t ) − 2ā ,
if t ∈ t + ā , ∞ ,
17

and the lower bound trajectory plvt− of (l, v, t− ), illustrated as the bottom boundary of the shade in Figure
6(a), is formulated as

i

(v̄−v)2
v−v̄
−
−

;
,
if
t
∈
−∞,
t
−
l
+
v̄(t
−
t
)
−

2a
a


i
h
plvt− (t) = l + v(t − t− ) + 0.5a(t − t− )2 , if t ∈ t− − v−v̄
;
, t− + −v
a
a

h



−v 2
−v
−

l + 2a ,
if t ∈ t + a , ∞ .
2

2

v
v
, 0, 0, t− − āv , −∞), (l− 2ā
, 0, ā, t− − āv , t− + v̄−v
In other words, p̄lvt− is composed of quadratic segments (l− 2ā
ā )
2
2
2
2
v̄ −v
v̄−v
v −v̄
v−v̄
−
−
and (l+ 2ā , v̄, 0, t + ā , ∞), and p̄lvt− is comprised of quadratic segments (l− 2a , v̄, 0, t − a , −∞),
2
2
2
(l − v −v̄ , v̄, ā, t− − v−v̄ , t− + −v ) and (l + −v , 0, 0, t− + −v , ∞). Note that p̄ − = pf ((l, v, t− ) , ∅) from
2a

a

a

2a

a

lvt

the FSP with āf = ā and af = a, p̄lvt− (t− ) = plvt− (t− ) = l, and p̄lvt− (t) ≥ plvt− (t), ∀t 6= t− . Further, Clvt−
is always non-empty as long as (l, v, t− ) is feasible.
Definition 13. We call the set of trajectories in T passing two feasible state points (l− , v − , t− ) and
+ + +
(l+ , v + , t+ ) with t− < t+ , l− ≤ l+ a quadratic prism, denoted by Pll− vv− tt− , as illustrated in Figure 6(b)
and formulated below:

+ + +
− − − \
+ + +
Pll− vv− tt− := p ∈ T p(t− ) = l− , ṗ(t− ) = v − , p(t+ ) = l+ , ṗ(t+ ) = v + = C p v t
Cp v t .
+ + +

+ + +

The upper bound of this Pll− vv− tt− (as the top boundary of the shade in 6(b)), denoted by p̄ll−vv−tt− ,
should be composed by p̄l− v− t− (∞ : t̄m ), merging segment s̄m p̄l− v− t− (t̄m ) , p̄˙ l− v− t− (t̄m ) , ā, t̄m , t̄+ and
p̄l+ v+ t+ (t̄+ : ∞), where we can actually apply FSP with āf = ā and af = a to obtain connection points
t̄m := tmf ((l− , v − , t− ) , p̄l+ v+ t+ ) and t̄+ := t+f ((l− , v − , t− ) , p̄l+ v+ t+ ). The lower bound of this prism (as
+ + +
the bottom boundary of the shade in 6(b)), denoted by pll−vv−tt− , is composed by section pl− v− t− (∞ : tm ),


merging segment s̄m pl− v− t− (tm ), ṗl− v− t− (tm ), ā, tm , t+ and pl+ v+ t+ (t+ : ∞), where we can apply FSP
in a transformed coordinate system to solve tm and t+ . We shift the first shift the origin to (l+ , t+ )

and rotate the whole coordinate system by 180 degree. Then state points (l+ , v + , t+ ) and (l− , v − , t− )
transfer into (0, v + , 0) and (l+ − l− , v − , t+ − t− ), respectively, and pl− v− t− transfers into p̂l− v− t− de

m
fined as p̂l− v− t− (t) := l+ − pl− v− t− (2t+ − (t− + t)). Then we solve t̂ := tmf (0, v + , 0) , p̂l− v− t− and


+
m
t̂ := t+f (0, v + , 0) , p̂l− v− t− with FSP with af = −a and af = −ā. Then we obtain t+ = t+ − t̂ and
+
tm = t+ − t̂ .
+ + +

Note that the feasibility of Pll− vv− tt− depends on the values of (l− , v − , t− ) and (l+ , v + , t+ ), as discussed in
the following propositions.
+ + +

l v t
Proposition 3. Giventwo feasible state 
points (l− , v −, t− ) and (l+ , v + , t+
 ), quadratic cone Pl− v− t− is not
empty if and only if D p̄l+ v+ t+ − pl− v− t− ≥ 0 and D p̄l− v− t− − pl+ v+ t+ ≥ 0 .
+ + +

t
Proof. We first prove the necessity.
If 
there exists a feasible trajectory
p ∈ Pll− vv− t
− , then we know the


D (p̄l+ v+ t+ − p) ≥ 0 and D p − pl− v− t− ≥ 0, which indicates D p̄l+ v+ t+ − pl− v− t− ≥ 0. Symmetrically,




D (p̄l− v− t− − p) ≥ 0 and D p − pl+ v+ t+ ≥ 0 indicates D p̄l− v− t− − pl+ v+ t+ ≥ 0.




Then we investigate the sufficiency. Given D p̄l+ v+ t+ − pl− v− t− ≥ 0 and D p̄l− v− t− − pl+ v+ t+ ≥

0, we can first obtain that l− < l+ and t− < t+ . Further we know that there exists a point t̄∗ ∈
[t− , t+ ] such that p̄l+ v+ t+ (t) ≥ p̄l− v− t− (t), ∀t ∈ [−∞, t̄∗ ], p̄l+ v+ t+ (t̄∗ ) = p̄l− v− t− (t̄∗ ) and p̄l+ v+t+ (t) ≤
p̄l− v− t− (t), ∀t ∈ [t̄∗ , ∞]. Then we can obtain a trajectory pm ∈ Cl− v− t− composed by p̄lvt− t− : t̂m , sm :=
18




p̄lvt− t̂m , p̄˙ lvt− t̂m , a, t̂m , t̄m , p̄l+ v+ t+ (t̄m : ∞) satisfying t− ≤ t̂m ≤ t̄m < ∞ and D (p̄l+ v+ t+ − pm ) ≥
m
+
m
˙
0. Next, we will prove t̄m ≤ t+ by contradiction.If t̄m > t+ , then
 p̄l+ v+ t+ (t̄ ) > l and p̄l+ v+ t+ (t̄ ) >
v + . Since segment sm decelerates at a, then D pl+ v+ t+ − sm > 0, which however is contradictory to


D p̄l− v− t− − pl+ v+ t+ ≥ 0 because the start point of sm is on p̄l− v− t− . This proves that t− ≤ t̂m ≤ t̄m ≤ t+ .
+ + +
Therefore, pm ∈ C − − − ∩ C + + + = P l− v− t− . This completes the proof.
l v t

l v t

l v t

Proposition 4. Given any δ ≥ 0 and two feasible state points (l− , v − , t− ) and (l+ , v + , t+ ) with D(p̄l− ,v− ,t− −
 + ++

l+ v + (t+ +δ )
+ + +
pl+ ,v+ ,t+ ) ≥ 0, if quadratic prism Pl− v− t−
is not empty, then Pll− vv− tt− is not empty and D p̄ll−vv−tt− − p ≥
l+ v + (t+ +δ )
0, ∀p ∈ Pl− v− t−
.


l+ v + (t+ +δ )
Proof. If Pl− v− t−
is not empty, Proposition 3 indicates that D p̄l+ v+ (t+ +δ) − pl− v− t− ≥ 0. Further,

apparently D p̄l+ v+ t+ − p̄l+ v+ (t+ +δ) ≥ 0 and thus due to the transitive property of function D, we obtain




D p̄l+ v+ t+ − pl− v− t− ≥ 0, which combined with the given condition D p̄l− ,v− ,t− − pl+ ,v+ ,t+ ≥ 0 indicates
+ + +

3.
that Pll− vv− tt− is not empty based on Proposition 


l+ v + (t+ +δ )
l+ v + (t+ +δ )
Further, for any p ∈ Pl− v− t−
, we have D p̄l− v− t−
− p > 0. Since D p̄l+ v+ t+ − p̄l+ v+ (t+ +δ) ≥

0, we also have D (p̄l+ v+ t+ − p) ≥
 0 due to the transitive property of function D. This implies that p ∈
l+ v + t+
l+ v + t+
Pl− v− t− and thus D p̄l− v− t− − p ≥ 0. This completes the proof.

Remark 4. Note that as ā → ∞ and a → −∞, every smooth speed transition segment on the borders of a
quartic cone or prism reduces into a vertex, and the QTG concept converges to the classic time geography
(Miller, 2005). Besides, when the spatiotemporal range of the studied problem is far greater than that
where acceleration ā and deceleration a is discernible, neither is QTG much different from the classic time
geography.

4.2

Relationship Between QTG and SH

As preparing for the investigation to the feasibility and optimality of the SH solution, we now discuss
the relationships between trajectories generated from FSP and BSP and the borders of the corresponding
quadratic cone and prism. For uniformity,
only considers FSP and BSP with the extreme
h this subsection
i
acceleration control variable values, i.e., āf , af , āb , ab = [ā, a, ā, a].
Proposition 5. The forward shooting trajectory pf ((l, v, t− ) , ∅) generated from FSP overlaps p̄lvt− (t− : ∞).

Proposition 6. Given two feasible state points (l− , v − , t− ) and (l+ , v + , t+ ) with l+ > l− and t+ > t− such
+ + +
that quadratic prism Pll− vv− tt− 6= ∅, the extended backward shooting trajectory peb ((l+ , v + , t+ ), pf ((l− , v − , t− ), ∅))
+ + +
generated from BSP overlaps p̄ll−vv−tt− (t− : ∞).
These two propositions obviously hold based on the definitions of FSP and BSP and thus we omit the
proofs. These properties can be extended to cases where the current trajectory is bounded by one or multiple
preceding trajectories from the top.
Definition 14. Given a set of trajectories q = {q1 , q2 , · · · , qM ∈ T }, we define u(q, t) := minm∈{1,··· ,M} qm (t), ∀t
and we call function u(q, ·) a quasi-trajectory and denote it with u(q) for simplicity. Let U denote the set
of all quasi-trajectories. Note that distance function D can be easily extended to U, i.e., D (u − u′ ) :=
mint∈(∞,∞) (u(t) − u′ (t)) , ∀u, u′ ∈ U. We can also denote EFSP result pf ((l, v, t) , q) as pf ((l, v, t) , u(q)).
Further, let p(q) denote the trajectory generated by merging all trajectories in q with EFSO, and we can
also denote BSP result pb ((l, v, t) , p(q)) and peb ((l, v, t) , p(q)) as pb ((l, v, t) , u(q)) and peb ((l, v, t) , u(q)),
respectively, for simplicity.
19

u
Definition 15. Given a feasible state point (l, v, t− ) and a quasi-trajectory u ∈ U , we define Clvt
− :=
−
{p |p ∈ Clvt− , D (u − p) ≥ 0 }, which we call a bounded cone of (l, v, t ) with respect to u.

Definition 16. Given
state points (l−o
, v − , t− ), (l+ , v + , t+ ) and a quasi-trajectory u ∈ U, we
n two feasible
l+ v + t+ ,u
l+ v + t+
define Pl− v− t− := p p ∈ Pl− v− t− , D (u − p) ≥ 0 , which we call a bounded prism of (l− , v − , t− ) and

(l+ , v + , t+ ) with respect to u.

Apparently, bounded cones and prisms shall satisfy the following properties.
Proposition 7. Given any two feasible state points (l− , v − , t− ), (l+ , v + , t+ ) and two quasi-trajectories
+ + +
+ + +
′
′
u, u′ ∈ T with D(u′ − u) ≥ 0, then Clu− v− t− ⊆ Clu− v− t− and Pll− vv− tt− ,u ⊆ Pll− vv− tt− ,u .
Then we will prove less intuitive properties for bounded cones and prisms.
Proposition 8. Given a feasible state point (l, v, t−) and a trajectory
p′ ∈ T , then trajectory pf ((l, v, t− ), p′ )

p′
′
obtained from FSP is not empty ⇔ Clvt− 6= ∅ ⇔ D p − plvt− ≥ 0.
p′
p′
f
Proof. It is apparent that pf := pf ((l, v, t− ), p′ ) 6= ∅ leads to Clvt
− 6= ∅ because p ∈ Clvt− . Further if we


p′
′
≥ 0, which
can find a feasible trajectory in p ∈ Clvt
,
we
know
that
D
(p
−
p)
≥
0
and
D
p
−
p
−
lvt− 



yields D p′ − plvt− ≥ 0 since D is transitive. Now we only need to prove that D p′ − plvt− ≥ 0 leads to
pf ((l, v, t− ), p′ ) 6= ∅. Now we are given p′ (t) ≥ p
(t), ∀t ∈ [t− , ∞). If p′ (t) ≥ p̄ − (t), ∀t ∈ [t− , ∞), then
lvt

lvt−

Proposition 5 indicates pf ((l, v, t− ), p′ ) = pf ((l, v, t− ), ∅) that overlaps p̄lvt− (t− : ∅). Therefore pf ((l, v, t− ), p′ )
should be always non-empty. Otherwise, it should be that p′ (t) ≥ p̄lvt− (t), ∀t ∈ [t− , t∗ ), p′ (t∗ ) = p̄lvt− (t∗ ) and
p′ (t) < p̄lvt− (t), ∀t ∈ (t∗ , ∞) for some t∗ ∈ [t− , ∞). We first define a continuous function of time t̂ ∈ [t− , ∞)
as follows. We construct a trajectory denoted by pt̂ composed by maximally accelerating section p̄lvt− (t− : t̂)
(t− : ∞). Then we define function
and a maximally decelerating section pp
(t̂)ṗ
(t̂)t−
lvt−



lvt−


d(t̂) := D p′ − pt̂ =

min p′ (t) − pt̂ (t).

t∈[t− ,∞)

Note that as t̂ increases continuously, pt̂ (t) increases continuously at every t ∈ [t− , ∞). Then we can see that
function d(t̂) shall continuously decrease with t̂. Note that pt̂ is identical to plvt− when t̂ = 0. Then since
p′ (t) ≥ plvt− (t), ∀t ∈ [t− , ∞), we obtain d(0) ≥ 0. Further, as t̂ increases to t∗ , then pt̂ (t) and p′ (t) shall
intersection at t∗ , which indicates that d(t∗ ) ≤ 0. Due to Bolzano’s Theorem (Apostol, 1969), we can always
find a t̂m ∈ [t− , t∗ ] such that d(t̂m ) = 0, which indicates that p′ and pt̂m get tangent at a time t̄m ∈ [t̂m , ∞).




Then a trajectory pf can be obtained by concatenating p̄ − t− : t̂m , p̄ − t̂m , p̄˙ − t̂m , a, t̂m , t̄m ,
lvt

lvt

lvt

p (t̄m : ∞). Note that pf is exactly pf ((l, v, t− ), p′ ) and thus pf ((l, v, t− ), p′ ) is not empty. This completes
the proof.
′

We can further extend this result to a quasi-trajectory as a upper bound.
f
−
Corollary 2. Given a feasible state point (l, v, t− ) and a quasi-trajectory

 u ∈ U, then trajectory p ((l, v, t ), u)

u
obtained from the EFSP is not empty ⇔ Clvt
u − plvt− ≥ 0.
− 6= ∅ ⇔ D

−
Proposition 9. Given a feasible state point (l, v,
u ∈ U and scalars δ, δ ′ ≥ 0, if
 t ), a quasi-trajectory

u
u
f
−
u
Clvt 6= ∅, then C(l−δ)v(t− +δ′ ) 6= ∅ and we obtain D p ((l, v, t ), u) − p ≥ 0, ∀p ∈ C(l−δ)v(t
− +δ ′ ) .


u
u
u − plvt− ≥ 0.
Proof. We first prove if Clvt
6= ∅, then C(l−δ)v(t
− +δ ′ ) 6= ∅. Due to Corollary 2, we know D




Since apparently D plvt− − p(l−δ)v(t− +δ′ ) ≥ 0, we obtain D u − p(l−δ)v(t− +δ′ ) ≥ 0 due to the transitive
u
property of operator D. This yields C(l−δ)v(t
− +δ ′ ) 6= ∅ based on Corollary 2.

20

The we prove the remaining part ofthis proposition.
In case that D (u − p̄lvt− ) ≥ 0, pf := pf ((l, v, t− ), u)

u
shall be identical to p̄lvt− and thus D pf − p ≥ 0 obviously holds ∀p ∈ Clvt
− = Clvt− . Otherwise, then we

i
h



know that pf = p̄lvt− (t− : tm ) , sm := p̄lvt− t̂m , p̄˙lvt− t̂m , a, t̂m , t̄m , p′ t+ : ∞ for some tm and t+
satisfying t− ≤ tm ≤ t+ ≤ ∞, where 
p′ is the lower-bound trajectory merged by all elements in u with

u
EFSO. If ∃p ∈ Clvt
pf − p < 0, then there much exist a t̃ ∈ (tm , t+ ) such that p t̃ is strictly
− such that D




m
above s . Since D(p̄lvt− − p) ≥ 0 and D p − pp t̃ ṗ t̃ t̃ ≥ 0, thus we have D p̄lvt− − pp t̃ ṗ t̃ t̃ ≥ 0, which
() ()
() ()
m 
m
′
indicates pp t̃ ṗ t̃ t̃ and s have to intersect at a time t ∈ t̂ , t̃ . However, sine D (u − p) ≥ 0, thus pp t̃ ṗ t̃ t̃
() ()
() ()

m has already
needs to intersect with sm at another time t” ∈ t̃, t̄m . This is contradictory to thefact that
s

′
decelerated at the extreme deceleration rate a. This contradiction proves that D pf − p ≥ 0, ∀p ∈ C p .
lvt−

u
Further, given δ, δ ′ ≥ 0, for any p ∈ C(l−δ)v(t
− +δ ′ ) ,we can


similar argument. This proves that D pf − p′ ≥ 0, ∀p′ ∈

p′
find a p′ ∈ Clvt
− satisfying
u
′
C(l−δ)v(t
− +δ ′ ) , δ, δ ≥ 0.

D(p′ − p) ≥ 0 with a

Symmetrically, we can obtain similar properties for BSP as well.

Corollary 3. Given a feasible state point (l, v, t+ ) 
and a quasi-trajectory
u ∈ U,then trajectory peb ((l, v, t+ ), u)

u
u
u
obtained from BSP is not empty ⇔ Clvt
u − ppvt+ ≥ 0. If Clvt
+ 6= ∅ ⇔ D
+ 6= ∅, we obtain C(l−δ)v(t+ +δ ′ ) 6= ∅


u
and D peb − p ≥ 0, ∀p ∈ C(l−δ)v(t
+ +δ ′ ) .

Combining Corollaries 2and 3 leads to the following property with respect to a quadratic prism.


Corollary 4. Given two feasible state point (l− , v − , t− ), (l+ , v + , t+ ) satisfying D p̄l− v− t− − pl+ v+ t+ ≥ 0


and D p̄l+ v+ t+ − pl− v− t− ≥ 0, and a quasi-trajectory u ∈ U, then pf ((l− , v − , t− ), u) 6= ∅ and peb ((l+ , v + , t+ ), u) 6=
+ + +

+ + +

∅ ⇔ Pll− vv− tt− ,u 6= ∅ ⇔ D(u − pl− v− t− ) ≥ 0 and D(u − pl+ v+ t+ ) ≥ 0. Whenever Pll− vv− tt− ,u 6= ∅, we obtain


(l+ −δ)v+ (t+ +δ′ ),u
D peb − p ≥ 0, ∀p ∈ P(l− −ǫ)v− (t− +ǫ′ ) , δ, δ ′ , ǫ, ǫ′ ≥ 0.

4.3

Feasibility Properties

Although the proposed heuristic algorithms are essentially heuristics that may not explore the entire feasible
region of the original problem, it can be used as a touchstone for the feasibility of the original problems
under certain mild conditions. This section will discuss the relationship between the feasibility of the SH
solutions and that of the original problems. Note that with different acceleration values, the SH algorithms
yields different solutions. For uniformity, this section only investigates the representative SH algorithms with
āf = āb = ā and af = ab = a.
The following analysis investigates LVP, i.e., the feasibility of P LVP and that of P PSH (a, ā) .
−
Definition 17. Entry boundary condition [vn− , t−
n ]n∈N is proper if vn ∈ [0, v̄] , ∀n ∈ N and


− −
D p̄(ms−ns)vm
(tm +nτ −mτ ) − p0v − t− ≥ 0, ∀m < n ∈ N .
n n

Proposition 10. P =
6 ∅ ⇒[vn− , t−
n ]n∈N is proper.

Proof. When P =
6 ∅, let P = [pn ]n∈N denote a generic feasible trajectory vector in P. For any given
m < n ∈ N , based on safety constraint (4), we obtain D (psm − pm+1 ) ≥ 0, D psm+1 − pm+2  ≥ 0, · · · ,

sn−m−1
sn−m−2
sn−m
sn−m−1
D psn−1 − pn ≥ 0. This can be translated as D pm
≥ 0, · · · ,
≥ 0, D pm+1
− pm+2
− pm+1
21


 n−m
s
≥ 0, which indicates that D pm
− pn ≥ 0 due to the transitive property of func



sn−m
≥
0
and
D
p
−
p
≥ 0 , we obtain
tion D (·). Further, since D p̄(ms−ns)vm
−
p
− −
−
−
n
m
[tm +(n−m)τ ]
0vn tn


D p̄(ms−ns)vm
− −
[tm +(n−m)τ ] − p0v− t− ≥ 0, ∀m < n ∈ N . This completes the proof.
D psn−1 − pn



n n

Theorem 1. P LVP 6= ∅ ⇔ P PSH (a, ā) 6= ∅ ⇔ [vn− , t−
n ]n∈N is proper.

Proof. When [vn− , t−
n ]n∈N is proper, based on Corollary 3, we know that every EFSP step will generate a
feasible trajectory. Thus P PSH (a, ā) is feasible. Since P PSH (a, ā) ∈ P LVP , we see that P LVP is feasible,
too. Further, Proposition 10 indicates that when P LVP is feasible, which means P too is feasible, [v − , t− ]
n

is proper. This completes the proof.

n n∈N

Now we add back the signal control and investigate the feasibility of P under milder conditions with the
SH solution. We consider a special subset of P where every trajectory has the maximum speed of v̄ at the
exit location L, i.e,


P̂ := [pn ] n∈N ∈ P ṗn pn−1 (L) = v̄, ∀n ∈ N .

This subset is not too restrictive, because in order to assure a high traffic throughput rate, the exist
speed of each vehicle should be high. The following analysis investigates the relationship between P̂ and
P SH (a, ā, a, ā).

Proposition 11. When L ≥ v̄ 2 /(2ā), if P SH (a, ā, a, ā) = [pn ] n∈N is feasible, then ṗn (t) = v̄, ∀t ≥
pn−1 (L), n ∈ N .
Proof. We use induction to prove this proposition. The induction assumption is , ˙pn (t) = v̄, ∀t ≥ p−1
n (L). If

−
f
2
the BSP is not needed, Proposition 5 indicates that p1 = p1 = p̄0v− t− t1 : ∞ and thus since L ≥ v̄ /(2ā), we
1 1
obtain ṗ1 (t) = p̄˙ 0v− t− (t) = v̄, ∀t ≥ p−1
(L) = p̄−1
− − (L). Otherwise, if BSP is activated, it shoots backwards
1
1 1

 0v1 t1 


−1
(L)
=
v̄,
G
p̄
from the state point L, p̄0v− t− p̄−1
(L)
, and thus Proposition 6 indicates that
0v − t−
0v − t−
1


Lv̄G p̄−1−

p1 = p̄0v− t−
1

− (L)
0v1 t1

1



1

1

1

1

1

2
. Therefore, ṗ1 (t) = v̄, ∀t ≥ p−1
1 (L) holds again since L ≥ v̄ /(2ā). Then assume

that this assumption holds for n = k − 1, and we will investigate whether it holds for n = k, ∀k ∈ N \{1}.
If the primary FSP is not blocked by psk−1 , apparently pk = p̄0v− t− if the BSP is not needed, or pk =
k


Lv̄G p̄−1−

− (L)
0v t
k k

k



2
if the BSP is activated. Either way ṗk (t) = v̄, ∀t ≥ p−1
k (L) holds since L ≥ v̄ /(2ā).
Otherwise, pfk merges into psk−1 before reaching L, and thus based on the induction assumption we obtain




−1
(L) = ṗk−1 p−1
ṗfk pfk−1 (L) = ṗsk−1 psk−1
k−1 (L + s) = v̄. Note that again the BSP could only shift segments



in parallel and thus ṗ p−1 (L) = ṗf pf−1 (L) = v̄. The induction assumption also indicates that the

p̄0v− t−
k

k

k

k

k

k

segments of pk−1 used in the auxiliary FSP for pk is at constant speed v̄. This means that the auxiliary
FSP for pk will not be blocked by pk−1 , and thus we obtain ṗk (t) = v̄, ∀t ≥ p−1
k (L). This completes the
proof.
Theorem 2. When L ≥ v̄ 2 /(2ā) , P̂ 6= ∅ ⇔ P SH (a, ā, a, ā) 6= ∅ .
Proof. The proof of the sufficiency is simple. Again, we can write P SH (a, ā, a, ā) as [pn ] n∈N . When
P SH (a, ā, a, ā) 6= ∅, Proposition 11 indicates that P ∈ P̂ and thus P̂ 6= ∅.
Then we only need to prove the necessity. When there exists P ′ = [p′n ] n∈N ∈ P̂ that is not empty, we
will show that [pn ] n∈N too is not empty with the following induction. For the notation convenience, we
′
−1
−1
denote tn+ = (p′n ) (L) and t+
and D (pn − p′n ) ≥ 0.
n := pn (L). The induction assumption is that pn exists
 
− −
f
When n = 1, if BSP is not activated in constructing p1 , then p1 = p 0, v1 , t1 , ∅ = p̄0v− t− (t− : ∞)
1

22

1

−1
based on Proposition 5. Therefore, p1 exists and D (p1 − p′1 ) ≥ 0. Otherwise, denote t̄+
1 = p̄0v − t− (L) and
1 1





+
2
˙
− − − p
p̄−1
=
v̄.
Apparently,
D
p̄
t+
≥0
+
− − (L)
1 := G t̄1 . Note that since L ≥ v̄ /(2ā), p̄0v1− t−
0v1 t1
Lv̄t̄1
0v1 t1


 1

and D pLv̄t̄+ − pLv̄t+ ≥ 0, which indicates D p̄0v− t− − pLv̄t+ ≥ 0. Further since L ≥ v̄ 2 /(2ā), we know
1 1
1
1
1

′
Lv̄t+
1
D p̄Lv̄t+ − p0v− t− ≥ 0. Then we obtain p1 = p̄0v− t− based on Proposition 6. Further, apparently t1+ ≥ t̄+
1,
1
1 1
1
1


′
′
+
+
+
+
and then t1 = G t1 ≥ G t̄1 = t1 since function G(·) is increasing. Then Proposition 4 indicates that
D (p1 − p′1 ) ≥ 0.
Then assume that the induction assumption holds for n = k − 1, ∀k ∈ N \{1}. Then for n = k, Since
′


Lv̄t + ,p’s
−
p
≥ 0 where p’s
p′ ∈ P0v−kt− k−1 , then we obtain from Corollary 4 that D p’s
−
−
k−1
k−1 is the shadow
0vk tk
k k


s
trajectory of p′k−1 . And the induction assumption tells that D psk−1 − p’s
k−1 ≥ 0 where pk−1 is the shadow


trajectory of pk−1 , which further indicates that D psk−1 − p0v− t− ≥ 0 based on the transitive property of
k k
s  6= ∅. For the simplicity of presentation, we denote
D. Then Proposition 8 indicate that pf (0, vk− , t−
),
p
k−1
k
s  by pf . If BSP is not used in constructing p , then p = pf exists and Proposition
pf (0, vk− , t−
),
p
k
k
k−1
k
k
 k
+
f
−1
+
′
then
9 indicates D (pk − pk ) ≥ 0. Otherwise, let t̄k = pk (L) and tk = G t̄+
k . Then if pk exists,


+
−1
+
2
pk (L) = tk and ṗk tk = v̄ since L ≥ v̄ /(2ā). Again, it is easy to see that D p̄0v− t− − pLv̄t+ ≥ 0 and
k k
k


′
D p̄Lv̄t+ − p0v− t− ≥ 0, and therefore Corollary 4 indicates that pk exists. Also, apparently tk+ ≥ t̄+
k , and
k

 k′ k


′
+
eb (L, v̄, t+ ), pf from
then tk+ = G tk+ ≥ G t̄+
k
k = tk since function G(·) is increasing. Note that pk = p
k
f
b
′
f
b
BSP with ā = ā = ā and a = a = a. Then Corollary 4 further indicates that D (p − p ) ≥ 0. This
k

k

completes the proof.

Further, we will show that when L is sufficiently long, the feasibility of P SH (a, ā, a, ā) is equivalent to
the feasibility of P.
Theorem 3. When L ≥
proper.

v̄ 2
2ā

+

v̄ 2

−2ab

+

v̄ 2

−2ab

+ s(N − 1) , P SH (a, ā, a, ā) 6= ∅ ⇔ P =
6 ∅ ⇔ [vn− , t−
n ]n∈N is

Proof. When P SH (a, ā, a, ā) 6= ∅, it is trivial to see that P 6= ∅ since P SH (a, ā, a, ā) ∈ P. Proposition 10
− −
indicates that P 6= ∅ leads to that [vn− , t−
n ]n∈N is proper. Then we only need to prove that when [vn , tn ]n∈N
is proper, P SH (a, ā, a, ā) 6= ∅. We denote the trajectories in P SH (a, ā, a, ā) with [p ]
. Note that
n n∈N

for each trajectory
then
 iit shall be always successfully completed within
h pn , if BSP in

 SH3 is activated,
highway segment L̂ := L − v̄ 2 / −2āb − v̄ 2 / −2āb , L . Therefore, BSP neither causes infeasibility nor

i


h

affects the shape of pn within 0, L̂n := L − v̄ 2 / −2āb − v̄ 2 / −2āb − s(n − 1) . Even if we consider

 
−1
=
:
ṗ
L̂n
the backward wave propagation caused by the previous trajectories. This indicates pn t−
n
n

 
−1
L̂n , and if the feasibility check of pn fails in SH, it must happens in this section. Note
pfn t−
n : ṗn
PSH (a, ā) is not empty. We denote P PSH (a, ā) with
that Theorem 1 shows that if [vn− , t−
n ]n∈N is proper, P
 

 

−
−1
−1
L̂n , ∀n ∈
t
:
p
=
p̂
L̂
:
p
[p̂n ] n∈N . Then to prove this theorem, we only need to show that pn t−
n
n
n
n
n
n
N from the following induction. 
 

 
−1
−1
−1
The induction assumption is pn t−
L̂n
= p̂n t−
L̂n and ṗn (t) = v̄, ∀t ∈ [p−1
n : pn
n (L̂n ), pn (L̂)].
n : pn

− −
f
f
When n = 1, the trajectory generated from
satisfies
1 ), ∅ = p̂n . Since BSP will not
 FSP 
 p1 (0, v1 , t
 p1 :=
−1
−1
affect the shape of p1 below L̂1 , thus p1 t−
= p̂1 t−
L̂1
L̂1 . Since pf1 shall finish acceler1 : p1
1 : p1
ating to v̄ before reaching location L̂ based on the value of L̂, then ṗ1 (t) = p̂˙ 1 (t) = v̄, ∀t ∈ [p−1 (L̂n ), p−1 (L̂)].
n

23

n

Then we assume that the induction assumption holds for n = k− 1, ∀k ∈ N \{1}.
When n = k, the

 s 
− −
f
f
s
forward shooting trajectory is pk := p 0, vk , tk , pk−1 . If D pk−1 − p̄0v− t− ≥ 0, then apparently
k k
 
−
−1
f (t− : p−1 (L̂ )) = p̂ (t− : p−1 (L̂ )) and
pfk = p̂k = pf 0, vk− , t−
,
∅
,
and
thus
p
(t
:
p
(
L̂
))
=
p
k k
k
k
k k
k
k k
k
k
k
k
ṗ (t) = v̄, ∀t ∈ [p−1 (L̂ ), p−1 (L̂)]. Otherwise, note that pf = pf ((0, v − , t− ), ps ) = pf ((0, v − , t− ), p̂s ) = p̂
k

k

k

k

k

k

k

k−1

k

k

k−1

k

and thus the existence of p̂k indicates that pfk exists as well. The induction assumption of ṗk−1 (t) = v̄, ∀t ∈
−1
s−1
s−1
s
f
[p−1
k−1 (L̂k−1 ), pk−1 (L̂)] indicates that ṗk−1 (t) = v̄, ∀t ∈ [pk−1 (L̂k = L̂k−1 − s), pk−1 (L̂ − s)], and therefore, pk
shall merge with psk−1 at a location before L̂ because the merging speed has to be less than v̄, and therefore
i
h
−1
, or
ṗk (t) = ṗfk (t) = v̄, ∀t ∈ [p−1
(
L̂
),
p
(
L̂)].
Therefore,
p
and
p̂
overlap
over
highway
segment
0,
L̂
k
k
k
n
k
k 

 
−1
−1
. This completes the proof.
L̂k
= p̂k t−
L̂k
p k t−
k : pk
k : pk

4.4

Relationship to Classic Traffic Flow Models

Evolution of highway traffic has been traditionally investigated with various microscopic models (e.g., car
following (Brackstone and McDonald, 1999), cellular automata (Nagel and Schreckenberg, 1992)) and macroscopic kinematic models (kinemetic models (Lighthill and Whitham, 1955; Richards, 1956) and cell transmission (Daganzo, 1994)). Daganzo (2006) proves the equivalence between the kinematic wave model with
the triangular fundamental diagram (KWT) (Newell, 1993), Newell’s lower-order model (Newell, 2002) and
the linear cellular automata model (Nagel and Schreckenberg, 1992). We will just show the relevance of the
the SHL solution to the KWT model, and this relevance can be easily transferred to other models based
on their equivalence. Given the first vehicle’s trajectory q1 = p1 ∈ T , the KWT model specifies a rule
to construct vehicle n’s trajectory, denoted by qn , with vehicle n′ s entry condition (0, ·, t−
n ) and preceding
trajectory qn−1 , as formulated below

−
qn (t) = min v̄(t − t−
(11)
n ), qn−1 (t − τ ) − s , ∀n ∈ N \{1}, t ∈ [tn , ∞).
For notation convenience, we denote this equation with qn = q KWT ((0, ·, t−
n ), qn−1 ). This section analyzes
the relationship between the SHL solution
with
the
KWT
solution
for
the
same
LVP setting. We denote the


SHL trajectory vector with P LVP af , āf = [pn ]n∈N and that from KWT by Q = [qn ]n∈N . Without loss


LVP af , āf is feasible.
of generality, we only investigate the case when [vn− , t−
]
is
proper
or
P
n n∈N
Daganzo (2006) showed that KWT has a contraction property; i.e., the result of KWT is insensitive to
small input errors, as stated in the following proposition.

Proposition 12. Given two trajectories q, q ′ ∈ T̄ satisfying
maxt∈(−∞,∞) |q(t) − q ′ (t)| ≤ ǫ for some ǫ >

′
0, then maxt∈(−∞,∞) q KWT ((0, ·, t− ), q s ) − q KWT (δ, ·, t− ), q s ≤ ǫ for any |δ| < ǫ and t− yielding


′
q KWT ((0, ·, t− ), q s ) 6= ∅ and q KWT (δ, ·, t− ), q s 6= ∅.


We now show that P LVP af , āf has the same contraction property.

Theorem 4. Given two feasible trajectories p, p′ ∈ T satisfying maxt∈(−∞,∞) |p(t) − p′ (t)| ≤ ǫ, then
′
maxt∈(−∞,∞) pf ((0, v − , t− ), ps ) − pf ((δ, v − , t− ), p s ) ≤ ǫ for any |δ| < ǫ and any (v − , t− ) yielding pf ((0, v − , t− ),
′
ps ) 6= ∅ and pf ((δ, v − , t− ), p s ) 6= ∅.
′
Proof. Since maxt∈(−∞,∞) |p(t) − p′ (t)| ≤ ǫ, we obtain maxt∈(−∞,∞) ps (t) − p s (t) ≤ ǫ. Further, define
ps+ǫ (t) := ps (t)+ǫ, ps−ǫ (t) := ps (t)−ǫ, pf+ǫ := pf ((ǫ, v − , t− ) , ps+ǫ ) and pf−ǫ := pf ((−ǫ, v − , t− ) , ps−ǫ ). Note
that p(t) = p+ǫ (t)−ǫ = p−ǫ (t)+ǫ, ∀t ∈ (−∞, ∞). Since D (ps+ǫ − ps ) = ǫ and maxt∈(−∞,∞) |p(t) − p′ (t)| ≤ ǫ,


p’s
ps+ǫ
we obtain D ps+ǫ − p’s ≥ 0. Then Proposition 7 indicates that Cδvt
− ⊆ Cδvt− . Further, Proposition 9

24





ps+ǫ
f
− −
s
f (δ, v − , t− ), p′ s as pf and p′ f
indicates D pf+ǫ − p̂ ≥ 0, ∀p̂ ∈ Cδvt
− . We denote p ((0, v , t ), p ) and p


′
′
p’s
ps+ǫ
for short, respectively. Since p f ∈ Cδvt
pf+ǫ − p f ≥ 0. On the other hand, we
− ⊆ Cδvt− , we obtain D


ps−ǫ
p’s
obtain D p’s − ps−ǫ ≥ 0. Then Proposition 7 indicates C−ǫvt
− ⊆ C−ǫvt− . Further, Proposition 9 indicates

 ′
p’s
ps−ǫ
p’s
D (p′ − p̂) ≥ 0, ∀p̂ ⊆ C−ǫvt
Since pf−ǫ ∈ C−ǫvt
p f − pf−ǫ ≥ 0. Combining
−.
− ⊆ C−ǫvt− , we obtain D


 ′

′
′
D pf+ǫ − p f ≥ 0 and D p f − pf−ǫ ≥ 0 yields maxt∈(−∞,∞) pf (t) − p f (t) ≤ ǫ .



Theorem 4 impliesthat P LVP af , āf is not sensitive to small input errors as well. However, we shall
note that the solution to the SH algorithm for a signalized section may be sensitive to small errors because
the exit time of a trajectory, if close to the start of a red phase, could be pushed back to the next green
phase due to a small input perturbation. Nonetheless, this kind of “jump” only affects a limited number of
trajectories that are close to a red phase, and most other trajectories will not
 be much affected.
f
f
LVP
a , ā and Q.
The following analysis investigates the difference between P
Proposition 13. Q = {qn }n∈N formulated in (11) can be solved as
n n−1
o
, ∀t ∈ [t−
qn (t) = min ps1 (t), v̄ t − t−
n , ∞), n ∈ N .
n

(12)

k
where ps1 (t) := p1 (t − kτ ) − ks, ∀k.

0
Proof. We prove this proposition with induction. Apparently, equation (12) holds for n = 1 since ps1 = p1 ∈

−
s0
T and thus v̄ t − t−
1 ≥ p1 (t), ∀t ∈ [t1 , ∞). Assume that equation (12) holds for n = k − 1. When n = k,
assumption into the
equation (11) indicates qk (t) = min{v̄(t − t−
k ), qk−1 (t − τ ) − s}. Then plug the induction
sk−2 (t−τ )−s, v̄ t − t− − τ  −s}= min{psk−1 (t), v̄(t−
above equation and we obtain qk (t) = min{v̄(t−t−
),
p
1
1
k
k−1
− −
−
−
− −
max{t−
k , tk−1 + τ + v̄/s})}. Since [vn , tn ]n∈N is proper, we obtain max tk , tk−1 + τ + v̄/s = tk . This
completes the proof.


Theorem 5. If P LVP af , āf 6= ∅ and Q 6= ∅, then D (qn − pn ) = 0 and

n
o
D (pn − qn ) ≥ min −0.5v̄ 2 /āf , 0.5v̄ 2 /af , ∀n ∈ N \ {1} .

(13)



Proof. We compare parallel formulations from P LVP af , āf from PSHL in Section 3.2 with equation (12)

for Q. We only need to prove this theorem for a generic 
n ∈ N \ {1}. From
 PSHL, we see that pn is
n n−m o
s
with tangent segments at
essentially obtained by smoothing quasi-trajectory un := u
p̄m
m=1,··· ,n

f
constant decelerating rate a. Define q̄n (t) := v̄ (t − t−
∈ [t−
n ) , ∀t o
n , +∞) , q n := p ((0, 0, tn ) , ∅). Note that

n

n−1
D q n − q̄n = −0.5v̄ 2 /āf , and qn (t) = min q̄n (t), ps1 (t) . Note that D (qn − un ) ≥ 0 since q̄n ≥ p̄n .

Also, D (un − pn ) ≥ 0 since the merging segments generated from EFSO-2 are all below un . This indicates
−
D (qn − pn ) ≥ 0. Further since qn and pn always
n meet at the initial
o point (0, tn ), we obtain D (qn − pn ) = 0.
Then we will prove D (pn − qn ) ≥ min −0.5v̄ 2 /āf , 0.5v̄ 2 /af . We first examine p′n := pf ((0, vn− , t−
n ),


n−m
s
{p̄m
}m=2,··· ,n−1 ), ∀n ∈ N \{1}, and claim D p′n − q n ≥ 0. Basically, p′n is composed by some shooting

 n−m
n n−m o
s
s
and intermediate tangent merging segments. Apparently, D p̄m
− qn ≥
segments from p̄m
m=2,··· ,n−1

0. Note that every merging segment shall be above pn or it will not catch up with the next shooting segment that accelerates at the maximum rate āf before reaching speed v̄. Thus this claim holds and thus
25

D (p′n − q̄n ) ≥ −0.5v̄ 2 /āf . Therefore, D (p′n − qn ) ≥ −0.5v̄ 2 /āf . Note
that pn is obtained by merging p′n
 n−1
n−1
and p̄s1 with a tangent segment denoted by ŝn . Apparently, D p̄1s
− qn ≥ 0 since qn (t) is defined
 n−1

n
o


n−1
n−1
− qn ≥ 0, we
as min q̄n (t), ps1 (t) . Further note that D ŝn − p̄1s
≥ 0.5v̄ 2 /af , and since D p̄s1

o
n
 n−1
obtain D (ŝn − qn ) ≥ 0.5v̄ 2 /af . Therefore D(pn − qn )≥ min D (p′n − qn ) , D p̄1s
− qn , D (ŝn − qn ) ≥
o
n
min −0.5v̄ 2 /āf , 0.5v̄ 2 /af . This completes the proof.



The above theorem reveals that a trajectory generated fromP LVP af , āf should be always below the
counterpart trajectory in Q and the difference is attributed to smoothed accelerations instead of speed jumps.
One elegant finding from this theorem is that this difference does not accumulate much across vehicles but is
bounded by a constant. Further, the lower bound to this difference is actually
n tight and we can find
o instances
2
f
2
f
where D (pn − qn ) for every vehicle n ∈ N \ {1} is exactly identical to min −0.5v̄ /ā , 0.5v̄ /a . One such
instance can be specified by setting p1 (t) = L, ∀t for a sufficiently long L, andvn− = 0, ∀n ∈ N \ {1}. This
theorem also leads to the following asymptotic relationship.


Corollary 5. If āf → ∞ and af → −∞, then we have P LVP af , āf → Q.

This relationship indicates that SHL can be viewed as a generalization of KWT as well as other equivalent
models, including Newell’s lower order model and the linear cellular automata model. Essentially, the SH
solution can be viewed as a smoothed version of these classic models that circumvents a common issue
of these classic models, i.e., infinite acceleration/deceleration or “speed jumps”. Such speed jumps would
cause unrealistic evaluation of traffic performance measures, particularly those on safety and environmental
impacts. Further, SHL inherits the simple structure of these models and thus can be solved very efficiently.
One commonality between SHL and KWT is that at stationary states, i.e., when each trajectory move at a
constant speed, both the SHL solution and the KWT solution are consistent with a triangular fundamental
diagram Newell 1993, as stated below.


Theorem 6. If solutions P LVP af , āf and Q are both feasible and each ṗn (t) or q̇n (t) remains constant

∀t ≥ t−
n , then there exists some V ∈ [0, v̄] such that

Further, if V = v̄,


− 
pn (t) = qn (t) = V t − t−
n , ṗn (t) = q̇n (t) = V, ∀t ∈ tn , ∞ , n ∈ N .

(14)

−
t−
n − tn−1 ≥ τ + V /s, ∀n ∈ N ,

(15)

−
t−
n = (n − 1)(τ + V /s) − t1 , ∀n ∈ N \ {1} .

(16)

If V < v̄, then

Further, define the traffic density as K :=
traffic volume as O :=

N −1
−1
p−1
N (l)−p1 (l)

=

PN

N −1
−1
qN
(l)−q1−1 (l)

(

N −1

n=2 (pn−1 (t)−pn (t))

=

PN

N −1

n=2 (qn−1 (t)−qn (t))

for any t ≥ t−
n and

for any l ≥ 0, then we will always have

K ≤ 1/(s + V τ ),
K = 1/(s + V τ )

if V = v̄;
if V < v̄.

O = KV = min {K v̄, (1 − sK)/τ } ∈ [0, v̄/(s + v̄τ )] .

(17)
(18)

Proof. We fist investigate the case when every ṗn (t) is constant. If there exist two consecutive trajectories
not parallel with each other, then they will either intersect or depart from each other to an infinite spacing
since they both are straight lines. The former is impossible because of safety constraints (4). Neither is the
latter possible since the following trajectory has to accelerate when their spacing exceeds the shadow spacing
26

and runs at a speed lower than the preceding vehicle. Therefore ṗn (t) values are identical to a V ∈ [0, v̄]
−
−
across n ∈ N . Therefore,

 pn (t) = V (t − tn ) , ṗn (t) = V, ∀t ∈ [tn , ∞) , n ∈ N .
Since P LVP af , āf is feasible, then we know from Theorem 1 that [vn− , t−
n ]n∈N is proper, which indicates

that equation (15) holds either V = v̄ or V < v̄. Further, when V < v̄, equation (15) becomes a strict equality
(or otherwise the following trajectory needs to accelerate). Thus equation
(16)

 holds in this case.
LVP
f
f
a , ā are at speed V , we know that
Then we will show that qn = pn . Since all trajectories in P

−
−
vn = V, ∀n ∈ N and the lead trajectory is given as p1 (t) = V t − t1 . If V = v̄, apparently no trajectory
−
blocks its following trajectory, and thus qn (t) = V (t − t−
n ) = pn (t), ∀t ∈ [tn , ∞) , n ∈ N . Otherwise if
V < v̄, due to equation (16), qn has no room to accelerate and thus has to stay at speed V . Therefore,
equation (14) holds. Then we will prove equations (17) and (18), which quantify the triangular fundamental
−
−
diagram. First, since [vn− , t−
n ]n∈N is proper, then we obtain pn−1 (tn ) − pn (tn ) ≥ V τ + s, ∀n ∈ N \ {1},
−
and thus K ≥ 1/(V τ + s) holds. When V < v̄, due to (16), then pn−1 (tn ) − pn (t−
n ) = V τ + s, ∀n ∈
−1
N \ {1}, and thus K = 1/(V τ + s) holds. This proves equation (17). Further note that p−1
n (0) − pn−1 (0) =
N
−1
N
−1
−
= KV .
= PN p
(pn−1 (t−
−1
−
−
n ) − pn (tn )) /V, ∀n ∈ N \ {1}, then O = PN (p−1
n (0)−pn−1 (0))
n=2
n=2 ( n−1 (tn )−pn (tn ))/V
When V = v̄, plugging inequality K ≤ 1/(s + V τ ) in equation (17) into the previous equation, we obtain
KV = K v̄ ≤ v̄/(s + v̄τ ), and K ≤ 1/(s + V τ ) can be rearranged into to (1 − sK)/τ ≥ KV . Therefore,
equation (18) holds in this case. When V < v̄, apparently, KV < K v̄. Further, equality K = 1/(s + V τ )
in equation (17) can be rearranged as KV = (1 − sK)/τ . Note that K = 1/(s + V τ ) > 1/(s + v̄τ ), and
plugging this inequality into KV = (1 − sK)/τ yields KV = (1 − sK)/τ < (1 − s/(s + v̄τ ))/τ = v̄/(s + v̄τ ).
This indicates that equation (18) holds in the case too. This completes the proof.

5

Illustrative Examples

This section presents a few illustrative examples that help visualize results of the algorithms and related
theoretical properties. In the following examples, we set the parameters to their default values unless
explicitly stated otherwise. These default parameter values are L = 1000 m, N = 50, a = −5 m/s2 ,
2
a = 2 m/s , v̄ = 25 m/s, G = R = 25 s, s = 7 m, and the default boundary condition is generated as follows.
We first set the arrival times as




C
−
−
−
t1 = 0, tn = tn−1 + (τ + s/v̄) 1 +
− 1 (1 − α + αǫn ) , ∀n ∈ N \{1},
(19)
Gf s
where f s ∈ (0, C/G] is the traffic saturation rate (or the ratio of the arrival traffic volume to the intersection’s
maximum capacity), α ∈ [0, 1] is the dispersion factor of the headway distribution, and {ǫn }n∈N \{1} are
P
uniformly distributed non-negative random numbers that satisfy n∈N \{1} ǫn = N − 1. The default values
of f s and α are both set to 1. We set the arrival times in this way such that the average time headway equals
(τ + s/v̄)C/ (Gf s ) yet the individual arrival times can be stochastic. The stochasticity of the arrival times
increases with headway dispersion factor α. Note that we always maintain every headway no less than (τ +
s/v̄) because the boundary condition would be infeasible otherwise. Next, for each n ∈ N , the initial speed
vn− is consecutively drawn as a random number uniformly distributed over
and
 the corresponding lower bound 
upper bound. These two bounds assure that vn− satisfies vn− ∈ [0, v̄], D p̄(ms−ns)vm
− −
≥
[tm +(n−m)τ ] − p0vn− t−
n


−
− p0v− t− ≥ 0, ∃vm ∈ [0, v̄], ∀m > n ∈ N with the maximum
0, ∀m < n ∈ N and D p̄(ns−ms)vn− [t−
n +(m−n)τ ]
m m

acceleration and the minimum deceleration for QTG downscaled to ā/3 and a/3, respectively. The downscale
of the acceleration limits assures that the boundary condition is feasible for any forward acceleration āf ≥ ā/3
and any forward deceleration af ≥ a/3, which allows to test a range of āf and af values. If a proper boundary
condition cannot be found, we will regenerate random parameters {ǫn }n∈N \{1} with a different random seed
and repeat this process until finding a proper boundary condition.
Section 5.1 compares the SH solutions with a benchmark instance that simulates the manually-driven
traffic counterpart. This comparison aims to qualitatively show the advantaged of the proposed CAV control
27

strategies over manual driving. Section 5.2 compares SHL and PSHL results and shows they produce the
identical results for the same LVP input. Section 5.3 tests the feasibility of SH and SHL solutions with
different boundary conditions to verify some theory predictions and reveal insights into how parameter
changes affect the solution feasibility. Section 5.4 compares SHL and LWK results and measures their
difference to check the theoretical error bounds.

5.1

Manual v.s. Automated Trajectories

To illustrated the advantage of results, we construct a benchmark instance that simulates the manually-driven
traffic counterpart. We adapt the Intelligent Driver model (Treiber et al., 2000) as the manual-driving rule
for every vehicle:
  

 
s∗
, ā′ , a′ ,
p̈n (t) = max min ā 1 −
(20)
f n−1 (t − τ ) − pn (t − τ ) − l0
(
(
0, if ṗn (t) ≤ 0;
0,
if
ṗ
(t)
≥
v̄;
n
, comwhere vehicle length l0 = 5m, acceleration bounds ā′ =
and a′ =
a, otherwise,
ā, otherwise,
ṗ (t−τ )−ṗ′

(t−τ )

√ n−1
fort deceleration b = 1.67m/s2, and the desired spacing s∗ = (s− l0 )+ ṗn (t− τ )τ + ṗn (t− τ ) n
.
āb
The effect of traffic lights is emulated with a bounding frontier f n−1 that is pn−1 if pn is not blocked by a
red light or a virtual vehicle parked at L + s otherwise. We define the yellow time prior to the beginning of
a red phase as y = 3s and f n−1 can be formulated as
(
L + s,
if L − pn (t − τ ) < v̄ 2 /(2b), t ∈ [mC − y, mC + G] and p̄−1
/ G;
pn (t−τ )ṗn (t−τ )(t−τ ) (L) ∈
f n−1 (t) =
,
pn−1 (t), otherwise,

To accommodate the lead vehicle that does not have a preceding trajectory, without loss of generality, we
define a virtual preceding vehicle p0 (t) = ∞ and ṗ0 (t) = v̄, ∀t. There are two reasons to select this model.
First, the trajectories produced from this model appear to be consistent with our driving experience at a
signalized intersection: we tend to slow down and make a stop only when we get close the intersection at a
yellow or red light. Secondly, it is easy to verify that at a stationary state, the same macroscopic relationship
between density and flow volume defined in Theorem 6 holds. This way, the comparison between the SH
solution and this benchmark will only focus on the “trajectory smoothing” effect rather than improvement of
stationary traffic characteristics, which has been investigated in other studies (e.g., Shladover et al. (2009)).
Figure 7 compares the benchmark result with the SH output. Figure 7(a) plots the benchmark manualdriving trajectories generated with car-following model (20). We see that due to abrupt accelerations and
decelerations in the vicinity of the traffic lights, a number of consecutive stop-and-go waves are formed and
propagated backwards from the intersection. These stop-and-go waves slow down the passing speed of the
vehicles at the intersections, and thus decrease the traffic throughput and increase the travel delay. As a
result, the total travel time (i.e., the time duration between the first vehicle’s entry at location 0 and the last
vehicle’s exist at location L) is over 300 seconds for the benchmark case. Further, it is intuitive that these
stop-and-go waves adversely
 impact fuelconsumptions and emissions and amplify collision risks. Figure 7(b)
plots the SH result with āf , af , āb , ab identical to their bounding values (ā, a, ā, a). We see that despite
some sharp accelerations and decelerations, all vehicles can pass the intersection at the maximum speed
and thus the traffic throughput gets maximized. The
 total travel time now is only around 170 seconds.
Figure 7(c) plots the SH result with āf , af , āb , ab downscaled to (ā/3, a/3, ā/3, a/9). We see that with

the acceleration/deceleration magnitudes reduces, trajectories become much smoother while the total travel
time keeps low around 170 seconds. This will further reduce the traffic’s environmental impacts and enhance
its safety.
To inspect the differences between the benchmark and the SH result from a macroscopic point of view,
we measure the macroscopic traffic characteristics, including density and flow volumes for the trajectory sets
in Figure 7 with the measuring method proposed by Laval (2011b). Basically, we roll a parallelogram with
28

1000

800

800

800

600
400
200
0

Space (m)

1000
Space (m)

Space (m)

1000

600
400

600
400

200
0

100

200
Time (s)
(a)

0

300

200
0

100
Time (s)
(b)

0

200

0

100
Time (s)
(c)

200

Figure 7: (a) Benchmark manual-driving trajectories, (b) SH result P (ā, a, ā, a) , and (c) SH result
P (ā/3, a/3, ā/3, a/9) .
3000

2000

1000

0

0

50
100
Density (vehs/km)

150

3000
stationary
measurements

Flow (vehs/hr)

stationary
measurements

Flow (vehs/hr)

Flow (vehs/hr)

3000

2000

1000

0

0

50
100
Density (vehs/km)

(a)

(b)

150

stationary
measurements
2000

1000

0

0

50
100
Density (vehs/km)

150

(c)

Figure 8: Macroscopic characteristics for (a) the benchmark trajectories, (b) P (ā, a, ā, a), and (c)
P (ā/3, a/3, ā/3, a/9) .
a length of 100m and a time interval of 5s along the shock wave direction (at a speed of −s/τ ) across the
trajectories in every plot in Figure 7 by a 100m×5s step size. We measure the flow volume and density at
each parallelogram and plot the measurements as circles in the corresponding diagrams in Figure 8, where
the solid curves represent the stationary flow-density relationships specified in equation 18. We see that in
Figure 8(a) for the bench mark trajectories, many measurements are distributed on the congested side of
this diagram and most of them are below the stationary curve, which explains why the performance of the
benchmark case is the worst. This is probably because traffic the stop and go waves (or traffic oscillations)
result in a lower traffic throughput even at the same density, which is known as the capacity drop phenomenon
(Cassidy and Bertini, 1999; Ma et al., 2015). In Figure 8(b) for the SH result P (ā, a, ā, a), there are much
fewer measurements falling in the congested branch, and these measurements are closer to the stationary
curve. In Figure 8(c) for the smoothed SH result P (ā/3, a/3, ā/3, a/9), even more measurements lie in the
free-flow branch, and these measurements become consistent with the stationary curve. This suggests that
the proposed SH algorithm with proper parameter values can counteract the capacity drop phenomenon and
bring macroscopic traffic characteristics toward the free-flow branch of the stationary curve.
Overall, the results in this Subsection show that the proposed SH algorithm can much improve the highway
traffic performance in mobility, environment and safety. To realize the full utility of the SH algorithm,
quantitative optimization needs to be conducted, which will be detailed in Part II of this study.

29

1000

1000

600
400
200
0

600
400
200

0

50
100
Time (s)

150

0

SHL
PSHL

800
Space (m)

800
Space (m)

Space (m)

800

1000
SHL
PSHL

600
400
200

0

50
100
Time (s)

(a)

150

0

0

50
100
Time (s)

150

(c)


Figure 9: (a) Benchmark manual-driving trajectories, (b) SHL and PSHL results with āf , af = (ā, a) , and


(c) SHL and PSHL results with āf , af = (ā/3, a/3) .

5.2

(b)

Lead Vehicle Problem

This subsection presents LVP results from manual driving law (20) and the proposed CAV driving algorithms.
In the LVP, we set G = ∞ and R = 0, and we update saturation rate to fs = 0.5 in generating the boundary
condition (so that the average headway remains 0.5(τ + s/v̄)). The lead trajectory is set to initially cruise
at speed v̄ for 20 seconds, then deceleration to the zero speed with a decelerating rate of a/3, then keep
stopped for 20 seconds, then accelerate to v̄ with a rate of ā/3, and finally keep cruising at this speed, i.e.,
 



3v̄
3v̄ 2
a
3v̄
3v̄
, 20v̄ −
,
p1 : =
(0, v̄, 0, 0, 20) , 20v̄, v̄, , 20, 20 −
, 0, 0, 20 − , 40 −
3
a
2a
a
a




a
3v̄ 3v̄
3v̄ 2
3v̄ 2
3v̄ 2
3v̄
3v̄ 3v̄
, 0, , 40 − , 40 −
+
+
+ , ∞ . (21)
20v̄ −
, 20v̄ −
, v̄, 0, 40 −
2a
3
a
a
ā
2a
2ā
a
ā
This way, p1 triggers a stopping wave and we can examine its propagation under different driving conditions.
Figure 9 shows the trajectory comparison results. We see that first, in Figures 9 (b) and (c), the PSHL
results (solid lines) exactly overlap with the SHL results (crosses), which verifies Proposition 2 that states the
equivalence between PSHL and SHL. Compared with the manual-driving case in Figure 9(a), the automateddriving case in Figure 9(b), even with the extreme acceleration and deceleration rates (ā, a), relatively better
absorbs the backward stopping wave within a fewer number of vehicles. Reducing the acceleration and
deceleration magnitudes to (ā/3, a/3) in Figure 9(c) can further smooth vehicle trajectories and dampen
the impact from the stopping wave. These results imply that proper CAV controls can effectively smooth
stop-and-go traffic and reduce backward shock wave propagation on a freeway.

5.3

Feasibility Tests

This section conducts some numerical tests to test the feasibility of the
algorithms with different

 proposed
input settings. We first investigate SHL (or PSHL) for LVP with āf , af = (ā, a) . Theorem 1 proves

that SHL is feasible if and only if boundary condition [vn− , t−
n ]n∈N is proper. Thus we investigate how
the feasibility of SHL changes with the distribution of vn− and t−
n . Since the default boundary condition
generation method always assures that [vn− , t−
]
is
proper,
this
subsection uses a different generation
n n∈N
method to allow [vn− , t−
]
to
be
non-proper.
We
still
use
equation
(19) to generate t−
n n∈N
n , and thus the
−
dispersion of time headway is controlled by α. In the next step, each vn is instead randomly pulled along a
uniform interval [(1 − β)v̄, v̄] where β ∈ [0, 1] is the speed dispersion factor and increases with the dispersion
−
of the vn− distribution. Note that the final values of t−
n and vn are randomly generated. We generate
20 boundary condition instances with the same α and β values yet different random seeds. Then we feed
each boundary condition instance to the SHL algorithm and record the feasibility of the result. We call
30

100%

0.8

0.8

0.8

80%

0.6

0.6

0.6

60%

α

1

α

1

α

1

0.4

0.4

0.4

40%

0.2

0.2

0.2

20%

0

0

0.2

0.4

0.6
β

0.8

1

0

0

0.2

0.4

0.6

0.8

1

β

0

0

0.2

0.4

0.6

0.8

1

0%

β

(a)

(b)

(c)

Figure 10: Feasibility rate of PSHL with (a) f s = 0.2, (b) f s = 0.5, and (c) f s = 0.8.
the percentage of feasible solutions over all 20 boundary conditions the feasibility rate with regard to this
specific parameter setting. Figure 10 plots hot maps for the feasibility rate over α × β ∈ [0, 1] × [0, 1] with
different f s values. We can see that overall, as α and β increase, the feasibility rate decreases, and more
−
instances are infeasible as f s increases. This is because higher dispersion of t−
n and vn is more likely to
cause conflicts between trajectories that cannot be reconciled under safety constraint (4), and such conflicts
may increase as traffic gets denser. Note that in all maps in Figure 10, the transition band between 100%
feasibility rate (the white color) and 0% feasibility rate (the black color) is very narrow. This indicates that
SHL’s feasibility is dichotomous. With this observation, the parameters could be partitioned into only two
phases (feasible and infeasible) to facilitate relevant analysis.


Next we investigate the SH algorithm considering traffic lights with āf , af , āb , ab = (ā, a, ā, a). We

conduct similar experiments as those for Figure 10 with the same adapted boundary condition generation
method. Theorems 2 and 3 suggest that the feasibility of SH is related to segment length L. Traffic congestion
f s and platoon size N shall also affect SH’s feasibility. This time, we fix α = β = 0.5 and analyze how the
feasibility rate varies with L and f s over different N values, and the results are shown in Figure 11. We
see that again the increase of f s raises the chance of infeasibility. Further, as L decreases, the likelihood
of feasibility diminishes. This is because a short section may not be sufficient to store enough stopping or
slowly moving vehicles to both comply with the signal phases and allow the following vehicles to enter the
section at their due times. Also, more instances are infeasible as N increases. This is because more vehicles
shall bare a higher chance of producing an irreconcilable conflict between two consecutive vehicles against
safety constraint (4). Similarly, the SH feasibility is dichotomous and a two-phase representation might be
applicable.

5.4

Comparison with Classic Traffic Flow Models



This section compares KWT solution Q and SHL solution P LVP af , āf for LVP. Again, we set G = ∞
and R = 0, f s = 0.5. The lead trajectory is generated with equation (21), and the boundary condition
Figure 12
is generated with the default method associated
 with equation (19) to assure the
 feasibility.


f
f
f
f
compares these trajectories with different ā , a values. In this section we allow ā , a go beyond (ā, a)

so as to investigate the asymptotic
in Q have abrupt

properties of SHL. We see that in general, trajectories

turns while those in P LVP af , āf are relatively smooth. All trajectories in P LVP af , āf is below those




in P LVP af , āf , which is consistent with the upper bound property stated in Theorem 5. As āf , af


amplifies from (ā/3, a/3) to (3ā, 3a), we see that accelerations and decelerations in P LVP af , āf become
31

0.8

0.8

0.8

80%

0.6

0.6

0.6

60%
40%

0.4

0.4

0.4

0.2

0.2

0.2

200

400

600
L

800

100%

fs

1

fs

1

fs

1

1000

200

400

600
L

(a)

800

1000

20%

200

400

600
L

(b)

800 1000

0%

(c)

Figure 11: Feasibility rate of PSHL with (a) N = 25; (b) N = 50; and (c) N = 100.

P

1

LVP āf ,af

2

600
400
200
0

1000

Q

800
Space (m)

800
Space (m)

1000

Q

P

1
2
LVP āf ,af

600
400
200

0

50
Time (s)

100

0

Q

800
Space (m)

1000

P

1
2
LVP āf ,af

600
400
200

0

50
Time (s)

(a)

(b)

100

0

0

50
Time (s)

100

(c)

Figure 12: Comparison between KWT solution Q and SHL solution P LVP (āf , af ) with (a)




(ā/3, a/3), (b) āf , af = (ā, a), and (c) āf , af = (3ā, 3a)..



āf , af =



sharper and trajectories in P LVP af , āf get closer to those in Q, which is consistent with the asymptotic
property stated in Corollary 5.
Figure 13 plots the errors between Q and P LVP (γā, γa) and their bounds (defined in Theorem 5), where
acceleration factor γ increases from 1/3 to 3. We see that D (qn − pn ) is always identical to 0 (or the upper
bound) and D (pn − qn ) is always above the lower bound (13) for all γ values. As γ increases, the errors
and their bounds all converge to 0, which again confirms Corollary 5. In summary, these experiments show
that SHL can be viewed as a smoothed version of KWT that replaces speed jumps in KWT with smooth
accelerations and decelerations.

6

Conclusion

This paper investigates the problem of controlling multiple vehicle trajectories on a highway with CAV
technologies. We propose a shooting heuristic to efficiently construct vehicle trajectories that follow one
another under a number of constraints, including the boundary condition, physical limits, following safety,
and traffic signals. With slight adaptation, this heuristic is applicable to not only highway arterials with
interrupted traffic but also uninterrupted freeway traffic. We generalize the time geography theory to consider
finite accelerations. This allows us to study the behavior of the proposed algorithms. We find that the
proposed algorithms can always find a feasible solution to the original complex multi-trajectory control

32

0

Error (m)

−100

−200
minD (pn − qn ) measured
Lower bound
D (qn − pn ) measured
Upper bound

−300

−400

0.5

1

1.5

2

2.5

3

γ
Figure 13: Measured errors between KWT solution Q and SHL solution P LVP (γā, γa) v.s. their bounds .
problem under certain mild conditions. We further point out that the shooting heuristic solution to the
lead vehicle problem can be viewed as a smoothed version of the classic kinematic theory’s result. We
find that the kinematic wave theory is essentially a special case of the proposed shooting heuristic with
infinite accelerations. Further, the difference between the shooting heuristic solution and the kinematic wave
solution is found to be limited within two theoretical bounds independent of the size of the vehicles in the
studied traffic stream. Numerical experiments are conducted to illustrate some theoretical results and draw
additional insights into how the proposed algorithms can improve highway traffic.
This paper provides a methodological and theoretical foundation for management of future CAV traffic.
The following part II paper Ma et al. (2015) of this study will apply the proposed constructive heuristic with
given acceleration rates to a trajectory optimization framework that optimizes the overall performance of
CAV traffic (e.g., in terms of mobility, environment impacts and safety) by finding the best acceleration rates.
Theoretical results and numerical examples on this optimization framework will be presented. This study
overall expects to provide both theoretical principles and application guidance for upgrading the existing
highway traffic management systems with emerging CAV technologies. It can be extended in a number of
directions to address practical challenges and emerging opportunities in deploying CAV technologies, such
as calibration with field experiments, more complex geometries, heterogeneous vehicles, and mixed manual
and automated traffic.

Acknowledgments
This research is supported in part by the U.S. National Science Foundation through Grants CMMI CAREER#1453949, CMMI #1234936 and CMMI #1541130 and by the U.S. Federal Highway Administration
through Grant DTFH61-12-D-00020.

References
Ahn, K., Rakha, H., Park, S., 2013. Ecodrive application: Algorithmic development and preliminary testing.
Transportation Research Record: Journal of the Transportation Research Board (2341), 1–11.
Ahn, S., 2005. Formation and spatial evolution of traffic oscillations. Ph.D. thesis, University of California,
Berkeley, Berkeley, California.
Apostol, T. M., 1969. Calculus, vol. ii. Ed Reverté.
33

Bando, M., Hasebe, K., Nakanishi, K., Nakayama, A., 1998. Analysis of optimal velocity model with explicit
delay. Physical Review E 58 (5), 5429–5435.
Bando, M., Hasebe, K., Nakayama, A., Shibata, A., Sugiyama, Y., 1995. Dynamical model of traffic congestion and numerical simulation. Physical Review E 51 (2), 1035–1042.
Beard, G. F., Griffin, M. J., 2013. Discomfort during lateral acceleration: Influence of seat cushion and
backrest. Applied ergonomics 44 (4), 588–594.
Bham, G. H., Long, S., Baik, H., Ryan, T., Gentry, L., Lall, K., Arezoumandi, M., Liu, D., Li, T., Schaeffer,
B., 2010. Evaluation of variable speed limits on i-270/i-255 in st. louis. Tech. rep.
Brackstone, M., McDonald, M., 1999. Car-following: a historical review. Transportation Research Part F:
Traffic Psychology and Behaviour 2 (4), 181 – 196.
Cassidy, M., Bertini, R., 1999. Some traffic features at freeway bottlenecks. Transportation Research Part B
33 (1), 25–42.
Chandler, R. E., Herman, R., Montroll, E. W., 1958. Traffic dynamics: Studies in car following. Operations
Research 6 (2), 165–184.
Daganzo, C. F., 1994. The cell transmission model: A dynamic representation of highway traffic consistent
with the hydrodynamic theory. Transportation Research Part B: Methodological 28 (4), 269 – 287.
Daganzo, C. F., 2006. In traffic flow, cellular automata=kinematic waves. Transportation Research Part B:
Methodological 40 (5), 396 – 403.
Daganzo, C. F., Cassidy, M. J., Bertini, R. L., 1999. Possible explanations of phase transitions in highway
traffic. Transportation Research Part A: Policy and Practice 33 (5), 365–379.
De Nunzio, G., Canudas de Wit, C., Moulin, P., Di Domenico, D., 2013. Eco-driving in urban traffic networks
using traffic signal information. In: Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on.
IEEE, pp. 892–898.
Dresner, K., Stone, P., 2008. A multiagent approach to autonomous intersection management. Journal of
Artificial Intelligence Research 31, 591–656.
Guan, T., Frey, C. W., 2013. Predictive fuel efficiency optimization using traffic light timings and fuel consumption model. In: Intelligent Transportation Systems-(ITSC), 2013 16th International IEEE Conference
on. IEEE, pp. 1553–1558.
Hegyi, A., De Schutter, B., Hellendoorn, H., 2005. Model predictive control for optimal coordination of
ramp metering and variable speed limits. Transportation Research Part C: Emerging Technologies 13 (3),
185–209.
Herman, R., Montroll, E. W., Potts, R. B., Rothery, R. W., 1958. Traffic dynamics: Analysis of stability in
car following. Operations Research 7 (1), 86–106.
Hoffmann, E. R., Mortimer, R. G., 1994. Drivers’ estimates of time to collision. Accident Analysis & Prevention 26 (4), 511–520.
Hooker, J., 1988. Optimal driving for single-vehicle fuel economy. Transportation Research Part A: General
22 (3), 183–201.
Iglesias, I., Isasi, L., Larburu, M., Martinez, V., Molinete, B., 2008. I2v communication driving assistance
system: on-board traffic light assistant. In: Vehicular Technology Conference, 2008. VTC 2008-Fall. IEEE
68th. IEEE, pp. 1–5.

34

Islam, M., Hadiuzzaman, M., Fang, J., Qiu, T., El-Basyouny, K., 2013. Assessing mobility and safety impacts
of a variable speed limit control strategy. Transportation Research Record: Journal of the Transportation
Research Board (2364), 1–11.
Kamalanathsharma, R. K., Rakha, H., et al., 2013. Multi-stage dynamic programming algorithm for ecospeed control at traffic signalized intersections. In: Intelligent Transportation Systems-(ITSC), 2013 16th
International IEEE Conference on. IEEE, pp. 2094–2099.
Kerner, B., 1998. Experimental features of self-organization in traffic flow. Physical Review Letter 81 (17),
3797–3800.
Kerner, B., Rehborn, H., 1996. Experimental properties of complexity in traffic flow. Physical Review E
53 (5), R4275–R4278.
Kerner, B. S., Rehborn, H., 1997. Experimental properties of phase transitions in traffic flow. Physical Review
Letters 79 (20), 4030–4033.
Kuhne, R. D., 1987. Freeway speed distribution and acceleration noise. In: Gartner, N. H., Wilson, N. H.
(Eds.), Proceedings of the 10th International Symposium on Transportation and Traffic Theory. pp. 119–
137.
Laval, J. A., 2011a. Hysteresis in traffic flow revisited: An improved measurement method. Transportation
Research Part B 45 (2), 385 – 391.
Laval, J. A., 2011b. Hysteresis in traffic flow revisited: An improved measurement method. Transportation
Research Part B 45 (2), 385 – 391.
Lee, J., Park, B., 2012a. Development and evaluation of a cooperative vehicle intersection control algorithm
under the connected vehicles environment. Intelligent Transportation Systems, IEEE Transactions on
13 (1), 81–90.
Lee, J., Park, B., 2012b. Development and evaluation of a cooperative vehicle intersection control algorithm
under the connected vehicles environment. Intelligent Transportation Systems, IEEE Transactions on
13 (1), 81–90.
Li, X., Cui, J., An, S., Parsafard, M., 2014. Stop-and-go traffic analysis: Theoretical properties, environmental impacts and oscillation mitigation. Transportation Research Part B: Methodological 70, 319–339.
Li, X., Ouyang, Y., 2011. Characterization of traffic oscillation propagation under nonlinear car-following
laws. Transportation Research Part B 45 (9), 1346–1361.
Lighthill, M. J., Whitham, G. B., 1955. On Kinematic Waves. II. A Theory of Traffic Flow on Long Crowded
Roads. Royal Society of London Proceedings Series A 229, 317–345.
Liu, B., Ghosal, D., Chuah, C.-N., Zhang, H. M., 2012. Reducing greenhouse effects via fuel consumptionaware variable speed limit (fc-vsl). Vehicular Technology, IEEE Transactions on 61 (1), 111–122.
Lu, X.-Y., Shladover, S., 2014. Review of variable speed limits and advisories: Theory, algorithms, and
practice. Transportation Research Record: Journal of the Transportation Research Board (2423), 15–23.
Ma, J., Li, X., Zhou, F., Hu, J., Park, B., 2015. A parsimonious two-way shooting algorithm for connected
automated traffic smoothing part ii: Optimization framework. Working paper, Mississippi State University.
Mandava, S., Boriboonsomsin, K., Barth, M., 2009. Arterial velocity planning based on traffic signal information under light traffic conditions. In: Intelligent Transportation Systems, 2009. ITSC’09. 12th International IEEE Conference on. IEEE, pp. 1–6.

35

Mauch, M., Cassidy, M., 2002. Freeway traffic oscillations: observations and predictions. In: Taylor, M. A.
(Ed.), Proceedings of the 15th International Symposium on Transportation and Traffic Theory. pp. 653–
674.
Miller, H. J., 2005. A measurement theory for time geography. Geographical analysis 37 (1), 17–45.
Nagel, K., Schreckenberg, M., 1992. A cellular automaton model for freeway traffic. Journal de Physique I
2 (12), 2221–2229.
Newell, G. F., 1993. A simplified theory of kinematic waves in highway traffic, part i: general theory.
Transportation Research Part B: Methodological 27 (4), 281–287.
Newell, G. F., 2002. A simplified car-following theory: a lower order model. Transportation Research Part
B 36 (3), 195 – 205.
Rakha, H., Kamalanathsharma, R. K., 2011. Eco-driving at signalized intersections using v2i communication.
In: Intelligent Transportation Systems (ITSC), 2011 14th International IEEE Conference on. IEEE, pp.
341–346.
Richards, P. I., 1956. Shock Waves on the Highway . Operations Research 4 (1), 42–51.
Sanchez, M., Cano, J.-C., Kim, D., 2006. Predicting traffic lights to improve urban traffic fuel consumption.
In: 2006 6th International Conference on ITS Telecommunications.
Schwarzkopf, A., Leipnik, R., 1977. Control of highway vehicles for minimum fuel consumption over varying
terrain. Transportation Research 11 (4), 279–286.
Shladover, S. E., Nowakowski, C., Cody, D., Bu, F., O′ Connell, J., Spring, J., Dickey, S., Nelson, D., 2009.
Effects of cooperative adaptive cruise control on traffic flow: Testing drivers′ choices of following distances.
Tech. Rep. UCB-ITS-PRR-2009-23, California PATH, Berkeley, CA.
Spiliopoulou, A. D., Papamichail, I., Papageorgiou, M., 2009. Toll plaza merging traffic control for throughput
maximization. Journal of Transportation Engineering 136 (1), 67–76.
Tielert, T., Killat, M., Hartenstein, H., Luz, R., Hausberger, S., Benz, T., 2010. The impact of traffic-lightto-vehicle communication on fuel consumption and emissions. In: Internet of Things (IOT), 2010. IEEE,
pp. 1–8.
Trayford, R., Doughty, B., van der Touw, J., 1984a. Fuel economy investigation of dynamic advisory speeds
from an experiment in arterial traffic. Transportation Research Part A: General 18 (5), 415–419.
Trayford, R., Doughty, B., Wooldridge, M., 1984b. Fuel saving and other benefits of dynamic advisory speeds
on a multi-lane arterial road. Transportation Research Part A: General 18 (5), 421–429.
Treiber, M., Hennecke, A., Helbing, D., 2000. Congested traffic states in empirical observations and microscopic simulations. Physical Review E 62 (2), 1805–1824.
Treiber, M., Kesting, A., Helbing, D., 2010. Three-phase traffic theory and two-phase models with a fundamental diagram in the light of empirical stylized facts. Transportation Research Part B: Methodological
44 (8), 983–1000.
Van Arem, B., van Driel, C., Visser, R., 2006. The impact of cooperative adaptive cruise control on traffic-flow
characteristics. Intelligent Transportation Systems, IEEE Transactions on 7 (4), 429–436.
Von Stryk, O., Bulirsch, R., 1992. Direct and indirect methods for trajectory optimization. Annals of operations research 37 (1), 357–373.

36

Wang, M., Daamen, W., Hoogendoorn, S. P., van Arem, B., 2014a. Rolling horizon control framework for
driver assistance systems. part i: Mathematical formulation and non-cooperative systems. Transportation
Research Part C: Emerging Technologies 40, 271–289.
Wang, M., Daamen, W., Hoogendoorn, S. P., van Arem, B., 2014b. Rolling horizon control framework for
driver assistance systems. part ii: Cooperative sensing and cooperative control. Transportation Research
Part C: Emerging Technologies 40, 290–311.
Wu, G., Boriboonsomsin, K., Zhang, W.-B., Li, M., Barth, M., 2010. Energy and emission benefit comparison
of stationary and in-vehicle advanced driving alert systems. Transportation Research Record: Journal of
the Transportation Research Board (2189), 98–106.
Wu, X., He, X., Yu, G., Harmandayan, A., Wang, Y., 2015. Energy-optimal speed control for electric vehicles
on signalized arterials. Intelligent Transportation Systems, IEEE Transactions on PP (99), 1–11.
Yang, H., Jin, W.-L., 2014. A control theoretic formulation ofgreen driving strategies based on inter-vehicle
communications. Transportation Research Part C: Emerging Technologies 41, 48–60.
Zohdy, I. H., Rakha, H. A., 2014. Intersection management via vehicle connectivity: The intersection cooperative adaptive cruise control system concept. Journal of Intelligent Transportation Systems (ahead-of-print),
1–16.

37

