# Optimal driving strategies for a fleet of trains on level track with
prescribed intermediate signal times and safe separation

Phil Howlett111Email<EMAIL_ADDRESS>Peter Pudney222Email:
<EMAIL_ADDRESS>Amie Albrecht333Email<EMAIL_ADDRESS>
(11 February 2022)

###### Abstract

We propose an analytic solution to the problem of finding optimal driving
strategies that minimize total tractive energy consumption for a fleet of
trains travelling on the same track in the same direction subject to
clearance-time equality constraints that ensure safe separation and compress
the line-occupancy timespan. We assume the track is divided into sections by a
set of trackside signals at fixed locations. For each intermediate signal
there is a signal-location segment consisting of the two adjacent sections.
Successive trains are safely separated only if the leading train leaves each
signal-location segment before the following train enters. The fleet can be
safely separated by a complete set of clearance times and associated
clearance-time inequality constraints. The problem of finding optimal
schedules with safe separation has been solved for two trains but for larger
fleets the problem rapidly becomes intractable as the number of trains and
signals increases. The main difficulty is in distinguishing between active
equality constraints and inactive inequality constraints. The curse of
dimensionality means it is not feasible to check every different combination
of active constraints, optimize the corresponding prescribed times and
calculate the cost. Nevertheless we can formulate and solve an alternative
problem with active clearance-time equality constraints for successive trains
on every signal-location segment. We show that this problem can be formulated
as an unconstrained convex optimization and we propose a viable solution
algorithm that finds the optimal schedule and the associated optimal
strategies for each train. Finally we use our solution to find optimal
schedules for a busy inter-city shuttle service.

Keywords: transportation, train control, safe separation, optimal schedules

##  1 Introduction

In modern rail networks train movements are planned to follow strict
timetables that allow coordinated operation of the entire network. Drivers are
encouraged to use energy-efficient driving strategies but are expected to
reach key locations at predetermined times or within prescribed time windows.
Despite these expectations network safety is paramount and drivers must always
comply with safe-operating instructions from the signalling system.

A safe-operating environment has traditionally been enabled using a system of
trackside signals at fixed locations. These signals divide the track into
sections. A three-aspect signalling system shows a green light if the next two
sections of track are clear, a yellow light if the next section is clear but
the section after that is occupied, and a red light if the next section is
occupied. A driver will follow the planned schedule when the train passes a
green signal but if the train passes a yellow signal the driver must follow a
modified speed profile so that the train can stop at the next signal if it
remains red. The train must not pass a red signal. In normal operation trains
will be separated by at least two fixed signals and one intervening clear
section of track. The signalling system ensures that trains are adequately
warned about unscheduled disruptions.

In this paper we wish to find an optimal schedule for a fleet of trains
travelling on the same track in the same direction. The trains must remain
safely separated at all times. In order to clarify our presentation the
remainder of the introduction is organised into separate sections—each one
with a specific objective. Some relate to the problem at hand while others
relate to essential background material. In Section 1.1 we state a preliminary
version of the problem. In Section 1.2 we explain how intermediate segment
clearance times can be used to ensure that successive trains are safely
separated. Section 1.3 introduces the technical basis for the paper—the
equations of motion—and Section 1.4 describes the general structural forms for
the strategies of optimal type. These strategies provide the framework for a
theory of optimal scheduling. Section 1.5 describes a typical solution to the
two-train separation problem. In Section 1.6 the general train separation
problem is formulated as two distinct problems. The first problem is to find
an optimal strategy for each train if the stopping patterns are known and the
prescribed signal-location times are also known. This problem has been solved.
The second problem is to find a set of optimal prescribed intermediate
clearance times that ensures safe separation and minimizes total energy
consumption for the fleet. This problem has not been solved in any realistic
sense because the number of combinations of active constraints which must be
checked increases exponentially as the number of trains and signals increases.
In Section 1.7 we describe our main theoretical result—formulation and
solution of an alternative train separation problem where a fleet of non-
identical trains is separated by a complete set of active clearance-time
equality constraints and the task is to find the optimal clearance times. We
explain briefly how our solution can be extended to include additional buffer
times between trains and how it can be relaxed by omitting some constraints.
Section 1.8 simply notes that we apply our results to a case study of a busy
inter-city shuttle service. Section 1.9 discusses the role of the train
performance functions and Section 1.10 reviews our terminology.

###  1.1 A preliminary problem formulation

We consider a fleet of $m$ successive trains travelling in the same direction
on a level track with $n+1$ signals at locations
$0=x_{0}<x_{1}<\cdots<x_{n-1}<x_{n}=X$. For each $i=1,\ldots,m$ the journey
for train ${\mathfrak{T}}_{i}$ is completely defined by the speed $v_{i}(x)$
and the elapsed journey time $t_{i}(x)$ at position $x\in[0,X]$. We assume
that the schedule for ${\mathfrak{T}}_{i}$ is defined by a vector
$\mbox{$\mbox{\boldmath$h$}$}_{i}=[h_{i,j}]_{j=0}^{n}$ of signal location
times with $t_{i}(x_{j})=h_{i,j}$ for each $i=1,\ldots,m$ and $j=0,\ldots,n$.
If ${\mathfrak{T}}_{i}$ is scheduled to stop at $x_{j}$ then we assume that
$h_{i,j}$ is the departure time and that the stopping time $\sigma_{i,j}$ is
known. We wish to find a schedule
$\mbox{$\mbox{\boldmath$h$}$}=[\mbox{$\mbox{\boldmath$h$}$}_{1},\ldots,\mbox{$\mbox{\boldmath$h$}$}_{m}]$
for the entire fleet that minimizes total energy consumption, allows each
train to finish the journey on time and ensures that successive trains are
safely separated at all times.

###  1.2 A safe separation scheme

For each $j=1,\ldots,n$ we define a signal-location segment
${\mathfrak{S}}_{j}=[x_{j-1},x_{j}]\cup[x_{j},x_{j+1}]=[x_{j-1},x_{j+1}]$.
Safe separation for successive trains ${\mathfrak{T}}_{i}$ and
${\mathfrak{T}}_{i+1}$ can be enforced by prescribing segment-clearance times
that define the latest allowed exit time for ${\mathfrak{T}}_{i}$ and the
earliest allowed entry time for ${\mathfrak{T}}_{i+1}$. The leading train
${\mathfrak{T}}_{i}$ must leave the segment before the following train
${\mathfrak{T}}_{i+1}$ enters. Thus we require $h_{i,j+1}=t_{i}(x_{j+1})\leq
t_{i+1}(x_{j-1})=h_{i+1,j-1}$ for all $i=1,\ldots,m-1$ and $j=1,\ldots,n-1$.
We could define a safe theoretical schedule by setting $h_{i+1,j-1}=h_{i,j+1}$
but in practice train operators allow for normal stochastic variation in
journey times by inserting additional buffer times. Thus, in practice, we may
wish to set $h_{i+1,j-1}=h_{i,j+1}+\delta_{i}$ where $\delta_{i}>0$ for each
$i=1,\ldots,m-1$ and each $j=1,\ldots,n-1$.

###  1.3 The equations of motion for realistic strategies

We formulate the equations of motion with position $x\in[0,X]$ as the
independent variable and with speed $v=v(x)\in[0,\infty)$ and time
$t=t(x)\in[0,T]$ as dependent state variables. The equations are

$\displaystyle v^{\,\prime}$ $\displaystyle=$ $\displaystyle[u-r(v)+g(x)]/v$
(1) $\displaystyle t^{\,\prime}$ $\displaystyle=$ $\displaystyle 1/v$ (2)

where $(v,t)=(v(x),t(x))$ is the state variable vector for $x\in[0,X]$ and
where $u=u(x)\in{\mathbb{R}}$ is the known measurable control—the force per
unit mass or acceleration. We have written $v^{\,\prime}=dv/dx$ and
$t^{\,\prime}=dt/dx$. This formulation decouples the dependent variables and
allows us to solve (1) for $v=v(x)$ with no knowledge of $t=t(x)$. We measure
distance in metres (m) and time in seconds (s).

For a journey from $x_{k-1}$ to $x_{\ell}$ where $1\leq k\leq\ell\leq n$ we
assume that $v(x_{k-1})=v(x_{\ell})=0$ with $v(x)>0$ for all
$x\in(x_{k-1},x_{\ell})$ and that $u(x)$ is bounded with $K[v(x)]\leq u(x)\leq
H[v(x)]$ for each $x\in(x_{k-1},x_{\ell})$. The bounds $K=K(v)\in(-\infty,0)$
and $H=H(v)\in(0,\infty)$ for $v\in(0,\infty)$ are monotone functions with
$K(v)\uparrow 0$ and $H(v)\downarrow 0$ as $v\uparrow\infty$. The functions
$K$ and $H$ define bounds for the maximum braking and driving forces per unit
mass in a form that includes—as special cases—the specified bounds for a wide
range of modern electric and diesel-electric locomotives. The function $r(v)$
is a general resistance per unit mass with no specific formula assumed. We
define auxiliary functions $\varphi(v)=vr(v)$ and
$\psi(v)=v^{2}r^{\,\prime}(v)$ and assume only that $\varphi(v)$ is strictly
convex with $\varphi(v)\geq 0$ for $v\geq 0$ and
$\varphi(v)/v\rightarrow\infty$ as $v\rightarrow\infty$. See [Howlett and
Cheng (1997), Appendix A.3, p 409] for an explanation. It follows that both
$r(v)$ and $\psi(v)$ are non-negative and strictly increasing for $v\geq 0$.
These properties capture the functional characteristics of the traditional
quadratic resistance formula—the so-called Davis formula [Davis (1926)]. The
function $g(x)$ is nominally the component of gravitational acceleration due
to track gradient but in practice may also include additional position-
dependent resistive forces. The cost is net mechanical energy usage per unit
mass,

$J_{k-1,\ell}=\int_{x_{k-1}}^{x_{\ell}}(1/2)[u(x)+|u(x)|]\,dx.$ (3)

See [Albrecht et al. (2015c), Albrecht et al. (2015d), Howlett and Cheng
(1997)] and the original papers [Howlett (2000), Khmelnitsky (2000), Liu and
Golovitcher (2003)] for more information. The equations (1) and (2) describe
the motion of a point-mass train. It is known [Howlett and Pudney (1995),
Section 2.3, pp 23–24] that the motion of a train with distributed mass can be
modelled as the motion of a point-mass train on a track with modified
gradient. In this paper we assume that energy recovered from regenerative
braking is not used to drive the train. This assumption spawns a more relaxed
optimal driving strategy that encourages coasting and discourages braking. We
also assume that the track is level with $g(x)=0$ for all $x\in[0,X]$.

###  1.4 The strategies of optimal type

For a fleet of $m$ trains with scheduled signal times $h_{i,j}$ at each
$x_{j}$ the optimal strategy for train ${\mathfrak{T}}_{i}$ will be a sequence
of optimal strategies for a succession of smaller journeys between scheduled
stops. Some of these strategies will be simple strategies for journeys on
single sections $[x_{k-1},x_{k}]$ with initial and final speeds
$v_{i}(x_{k-1})=v_{i}(x_{k})=0$ and with initial and final time constraints
$t_{i}(x_{k-1})=h_{i,k-1}$ and $t_{i}(x_{k})=h_{i,k}-\sigma_{i,k}$ where
$\sigma_{i,k}$ is the stopping time at $x_{k}$ but with no intermediate time
constraints. Others will be more complex strategies for journeys on composite
segments $[x_{k-1},x_{\ell}]$ where $k<\ell$ with initial and final speeds
$v_{i}(x_{k-1})=v_{i}(x_{\ell})=0$, initial and final time constraints
$t_{i}(x_{k-1})=h_{i,k-1}$ and $t_{i}(x_{\ell})=h_{i,\ell}-\sigma_{i,\ell}$
where $\sigma_{i,\ell}$ is the stopping time at $x_{\ell}$ and intermediate
time constraints $t_{i}(x_{j})=h_{i,j}$ for each $j=k,\ldots,\ell-1$ but no
intermediate stops.

The Pontryagin principle shows that only certain control modes are allowed in
an optimal strategy [Albrecht et al. (2015c), Section 3, pp 489–507]. There
are three permissible regular modes—maximum acceleration, coast and maximum
brake—and one singular mode—speedhold with partial acceleration. For trains
with regenerative braking there is another permissible singular mode—speedhold
with partial brake. These rules are independent of the initial and final
speeds and apply on both level and nonlevel tracks. A strategy that is
generated entirely by a sequence of permissible optimal control modes is
called a strategy of optimal type.

For journeys with $v(0)=v(X)=0$ and no intermediate time constraints the
minimum possible journey time $T_{\min}$ has only two phases—maximum
acceleration to some speed $V_{\max}$ and maximum brake. For $T>T_{\min}$
there is always a rapid-transit strategy of optimal type consisting of a phase
of maximum acceleration to speed $V_{\max}$, coast to speed $U$ and maximum
brake. The values of $V_{\max}$ and $U$ are uniquely determined by the
distance and time constraints

$X=\int_{0}^{V_{\max}}dx_{a}(v)+\int_{U}^{V_{\max}}|dx_{c}(v)|+\int_{0}^{U}|dx_{b}(v)|$
(4)

and

$T=\int_{0}^{V_{\max}}dt_{a}(v)+\int_{U}^{V_{\max}}|dt_{c}(v)|+\int_{0}^{U}|dt_{b}(v)|$
(5)

where the distance and time differentials for maximum acceleration, coast and
maximum brake are defined respectively from (1) and (2) by

$dx_{a}(v)=vdt_{a}(v)=vdv/[H(v)-r(v)],$ (6) $dx_{c}(v)=vdt_{c}(v)=-vdv/r(v)$
(7)

and

$dx_{b}(v)=vdt_{b}(v)=-vdv/[K(v)+r(v)]$ (8)

for $v\in[0,V_{\sup})$ where $v=V_{\sup}$ is the upper bound on the speed
obtained by solving the equation $H(v)-r(v)=0$. The rapid-transit strategy is
optimal only if $U>U_{b}(V_{\max})$ where

$U_{b}(v)=\psi(v)/\varphi^{\,\prime}(v).$ (9)

If the rapid-transit strategy is not optimal then the optimal strategy is a
long-haul strategy of optimal type defined by a phase of maximum acceleration
to speed $V$, speedhold at speed $V$, coast to speed $U=U_{b}(v)$ and maximum
brake. The length of the speedhold segment is defined by

$\xi(V)=X-\left[\int_{0}^{V}dx_{a}(v)+\int_{U_{b}(V)}^{V}|dx_{c}(v)|+\int_{0}^{U_{b}(V)}|dx_{b}(v)|\right]$
(10)

and $V$ is uniquely determined by the time constraint

$T=\int_{0}^{V}dt_{a}(v)+\xi(V)/V+\int_{U_{b}(V)}^{V}|dt_{c}(v)|+\int_{0}^{U_{b}(V)}|dt_{b}(v)|.$
(11)

The Pontryagin principle shows that each strategy of optimal type is uniquely
defined by an optimal driving speed. For a long-haul strategy the optimal
driving speed is the speed $V$ on the speedhold segment. If the rapid-transit
strategy is optimal then the optimal driving speed is defined by
$\psi(V)=\varphi(V_{\max})U/(V_{\max}-U)\iff
U=V_{\max}-V_{\max}\varphi(V_{\max})/[\psi(V)+\varphi(V_{\max})]$. In this
case $V>V_{\max}$ and $U>U_{b}(V_{\max})$. See [Albrecht et al. (2015c),
Section 3.6, pp 494–497] for a detailed discussion.

Now consider a journey with initial and final speeds $v(0)=v(X)=0$, initial
and final times $t(0)=0$ and $t(X)=T$, and prescribed intermediate times
$t(x_{j})=h_{j}$ for each $j=1,\ldots,n-1$ but no intermediate stops. If the
section times $h_{j}-h_{j-1}$ are sufficiently large for each $j=1,\ldots,n$
then an optimal strategy exists and there is an optimal driving speed $V_{j}$
on each timed section. On $(x_{0},x_{1})$ the strategy is maximum
acceleration, speedhold at speed $V_{1}$ on some interval
$[a_{1},b_{1}]\subset(x_{0},x_{1})$ and either maximum acceleration or coast
to speed $v(x_{1})=U_{1}=U_{s}(V_{1},V_{2})$ where

$U_{s}(v,w)=[\psi(v)-\psi(w)]/[\varphi^{\,\prime}(v)-\varphi^{\,\prime}(w)].$
(12)

In general, on $(x_{j-1},x_{j})$ for $j=2,\ldots,n-1$ the strategy is either
maximum acceleration or coast from speed
$v(x_{j-1})=U_{j-1}=U_{s}(V_{j-1},V_{j})$ to speed $V_{j}$, speedhold at speed
$V_{j}$ on some interval $[a_{j},b_{j}]\subset(x_{j-1},x_{j})$, and either
maximum acceleration or coast to speed $v(x_{j})=U_{j}=U_{s}(V_{j},V_{j+1})$.
On $(x_{n-1},x_{n})$ the strategy is either maximum acceleration or coast from
speed $v(x_{n-1})=U_{n-1}=U_{s}(V_{n-1},V_{n})$ to speed $V_{n}$, speedhold at
speed $V_{n}$, coast to speed $U_{n}=U_{b}(V_{n})$ and maximum brake. The
transition phase on $(b_{j},a_{j+1})$ is maximum acceleration if
$V_{j+1}>V_{j}$ and coast if $V_{j+1}<V_{j}$. If there is insufficient time
for a speedhold phase on the final section $(x_{n-1},x_{n})$ of the journey
the strategy is maximum acceleration from speed
$v(x_{n-1})=U_{n-1}=U_{s}^{{\dagger}}(U_{n},V_{n-1},V_{\max,n})$ to a maximum
speed $V_{\max,n}$, coast to speed $U_{n}$ and maximum brake where

$U_{s}^{{\dagger}}(u,v,w)=\frac{\varphi(w)u/(w-u)-\psi(v)}{\varphi(w)/(w-u)-\varphi^{\,\prime}(v)}.$
(13)

The optimal driving speeds $\\{V_{j}\\}_{j=1}^{n-1}$ and the speeds
$V_{\max,n}$ and $U_{n}$ are determined by the time constraints on each
section and the distance constraint on the final section. We still have
$v(x_{j})=U_{j}=U_{s}(V_{j},V_{j+1})$ for $j=1,\ldots,n-2$. The optimal
driving speed $V_{n}$ on $(x_{n-1},x_{n})$ is defined by
$\psi(V_{n})=\varphi(V_{\max,n})U_{n}/(V_{\max,n}-U_{n})$. We also have
$V_{n}>V_{\max,n}$ and $U_{n}>U_{b}(V_{\max,n})$.

###  1.5 The two-train separation problem

Much of the train separation work has been done for a fleet of two trains. For
each train the optimal strategy is defined by a sequence of optimal driving
speeds. For the leading train $\\{V_{\ell,j}\\}_{j=1}^{n}$ is a decreasing
sequence and for the following train $\\{V_{f,j}\\}_{j=1}^{n}$ is an
increasing sequence. See [Albrecht, Howlett, and Pudney (2020)]. The graphs in
Figure 1 depict the optimal solution to a two-train separation problem on
level track [Albrecht, Howlett, and Pudney (2020), Section VII, Example 3,
Figure 4]. The speed profiles are shown on the left for the leading train
${\mathfrak{T}}_{\ell}$ and in the centre for the following train
${\mathfrak{T}}_{f}$. Only one active time constraint is required to ensure
safe separation. The optimal clearance time
$t_{\ell}(x_{5})=t_{f}(x_{3})=h_{4}$ on segment
${\mathfrak{S}}_{4}=[x_{3},x_{4}]\cup[x_{4},x_{5}]=[x_{3},x_{5}]$ minimizes
total energy consumption. The train graph shows that the trains are safely
separated.

Figure 1: A typical two train separation problem with distance $X$ and time
$T$ and signal locations
$\mbox{$\mbox{\boldmath$x$}$}=(x_{0}=0,x_{1},\ldots,x_{7},x_{8}=X)$ showing
optimal speed profiles for the leading train ${\mathfrak{T}}_{\ell}$ (left)
and following train ${\mathfrak{T}}_{f}$ (centre). The train graph (right)
shows one clear section between ${\mathfrak{T}}_{\ell}$ and
${\mathfrak{T}}_{f}$ at all times. There is one active time constraint on
${\mathfrak{S}}_{4}$ with $t_{\ell}(x_{5})=t_{f}(x_{3})=h_{4}$.

When speed limits are imposed the optimal strategies are not changed
substantially but the speed limits must be enforced [Howlett, Milroy and
Pudney, (1994), Pudney and Howlett (1994)]. We will not consider speed limits
here but we note that the very nature of optimal strategies ensures that
speeds must be kept as low as possible. Thus virtual speed limits are imposed.

###  1.6 A general formulation of the train separation problem

The task of designing optimal strategies for a fleet of trains travelling on
the same track in the same direction subject to conditions of safe separation
can be formulated as two distinct problems.

###### Problem 1

Let
$\mbox{$\mbox{\boldmath$h$}$}=[\mbox{$\mbox{\boldmath$h$}$}_{1},\ldots,\mbox{$\mbox{\boldmath$h$}$}_{m}]$,
where $\mbox{$\mbox{\boldmath$h$}$}_{i}=[h_{i,j}]_{j\in{\mathcal{C}}_{i}}$ is
a given set of prescribed signal times for train ${\mathfrak{T}}_{i}$ on some
subset ${\mathcal{C}}_{i}\subset\\{0,\ldots,n\\}$ of signal-location indices
which includes the indices of all scheduled stops. Suppose the set of
clearance-time constraints $t_{i}(x_{j})=h_{i,j}$ for each $i=1,\ldots,m$ and
each $j\in{\mathcal{C}}_{i}$ is sufficient to ensure safe separation. Let
${\mathcal{U}}(\mbox{$\mbox{\boldmath$h$}$})$ be the set of feasible controls.
Find a control vector
$\mbox{$\mbox{\boldmath$u$}$}=\mbox{$\mbox{\boldmath$u$}$}(x)$ where
$\mbox{$\mbox{\boldmath$u$}$}=[u_{1},\ldots,u_{m}]\in{\mathcal{U}}(\mbox{$\mbox{\boldmath$h$}$})$
and $u_{i}=u_{i}(x)$ is the control function for ${\mathfrak{T}}_{i}$ and the
associated speed profile vector
$\mbox{$\mbox{\boldmath$v$}$}=\mbox{$\mbox{\boldmath$v$}$}(x)$ where
$\mbox{$\mbox{\boldmath$v$}$}=[v_{1},\ldots,v_{m}]$ and $v_{i}=v_{i}(x)$ is
the speed profile for ${\mathfrak{T}}_{i}$, such that the constraints are
satisfied and tractive energy consumption
$J=J(\mbox{$\mbox{\boldmath$u$}$},\mbox{$\mbox{\boldmath$h$}$})$ is minimized.
That is find
$\mbox{$\mbox{\boldmath$u$}$}=\mbox{$\mbox{\boldmath$u$}$}_{\mbox{$\mbox{\boldmath\scriptsize$h$}$}}$
such that
$J(\mbox{$\mbox{\boldmath$h$}$})=J(\mbox{$\mbox{\boldmath$u$}$}_{\mbox{$\mbox{\boldmath\scriptsize$h$}$}},\mbox{$\mbox{\boldmath$h$}$})=\min\\{J(\mbox{$\mbox{\boldmath$u$}$},\mbox{$\mbox{\boldmath$h$}$})\mid\mbox{$\mbox{\boldmath$u$}$}\in{\mathcal{U}}(\mbox{$\mbox{\boldmath$h$}$})\\}$.
$\hfill\Box$

###### Problem 2

Find necessary conditions for a vector $\mbox{$\mbox{\boldmath$h$}$}_{0}$ of
optimal prescribed clearance times that minimizes the total tractive energy
$J(\mbox{$\mbox{\boldmath$h$}$})$ consumed by the fleet over all
$\mbox{$\mbox{\boldmath$h$}$}\in{\mathcal{H}}$, where ${\mathcal{H}}$ denotes
the collection of all feasible sets of prescribed clearance-time constraints
that ensure safe separation for the given stopping plan. Thus
$J_{0}=J(\mbox{$\mbox{\boldmath$h$}$}_{0})=\min\\{J(\mbox{$\mbox{\boldmath$h$}$})\mid\mbox{$\mbox{\boldmath$h$}$}\in{\mathcal{H}}\\}$.
$\hfill\Box$

Problem 1 has been solved. If train ${\mathfrak{T}}$ must pass certain signal
locations at known times and there are no other active time constraints the
precise form of the optimal strategy is known [Albrecht et al. (2015a),
Albrecht et al. (2015b)] and successful computational algorithms can be used
on level track to calculate the optimal speed profile [Albrecht, Howlett, and
Pudney (2020)]. When the set of active clearance times is known for each train
in the fleet the individual optimal strategies can be computed separately
[Albrecht, Howlett, and Pudney (2020)].

Problem 2 has been partially solved. Necessary conditions are known in various
forms for the two-train separation problem [Albrecht et al. (2015a), Albrecht
et al. (2015b), Albrecht et al. (2018)] and more recently in [Albrecht,
Howlett, and Pudney (2020)]. Similar necessary conditions are also known for
the three-train separation problem [Albrecht et al. (2018), Section 16, pp
162–165] and it is clear that the same arguments and conclusions will remain
valid for a fleet of more than three trains. However computation of the
optimal solution—an optimal speed profile for each train in the fleet—depends
on knowing the locations of the active constraints. Safe separation requires
$t_{i}(x_{j+1})\leq t_{i+1}(x_{j-1})$ for each $i=1,\ldots m-1$ and each
$j=1,\ldots n-1$. This means $(m-1)(n-1)$ inequality constraints and
$2^{(m-1)(n-1)}$ possible combinations of active equality constraints. For
each combination it is necessary to compute the optimal times. There is
currently no known way to discard a given combination without checking for
safe separation, computing the optimal times and calculating the cost.

###  1.7 The main theoretical result

In this paper we formulate and solve a train-separation problem for $m$ trains
and $n+1$ signals where we aim to minimize total cost subject to a complete
set of active clearance time equality constraints that are designed to ensure
safe separation and compress the total line-occupancy timespan. We compress
the total line-occupancy timespan by assuming that ${\mathfrak{T}}_{i+1}$
enters segment ${\mathfrak{S}}_{j}=[x_{j-1},x_{j+1}]$ at the same time as
${\mathfrak{T}}_{i}$ leaves. Thus we assume that
$t_{i,j+1}=t_{i}(x_{j+1})=t_{i+1}(x_{j-1})=t_{i+1,j-1}$. Therefore

$t_{i,\,j+1}=t_{i+1,\,j-1}=t_{i+2,\,j-3}=\cdots=t_{i+\lfloor(j+1)/2\rfloor,\,j+1-2\lfloor(j+1)/2\rfloor}$
(14)

for each $i=1,\ldots,m-1$ and each $j=1,\ldots,n$ where
$\lfloor(j+1)/2\rfloor$ denotes the integer part of $(j+1)/2$. Thus we have
$t_{1,2}=t_{2,0}$, $t_{1,3}=t_{2,1}$, $t_{1,4}=t_{2,2}=t_{3,0}$,
$t_{1,5}=t_{2,3}=t_{3,1}$, $t_{1,6}=t_{2,4}=t_{3,2}=t_{4,0}$ and so on.

We will solve the following so-called alternative train-separation problem.

###### Problem 3

Find necessary conditions for a vector $\mbox{$\mbox{\boldmath$h$}$}_{0}$ of
optimal prescribed segment clearance times that minimizes the total tractive
energy $J(\mbox{$\mbox{\boldmath$h$}$})$ required by the fleet over all
$\mbox{$\mbox{\boldmath$h$}$}=[h_{i,j}]\in{\mathcal{H}}_{\mbox{\scriptsize
f}}$, where ${\mathcal{H}}_{\mbox{\scriptsize f}}$ denotes the collection of
all feasible sets of prescribed section clearance times with active
constraints $t_{i}(x_{j})=h_{i,j}$ and with
$h_{i+1,\,j-1}=t_{i+1,\,j-1}=t_{i,\,j+1}=h_{i,\,j+1}$ for each
$i=1,\ldots,m-1$ and $j=1,\ldots,n-1$. The trains may have different
performance functions. $\hfill\Box$

In practice there are two important modifications that we can make to Problem
3.

  * •

We can allow an additional buffer-time delay $\delta_{i}\geq 0$ between
${\mathfrak{T}}_{i}$ and ${\mathfrak{T}}_{i+1}$ so that
$t_{i+1,\,j-1}=t_{i,\,j+1}+\delta_{i}$ for each $i=1,\ldots,m-1$. Thus we have
$t_{2,0}=t_{1,2}+\delta_{1}$, $t_{2,1}=t_{1,3}+\delta_{1}$,
$t_{3,0}=t_{2,2}+\delta_{2}=t_{1,4}+(\delta_{1}+\delta_{2})$,
$t_{3,1}=t_{2,3}+\delta_{2}=t_{1,5}+(\delta_{1}+\delta_{2})$,
$t_{4,0}=t_{3,2}+\delta_{3}=t_{2,4}+(\delta_{2}+\delta_{3})=t_{1,6}+(\delta_{1}+\delta_{2}+\delta_{3})$
and so on. The optimal speed profiles are not changed by this additional
delay. On a typical train graph this simply means that the planned graph for
${\mathfrak{T}}_{i+1}$ is shifted to the right by
$\delta_{1}+\cdots+\delta_{i}$ time units. For instance in Figure 1 the train
graph for ${\mathfrak{T}}_{2}$ is simply moved to the right by $\delta_{1}$
time units.

  * •

We can assume that active constraints are only required for successive trains
at certain key locations. For instance, in the problem depicted in Figure 1,
we could set signal times
${\mathcal{H}}_{1}=[h_{1,j}]_{j=0}^{8}=[0,h_{1},h_{2},\ldots,h_{7},T]$ for
${\mathfrak{T}}_{1}$ and ${\mathcal{H}}_{2}=[h_{2,j}]_{j=0}^{8}=[\Delta
T,h_{7},h_{8},h_{4},h_{9},h_{10},h_{11},h_{12},\Delta T+T]$ for
${\mathfrak{T}}_{2}$. The only active intermediate time constraint is
$t_{2,3}=h_{2,3}=h_{4}=h_{1,5}=t_{1,5}$. We now optimize over all
$\mbox{$\mbox{\boldmath$h$}$}=[h_{1},\ldots,h_{12}]$ but must check
retrospectively that $h_{1,j+1}\leq h_{2,j-1}$ for all $j=1,\ldots,7$.

We solve Problem 3 using an extended form of a little-known formula

$\frac{dJ}{dT}=-\psi(V)$ (15)

that expresses the rate of change of cost with respect to journey time for an
optimal strategy with no intermediate time constraints as a function of the
optimal driving speed. An embryonic form of the extended formula [Albrecht,
Howlett, and Pudney (2020), Section IV A] for the two-train separation
problem, shows that the partial rate of change of journey cost with respect to
the prescribed signal times is a known function of the preceding and
succeeding optimal section driving speeds. Direct derivations of (15) have
been given for level track [Albrecht, Howlett, and Pudney (2016)] and more
generally for non-level track [Howlett (2016)]. We note that (15) was known
much earlier in the Russian literature using a high-level derivation based on
a deep understanding of the Pontryagin Principle. See, for instance, a brief
reference to the formula in [Liu and Golovitcher (2003), Section 3, p 922,
following equation (12)].

###  1.8 Application of the theoretical results

The theoretical results are applied to a case study of the regular $15$-minute
daily passenger shuttle service from Glasgow to Edinburgh in Scotland.

###  1.9 The role of the train performance functions

For each train ${\mathfrak{T}}_{i}$ the precise details of the optimal
strategy—the optimal driving speeds, the tractive energy consumption, and the
optimal switching locations—depend only on the stopping pattern, the
prescribed signal times and the performance functions
$(H_{i}(v),K_{i}(v),r_{i}(v))$. Hence the optimal strategy for
${\mathfrak{T}}_{i}$ can be computed separately with no knowledge of the other
optimal driving strategies. Consequently we can use individual performance
functions without changing the overall structure of the solution. This is
confirmed by our theoretical results and illustrated in Case Study 5.

###  1.10 Terminology

It is convenient to summarize our terminology.

  * •

In the case studies we assume each train ${\mathfrak{T}}$ has bounded
acceleration with $-K(v)\leq u\leq H(v)$ where $H(v)=\max\\{P_{0},P_{1}/v\\}$
and $K(v)=\max\\{Q_{0},Q_{1}/v\\}$ for $v>0$ where
$P_{0},P_{1},Q_{0},Q_{1}\in{\mathbb{R}}_{+}$ are positive constants. The
resistive acceleration is given by $r(v)=r_{0}+r_{1}v+r_{2}v^{2}$ for $v\geq
0$ where $r_{0},r_{1},r_{2}\in{\mathbb{R}}_{+}$ are positive constants. We
make repeated use of the functions $\varphi(v)=vr(v)$ and
$\psi(v)=v^{2}r^{\,\prime}(v)$.

  * •

The distance and time differentials $dx_{a}(v)=vdt_{a}(v)$,
$dx_{c}(v)=vdt_{c}(v)$ and $dx_{b}(v)=vdt_{b}(v)$ for phases of maximum
acceleration, coast and maximum brake are defined as functions of the speed
$v$ by (6), (7) and (8) respectively.

  * •

The known speed functions $U_{b}(v)$, $U_{s}(v,w)$ and
$U_{s}^{{\dagger}}(u,v,w)$ which depend only on the resistance function for
the train are defined by (9), (12) and (13) respectively.

  * •

For our theoretical derivations it is convenient to assume there is no buffer
time in the form of an additional delay between ${\mathfrak{T}}_{i}$ and
${\mathfrak{T}}_{i+1}$. That is, in general, we assume
$t_{i+1,\,j-1}=t_{i,\,j+1}$ for each $i=1,\ldots,m-1$ and $j=1,\ldots,n-1$. If
a buffer time $\delta_{i}>0$ is subsequently imposed between successive trains
${\mathfrak{T}}_{i}$ and ${\mathfrak{T}}_{i+1}$ with
$t_{i+1,\,j-1}=t_{i,\,j+1}+\delta_{i}$ the optimal speed profiles do not
change and one simply moves the optimal train graph for ${\mathfrak{T}}_{i+1}$
an additional $\Delta_{i}=\delta_{1}+\cdots+\delta_{i}$ units to the right.
Buffer times are essential in practice.

  * •

The term clearance times for sections $[x_{j-1},x_{j}]$ or segments
${\mathfrak{S}}_{j}=[x_{j-1},x_{j+1}]$ is a collective term for both the
earliest allowed entry times and the latest allowed exit times. The times
$t_{i,\,j}=t_{i}(x_{j})$ are also known as signal times.

  * •

An inequality constraint, either $t_{i,\,j}\geq h_{i,\,j}$ or $t_{i,\,j}\leq
h_{i,\,j}$, is described as active if $t_{i,\,j}=h_{i,\,j}$ and inactive
otherwise.

  * •

A strategy of optimal type satisfies the necessary conditions for optimality
but may not satisfy the imposed time constraints.

  * •

A feasible strategy satisfies the imposed time constraints.

  * •

For $s\in{\mathbb{R}}$ with $s>0$ we write $\lfloor s\rfloor$ to denote the
integer part of $s$.

  * •

For vectors
$\mbox{$\mbox{\boldmath$s$}$}=[s_{j}]_{j=1}^{p},\mbox{$\mbox{\boldmath$t$}$}=[t_{j}]_{j=1}^{p}\in{\mathbb{R}}^{p}$
the Hadamard product is the vector
$\mbox{$\mbox{\boldmath$r$}$}=\mbox{$\mbox{\boldmath$s$}$}\circ\mbox{$\mbox{\boldmath$t$}$}$
defined by $\mbox{$\mbox{\boldmath$r$}$}=[r_{j}]_{j=1}^{p}$ where
$r_{j}=s_{j}t_{j}$ for each $j=1,\ldots,p$.

##  2 Structure of the paper

In Section 3 we review the relevant literature. In Section 4 we outline the
contribution of this paper to the theory and practice of optimal train
control. We propose a systematic scheme for definition of the clearance-time
constraints in Section 5. The constraints are displayed in a convenient table
format. The next two sections contain the main theoretical results. In Section
6 we solve the optimal scheduling problem for a fleet of trains using
constant-speed strategies subject to safe separation of successive trains
enforced by active equality constraints. The problem is formulated as an
unconstrained convex optimization. We find analytic formulæ for the cost
gradient with respect to the prescribed clearance times and for the associated
Hessian matrix. An analogous optimal scheduling problem for realistic
strategies is formulated and solved in Section 7. Once again the problem is
formulated as an unconstrained convex optimization and we establish an
analogous analytic formula for the cost gradient. A general procedure for
calculation of realistic optimal strategies for journeys with intermediate
time constraints is described in Section 8. In Section 9 we outline a proposed
algorithm to find an optimal schedule for a fleet of trains subject to a
typical set of safe separation conditions enforced by active equality
constraints. Section 10 contains a suite of case studies where the theoretical
techniques are used to find an optimal schedule for a busy intercity passenger
shuttle service subject to safe-separation constraints for a set of nominal
sections defined by the key locations. In Section 11 we formulate a
rudimentary model for the stochastic evolution of a typical train journey
where the driver follows advice provided by an on-board driver advisory
system. These ideas are then applied to the optimal schedule developed in the
earlier case studies. Selected background mathematical material is explained
and extended in the Appendix.

##  3 Previous work

There are several widely cited papers which propose analytic solutions to the
classic single train control problem. When continuous control is allowed we
refer to [Albrecht, Howlett, and Pudney (2013), Albrecht et al. (2015c),
Albrecht et al. (2015d), Howlett, Pudney, and Vu (2009)] and to earlier
papers, [Howlett (2000), Khmelnitsky (2000), Liu and Golovitcher (2003)].
These authors all use the commonly accepted model of a point-mass train and
find solutions by applying classical methods of constrained optimization. See
also [Baranov, Meleshin, and Chin (2011)]. The strategies have been
implemented in real time on very fast trains where updated strategies are
routinely calculated on-board in a matter of a few seconds [Albrecht et al.
(2015d), Section 9, pp 534–535]. The point-mass model does not consider in-
train forces which may be significant in heavy-haul trains [Zhuan and Xia
(2008)]. Other authors use pseudo-spectral methods [Goverde, Scheepmaker, and
Wang (2020), Wang and Goverde (2017)] but these methods are too slow for on-
board use [Scheepmaker et al. (2020)]. The train control problem has also been
solved for the discrete control systems used on diesel-electric locomotives.
See [Cheng and Howlett (1992), Howlett and Cheng (1993), Pudney and Howlett
(1994)] for solutions on level track and subsequent papers [Howlett, Milroy
and Pudney, (1994), Howlett (1996), Howlett and Cheng (1997)] for solutions on
tracks with nonzero gradients.

There are numerous papers that use standard methods of operations
research—mathematical programming, job-shop scheduling, graph theory and
various heuristic search procedures—to find efficient train schedules on
complex rail networks. The work is often broadly-based with objectives that
include improved efficiencies obtained by adjusting allowed journey times [Su
et al. (2014)], and best ordering of scheduled services [Burdett and Kozan
(2009), Burdett and Kozan (2010), Caprara, Fischetti, and Toth (2002), Liu and
Kozan (2009)] and by coordinating arrival and departure times to capture
energy from regenerative braking [Li and Lo (2014a), Li and Lo (2014b)]. Other
authors considered selecting the best meeting locations [Higgins, Kozan, and
Ferreira (1996), Wang et al. (2014)], and providing improved service to
customers [Wang and Goverde (2016), Yang et al. (2018)]. The development of
efficient timetables on complex networks has also spawned work on conflict
detection and resolution [Corman et al. (2012), D’Ariano, Pranzo, and Hansen
(2007)] and schedule recovery from disruption [Wang and Goverde (2017)].

See [Scheepmaker, Goverde, and Kroon (2017), Yang et al. (2016), Yin et al.
(2017)] for recent broadly-based and detailed reviews.

A recent paper [Wang and Goverde (2019)] considers multi-train trajectory
optimization for the development of energy-efficient schedules. The main focus
is on single track corridors where conflicts between opposing trains must be
resolved and on double track corridors where the focus is on the development
of efficient timetables for successive trains and—to a lesser extent—on
provision for occasional overtaking. The first step is to replace the existing
arrival and departure times with time-window constraints in order to relax the
timetable. Energy-efficient speed profiles are then used either individually
(if there are no conflicts) or collectively (if conflicting train paths are
involved) to find optimal arrival and departure times within the relaxed time
windows. The two problems are reformulated as a multiple-phase optimal control
problem and solved by a pseudo-spectral method. There is no attempt to develop
a cohesive theory of optimal scheduling.

##  4 Contribution

Our focus is on developing a theory of optimal scheduling and using it to find
analytic solutions to unsolved timetable problems on dedicated double track
corridors where all trains have similar performance functions. This includes
busy metropolitan transport systems in many major cities, regular intercity
passenger shuttle services between neighbouring cities and dedicated heavy-
haul freight corridors. The main theoretical contributions are complementary
solutions to the alternative train-separation problem where the trains are
separated by active clearance-time equality constraints using, firstly,
constant-speed strategies and, secondly, realistic strategies. We show that
this problem can be reformulated as an unconstrained convex optimization and
that an analogous cost gradient formula defines the optimal solution in each
instance. We apply our results to a set of case studies for the daily shuttle
service between Glasgow and Edinburgh in Scotland. Our aim is to minimize
total energy consumption subject to active intermediate clearance-time
equality constraints that ensure safe separation of successive trains and
preserve overall journey times. For the constant-speed strategies we show that
the optimal schedule can be found using a single multi-dimensional Newton
iteration. For the realistic strategies we use the method of steepest descent
to find the optimal schedules with a sequence of Newton iterations required at
each step to determine the individual optimal strategies. We also propose a
theoretical model to quantify the normal stochastic variation in section
running times and hence find appropriate additional buffer times for the
separation constraints. The effectiveness of these buffer times is tested in
our final case study.

##  5 The time constraints for individual trains in the fleet

We will use a single vector
$\mbox{$\mbox{\boldmath$h$}$}=[h_{k}]\in{\mathbb{R}}^{n+m-2}$ of unknown
prescribed times to define the separation constraints. The prescribed
intermediate times for ${\mathfrak{T}}_{1}$ are all unknown with
$t_{1,j}=h_{j}$ for each $j=1,\ldots,n-1$. For $1\leq i\leq m-1$ the
prescribed times for train ${\mathfrak{T}}_{i+1}$ are defined by the equality
constraint $t_{i+1,j-1}=t_{i,j+1}$ for each $j=1,\ldots,n-1$. The time
$t_{i+1,n-1}$ at $x_{n-1}$ is not constrained because ${\mathfrak{T}}_{i}$ has
already completed the journey. Thus we set $t_{i+1,n-1}=h_{n+i-1}$ where
$h_{n+i-1}$ is unknown. For each additional train there is one additional
unknown. The easiest way to visualize the scheduled times for the entire fleet
is to construct a table of constraints and unknowns.

${\mathfrak{T}}_{i}$ | $t_{i,0}$ | $t_{i,1}$ | $t_{i,2}$ | $t_{i,3}$ | $t_{i,4}$ | $\cdot$ | $t_{i,2k-4}$ | $t_{i,2k-3}$ | $t_{i,2k-2}$ | $t_{i,2k-1}$ | $t_{i,2k}$
---|---|---|---|---|---|---|---|---|---|---|---
${\mathfrak{T}}_{1}$ | $0$ | $h_{1}$ | $h_{2}$ | $h_{3}$ | $h_{4}$ | $\cdot$ | $h_{2k-4}$ | $h_{2k-3}$ | $h_{2k-2}$ | $h_{2k-1}$ | T
${\mathfrak{T}}_{2}$ | $h_{2}$ | $h_{3}$ | $h_{4}$ | $h_{5}$ | $h_{6}$ | $\cdot$ | $h_{2k-2}$ | $h_{2k-1}$ | $T$ | $h_{2k}$ | $h_{2}+T$
${\mathfrak{T}}_{3}$ | $h_{4}$ | $h_{5}$ | $h_{6}$ | $h_{7}$ | $h_{8}$ | $\cdot$ | $T$ | $h_{2k}$ | $h_{2}+T$ | $h_{2k+1}$ | $h_{4}+T$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
${\mathfrak{T}}_{k-1}$ | $h_{2k-4}$ | $h_{2k-3}$ | $h_{2k-2}$ | $h_{2k-1}$ | $T$ | $\cdot$ | $h_{2k-8}+T$ | $h_{3k-3}$ | $h_{2k-6}+T$ | $h_{3k-2}$ | $h_{2k-4}+T$
${\mathfrak{T}}_{k}$ | $h_{2k-2}$ | $h_{2k-1}$ | $T$ | $h_{2k}$ | $h_{2}+T$ | $\cdot$ | $h_{2k-6}+T$ | $h_{3k-2}$ | $h_{2k-4}+T$ | $h_{3k-1}$ | $h_{2k-2}+T$
${\mathfrak{T}}_{k+1}$ | $T$ | $h_{2k}$ | $h_{2}+T$ | $h_{2k+1}$ | $h_{4}+T$ | $\cdot$ | $h_{2k-4}+T$ | $h_{3k-1}$ | $h_{2k-2}+T$ | $h_{3k}$ | $h_{2k}+T$
${\mathfrak{T}}_{k+2}$ | $h_{2}+T$ | $h_{2k+1}$ | $h_{4}+T$ | $h_{2k+2}$ | $h_{6}+T$ | $\cdot$ | $h_{2k-2}+T$ | $h_{3k}$ | $h_{2k}+T$ | $h_{3k+1}$ | $h_{2k+2}+T$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
Table 1: Table of constraints and unknown times when $n=2k\in{\mathbb{N}}$. ${\mathfrak{T}}_{i}$ | $t_{i,0}$ | $t_{i,1}$ | $t_{i,2}$ | $t_{i,3}$ | $t_{i,4}$ | $\cdot$ | $t_{i,2k-3}$ | $t_{i,2k-2}$ | $t_{i,2k-1}$ | $t_{i,2k}$ | $t_{i,2k+1}$
---|---|---|---|---|---|---|---|---|---|---|---
${\mathfrak{T}}_{1}$ | $0$ | $h_{1}$ | $h_{2}$ | $h_{3}$ | $h_{4}$ | $\cdot$ | $h_{2k-3}$ | $h_{2k-2}$ | $h_{2k-1}$ | $h_{2k}$ | T
${\mathfrak{T}}_{2}$ | $h_{2}$ | $h_{3}$ | $h_{4}$ | $h_{5}$ | $h_{6}$ | $\cdot$ | $h_{2k-1}$ | $h_{2k}$ | $T$ | $h_{2k+1}$ | $h_{2}+T$
${\mathfrak{T}}_{3}$ | $h_{4}$ | $h_{5}$ | $h_{6}$ | $h_{7}$ | $h_{8}$ | $\cdot$ | $T$ | $h_{2k+1}$ | $h_{2}+T$ | $h_{2k+2}$ | $h_{4}+T$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
${\mathfrak{T}}_{k-1}$ | $h_{2k-4}$ | $h_{2k-3}$ | $h_{2k-2}$ | $h_{2k-1}$ | $h_{2k}$ | $\cdot$ | $h_{2k-8}+T$ | $h_{3k-3}$ | $h_{2k-6}+T$ | $h_{3k-2}$ | $h_{2k-4}+T$
${\mathfrak{T}}_{k}$ | $h_{2k-2}$ | $h_{2k-1}$ | $h_{2k}$ | $T$ | $h_{2k+1}$ | $\cdot$ | $h_{2k-6}+T$ | $h_{3k-2}$ | $h_{2k-4}+T$ | $h_{3k-1}$ | $h_{2k-2}+T$
${\mathfrak{T}}_{k+1}$ | $h_{2k}$ | $T$ | $h_{2k+1}$ | $h_{2}+T$ | $h_{2k+2}$ | $\cdot$ | $h_{2k-4}+T$ | $h_{3k-2}$ | $h_{2k-2}+T$ | $h_{3k}$ | $h_{2k}+T$
${\mathfrak{T}}_{k+2}$ | $h_{2k+1}$ | $h_{2}+T$ | $h_{2k+2}$ | $h_{4}+T$ | $h_{2k+3}$ | $\cdot$ | $h_{2k-2}+T$ | $h_{3k-2}$ | $h_{2k}+T$ | $h_{3k+1}$ | $h_{2k+2}+T$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
Table 2: Table of constraints and unknown times when $n=2k+1\in{\mathbb{N}}$.

Although the patterns in Tables 1 and 2 are ultimately different they are
essentially the same above the double line, where $i\leq\lfloor n/2\rfloor$.
Thus, a general algebraic description is much easier when $m\leq\lfloor
n/2\rfloor$.

##  6 The optimization problem with constant-speed strategies

For each feasible $h$ assume that ${\mathfrak{T}}_{i}$ travels at constant
speed

$W_{i,j}(\mbox{$\mbox{\boldmath$h$}$})=(x_{j}-x_{j-1})/[t_{i,j}(\mbox{$\mbox{\boldmath$h$}$})-t_{i,j-1}(\mbox{$\mbox{\boldmath$h$}$})]$

on section $(x_{j-1},x_{j})$ for each $i=1,\ldots,m$ and $j=1,\ldots,n$
subject to the constraints listed in Table 1 or Table 2. Let $r_{i}(v)$ be the
resistive acceleration for ${\mathfrak{T}}_{i}$ and let
$\varphi_{i}(v)=vr_{i}(v)$ and $\psi_{i}(v)=v^{2}r_{i}(v)$ be the associated
functions. Problem 3 can now be posed as an unconstrained optimization.

###### Problem 4

Let

$L(\mbox{$\mbox{\boldmath$h$}$})=\sum_{i=1}^{m}\sum_{j=1}^{n}r_{i}[W_{i,j}(\mbox{$\mbox{\boldmath$h$}$})](x_{j}-x_{j-1})$
(16)

denote the total cost for the fleet to complete the journey. Find
$\mbox{$\mbox{\boldmath$h$}$}=[h_{k}]_{k=1}^{n+m-2}$ to minimize $L$ subject
to the time constraints defined in Table 1 or Table 2. In the special case
where $m\leq\lfloor n/2\rfloor$ the time constraints for ${\mathfrak{T}}_{i}$
for all $i=1,\ldots,m$ are given by $t_{i,\,j}=h_{2i-2+j}$ for each
$j=0,\ldots,n-2i+1$; $t_{i,n-2i+2}=T$; $t_{i,n-2i+2\ell+1}=h_{n+\ell-1}$ for
each $\ell=1,\ldots,i-1$; and $t_{i,n-2i+2\ell+2}=h_{2\ell}+T$ for each
$\ell=1,\ldots,i-1$. Note that the trains are not assumed to be identical.
$\hfill\Box$

To minimize $L$ we must solve the equation

$\mbox{$\mbox{\boldmath$\nabla$}$}L(\mbox{$\mbox{\boldmath$h$}$})=\mbox{$\mbox{\boldmath$0$}$}\iff\left[\partial
L/\partial h_{k}\right]_{k=1}^{n+m-2}=\mbox{$\mbox{\boldmath$0$}$}.$ (17)

The total cost for train ${\mathfrak{T}}_{i}$ is
$L_{i}(\mbox{$\mbox{\boldmath$h$}$})=\sum_{j=1}^{n}r_{i}[W_{i,j}(\mbox{$\mbox{\boldmath$h$}$})](x_{j}-x_{j-1})$.
For each fixed $k\in\\{1,\ldots,n\\}$ it is useful to begin by identifying the
terms which depend on the variable $h_{k}$. Let ${\mathcal{F}}_{i,k}=\\{j\mid
t_{i,j}=h_{k}+c_{i,j}$ for some constant $c_{i,j}\geq 0$ }. It is easy to see
from Table 1 and Table 2 that $j\in{\mathcal{F}}_{i,k}\Rightarrow
j-1,j+1\notin{\mathcal{F}}_{i,k}$. Therefore

$\displaystyle\frac{\partial L_{i}}{\partial h_{k}}$ $\displaystyle=$
$\displaystyle\sum_{j\in{\mathcal{F}}_{i,k}}\left[r_{i}^{\,\prime}(W_{i,j+1})(x_{j+1}-x_{j})\cdot(x_{j+1}-x_{j})/(t_{i,j+1}-t_{i,j})^{2}\right.$
(18) $\displaystyle\hskip
113.81102pt\left.-r_{i}^{\,\prime}(W_{i,j})(x_{j}-x_{j-1})\cdot(x_{j}-x_{j-1})/(t_{i,j}-t_{i,j-1})^{2}\right]$
$\displaystyle=$
$\displaystyle\sum_{j\in{\mathcal{F}}_{i,k}}\left[\psi_{i}(W_{i,j+1})-\psi_{i}(W_{i,j})\right].$

In order to apply a Newton iteration to solve (17) it is necessary to
calculate the Hessian matrix of second derivatives. In this regard we find

$\frac{\partial^{2}L_{i}}{\partial
h_{k}^{2}}=\sum_{j\in{\mathcal{F}}_{k}}\left[\rule{0.0pt}{11.38092pt}W_{i,j+1}\psi_{i}^{\,\prime}(W_{i,j+1})/(t_{i,j+1}-t_{i,j})+W_{i,j}\psi_{i}^{\,\prime}(W_{i,j})/(t_{i,j}-t_{i,j-1})\right]$
(19)

and since $j\in{\mathcal{F}}_{i,k}\Rightarrow j\notin{\mathcal{F}}_{i,\ell}$
when $\ell\neq k$ we have

$\frac{\partial^{2}L_{i}}{\partial h_{\ell}\partial h_{k}}=\hskip
5.69054pt-\sum_{j\in{\mathcal{F}}_{k}\,\mbox{\scriptsize\&}\,j+1\in{\mathcal{F}}_{\ell}}W_{i,j+1}\psi_{i}^{\,\prime}(W_{i,j+1})/(t_{i,j+1}-t_{i,j})\hskip
5.69054pt-\sum_{j\in{\mathcal{F}}_{k}\,\mbox{\scriptsize\&}\,j-1\in{\mathcal{F}}_{\ell}}W_{i,j}\psi_{i}^{\,\prime}(W_{i,j})/(t_{i,j}-t_{i,j-1})$
(20)

when $\ell\neq k$. We will show that each
$L_{i}(\mbox{$\mbox{\boldmath$h$}$})$ is convex. We may assume without loss of
generality that ${\mathfrak{T}}_{i}$ satisfies a set of intermediate time
constraints $t_{i}(x_{j})=g_{i,j}$ for each $j=1,\ldots,n$. It follows from
(19) and (20) that the Hessian matrix
$P_{i}=[p_{i,k,\ell}]=[\partial^{2}L_{i}/(\partial g_{i,k}\partial
g_{i,\ell})]\in{\mathbb{R}}^{n\times n}$ is given by

$p_{i,k,\ell}=\left\\{\begin{array}[]{ll}-\beta_{i,k}&\mbox{when}\ \ell=k-1\\\
\beta_{i,k+1}+\beta_{i,k}&\mbox{when}\ \ell=k\\\ -\beta_{i,k+1}&\mbox{when}\
\ell=k+1\\\ 0&\mbox{otherwise}\end{array}\right.$

where $W_{i,k}=(x_{k}-x_{k-1})/(g_{i,k}-g_{i,k-1})$ and
$\beta_{i,k}=W_{i,k}\psi_{i}^{\,\prime}(W_{i,k})/(g_{i,k}-g_{i,k-1})>0$. Let
$P_{i,r}=[p_{i,k,\ell}]_{k,\ell=1}^{r}$ denote the principal minor for each
$r=1,\ldots,n$. Now it can be shown that

$\det
P_{i,r}=\mbox{$\sum_{\mbox{$\mbox{\boldmath\scriptsize$\sigma$}$}\in{\mathcal{P}_{r}}}\left[\prod_{j=1}^{r}\beta_{i,\sigma(j)}\right]$}>0$

where ${\mathcal{P}}_{r}$ is the set of all strictly increasing sequences
$\mbox{$\mbox{\boldmath$\sigma$}$}=\\{\sigma(j)\\}_{j=1}^{r}$ with
$1\leq\sigma(1)<\cdots<\sigma(r)\leq n$ for each $r=1,\ldots,n$. It follows
from Sylvester’s criterion [Gilbert (1991)] that $P_{i}$ is positive definite.
Hence $L_{i}(\mbox{$\mbox{\boldmath$h$}$})$ is convex for each $i=1,\ldots,m$.
It follows that $L(\mbox{$\mbox{\boldmath$h$}$})$ is also convex. Thus the
solution to (17) is unique. It is conceptually straightforward but
algebraically complicated to write down general formulæ for the Newton
iteration. We prefer to elaborate those details in particular case studies
where (17) will solved directly using a Newton iteration.

##  7 The optimization problem with realistic optimal driving strategies

For each feasible $\mbox{$\mbox{\boldmath$h$}$}=[h_{k}]_{k=1}^{n+m-2}$ assume
that all trains use realistic strategies subject to the time constraints
listed in Table 1 or Table 2. For each $i=1,\ldots,m$ let
$\mbox{$\mbox{\boldmath$V$}$}_{i}(\mbox{$\mbox{\boldmath$h$}$})=\\{V_{i,j}(\mbox{$\mbox{\boldmath$h$}$})\\}_{j=1}^{n}$
denote the vector of optimal driving speeds for ${\mathfrak{T}}_{i}$ and let
$J_{i}(\mbox{$\mbox{\boldmath$h$}$})=J_{i}[\mbox{$\mbox{\boldmath$V$}$}_{i}(\mbox{$\mbox{\boldmath$h$}$})]$
denote the total cost for ${\mathfrak{T}}_{i}$. The constrained optimization
posed in Problem 3 is now an unconstrained optimization problem in $h$.

###### Problem 5

Let

$J(\mbox{$\mbox{\boldmath$h$}$})=\sum_{i=1}^{m}J_{i}[\mbox{$\mbox{\boldmath$V$}$}_{i}(\mbox{$\mbox{\boldmath$h$}$})]$
(21)

denote the total cost for the fleet to complete the journey. Find
$\mbox{$\mbox{\boldmath$h$}$}=[h_{k}]_{k=1}^{n+m-2}$ to minimize $J$ subject
to the time constraints defined in Table 1 or Table 2. If $m\leq\lfloor
n/2\rfloor$ the time constraints take the algebraic form described in Problem
4. The trains are not assumed to be identical. $\hfill\Box$

To minimize $J$ we must solve the equations

$\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$})=\mbox{$\mbox{\boldmath$0$}$}\iff\left[\partial
J/\partial h_{k}\right]_{k=1}^{n+m-2}=\mbox{$\mbox{\boldmath$0$}$}.$ (22)

For train ${\mathfrak{T}}_{i}$ we will argue that

$\frac{\partial J_{i}}{\partial
h_{k}}=\sum_{j\in{\mathcal{F}}_{i,k}}\left[\psi_{i}(V_{i,j+1})-\psi_{i}(V_{i,j})\right]$
(23)

where ${\mathcal{F}}_{i,k}=\\{j\mid t_{i,j}=h_{k}+c_{i,j}$ for some constant
$c_{i,j}\geq 0$ }. In the following argument it is convenient to drop the
subscript $i$ and argue for a generic train ${\mathfrak{T}}$. We may assume
without loss of generality that $v_{0}=v(x_{0})=0$ and $v_{n}=v(x_{n})=0$ with
$v(x)>0$ for all $x\in(0,X)$ and that $t(x_{j})=g_{j}$ for each $j=0,\ldots,n$
where $g_{0}<g_{1}<\cdots<g_{n-1}<g_{n}$ and where $g_{0}$ and $g_{n}=g_{0}+T$
are fixed. The optimal strategy, described in Section 1.4, is a sequence of
speedhold phases on segments $[a_{j},b_{j}]\subset(x_{j-1},x_{j})$ separated
by transition phases of either maximum acceleration or coast when passing
through the signal locations $\\{x_{j}\\}_{j=1}^{n-1}$. Because we do not know
whether a particular transition phase will be maximum acceleration or coast we
will use an elementary notational subterfuge. For the transition phase at
$x_{j}$ the acceleration will be denoted by $A_{j}(v)$. Thus $v=v(x)$ is
defined by $vv^{\,\prime}=A_{j}(v)-r_{i}(v)$ for $x\in(b_{j},a_{j+1})$ for
each $j=1,\ldots,n-1$ where $A_{j}(v)=H(v)$ for a phase of maximum
acceleration and $A_{j}(v)=0$ for a phase of coast. The time taken on
$(x_{0},x_{1})$ is

$g_{1}-g_{0}=\int_{0}^{V_{1}}\frac{dv}{H(v)-r(v)}+\int_{V_{1}}^{U_{1}}\frac{dv}{A_{1}(v)-r(v)}+\frac{\xi_{1}}{V_{1}},$
(24)

where

$\xi_{1}=x_{1}-x_{0}-\int_{0}^{V_{1}}\frac{vdv}{H(v)-r(v)}-\int_{V_{1}}^{U_{1}}\frac{vdv}{A_{1}(v)-r(v)}$
(25)

is the length of the speedhold segment $[a_{1},b_{1}]$, the time taken on
$(x_{j-1},x_{j})$ is

$g_{j}-g_{j-1}=\int_{U_{j-1}}^{V_{j}}\frac{dv}{A_{j-1}(v)-r(v)}+\int_{V_{j}}^{U_{j}}\frac{dv}{A_{j}(v)-r(v)}+\frac{\xi_{j}}{V_{j}}$
(26)

where

$\xi_{j}=x_{j}-x_{j-1}-\int_{U_{j-1}}^{V_{j}}\frac{vdv}{A_{j-1}(v)-r(v)}-\int_{V_{j}}^{U_{j}}\frac{vdv}{A_{j}(v)-r(v)}$
(27)

is the length of the speedhold segment $[a_{j},b_{j}]$ for each
$j=1,\ldots,n-1$ and the time taken on $(x_{n-1},x_{n})$ is

$T-g_{n-1}=\int_{U_{n-1}}^{V_{n}}\frac{dv}{A_{n-1}(v)-r(v)}+\int_{U_{n}}^{V_{n}}\frac{dv}{r(v)}+\int_{0}^{U_{n}}\frac{dv}{K(v)+r(v)}+\frac{\xi_{n}}{V_{n}}$
(28)

where

$\xi_{n}=x_{n}-x_{n-1}-\int_{U_{n-1}}^{V_{n}}\frac{vdv}{A_{n-1}(v)-r(v)}-\int_{U_{n}}^{V_{n}}\frac{vdv}{r(v)}-\int_{0}^{U_{n}}\frac{vdv}{K(v)+r(v)}$
(29)

is the length of the speedhold segment $[a_{n},b_{n}]$. If we differentiate
(24), (26) and (28) with respect to $g_{k}$ and rearrange the terms we get

$\frac{\xi_{1}}{V_{1}^{2}}\frac{\partial V_{1}}{\partial
g_{k}}=-\delta_{1,k}+\frac{1-U_{1}/V_{1}}{A_{1}(U_{1})-r(U_{1})}\frac{\partial
U_{1}}{\partial g_{k}},$ (30) $\frac{\xi_{j}}{V_{j}^{2}}\frac{\partial
V_{j}}{\partial
g_{k}}=\delta_{j-1,k}-\delta_{j,k}-\frac{1-U_{j-1}/V_{j}}{A_{j-1}(U_{j-1})-r(U_{j-1})}\frac{\partial
U_{j-1}}{\partial
g_{k}}+\frac{1-U_{j}/V_{j}}{A_{j}(U_{j})-r(U_{j})}\frac{\partial
U_{j}}{\partial g_{k}}$ (31)

for each $j=2,\ldots,n-1$ and

$\frac{\xi_{n}}{V_{n}^{2}}\frac{\partial V_{n}}{\partial
g_{k}}=\delta_{n-1,k}-\frac{1-U_{n-1}/V_{n}}{A_{n-1}(U_{n-1})-r(U_{n-1})}\frac{\partial
U_{n-1}}{\partial
g_{k}}-\frac{(1-U_{n}/V_{n})K(U_{n})}{r(U_{n})(K(U_{n})+r(U_{n}))}\frac{\partial
U_{n}}{\partial g_{k}}$ (32)

where $\delta_{r,s}=1$ if $s=r$ and $\delta_{r,s}=0$ otherwise. The cost of
the strategy is given by

$J=\int_{0}^{V_{1}}\frac{vH(v)dv}{H(v)-r(v)}+\sum_{j=1}^{n}r(V_{j})\xi_{j}+\sum_{j=1}^{n-1}\int_{V_{j}}^{V_{j+1}}\frac{vA_{j}(v)dv}{A_{j}(v)-r(v)}.$
(33)

Differentiation with respect to $g_{k}$ and simplification gives

$\frac{\partial J}{\partial
g_{k}}=\sum_{j=1}^{n-1}\frac{[r(V_{j+1})-r(V_{j})]U_{j}}{A_{j}(U_{j})-r(U_{j})}\frac{\partial
U_{j}}{\partial
g_{k}}+\frac{r(V_{n})U_{n}K(U_{n})}{r(U_{n})(K(U_{n})+r(U_{n}))}\frac{\partial
U_{n}}{\partial g_{k}}+\sum_{j=1}^{n}r^{\,\prime}(V_{j})\xi_{j}\frac{\partial
V_{j}}{\partial g_{k}}$ (34)

and if we eliminate terms in $\partial V_{j}/\partial g_{k}$ using (30), (31)
and (32) we obtain

$\displaystyle\frac{\partial J}{\partial g_{k}}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1}\frac{[r(V_{j+1})-r(V_{j})]U_{j}}{A_{j}(U_{j})-r(U_{j})}\frac{\partial
U_{j}}{\partial
g_{k}}+\frac{r(V_{n})U_{n}K(U_{n})}{r(U_{n})(K(U_{n})+r(U_{n}))}\frac{\partial
U_{n}}{\partial g_{k}}$ (35)
$\displaystyle+\psi(V_{1})\left[-\delta_{1,k}+\frac{1-U_{1}/V_{1}}{A_{1}(U_{1})-r(U_{1})}\frac{\partial
U_{1}}{\partial g_{k}}\right]$
$\displaystyle+\sum_{j=2}^{n-1}\psi(V_{j})\left[\delta_{j-1,k}-\delta_{j,k}-\frac{1-U_{j-1}/V_{j}}{A_{j-1}(U_{j-1})-r(U_{j-1})}\frac{\partial
U_{j-1}}{\partial
g_{k}}+\frac{1-U_{j}/V_{j}}{A_{j}(U_{j})-r(U_{j})}\frac{\partial
U_{j}}{\partial g_{k}}\right]\hskip 35.56593pt$
$\displaystyle+\psi(V_{n})\left[\delta_{n-1,k}-\frac{1-U_{n-1}/V_{n}}{A_{n-1}(U_{n-1})-r(U_{n-1})}\frac{\partial
U_{n-1}}{\partial
g_{k}}-\frac{(1-U_{n}/V_{n})K(U_{n})}{r(U_{n})(K(U_{n})+r(U_{n}))}\frac{\partial
U_{n}}{\partial g_{k}}\right].$

If we collect like terms and use (9) and (12) we see that the coefficient of

$(K(U_{n})/[r(U_{n})(K(U_{n})+r(U_{n}))])/(\partial U_{n}/\partial g_{k})$

is $\varphi^{\,\prime}(V_{n})U_{n}-\psi(V_{n})=0$ and that the coefficient of

$(1/[A_{j}(U_{j})-r(U_{j})])(\partial U_{j}/\partial g_{k})$

is
$[\varphi^{\,\prime}(V_{j+1})-\varphi^{\,\prime}(V_{j})]U_{j}+\psi(V_{j})-\psi(V_{j+1})=0$
for each $j=1,\ldots,n-1$. Therefore

$\frac{\partial J}{\partial
g_{k}}=-\psi(V_{1})\delta_{1,k}+\sum_{j=2}^{n-1}\psi(V_{j})[\delta_{j-1,k}-\delta_{j,k}]+\psi(V_{n})\delta_{n-1,k}=\psi(V_{k+1})-\psi(V_{k}).$

To determine an optimal strategy for a journey with prescribed intermediate
times but no intermediate stops it may be necessary to use a progressive
sequence of Newton iterations. We will describe a general procedure for that
purpose in the next section. When we find the optimal strategy we also find
the optimal driving speeds $V_{i,j}$. Thus we can calculate
$\psi_{i}(V_{i,j})$. If there is no speedhold phase on the final section
$(x_{n-1},x_{n})$ then we must use the formula
$\psi_{i}(V_{i,n})=\varphi(V_{\max,i,n})U_{i,n}/(V_{\max,i,n}-U_{i,n})$. See
Appendix A.2 for a detailed justification in a special case. The general
argument is similar.

The question still remains as to how we solve (22). We cannot use a Newton
iteration in the way that we could for Problem 4 because, aside from the need
for a separate Newton iteration to find the optimal strategies and the
associated optimal driving speeds for each train on the segments between
scheduled stops, there is no known analytic expression for $\partial
V_{i,j}/\partial h_{\ell}$ and hence no analytic expression for the Hessian
matrix. However the cost function (23) is a sum of terms in essentially the
same form as the locally convex functions considered in [Albrecht, Howlett,
and Pudney (2020), Appendices C, D and F]. We can use the same algebraic
arguments here to estimate the derivatives $\partial V_{i,j}/\partial
h_{\ell}$ and hence show that each $J_{i}(\mbox{$\mbox{\boldmath$h$}$})$ is
locally convex. Thus
$J(\mbox{$\mbox{\boldmath$h$}$})=\sum_{i=1}^{m}J_{i}(\mbox{$\mbox{\boldmath$h$}$})$
is also locally convex. Consequently we can use the method of steepest descent
to find a uniquely defined set of clearance times
$\mbox{$\mbox{\boldmath$h$}$}_{0}$ and a corresponding locally optimal cost
$J(\mbox{$\mbox{\boldmath$h$}$}_{0})$.

To apply the method of steepest descent we need an initial set of feasible
time constraints. We will use the optimal times obtained from the solution to
Problem 4 for that purpose. Let us suppose then that we have an initial set of
times defined by a particular value of $h$. We calculate optimal realistic
strategies for each train in the fleet subject to the given constraints. This
gives us a complete set of optimal driving speeds $\\{V_{i,j}\\}$ for each
$i=1,\ldots,m$ and each $j=1,\ldots,n$. Thus we can calculate
$\mbox{$\mbox{\boldmath$\nabla$}$}J$ and find a new value of $h$ according to
the formula $\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize\rm
new}}=\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}}-r\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}})$ for an appropriate value of $r>0$. Because $J$ is convex $r$ can be
determined using a golden search [Albrecht, Howlett, and Pudney (2020),
Appendix F]. We now find optimal realistic strategies for the new value of $h$
and calculate a reduced value of $J$. The procedure can then be repeated using
the new optimal driving speeds to further reduce $J$ until we find an
approximate solution to (22).

A remarkable analogy. The formulæ (18) and (23) are remarkable because they
are essentially identical. Thus the necessary conditions for optimality are
basically the same for constant-speed strategies as they are for realistic
strategies. This does not mean the optimal speeds computed for the constant-
speed strategies are identical to the optimal driving speeds computed for the
realistic strategies. There are however important structural similarities to
the optimal train graphs. In each case the trains must travel faster on the
longer sections and in each case the optimal solutions are a compromise
between minimizing the higher speeds and equalising the section traversal
times.

##  8 Calculating an optimal strategy for a journey with intermediate time
constraints but no intermediate stops

We wish to calculate a realistic optimal strategy for a typical train
${\mathfrak{T}}$ subject to a known set of prescribed intermediate times
$t(x_{j})=t_{j}$ for each $j=1,\ldots,n$ with
$0=t_{0}<t_{1}<\cdots<t_{n-1}<t_{n}=T$ where $T$ is the total journey time.
The optimal strategy is uniquely defined by a sequence of optimal driving
speeds $\\{V_{j}\\}_{j=1}^{n}$. For each set of prescribed times it may be
difficult to decide a priori whether the transition from speed $V_{j}$ on
$[a_{j},b_{j}]\subset(x_{j-1},x_{j})$ to speed $V_{j+1}$ on
$[a_{j+1},b_{j+1}]\subset(x_{j},x_{j+1})$ will require a phase of coast or a
phase of maximum acceleration. In such cases a progressive procedure could be
used. At each stage the relevant equations can be solved by a Newton
iteration. Every optimal journey begins with a phase of maximum acceleration
followed by a phase of speedhold at the optimal driving speed $V_{1}$. At
Stage 1 we choose $V_{1}={V_{1}}^{(1)}$ to satisfy

$\mbox{$\int_{0}^{V_{1}}$}dt_{a}(v)+(1/V_{1})\left[x_{1}-x_{0}-\mbox{$\int_{0}^{V_{1}}$}dx_{a}(v)\right]=t_{1}$

where $t_{1}$ is the prescribed arrival time at $x_{1}$. Suppose now that the
speedhold phase at speed $V_{1}={V_{1}}^{(1)}$ is continued until $x_{2}$ and
that $t_{1}+[x_{2}-x_{1}]/V_{1}=t_{2}+\epsilon$ where $\epsilon>0$ is a small
positive number. Hence we must go a little faster on $(x_{1},x_{2})$. Thus we
insert a phase of maximum acceleration to change from the driving speed
$V_{1}={V_{1}}^{(1)}$ on $[a_{1},b_{1}]\subset(x_{0},x_{1})$ to a slightly
higher driving speed $V_{2}$ on $[a_{2},b_{2}]\subset(x_{1},x_{2})$. It is
known that $v(x_{1})=U_{1}=U_{s}(V_{1},V_{2})$ always lies between $V_{1}$ and
$V_{2}$. Thus the train must begin increasing speed before it reaches $x_{1}$.
This means the true optimal driving speed $V_{1}$ must be slightly lower than
${V_{1}}^{(1)}$. Thus, at Stage 2 we assume a transition phase of maximum
acceleration and choose $V_{1}={V_{1}}^{(2)}$ and $V_{2}={V_{2}}^{(2)}$ to
satisfy

$\displaystyle\mbox{$\int_{0}^{U_{1}}$}dt_{a}(v)+(1/V_{1})\left[x_{1}-x_{0}-\mbox{$\int_{0}^{U_{1}}$}dx_{a}(v)\right]$
$\displaystyle=$ $\displaystyle t_{1}$
$\displaystyle\mbox{$\int_{U_{1}}^{V_{2}}$}dt_{a}(v)+(1/V_{2})\left[x_{2}-x_{1}-\mbox{$\int_{U_{1}}^{V_{2}}$}dx_{a}(v)\right]$
$\displaystyle=$ $\displaystyle t_{2}-t_{1}.$

This means ${V_{2}}^{(2)}$ will be slightly larger than ${V_{1}}^{(2)}$. Now
suppose we continue at speed $V_{2}={V_{2}}^{(2)}$ through until $x_{3}$ and
find that $t_{2}+[x_{3}-x_{2}]/V_{2}=t_{3}+M$ where $M>0$ is large. Thus we
need to go much faster on $(x_{2},x_{3})$. Hence we insert a phase of maximum
acceleration at Stage 3 to change from speed $V_{2}={V_{2}}^{(2)}$ on
$[a_{2},b_{2}]\subset(x_{1},x_{2})$ to a much higher speed $V_{3}$ on
$[a_{3},b_{3}]\subset(x_{2},x_{3})$. Therefore $U_{2}=U_{s}(V_{2},V_{3})$ is
also much larger than $V_{2}={V_{2}}^{(2)}$ and so the train must start going
much faster as it approaches $x_{2}$. If we wish to solve the system

$\displaystyle\mbox{$\int_{0}^{U_{1}}$}dt_{a}(v)+(1/V_{1})\left[x_{1}-x_{0}-\mbox{$\int_{0}^{U_{1}}$}dx_{a}(v)\right]$
$\displaystyle=$ $\displaystyle t_{1}$
$\displaystyle\mbox{$\int_{U_{1}}^{U_{2}}$}dt_{a}(v)+(1/V_{2})\left[x_{2}-x_{1}-\mbox{$\int_{U_{1}}^{U_{2}}$}dx_{a}(v)\right]$
$\displaystyle=$ $\displaystyle t_{2}-t_{1}$
$\displaystyle\mbox{$\int_{U_{2}}^{V_{3}}$}dt_{a}(v)+(1/V_{3})\left[x_{3}-x_{2}-\mbox{$\int_{U_{2}}^{V_{3}}$}dx_{a}(v)\right]$
$\displaystyle=$ $\displaystyle t_{3}-t_{2}$

at Stage 3 we must choose $V_{2}={V_{2}}^{(3)}$ to be substantially less than
${V_{2}}^{(2)}$. This in turn means we must choose
${V_{1}}^{(3)}>{V_{1}}^{(2)}$. If $\epsilon$ is sufficiently small and $M$ is
sufficiently large these changes will mean that ${V_{1}}^{(3)}>{V_{2}}^{(3)}$.
Therefore we will now need to use a phase of coast to change from driving
speed $V_{1}={V_{1}}^{(3)}$ on $[a_{1},b_{1}]\subset(x_{0},x_{1})$ to a lower
driving speed $V_{2}={V_{2}}^{(3)}$ on $[a_{2},b_{2}]\subset(x_{2},x_{2})$. As
we progress further and further with the calculation the impacts on our
earlier decisions become less and less pronounced. It is most likely, in the
case described above, that the revised decision will ultimately be the correct
decision. The new optimal driving speeds will indicate the correct choices for
the revised calculation. The final stage on the interval $(x_{n-1},x_{n})$ is
different. There are two possibilities. If there is a speedhold phase at speed
$V_{n}$ on some interval $[a_{n},b_{n}]\subset(x_{n-1},x_{n})$ then the speed
at $x_{n-1}$ is given by $U_{n-1}=U_{s}(V_{n-1},V_{n})$ and the strategy takes
the form of a transition phase—either maximum acceleration or coast—followed
by speedhold at the optimal driving speed $V_{n}$, coast to the optimal
braking speed $U_{n}=U_{b}(V_{n})$ and maximum brake. If there is insufficient
time for a speedhold phase then the transition phase through $x_{n-1}$ must be
maximum acceleration to speed $V_{\max,n}$, coast to speed $U_{n}$ and maximum
brake. In this case the speed at $x_{n-1}$ must be
$U_{n-1}=U_{n-1}^{{\dagger}}(U_{n},V_{n-1},V_{\max,n})$ where the variables
$V_{\max,n}$ and $U_{n}$ must be chosen to satisfy the distance and time
constraints on $(x_{n-1},x_{n})$. See Appendix A.1 for details and an
application to a journey with one intermediate time constraint.

###### Remark 1

It is often possible to decide a priori on the correct choices for the
transitional phases in which case a single Newton iteration is sufficient to
determine the optimal times. In most cases $W_{i,j}<W_{i,j+1}\Rightarrow
V_{i,j}<V_{i,j+1}$ and $W_{i,j}>W_{i,j+1}\Rightarrow V_{i,j}>V_{i,j+1}$. If
the journey for ${\mathfrak{T}}_{i}$ consists of a sequence of shorter
journeys between scheduled stops then the separate journeys depend only on the
prescribed times and can be computed independently. $\hfill\Box$

##  9 A general solution algorithm

The following algorithm finds a near optimal schedule for a fleet of trains.

Step $1$. Define the table of active time constraints. Choose an error margin
$\epsilon>0$ for the cost.

Step $2$. Define $0=j(i,0)<j(i,1)<\cdots<j(i,p_{i})=n$ for each $i=1,\ldots,m$
to denote the stopping pattern
$0=x_{j(i,0)}<x_{j(i,1)}<\cdots<x_{j(i,p_{i})}=x_{n}$ for
${\mathfrak{T}}_{i}$.

Step $3$. Use a Newton iteration to find optimal times and speeds for the
constant-speed strategies. Repeat with appropriate speed penalties if the
timetable is unsuitable for realistic strategies.

Step $4$. For each $i=1,\ldots,m$ find the vector of optimal driving speeds
$\mbox{$\mbox{\boldmath$V$}$}_{i}$ for ${\mathfrak{T}}_{i}$ using realistic
strategies of optimal type on each segment of the journey subject to the times
generated at Step $3$. For ${\mathfrak{T}}_{i}$ the separate journey segments
will be
$(x_{j(i,0)},x_{j(i,1)}),(x_{j(i,1)},\,x_{j(i,2)}),\,\ldots,(x_{j(i,p_{i}-1)},x_{j(i,p_{i})})$.
If $j(i,r+1)=j(i,r)+1$ the strategy on segment $(x_{j(i,r)}.x_{j(i,r+1)})$
will be a long-haul strategy or a rapid-transit strategy. If
$j(i,r+1)>j(i,r)+1$ the strategy on segment $(x_{j(i,r)},x_{j(i,r+1)})$ will
be an optimal strategy with one or more intermediate time constraints.
Calculate
$J(\mbox{$\mbox{\boldmath$V$}$}_{1},\ldots,\mbox{$\mbox{\boldmath$V$}$}_{m})$.

Step $5$. Calculate the gradient $\mbox{$\mbox{\boldmath$\nabla$}$}J=\partial
J/\partial\mbox{$\mbox{\boldmath$h$}$}$ of the cost with respect to the
prescribed intermediate times defined by
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize old}}$ for the current
optimal driving speed vectors
$\mbox{$\mbox{\boldmath$V$}$}_{1},\ldots,\mbox{$\mbox{\boldmath$V$}$}_{m}$.
Move an appropriate distance $r$ in the direction of
$(-1)\mbox{$\mbox{\boldmath$\nabla$}$}J$ to find improved intermediate times
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
new}}=\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}}-r\mbox{$\mbox{\boldmath$\nabla$}$}J$. An approximate optimal value for
$r$ can be found using a golden search. This requires running Step $4$ for
each selected value of $r$.

Step $6$. Repeat Step $4$ using the new value
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
new}}=\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}}-r_{\mbox{\scriptsize
opt}}\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}})$.

Step $7$. If $J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize
old}})-J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize new}})>\epsilon$ go
to Step $5$. Else End.

##  10 Case studies

We will apply our results to the premium shuttle service operated by Abellio
ScotRail on the Glasgow Queen Street to Edinburgh Waverley via Falkirk line.
The trains in this service are a British Rail Class 385 AT 200 Hitachi
electric multiple unit operated as three or four cars driven respectively by
three or four 250 kW (335 hp) tandem motors with an IGBT converter/inverter.
The multiple unit can be effectively modelled in each case as a point mass
train using the equations of motion (1) and (2) with constraints on the
acceleration given by $H(v)\leq\min\\{P_{0},P_{1}/v\\}$ ms-2 where
$P_{0}=0.84$ ms-2 and $P_{1}=9.10$ m2s-3 and
$K(v)\leq\max\\{-Q_{0},-Q_{1}/v\\}$ ms-2 where $Q_{0}=1.00$ ms-2 and
$Q_{1}=10.83$ m2s-3 and with resistance $r(v)=r_{0}+r_{1}v+r_{2}v^{2}$ ms-2
where $r_{0}=0.12$ ms-2, $r_{1}=0.0001$ s-1 and $r_{2}=0.00004$ m-1. We assume
that the track is level. The key locations and a typical weekday timetable for
departures from Glasgow Queen Street at $15$-minute intervals over a
$60$-minute period are shown in Table 3. The station codes are Glasgow Queen
Street (GLQ), Bishopbriggs (BBG), Lenzie (LNZ), Croy (CRO), Falkirk High
(FKK), Polmont (PMT), Linlithgow (LIN), Winchburgh Junction (WGJ), Haymarket
(HYM) and Edinburgh Waverley (EDB).

Station | Position | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$
---|---|---|---|---|---
Glasgow Queen Street (GLQ) | $x_{0}=00000$ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$
Bishopbriggs (BBG) | $x_{1}=05140$ | — | — | — | —
Lenzie (LNZ) | $x_{2}=09980$ | — | — | — | —
Croy (CRO) | $x_{3}=18350$ | $t_{1,3}=780$ | — | $t_{3,3}=2520$ | —
Falkirk High (FKK) | $x_{4}=34820$ | $t_{1,4}=1380$ | $t_{2,4}=2040$ | $t_{3,4}=3120$ | $t_{4,4}=3820$
Polmont (PMT) | $x_{5}=40250$ | — | $t_{2,5}=2340$ | — | $t_{4,5}=4120$
Linlithgow (LIN) | $x_{6}=47590$ | — | $t_{2,6}=2700$ | — | $t_{4,6}=4780$
Winchburgh Junction (WGJ) | $x_{7}=55610$ | — | — | — | —
Haymarket (HYM) | $x_{8}=73010$ | $t_{1,8}=2760$ | $t_{2,8}=3840$ | $t_{3,8}=4560$ | $t_{4,8}=5460$
Edinburgh Waverley (EDB) | $x_{9}=75700$ | $t_{1,9}=3180$ | $t_{2,9}=4140$ | $t_{3,9}=4860$ | $t_{4,9}=5820$
Table 3: Published departure times for a $60$-minute period on a typical
weekday morning.

In practice safe separation is assured using a three-aspect signalling system
and a set of designated sections defined by the trackside signals. The precise
details depend on the number and location of the designated signals. We will
illustrate the underlying issues using nominal track sections defined by the
key locations shown in Table 3. We will assume that in normal operation we
require one clear section of track between successive trains at all times. The
mathematical optimization does not depend on the number of sections, the
lengths of the sections or on a common journey time. Nor does it depend on the
precise train performance functions although each train must have the capacity
to complete the entire journey in the scheduled time using a realistic
strategy.

We begin by designing energy-efficient schedules using (unrealistic) constant-
speed strategies for each train on each section. To ensure realistic outcomes
we may need to impose speed penalties on selected sections that recognise the
realistic constraints on maximum speed imposed by the train performance
functions and—if the train has to stop at particular stations—to allow
additional time for the train to speed up and slow down. For the Class 385 AT
200 Hitachi electric multiple-unit trains the upper bound on speed
$v=V_{\sup}$ can be calculated by solving the equation $H(v)-r(v)=0$. This
gives $V_{\sup}\approx 44.6011$ ms-1. For a typical speed $V_{t}=30$ ms-1 we
have

$\tau_{a,t}=\int_{0}^{V_{t}}dt_{a}(v)\approx
82.91\quad\mbox{and}\quad\xi_{a,t}=\int_{0}^{V_{t}}dx_{a}(v)\approx 1626.11.$

Thus the train takes $83$ s to reach speed $30$ ms-1 and travels $1626$ m. We
also have

$\tau_{c,t}=\int_{U_{b}(V_{t})}^{V_{t}}|dt_{c}(v)|\approx
147.33\quad\mbox{and}\quad\xi_{c,t}=\int_{U_{b}(V_{t})}^{V_{t}}|dx_{c}(v)|\approx
2857.28.$

Hence the train takes $147$ s to coast from a typical optimal driving speed
$V_{t}=30$ ms-1 to the associated optimal braking speed
$U_{b}(V_{t})=\psi(V_{t})/\varphi^{\,\prime}(V_{t})\approx 9.62$ ms-1 and
travels $2857$ m. The advantage of the constant-speed model—with or without
speed penalties—is that the optimal schedules can be conveniently computed
using a single multi-dimensional Newton iteration.

Once we have an initial feasible schedule for the realistic strategies—using
the weighted optimal constant-speed schedule—we can find an optimal schedule
using the method of steepest descent. At each step the optimal strategies
between stops for each train can be computed by a Newton iteration—an elegant
but much more protracted procedure than that required for the constant-speed
schedules. The case studies show that the realistic schedule is very similar
in structure to the constant-speed schedule. In each case the trains must go
faster on the longer sections.

###### Case Study 1

We use the published departure times for GLQ and EDB shown in Table 3. We
assume each train travels at the same constant speed on every section. The
journey times are $3180$ s for ${\mathfrak{T}}_{1}$, $3240$ s for
${\mathfrak{T}}_{2}$, $3060$ s for ${\mathfrak{T}}_{3}$ and $3120$ s for
${\mathfrak{T}}_{4}$. Trains ${\mathfrak{T}}_{1}$ and ${\mathfrak{T}}_{3}$
stop at CRO, FKK and HYM. Trains ${\mathfrak{T}}_{2}$ and ${\mathfrak{T}}_{4}$
stop at FKK, PMT, LIN and HYM. Where stops are scheduled the stopping time is
$\sigma=60$ s. The scheduled time is the departure time except at EDB.

The optimal speeds are $W_{1}=X/(T_{1}-3\sigma)=75700/3000\approx 25.23$ ms-1
for ${\mathfrak{T}}_{1}$, $W_{2}=X/(T_{2}-4\sigma)=75700/3000\approx 25.23$
ms-1 for ${\mathfrak{T}}_{2}$, $W_{3}=X/(T_{3}-3\sigma)=75700/2880\approx
26.28$ ms-1 for ${\mathfrak{T}}_{3}$ and
$W_{4}=X/(T_{4}-4\sigma)=75700/2880\approx 26.28$ ms-1 for
${\mathfrak{T}}_{4}$. The total cost is

$L=[r(W_{1})+r(W_{2})+r(W_{3})+r(W_{4})]X\approx 45156\ \mbox{{J kg}}^{-1}.$

For costing purposes we assume the trains have equal masses. The optimal
schedules are shown in Table 4. The brackets indicate that the train does not
stop. The train graphs are shown on the left in Figure 2. The shaded
rectangles show that the separation conditions are not always satisfied. To
satisfy the separation conditions using these strategies the departure times
must be delayed. The changes are $[0900,4140]\rightarrow[1104,4340]$ s for
${\mathfrak{T}}_{2}$, $[1800,4860]\rightarrow[2307,5367]$ s for
${\mathfrak{T}}_{3}$, $[2700,5820]\rightarrow[3372,6492]$ s for
${\mathfrak{T}}_{4}$ and $[3600,6780]\rightarrow[4384,7564]$ s for the repeat
service ${\mathfrak{T}}_{1,\star}$ in the next cycle. The line-occupancy
timespan for the fleet of four trains increases from $5820$ to $6492$ s. The
train graphs for the separated schedule are shown on the right in Figure 2.
$\hfill\Box$

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$ | ${\mathfrak{T}}_{1,\star}$
---|---|---|---|---|---
GLQ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$ | $t_{1,\star,0}=3600$
BBG | $(t_{1,1}=0204)$ | $(t_{2,1}=1104)$ | $(t_{3,1}=1996)$ | $(t_{4,1}=2896)$ | $(t_{1,\star,1}=3804)$
LNZ | ($t_{1,2}=0396)$ |  † $(t_{2,2}=1296)$ |  † $(t_{3,2}=2180)$ |  † $(t_{4,2}=3080)$ |  † $(t_{1,\star,2}=3996)$
CRO | $t_{1,3}=0787$ |  † $(t_{2,3}=1627)$ |  † $t_{3,3}=2558$ |  † $(t_{4,3}=3398)$ | $(t_{1,\star,3}=4387)$
FKK | $t_{1,4}=1500$ | $t_{2,4}=2340$ | $t_{3,4}=3245$ | $t_{4,4}=4085$ | $t_{1,\star,4}=5100$
PMT | $(t_{1,5}=1715)$ | $t_{2,5}=2615$ | $(t_{3,5}=3451)$ | $t_{4,5}=4351$ | $(t_{1,\star,5}=5315)$
LIN | $(t_{1,6}=2006)$ |  † $t_{2,6}=2966$ |  † $(t_{3,6}=3731)$ |  † $t_{4,6}=4691$ |  † $(t_{1,\star,6}=5605)$
WGJ | $(t_{1,7}=2324)$ | $(t_{2,7}=3284)$ |  † $(t_{3,7}=4036)$ | $(t_{4,7}=4996)$ | $(t_{1,\star,7}=5924)$
HYM | $t_{1,8}=3073$ | $t_{2,8}=4033$ | $t_{3,8}=4758$ | $t_{4,8}=5718$ | $t_{1,\star,8}=6673$
EDB | $t_{1,9}=3180$ | $t_{2,9}=4140$ | $t_{3,9}=4860$ | $t_{4,9}=5820$ | $t_{1,\star,9}=6780$
Table 4:  Case Study 1. Optimal constant-speed strategies for each train using
the scheduled starting times. The daggers † show instances where a train is
scheduled to reach a signal location too soon.

Figure 2: Case Study 1. Train graphs for the regular shuttle service from GLQ
to EDB using optimal constant-speed strategies with no separation constraints
(left) and with delayed departures to satisfy the separation conditions
(right). The shaded rectangles show that the unrestricted optimal strategies
do not satisfy the separation rules but that the delayed strategies do. The
cost is $L\approx 45156$ J kg-1 in each case. The line-occupancy timespan
increases from $5820$ to $6492$ s when the separation conditions are imposed.

###### Remark 2

Case Study 1 shows that if each train uses an individual optimal strategy the
safe separation conditions will be violated. If the departure times for
subsequent trains are delayed to ensure safe separation the cycle time
increases from 60 minutes to $74$ minutes. $\hfill\Box$

###### Case Study 2

We find optimal constant-speed strategies using the scheduled times for GLQ
and EDB with selective constraints to eliminate violations of the separation
conditions. In Case Study 1 we showed $t_{i+1,2}<t_{i,4}$, $t_{i+1,3}<t_{i,5}$
and $t_{i+1,6}<t_{i,8}$ for each $i=1,2,3$ and $t_{1,\star,2}<t_{4,4}$ and
$t_{1,\star,6}<t_{4,8}$ when there are no separation constraints. To ensure
minimal safe separation we set $t_{i+1,2}=t_{i,4}$, $t_{i+1,3}=t_{i,5}$ and
$t_{i+1,6}=t_{i,8}$ for each $i=1,2,3$ and $t_{1,\star,j-1}=t_{4,j+1}$ for
$j=1,2,5$. The variables and constraints are shown in Table 5. The vector of
unknown times is denoted by
$\mbox{$\mbox{\boldmath$h$}$}=(h_{1},\ldots,h_{12})$. We assume that
$W_{i,2}=W_{i,1}$ and $W_{i,8}=W_{i,7}$ for each $i=1,\ldots,4$.

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$ | ${\mathfrak{T}}_{1,\star}$
---|---|---|---|---|---
GLQ | $t_{1,0}=0$ | $t_{2,0}=900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$ | $t_{1,\star,0}=3600$
BBR | — | — | — | — | —
LNZ | $t_{1,2}=h_{1}$ | $t_{2,2}=h_{3}$ | $t_{3,2}=h_{7}$ | $t_{4,2}=h_{10}$ | $t_{1,\star,2}=h_{1}+3600$
CRO | $t_{1,3}=h_{2}$ | $t_{2,3}=h_{4}$ | $t_{3,3}=h_{8}$ | $t_{4,3}=h_{11}$ | $t_{1,\star,3}=h_{2}+3600$
FKK | $t_{1,4}=h_{3}$ | $t_{2,4}=h_{7}$ | $t_{3,4}=h_{10}$ | $t_{4,4}=h_{1}+3600$ | $t_{1,\star,4}=h_{3}+3600$
PMT | $t_{1,5}=h_{4}$ | $t_{2,5}=h_{8}$ | $t_{3,5}=h_{11}$ | $t_{4,5}=h_{2}+3600$ | $t_{1,\star,5}=h_{4}+3600$
LIN | $t_{1,6}=h_{5}$ | $t_{2,6}=h_{6}$ | $t_{3,6}=h_{9}$ | $t_{4,6}=h_{12}$ | $t_{1,\star,6}=h_{5}+3600$
WGJ | — | — | — | — | —
HYM | $t_{1,8}=h_{6}$ | $t_{2,8}=h_{9}$ | $t_{3,8}=h_{12}$ | $t_{4,8}=h_{5}+3600$ | $t_{1,\star,8}=h_{6}+3600$
EDB | $t_{1,9}=T_{1}$ | $t_{2,9}=T_{2}+900$ | $t_{3,9}=T_{3}+1800$ | $t_{4,9}=T_{4}+2700$ | $t_{5,9}=T_{1}+3600$
Table 5: Case Study 2. Departure time variables for the schedule optimization
subject to minimal required separation.

The speeds for train ${\mathfrak{T}}_{i}$ for each $i=1,\ldots,4$ are given by
the vector
$\mbox{$\mbox{\boldmath$W$}$}_{i}=\mbox{$\mbox{\boldmath$W$}$}_{i}(\mbox{$\mbox{\boldmath$h$}$})$
with components

$W_{i,j}=\left\\{\begin{array}[]{ll}(x_{2}-x_{0})/(t_{i,2}-\sigma_{i,2}-t_{i,0})&\mbox{for}\
j=1,2\\\ (x_{j}-x_{j-1})/(t_{i,j}-\sigma_{i,j}-t_{i,j-1})&\mbox{for}\
j=3,\ldots,6\\\ (x_{8}-x_{6})/(t_{i,8}-\sigma_{i,8}-t_{i,6})&\mbox{for}\
j=7,8\\\ (x_{9}-x_{8})/(t_{i,9}-t_{i,8})&\mbox{for}\ j=9.\end{array}\right.$

where $\sigma_{i,j}=\sigma$ if ${\mathfrak{T}}_{i}$ stops at $x_{j}$ for each
$j=1,\ldots,8$ and $\sigma_{i,j}=0$ otherwise. The total cost is

$L=\sum_{i=1}^{4}\left[\sum_{j=1}^{9}r(W_{i,j})(x_{j}-x_{j-1})\right]$

and the cost gradient vector is

$\mbox{$\mbox{\boldmath$\nabla$}$}L=\left[\begin{array}[]{l}\psi_{13}-\psi_{11}+\psi_{45}-\psi_{44}\\\
\psi_{14}-\psi_{13}+\psi_{46}-\psi_{45}\\\
\psi_{15}-\psi_{14}+\psi_{23}-\psi_{21}\\\
\psi_{16}-\psi_{15}+\psi_{24}-\psi_{23}\\\
\psi_{17}-\psi_{16}+\psi_{49}-\psi_{47}\\\
\psi_{19}-\psi_{17}+\psi_{27}-\psi_{26}\\\
\psi_{25}-\psi_{24}+\psi_{33}-\psi_{31}\\\
\psi_{26}-\psi_{25}+\psi_{34}-\psi_{33}\\\
\psi_{29}-\psi_{27}+\psi_{37}-\psi_{36}\\\
\psi_{35}-\psi_{34}+\psi_{43}-\psi_{41}\\\
\psi_{36}-\psi_{35}+\psi_{44}-\psi_{43}\\\
\psi_{39}-\psi_{37}+\psi_{47}-\psi_{46}\end{array}\right]$

where we have written $\psi_{i,j}=\psi(W_{i,j})$ for convenience. We use a
Newton iteration to solve the equation
$\mbox{$\mbox{\boldmath$\nabla$}$}L=\mbox{$\mbox{\boldmath$0$}$}$. The
iteration converges rapidly. The optimal speeds in ms-1 are

$\mbox{$\mbox{\boldmath$W$}$}=\left[\begin{array}[]{c}\mbox{$\mbox{\boldmath$W$}$}_{1}\\\
\mbox{$\mbox{\boldmath$W$}$}_{2}\\\ \mbox{$\mbox{\boldmath$W$}$}_{3}\\\
\mbox{$\mbox{\boldmath$W$}$}_{4}\end{array}\right]\approx\left[\begin{array}[]{ccccccccc}21.27&21.27&31.68&29.97&19.53&18.28&28.99&28.99&16.75\\\
19.84&19.84&30.11&30.60&20.07&20.98&30.71&30.71&11.55\\\
20.83&20.83&30.94&30.53&19.76&17.34&31.99&31.99&27.35\\\
19.61&19.61&30.46&31.35&20.55&23.81&29.53&29.53&19.56\end{array}\right].$

The optimal departure times are shown in Table 6 and the corresponding train
graphs are displayed on the left in Figure 3. The total cost is $L\approx
46295$ J kg-1.

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$
---|---|---|---|---
GLQ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$
BBG | $(t_{1,1}=0242)$ | $(t_{2,1}=1159)$ | $(t_{3,1}=2047)$ | $(t_{4,1}=2962)$
LNZ |  ($t_{1,2}=0469)$ | $(t_{2,2}=1403)$ | $(t_{3,2}=2279)$ | $(t_{4,2}=3209)$
CRO | $t_{1,3}=0793$ | $(t_{2,3}=1681)$ | $t_{3,3}=2610$ | $(t_{4,3}=3484)$
FKK | $t_{1,4}=1403$ | $t_{2,4}=2279$ | $t_{3,4}=3209$ | $t_{4,4}=4069$
PMT | $(t_{1,5}=1681)$ | $t_{2,5}=2610$ | $(t_{3,5}=3484)$ | $t_{4,5}=4393$
LIN | $(t_{1,6}=2083)$ | $t_{2,6}=3019$ | $(t_{3,6}=3907)$ | $t_{4,6}=4762$
WGJ | $(t_{1,7}=2378)$ | $(t_{2,7}=3300)$ | $(t_{3,7}=4177)$ | $(t_{4,7}=5052)$
HYM | $t_{1,8}=3019$ | $t_{2,8}=3907$ | $t_{3,8}=4762$ | $t_{4,8}=5683$
EDB | $t_{1,9}=3180$ | $t_{2,9}=4140$ | $t_{3,9}=4860$ | $t_{4,9}=5820$
Table 6: Case Study 2. Optimal constant-speed schedule with minimal
separation.

Ultimately we wish to find realistic strategies to implement the optimized
schedule. An effective schedule needs to allow for normal stochastic variation
in journey times by providing additional buffer times between successive
trains. If we set $t_{i+1,2}=t_{i,4}+60$, $t_{i+1,3}=t_{i,5}+60$ and
$t_{i+1,6}=t_{i,8}+60$ for each $i=1,2,3$ we will provide at least a $60$ s
buffer on each segment. There may be some segments on the constant-speed
schedule where the traversal time is less than the minimum time required by a
realistic strategy. If we wish to allow more time on $(x_{j-1},x_{j})$ for
${\mathfrak{T}}_{i}$ we can repeat the optimization with $r(W_{i,j})$ replaced
in the cost term by $r(W_{i,j}+p_{i,j})$ where $p_{i,j}>0$ is a fixed penalty.
In this case we set $p_{13}=2$, $p_{33}=1$ and $p_{39}=7$. The variables and
constraints are shown in Table 7.

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$ | ${\mathfrak{T}}_{1,\star}$
---|---|---|---|---|---
GLQ | $t_{1,0}=0$ | $t_{2,0}=900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$ | $t_{1,\star,0}=3600$
BBR | — | — | — | — | —
LNZ | $t_{1,2}=h_{1}$ | $t_{2,2}=h_{3}+60$ | $t_{3,2}=h_{7}+60$ | $t_{4,2}=h_{10}+60$ | $t_{1,\star,2}=h_{1}+3600$
CRO | $t_{1,3}=h_{2}$ | $t_{2,3}=h_{4}+60$ | $t_{3,3}=h_{8}+60$ | $t_{4,3}=h_{11}+60$ | $t_{1,\star,3}=h_{2}+3600$
FKK | $t_{1,4}=h_{3}$ | $t_{2,4}=h_{7}$ | $t_{3,4}=h_{10}$ | $t_{4,4}=h_{1}+3540$ | $t_{1,\star,4}=h_{3}+3600$
PMT | $t_{1,5}=h_{4}$ | $t_{2,5}=h_{8}$ | $t_{3,5}=h_{11}$ | $t_{4,5}=h_{2}+3540$ | $t_{1,\star,5}=h_{4}+3600$
LIN | $t_{1,6}=h_{5}$ | $t_{2,6}=h_{6}+60$ | $t_{3,6}=h_{9}+60$ | $t_{4,6}=h_{12}+60$ | $t_{1,\star,6}=h_{5}+3600$
WGJ | — | — | — | — | —
HYM | $t_{1,8}=h_{6}$ | $t_{2,8}=h_{9}$ | $t_{3,8}=h_{12}$ | $t_{4,8}=h_{5}+3540$ | $t_{1,\star,8}=h_{6}+3600$
EDB | $t_{1,9}=T_{1}$ | $t_{2,9}=T_{2}+900$ | $t_{3,9}=T_{3}+1800$ | $t_{4,9}=T_{4}+2700$ | $t_{1,\star,9}=T_{1}+3600$
Table 7: Case Study 2. Departure time variables for a weighted schedule
optimization with a $60$ s separation buffer.

Once again the Newton iteration converges rapidly. The optimal speeds in ms-1
are

$\mbox{$\mbox{\boldmath$W$}$}=\left[\begin{array}[]{c}\mbox{$\mbox{\boldmath$W$}$}_{1}\\\
\mbox{$\mbox{\boldmath$W$}$}_{2}\\\ \mbox{$\mbox{\boldmath$W$}$}_{3}\\\
\mbox{$\mbox{\boldmath$W$}$}_{4}\end{array}\right]\approx\left[\begin{array}[]{ccccccccc}19.21&19.21&33.43&31.74&21.09&16.58&31.68&31.68&12.89\\\
17.55&17.55&32.51&33.99&21.43&18.96&33.20&33.20&9.51\\\
18.80&18.80&33.03&32.94&21.22&16.06&34.20&34.20&19.26\\\
17.69&17.69&32.71&34.35&21.69&20.94&31.44&31.44&15.72\end{array}\right].$

The optimal departure times are shown in Table 8 and the corresponding train
graphs are displayed on the right in Figure 3. The total cost is $L\approx
47307$ J kg-1. $\hfill\Box$

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$
---|---|---|---|---
GLQ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$
BBG | $(t_{1,1}=0268)$ | $(t_{2,1}=1193)$ | $(t_{3,1}=2073)$ | $(t_{4,1}=2991)$
LNZ | ($t_{1,2}=0519)$ | $(t_{2,2}=1469)$ | $(t_{3,2}=2331)$ | $(t_{4,2}=3264)$
CRO | $t_{1,3}=0830$ | $(t_{2,3}=1726)$ | $t_{3,3}=2644$ | $(t_{4,3}=3520)$
FKK | $t_{1,4}=1409$ | $t_{2,4}=2271$ | $t_{3,4}=3204$ | $t_{4,4}=4059$
PMT | $(t_{1,5}=1666)$ | $t_{2,5}=2584$ | $(t_{3,5}=3460)$ | $t_{4,5}=4370$
LIN | $(t_{1,6}=2109)$ | $t_{2,6}=3031$ | $(t_{3,6}=3917)$ | $t_{4,6}=4780$
WGJ | $(t_{1,7}=2381)$ | $(t_{2,7}=3232)$ | $(t_{3,7}=4170)$ | $(t_{4,7}=4994)$
HYM | $t_{1,8}=2971$ | $t_{2,8}=3857$ | $t_{3,8}=4720$ | $t_{4,8}=5649$
EDB | $t_{1,9}=3180$ | $t_{2,9}=4140$ | $t_{3,9}=4860$ | $t_{4,9}=5820$
Table 8: Case Study 2. Optimal weighted constant-speed schedule with a $60$ s
separation buffer.

Figure 3: Case Study 2. Train graphs for the optimal constant-speed strategies
with minimal required separation (left) and optimal weighted constant-speed
strategies with a $60$ s separation buffer (right).

###### Remark 3

Case Study 2 shows that by inserting intermediate time constraints we can find
a schedule with no violations and additional buffer times between trains that
preserves the scheduled times at GLQ and EDB with only a marginal increase in
cost. The key observation is that the trains go faster on the longer sections.
The optimal schedule is a compromise between reducing the highest speeds and
equalising the section traversal times. $\hfill\Box$

###### Case Study 3

We construct optimal realistic strategies to fit the optimal weighted
constant-speed schedule with $60$ s buffer times obtained in Case Study 2.

Train ${\mathfrak{T}}_{1}$: The first segment is from GLQ to CRO. The time
allowed from GLQ to LNZ is $t_{1,2}-t_{1,0}=519$ s and from LNZ to CRO is
$t_{1,3}-\sigma-t_{1,2}=251$ s. The strategies in Case Study 2 suggest that
${\mathfrak{T}}_{1}$ must travel faster on the section LNZ to CRO. If so there
are two possible forms for the optimal realistic strategy. The two forms are
described and justified in Appendix A.1.

If there is no speedhold phase on the segment from LNZ to CRO then
${\mathfrak{T}}_{1}$ will use a strategy of maximum acceleration, speedhold at
speed $V_{11}=V_{12}$ on some segment $(a_{12},b_{12})\subset(x_{0},x_{2})$,
maximum acceleration through $x_{2}$ with speed
$U_{12}=U_{s}^{{\dagger}}(U_{13},V_{12},V_{13})$ at $x=x_{2}$ to reach a
maximum speed $V_{13}$ at some point $a_{13}\in(x_{2},x_{3})$, coast to speed
$U_{13}$ at some point $\gamma_{13}\in(x_{2},x_{3})$ and maximum brake. The
unknown parameters are $V_{12}$, $V_{13}$ and $U_{13}$. The distance travelled
on $(x_{2},x_{3})$ is

$\xi_{1,3}(U_{13},V_{12},V_{13})=\int_{U_{12}}^{V_{13}}dt_{a}(v)+\int_{U_{13}}^{V_{13}}|dt_{c}(v)|+\int_{0}^{U_{13}}|dt_{b}(v)|.$

The times taken on $(x_{0},x_{2})$ and $(x_{2},x_{3})$ are

$\tau_{1,2}(U_{13},V_{12},V_{13})=\int_{0}^{U_{12}}dt_{a}(v)+\frac{1}{V_{12}}\left[x_{2}-\int_{0}^{U_{12}}dx_{a}(v)\right],$
$\displaystyle\tau_{1,3}(U_{13},V_{12},V_{13})$ $\displaystyle=$
$\displaystyle\int_{U_{12}}^{V_{13}}dt_{a}(v)+\int_{U_{13}}^{V_{13}}|dt_{c}(v)|+\int_{0}^{U_{13}}|dt_{b}(v)|$

respectively. We apply a Newton iteration to solve the system of equations

$\displaystyle\xi_{1,3}(U_{13},V_{12},V_{13})-x_{3}+x_{2}$ $\displaystyle=$
$\displaystyle 0$ $\displaystyle\tau_{1,2}(U_{13},V_{12},V_{13})-t_{1,2}$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\tau_{1,3}(U_{13},V_{12},V_{13})-t_{1,3}+\sigma+t_{1,2}$
$\displaystyle=$ $\displaystyle 0$

with initial values $(U_{13},V_{12},V_{13})=(15,25,40)$. We obtain
$V_{11}=V_{12}\approx 17.4819$, $V_{13}\approx 41.2937$ and $U_{13}\approx
23.8935$ ms-1. We calculate $U_{12}\approx 35.2248$ ms-1. The cost is
$J_{1,03}\approx 3113.2266$ J kg-1. The speed profile is shown in Figure 4.
Since $U_{13}>U_{b}(V_{13})=\psi(V_{13})/\varphi^{\,\prime}(V_{13})\approx
17.4344$ ms-1 this is the optimal strategy. A strategy of optimal type with a
speedhold phase on $(x_{2},x_{3})$ will not be feasible.

Figure 4: Case Study 3. Optimal strategies for ${\mathfrak{T}}_{1}$ on the
segments from GLQ to CRO, from CRO to FKK and from FKK to HYM passing through
PMT, LIN and WGJ. The horizontal scales are different on each graph. Distances
are $18350$ m from GLQ to CRO, $16470$ m from CRO to FKK and $38190$ m from
FKK to HYM.

For the segment from CRO to FKK on $(x_{3},x_{4})$ train ${\mathfrak{T}}_{1}$
uses a long-haul strategy of maximum acceleration, speedhold at speed
$V_{14}$, coast to speed $U_{14}=U_{b}(V_{14})$ and maximum brake. The time
allowed is $t_{1,4}-\sigma-t_{1,3}=519$ s. The time taken on $(x_{3},x_{4})$
is

$\displaystyle\tau_{1,4}(V_{14})$ $\displaystyle=$
$\displaystyle\int_{0}^{V_{14}}dt_{a}(v)+\int_{U_{14}}^{V_{14}}|dt_{c}(v)|+\int_{0}^{U_{14}}|dt_{b}(v)|$
$\displaystyle\hskip
85.35826pt\frac{1}{V_{14}}\left[\int_{0}^{V_{14}}dx_{a}(v)+\int_{U_{14}}^{V_{14}}|dx_{c}(v)|+\int_{0}^{U_{14}}|dx_{b}(v)|\right].$

We use a Newton iteration to solve
$\tau_{1,4}(V_{14})-t_{1,4}+\sigma+t_{1,3}=0$ with initial value $V_{14}=40$.
We obtain $V_{14}\approx 41.2507$ ms-1. We calculate $U_{14}\approx 17.4032$
ms-1. The cost is $J_{1,34}\approx 3001.7179$ J kg-1. The speed profile is
shown in Figure 4.

For the segment from FKK to HYM on $(x_{4},x_{8})$ train ${\mathfrak{T}}_{1}$
uses a strategy of maximum acceleration, speedhold at speed $V_{15}$, coast
through PMT with speed $U_{15}=U_{s}(V_{15},V_{16})$, speedhold at speed
$V_{16}$, maximum acceleration through LIN with speed
$U_{16}=U_{s}(V_{16},V_{17})$, speedhold at speed $V_{17}=V_{18}$ through WGJ,
coast to speed $U_{18}=U_{b}(V_{18})$ and maximum brake. The time constraints
are $t_{1,5}-t_{1,4}=257$, $t_{1,6}-t_{1,5}=443$, and $t_{1,8}-\sigma-
t_{1,6}=802$ s. The respective times are

$\tau_{1,5}(V_{15},V_{16})=\int_{0}^{V_{15}}dt_{a}(v)+\int_{U_{15}}^{V_{15}}|dt_{c}(v)|+\frac{1}{V_{15}}\left[x_{5}-x_{4}-\int_{0}^{V_{15}}dx_{a}(v)-\int_{U_{15}}^{V_{15}}|dx_{c}(v)|\right],$
$\tau_{1,6}(V_{15},V_{16},V_{18})=\int_{V_{16}}^{U_{15}}|dt_{c}(v)|+\int_{V_{16}}^{U_{16}}dt_{a}(v)+\frac{1}{V_{16}}\left[x_{6}-x_{5}-\int_{V_{16}}^{U_{15}}|dx_{c}(v)|-\int_{V_{16}}^{U_{16}}dx_{a}(v)\right],$
$\tau_{1,8}(V_{16},V_{18})=\int_{U_{18}}^{V_{18}}|dt_{c}(v)|+\int_{0}^{U_{18}}|dt_{b}(v)|+\frac{1}{V_{18}}\left[x_{8}-x_{6}-\int_{U_{18}}^{V_{18}}|dx_{c}(v)|-\int_{0}^{U_{18}}|dx_{b}(v)|\right].$

We apply a Newton iteration to solve the system of equations

$\displaystyle\tau_{1,5}(V_{15},V_{16})-t_{1,5}+t_{1,4}$ $\displaystyle=$
$\displaystyle 0$
$\displaystyle\tau_{1,6}(V_{15},V_{16},V_{18})-t_{1,6}+t_{1,5}$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\tau_{1,8}(V_{16},V_{18})-t_{1,8}+\sigma+t_{1,6}$
$\displaystyle=$ $\displaystyle 0$

using the initial value $(V_{15},V_{16},V_{18})=(21,18,30)$. We obtain
$V_{15}\approx 22.9024$, $V_{16}\approx 15.9710$ and $V_{17}=V_{18}\approx
34.5262$ ms-1. We calculate $U_{15}\approx 19.6342$, $U_{16}\approx 26.3486$
and $U_{18}\approx 12.6385$ ms-1. The cost is $J_{1,48}\approx 6070.0102$ J
kg-1. The speed profile is shown in Figure 4.

For the segment from HYM to EDB on $(x_{8},x_{9})$ train ${\mathfrak{T}}_{1}$
uses a long-haul strategy of maximum acceleration, speedhold at speed
$V_{19}$, coast to speed $U_{19}=U_{b}(V_{19})$ and maximum brake. The time
constraint is $t_{1,9}-t_{1,8}=209$ s. The time taken is

$\displaystyle\tau_{1,9}(V_{19})$ $\displaystyle=$
$\displaystyle\int_{0}^{V_{19}}dt_{a}(v)+\int_{U_{19}}^{V_{19}}|dt_{c}(v)|+\int_{0}^{U_{19}}|dt_{b}(v)|$
$\displaystyle\hskip
85.35826pt+\frac{1}{V_{19}}\left[x_{9}-x_{8}-\int_{0}^{V_{19}}dx_{a}(v)-\int_{U_{19}}^{V_{19}}|dx_{c}(v)|-\int_{0}^{U_{19}}|dx_{b}(v)|\right].$

We use a Newton iteration to solve $\tau_{1,9}(V_{19})-t_{1,9}+t_{1,8}=0$ with
initial value $V_{19}=15$. We obtain $V_{19}\approx 19.0591$ ms-1. We
calculate $U_{19}\approx 3.5255$ ms-1 and $J_{1,89}\approx 359.5285$ J kg-1.
The speed profile is shown in Figure 5. The total cost for
${\mathfrak{T}}_{1}$ is

$J_{1}=J_{1,03}+J_{1,34}+J_{1,48}+J_{1,89}\approx 12544.4832\ \mbox{{J
kg}}^{-1}.$ (36)

Figure 5: Case Study 3. Optimal strategies for ${\mathfrak{T}}_{1}$ on the
segment from HYM to EDB (left) and ${\mathfrak{T}}_{2}$ on the segments from
GLQ to FKK (centre) and FKK to PMT (right). The horizontal scales are
different on each graph. Distances are $2690$ m from HYM to EDB, $34820$ m
from GLQ to FKK and $5430$ m from FKK to PMT.

Train ${\mathfrak{T}}_{2}$: The strategies in Case Study 2 suggest that on the
segment from GLQ to FKK train ${\mathfrak{T}}_{2}$ should use a strategy of
maximum acceleration, speedhold at speed $V_{21}=V_{22}$ through BBG at
$x_{1}$, maximum acceleration through LNZ with speed
$U_{22}=U_{s}(V_{22},V_{23})$ at $x_{2}$, speedhold at speed $V_{23}$, maximum
acceleration through CRO with speed $U_{23}=U_{s}(V_{23},V_{24})$ at $x_{3}$,
speedhold at speed $V_{24}$, coast to speed $U_{24}=U_{b}(V_{24})$ and maximum
brake. The time constraints are $t_{2,2}-t_{2,0}=569$, $t_{2,3}-t_{2,2}=257$,
and $t_{2,4}-\sigma-t_{2,3}=485$ s. The respective times taken are

$\tau_{2,2}(V_{22},V_{23})=\int_{0}^{U_{22}}dt_{a}(v)+\frac{1}{V_{22}}\left[x_{2}-x_{0}-\int_{0}^{U_{22}}dx_{a}(v)\right],$
$\tau_{2,3}(V_{22},V_{23},V_{24})=\int_{U_{22}}^{U_{23}}dt_{a}(v)+\frac{1}{V_{23}}\left[x_{3}-x_{2}-\int_{U_{22}}^{U_{23}}dx_{a}(v)\right],$
$\displaystyle\tau_{2,4}(V_{23},V_{24})$ $\displaystyle=$
$\displaystyle\int_{U_{23}}^{V_{24}}dt_{a}(v)+\int_{U_{24}}^{V_{24}}|dt_{c}(v)|+\int_{0}^{U_{24}}|dt_{b}(v)|$
$\displaystyle\hskip
56.9055pt+\frac{1}{V_{24}}\left[x_{4}-x_{3}-\int_{U_{23}}^{V_{24}}dx_{a}(v)-\int_{U_{24}}^{V_{24}}|dx_{c}(v)|-\int_{0}^{U_{24}}|dx_{b}(v)|\right].$

We apply a Newton iteration to solve the system of equations

$\displaystyle\tau_{2,2}(V_{22},V_{23})-t_{2,2}+t_{2,0}$ $\displaystyle=$
$\displaystyle 0$
$\displaystyle\tau_{2,3}(V_{22},V_{23},V_{24})-t_{2,3}+t_{2,2}$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\tau_{2,4}(V_{23},V_{24})-t_{2,4}+\sigma+t_{2,3}$
$\displaystyle=$ $\displaystyle 0$

using initial values $(V_{22},V_{23},V_{24})=(20,30,35)$. We obtain
$V_{21}=V_{22}\approx 17.6871$, $V_{23}\approx 32.9234$ and $V_{24}\approx
38.8491$ ms-1. We calculate $U_{22}\approx 26.0454$, $U_{23}\approx 35.9660$,
$U_{24}\approx 15.6746$ ms-1 and $J_{2,04}\approx 5750.0444$ J kg-1. The speed
profile is shown in Figure 5.

Figure 6: Case Study 3. Optimal strategies for ${\mathfrak{T}}_{2}$ on the
segments from PMT to LIN (left), from LIN to HYM (centre) and from HYM to EDB
(right). The horizontal scales are different on each graph. Distances are
$7340$ m from PMT to LIN, $25420$ m from LIN to HYM and $2690$ m from HYM to
EDB.

The optimal strategy for ${\mathfrak{T}}_{2}$ from FKK to PMT is a rapid-
transit strategy with $U_{25}\approx 12.8945$ and $V_{25}\approx 32.6508$ ms-1
and $J_{2,45}\approx 874.9529$ J kg-1. The speed profile is shown in Figure 5.
The remaining strategies are all standard long-haul strategies from PMT to LIN
with $V_{26}\approx 23.6455$ ms-1, $U_{26}=U_{b}(V_{26})\approx 5.8051$ ms-1
and $J_{2,56}\approx 1047.6125$ J kg-1, from LIN to HYM with $V_{28}\approx
38.7348$ ms-1, $U_{28}=U_{b}(V_{28})\approx 15.5929$ ms-1 and $J_{2,68}\approx
4563.8225$ J kg-1, and from HYM to EDB with $V_{29}\approx 11.4642$ ms-1,
$U_{29}=U_{b}(V_{29})\approx 0.9682$ ms-1 and $J_{2,89}\approx 338.5729$ J
kg-1. The speed profiles are shown in Figure 6. The total cost for
${\mathfrak{T}}_{2}$ is

$J_{2}=J_{2,04}+J_{2,45}+J_{2,56}+J_{2,68}+J_{2,89}\approx 12575.0052\
\mbox{{J kg}}^{-1}.$ (37)

Train ${\mathfrak{T}}_{3}$: The strategies for ${\mathfrak{T}}_{3}$ are
similar to those for ${\mathfrak{T}}_{1}$. The optimal driving speeds from GLQ
to CRO are $V_{31}=V_{32}\approx 17.1769$, $V_{33}\approx 41.1474$,
$U_{33}\approx 23.3292$,
$U_{32}=U_{s}^{{\dagger}}(U_{33},V_{23},V_{33})\approx 34.8388$ ms-1 and
$J_{3,03}\approx 3086.6375$ J kg-1. The speed profile is shown in Figure 7.
The optimal strategy from CRO to FKK is a rapid-transit strategy with
$U_{34}\approx 22.7752$ and $V_{34}\approx 43.2069$ ms-1 and with
$J_{3,34}\approx 3139.5673$ J kg-1. The optimal strategy for
${\mathfrak{T}}_{3}$ from FKK to HYM takes the same form as the strategy for
${\mathfrak{T}}_{1}$. The speeds are $V_{35}\approx 23.0633$, $V_{36}\approx
15.1369$ and $V_{37}=V_{38}\approx 37.7486$ ms-1. We calculate
$U_{35}=U_{s}(V_{35},V_{36})\approx 19.3628$,
$U_{36}=U_{s}(V_{36},V_{38})\approx 28.0048$ and $U_{38}=U_{b}(V_{38})\approx
14.8912$ ms-1. The cost is $J_{3,48}\approx 6296.2674$ J kg-1. The speed
profile is shown in Figure 7. The optimal strategy for the segment from HYM to
EDB is a rapid-transit strategy with $U_{39}\approx 21.2930$ and
$V_{39}\approx 28.12294$ ms-1 and $J_{3,89}\approx 576.9359$ J kg-1. The total
cost for ${\mathfrak{T}}_{3}$ is

$J_{3}=J_{3,03}+J_{3,34}+J_{3,48}+J_{3,89}\approx 13099.4081\ \mbox{{J
kg}}^{-1}.$ (38)

Figure 7: Case Study 3. Optimal strategies for ${\mathfrak{T}}_{3}$ from GLQ
to CRO (left) and from FKK to HYM (centre) and for ${\mathfrak{T}}_{4}$ from
LIN to HYM (right). The horizontal scales are different on each graph.
Distances are $18350$ m from GLQ to CRO, $38190$ m from FKK to HYM and $25420$
m from LIN to HYM.

Train ${\mathfrak{T}}_{4}$: The strategies for ${\mathfrak{T}}_{4}$ are
similar to those for ${\mathfrak{T}}_{2}$. For the first segment from GLQ to
FKK the optimal driving speeds are $V_{41}=V_{42}\approx 17.8532$,
$V_{43}\approx 33.0054$ and $V_{44}\approx 39.4441$ ms-1. We calculate
$U_{42}=U_{s}(V_{42},V_{43})\approx 26.1578$,
$U_{43}=U_{s}(V_{43},V_{44})\approx 36.3180$ and $U_{44}=U_{b}(V_{44})\approx
16.1006$ ms-1. The cost is $J_{4,04}\approx 5785.1358$ J kg-1. The speed
profile is shown in Figure 7. The strategy from FKK to PMT is a rapid-transit
strategy with $U_{45}\approx 13.3900$ and $V_{45}\approx 32.7408$ ms-1. The
cost is $J_{4,45}\approx 882.2498$ J kg-1. The strategy from PMT to LIN, is a
long-haul strategy with $V_{46}\approx 27.5398$ and
$U_{46}=U_{b}(V_{46})\approx 8.0677$ ms-1. The cost is $J_{4,56}\approx
1099.2413$ J kg-1. The strategy from LIN to HYM is also a long-haul strategy
with $V_{47}=V_{48}\approx 35.9119$ and $U_{48}=U_{b}(V_{48})\approx 13.5989$
ms-1. The cost is $J_{4,68}\approx 4379.5172$ J kg-1. The optimal strategy
from HYM to EDB is a rapid-transit strategy with $U_{49}\approx 9.7601$ and
$V_{49}\approx 24.4923$ ms-1. The cost is $J_{4,89}\approx 406.9617$ J kg-1.
The total cost for ${\mathfrak{T}}_{4}$ is

$J_{4}=J_{4,04}+J_{4,45}+J_{4,56}+J_{4,68}+J_{4.89}=12553.1058\ \mbox{{J
kg}}^{-1}.$ (39)

This means that the overall cost for a realistic implementation of the
weighted optimal constant-speed schedule from Case Study 2 is

$J=J_{1}+J_{2}+J_{3}+J_{4}\approx 50772.0023\ \mbox{{J kg}}^{-1}.$ (40)

In adding the costs we have once again assumed that the masses of the trains
are all equal. $\hfill\Box$

###### Remark 4

Case Study 3 shows that the optimal weighted constant-speed timetable from
Case Study 2 provides a feasible schedule for the optimal realistic
strategies. $\hfill\Box$

###### Case Study 4

We can use the optimal driving speeds calculated in Case Study 3 to find an
improved timetable for the realistic strategies. The journey times used in
Case Study 3 are obtained from the vector
$\mbox{$\mbox{\boldmath$h$}$}=[h_{j}]_{j=1}^{12}$ defined in Table 7 with
values given in Table 8. We have

$\mbox{$\mbox{\boldmath$h$}$}^{T}=[519,830,1409,1666,2109,2971,2271,2584,3857,3204,3460,4720].$

The cost gradient vector with respect to $h$ at this point is given by

$\mbox{$\mbox{\boldmath$\nabla$}$}J=\left[\begin{array}[]{l}\psi_{13}^{{\dagger}}-\psi_{12}+\psi_{45}^{{\dagger}}-\psi_{44}\\\
\psi_{14}-\psi_{13}^{{\dagger}}+\psi_{46}-\psi_{45}^{{\dagger}}\\\
\psi_{15}-\psi_{14}+\psi_{23}-\psi_{22}\\\
\psi_{16}-\psi_{15}+\psi_{24}-\psi_{23}\\\
\psi_{18}-\psi_{16}+\psi_{49}^{{\dagger}}-\psi_{48}\\\
\psi^{{\dagger}}_{19}-\psi_{18}+\psi_{28}-\psi_{26}\\\
\psi_{25}^{{\dagger}}-\psi_{24}+\psi_{33}^{{\dagger}}-\psi_{32}\\\
\psi_{26}-\psi_{25}^{{\dagger}}+\psi_{34}^{{\dagger}}-\psi_{33}^{{\dagger}}\\\
\psi_{29}-\psi_{28}+\psi_{38}-\psi_{36}\\\
\psi_{35}-\psi_{34}^{{\dagger}}+\psi_{43}-\psi_{42}\\\
\psi_{36}-\psi_{35}+\psi_{44}-\psi_{43}\\\
\psi_{39}^{{\dagger}}-\psi_{38}+\psi_{48}-\psi^{{\dagger}}_{46}\end{array}\right]$

where $\psi_{i,j}=\psi(V_{i,j})$ for the standard entries and
$\psi^{{\dagger}}_{i,j}=\varphi(V_{i,j})U_{i,j}/(V_{i,j}-U_{i,j})$ for the
non-standard entries corresponding to sections with no speedhold segment where
$V_{i,j}$ is a maximum speed rather than an optimal driving speed. The
calculations in Case Study 3 give

$\mbox{$\mbox{\boldmath$\nabla$}$}J^{T}\approx[9.16,-7.12,-2.29,1.22,1.61,0.86,8.60,2.38,-0.52,-6.06,1.34,11.17].$

We calculate $\|\mbox{$\mbox{\boldmath$\nabla$}$}J\|\approx 19.79$. We can now
compute an improved timetable by defining a new value of $h$ using the formula
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
new}}=\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}}-r\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}})$ where $r=r_{0}>0$ is chosen so that

$J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize new}})=\min_{r\geq
0}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}}-r\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}}))=J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}}-r_{0}\mbox{$\mbox{\boldmath$\nabla$}$}J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
old}})).$

Some preliminary calculations reveal that $r_{0}\approx 1.5$. This gives

$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize
new}}^{T}\approx[505,841,1412,1664,2107,2970,2258,2580,3858,3213,3458,4703]$

where we have taken the components of
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize new}}$ as the nearest
integer to the computed value. We substitute
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\rm\scriptsize new}}$ into Table 7 to
obtain the improved timetable shown in Table 9.

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$
---|---|---|---|---
GLQ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$
BBG | — | — | — | —
LNZ |  ($t_{1,2}=0505)$ | $(t_{2,2}=1472)$ | $(t_{3,2}=2318)$ | $(t_{4,2}=3273)$
CRO | $t_{1,3}=0841$ | $(t_{2,3}=1724)$ | $t_{3,3}=2640$ | $(t_{4,3}=3518)$
FKK | $t_{1,4}=1412$ | $t_{2,4}=2258$ | $t_{3,4}=3213$ | $t_{4,4}=4045$
PMT | $(t_{1,5}=1664)$ | $t_{2,5}=2580$ | $(t_{3,5}=3458)$ | $t_{4,5}=4381$
LIN | $(t_{1,6}=2107)$ | $t_{2,6}=3030$ | $(t_{3,6}=3918)$ | $t_{4,6}=4763$
WGJ | — | — | — | —
HYM | $t_{1,8}=2970$ | $t_{2,8}=3858$ | $t_{3,8}=4703$ | $t_{4,8}=5647$
EDB | $t_{1,9}=3180$ | $t_{2,9}=4140$ | $t_{3,9}=4860$ | $t_{4,9}=5820$
Table 9: Case Study 4. Scheduled departure times for the improved timetable.

We now calculate revised optimal strategies for the new schedule. The
calculations are similar to the previous calculations but not identical. The
calculations are summarised below.

Train ${\mathfrak{T}}_{1}$: From GLQ to CRO the strategy takes the same form
as the original strategy. We have $V_{11}=V_{12}\approx 19.4930$,
$V_{13}\approx 39.8883$, $U_{13}\approx 17.2814$ ms-1. We calculate
$U_{12}\approx 31.5081$ ms-1 and $J_{1,03}\approx 2923.8157$ J kg-1. From CRO
to FKK the optimal strategy is a rapid-transit strategy defined by
$U_{14}\approx 19.0041$ and $V_{14}\approx 43.0894$ ms-1 with $J_{1,34}\approx
3051.2727$ J kg-1. From FKK to HYM the strategy is similar to the original
strategy with $V_{15}\approx 23.4916$, $V_{16}\approx 15.9525$ and
$V_{17}=V_{18}\approx 34.4778$ ms-1. We calculate
$U_{15}=U_{s}(V_{15},V_{16})\approx 19.9525$ and
$U_{16}=U_{s}(V_{16},V_{17})\approx 26.3131$ ms-1 and $J_{1,48}\approx
6071.8661$ J kg-1. From HYM to EDB the optimal strategy is a long-haul
strategy with $V_{19}\approx 18.8740$, $U_{19}=U_{b}(V_{19})\approx 3.4440$
ms-1 and $J_{1,89}\approx 358.9467$ J kg-1. Total cost for
${\mathfrak{T}}_{1}$ is $J_{1}\approx 12405.9012$ J kg-1.

Train ${\mathfrak{T}}_{2}$: From GLQ to FKK the strategy takes the same form
as the original strategy with $V_{21}=V_{22}\approx 17.5539$, $V_{23}\approx
33.6036$ and $V_{24}\approx 39.9312$ ms-1. We calculate
$U_{22}=U_{s}(V_{22},V_{23})\approx 26.3195$,
$U_{23}=U_{s}(V_{23},V_{24})\approx 36.8562$, $U_{24}=U_{b}(V_{24})\approx
16.4505$ ms-1 and $J_{2,04}\approx 5819.3861$ J kg-1. The remaining strategies
are all long-haul strategies. From FKK to PMT we have $V_{25}\approx 31.8910$
ms-1 with $U_{25}=U_{b}(V_{25})\approx 10.8543$ ms-1 and $J_{2,45}\approx
847.1220$ J kg-1. From PMT to LIN we have $V_{26}\approx 23.3843$,
$U_{26}=U_{b}(V_{26})\approx 5.6630$ ms-1 and $J_{2,56}\approx 1044.3267$ J
kg-1. From LIN to HYM we have $V_{27}=V_{28}\approx 38.5875$ ms-1 and with
$U_{28}=U_{b}(V_{28})\approx 15.4879$ ms-1 and $J_{2,68}\approx 4554.2779$ J
kg-1. From HYM to EDB we have $V_{19}\approx 11.5225$ and
$U_{29}=U_{b}(V_{29})\approx 0.9814$ ms-1. The cost is $J_{2,89}\approx
338.7075$ J kg-1. The total cost for ${\mathfrak{T}}_{2}$ is $J_{2}\approx
12603.8202$ J kg-1.

Train ${\mathfrak{T}}_{3}$: From GLQ to CRO the strategy takes the same form
as the original strategy. We have $V_{31}=V_{32}\approx 18.3070$,
$V_{33}\approx 40.6212$ and $U_{33}\approx 20.6766$ ms-1. We calculate
$U_{32}=U_{s}^{{\dagger}}(U_{33},V_{31},V_{32})\approx 33.5071$ ms-1 and
$J_{3,03}\approx 3011.0629$ J kg-1. From CRO to FKK the optimal strategy is a
rapid-transit strategy with $U_{34}\approx 18.4111$ and $V_{34}=43.0711$ ms-1
and $J_{3,34}\approx 3038.1430$ J kg-1. From FKK to HYM the strategy is
similar to the original strategy with $V_{35}\approx 24.4651$,
$V_{36}=14.8277$ and $V_{37}=V_{38}\approx 38.8945$ ms-1. We calculate
$U_{35}=U_{s}(V_{35},V_{36})\approx 20.0243$ and
$U_{36}=U_{s}(V_{36},V_{37})\approx 28.6040$ ms-1 and $J_{3,48}\approx
6391.4530$ J kg-1. From HYM to EDB the optimal strategy is a rapid-transit
strategy with $U_{39}\approx 13.5260$ and $V_{39}\approx 25.5566$ ms-1 and
$J_{3,89}\approx 451.7930$ J kg-1. Total cost for ${\mathfrak{T}}_{3}$ is
$J_{3}\approx 12882.4519$ J kg-1.

Train ${\mathfrak{T}}_{4}$: From GLQ to FKK the strategy takes the same form
as the original strategy with $V_{41}=V_{42}\approx 17.4604$, $V_{43}\approx
34.7200$ and $V_{44}\approx 40.6221$ ms-1. We calculate
$U_{42}=U_{s}(V_{42},V_{43})\approx 27.0122$,
$U_{43}=U_{s}(V_{43},V_{44})\approx 37.7464$ and $U_{44}=U_{b}(V_{44})\approx
16.9485$ ms-1 and $J_{4,04}\approx 5879.7786$ J kg-1. The next three
strategies are all long-haul strategies. From FKK to PMT we have
$V_{45}\approx 28.4459$ ms-1 with $U_{45}=U_{b}(V_{45})\approx 8.6284$ ms-1
and $J_{4,45}\approx 815.3487$ J kg-1. From PMT to LIN we have $V_{46}\approx
31.8700$, $U_{46}=U_{b}(V_{46})\approx 10.8403$ ms-1 and $J_{4,56}\approx
1159.8224$ J kg-1. From LIN to HYM we have $V_{47}=V_{48}\approx 35.0587$ ms-1
and we calculate $U_{48}=U_{b}(V_{48})\approx 13.0060$ ms-1 and
$J_{4,68}\approx 4324.0217$ J kg-1. From HYM to EDB we have a rapid-transit
strategy with $U_{49}\approx 9.3007$ and $V_{49}\approx 24.3787$ ms-1 and
$J_{4,89}\approx 402.3895$ J kg-1. The total cost for ${\mathfrak{T}}_{4}$ is
$J_{2}\approx 12581.3709$ J kg-1.

The overall cost for all trains using the improved timetable is

$J=J_{1}+J_{2}+J_{3}+J_{4}\approx 50473.8853\ \mbox{{J kg}}^{-1}$ (41)

which is a modest improvement on the original cost. Once again we have assumed
that the masses of the trains are equal. We could continue to reduce the
overall cost by repeated application of the method of steepest descent.
$\hfill\Box$

###### Remark 5

Case Study 4 shows that we can use the elegant cost gradient formula to find
an improved clearance time vector
$\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize new}}$ and a corresponding
reduced cost $J=J(\mbox{$\mbox{\boldmath$h$}$}_{\mbox{\scriptsize new}})$.
Although it seems that the major task in this procedure is calculation of
optimal speed profiles for each train it is pertinent to realise that the
Energymiser® system (known as Opti-Conduite in France:
https://www.sncf.com/fr/groupe/newsroom/opticonduite-energie-economisee) is
currently used on-board the famed TGV service operated by SNCF in France to
continually update optimal driving strategies for journeys in excess of $100$
km in a matter of a few seconds. $\hfill\Box$

###### Case Study 5

We will show that trains with similar but not identical performance functions
can use the same timetable. We assume that the alternative train satisfies (1)
and (2) with $H(v)=\min\\{P_{0},P_{1}/v\\}$ ms-2 where $P_{0}=1.00$ ms-2 and
$P_{1}=7.00$ m2s-3 and $K(v)=\max\\{-Q_{0},-Q_{1}/v\\}$ ms-2 where $Q_{0}=1.5$
ms-2 and $Q_{1}=9.00$ m2s-3 and with resistance $r(v)=r_{0}+r_{1}v+r_{2}v^{2}$
ms-2 where $r_{0}=0.070$ ms-2, $r_{1}=0$ s-1 and $r_{2}=0.00005$ m-1. We use
the schedule in Case Study 4.

On the segment from FKK to HYM train ${\mathfrak{T}}_{1,a}$ uses a similar
strategy to ${\mathfrak{T}}_{1}$ with $V_{15}\approx 23.6161$, $V_{16}\approx
15.7257$, $V_{17}=V_{18}\approx 34.5982$, $U_{15}=U_{s}(V_{22},V_{23})\approx
19.9346$, $U_{16}=U_{s}(V_{16},V_{17})\approx 26.3416$ and
$U_{18}=U_{b}(V_{18})\approx 16.5956$ ms-1 and with $J_{1,a,48}\approx
4423.5502$ J kg-1.

Train ${\mathfrak{T}}_{2,a}$ uses a similar strategy to train
${\mathfrak{T}}_{2}$ from GLQ to FKK with $V_{21}=V_{22}\approx 17.4394$,
$V_{23}\approx 33.6715$, $V_{24}\approx 40.0411$,
$U_{22}=U_{s}(V_{22},V_{23})\approx 26.4147$,
$U_{23}=U_{s}(V_{23},V_{24})\approx 36.9481$ and $U_{24}=U_{b}(V_{24})\approx
20.6759$ ms-1 and with $J_{2,a,14}\approx 4379.3064$ J kg-1.

The optimal strategy for ${\mathfrak{T}}_{3,a}$ from FKK to HYM is similar to
the strategy for ${\mathfrak{T}}_{3}$ with $V_{35}\approx 24.7406$,
$V_{36}\approx 14.3727$ and $V_{37}=V_{38}\approx 39.1359$ ms-1 with
$U_{32}=U_{s}(V_{32},V_{33})\approx 20.0147$,
$U_{33}=U_{s}(V_{33},V_{34})\approx 28.6643$ and $U_{24}=U_{b}(V_{34})\approx
19.9975$ ms-1 and with $J_{3,a,48}\approx 4815.7082$ J kg-1.

Figure 8: Case Study 5. Optimal strategies for ${\mathfrak{T}}_{1}$ from FKK
to HYM (left), for ${\mathfrak{T}}_{2}$ from GLQ to FKK (centre) and for
${\mathfrak{T}}_{3}$ from FKK to HYM using the improved timetable in Case
Study 4 and an alternative train model. The horizontal scale on the centre
graph is different but the horizontal scale of the other graphs is the same.
Distances are $38190$ m from FKK to HYM and $34820$ m from GLQ to FKK.

The speed profiles are shown in Figure 8. Although the profiles are similar to
the corresponding profiles for ${\mathfrak{T}}_{1}$, ${\mathfrak{T}}_{2}$ and
${\mathfrak{T}}_{3}$ the cost for ${\mathfrak{T}}_{1,a}$,
${\mathfrak{T}}_{2,a}$ and ${\mathfrak{T}}_{3,a}$ is significantly less
because the static resistance is lower. The key observed impact of the static
resistance defined by $r_{0}$ is the effect on cost whereas the key observed
impact of $r_{2}$ is to limit the maximum achievable speed. $\hfill\Box$

###### Remark 6

Case Study 5 shows that trains with similar but not identical performance
functions can drive to the same timetable. The entire process of timetable
development can be implemented in precisely the same way if the trains
${\mathfrak{T}}_{i}$ are not identical. The speed profile and the costs for
${\mathfrak{T}}_{i}$ depend only on the performance functions and the
scheduled times. $\hfill\Box$

##  11 Train separation with stochastic journey evolution

It is important that theoretical strategies can be implemented effectively in
practice. When pre-planned strategies are implemented on real trains there
will inevitably be small discrepancies between planned and actual schedules.
This can cause unwanted difficulties. When safe separation requires
coordinated clearance times and ${\mathfrak{T}}_{i}$ is slightly behind
schedule with $t_{i,j+1}=h_{i,j+1}+\epsilon_{i,j}$ or ${\mathfrak{T}}_{i+1}$
is slightly ahead of schedule with $t_{i+1,j-1}=h_{i+1,j-1}-\epsilon_{i+1,j}$
where $h_{i,j+1}=h_{i+1,j-1}$ the signal for ${\mathfrak{T}}_{i+1}$ at
$x_{j-1}$ will be yellow and the signal for ${\mathfrak{T}}_{i+1}$ at $x_{j}$
will be red. Consequently ${\mathfrak{T}}_{i+1}$ must slow down so that it can
stop at signal $x_{j}$ if necessary. Yellow signals from a minor time
violation can cause significant delays that propagate back through the system.
These delays can be largely avoided by specifying adequate buffer times at
each signal. To model unplanned discrepancies we must find a way to allow for
normal stochastic variation.

In Section 11.1 we begin by analysing the relationship between train position
and elapsed journey time. In Section 11.2 we propose a model that generates
stochastic differences between the actual elapsed time and the scheduled
elapsed time. In Section 11.3 we apply the stochastic model to a case study
looking at implementation of an optimal schedule.

###  11.1 Implementation of strategies with prescribed intermediate times

Consider an optimal strategy on a section of level track $[x_{j-1},x_{j}]$
using a phase of maximum acceleration with $u=H(v)$ from speed
$v(x_{j-1})=U_{j-1}=U_{s}(V_{j-1},V_{j})$ to speed $V_{j}$, followed by a
phase of speedhold at speed $V_{j}$ with $u=r(V_{j})$ and a phase of maximum
acceleration to speed $v(x_{j})=U_{j}=U_{s}(V_{j},V_{j+1})$ with $u=H(v)$. The
speed $v=v(x)$ can be found as a function of position by solving the
differential equation $vdv/dx=u(v)-r(v)$ subject to the given boundary
conditions and the appropriate control function. For the first phase of
maximum acceleration define

$x_{a}(v)=x_{j-1}+\int_{U_{j-1}}^{v}wdw/[H(w)-r(w)]$

for each $v\in[U_{j-1},V_{j})$ and let $a_{j}=\lim_{v\uparrow V_{j}}x_{a}(v)$
be the point where the speed reaches $v=V_{j}$ and the first phase ends. For
the second phase of maximum acceleration define

$x_{a}(v)=x_{j}-\int_{v}^{U_{j}}wdw/[H(w)-r(w)]$

for each $v\in(V_{j},U_{j}]$ and let $b_{j}=\lim_{v\downarrow V_{j}}x_{a}(v)$
be the point where the second phase begins. Now the speed function $v=v(x)$ is
given by

$v(x)=\left\\{\begin{array}[]{ll}x_{a}^{-1}(x)&\mbox{for}\
x\in[x_{j-1},\xi_{j,1})\cup(\xi_{j,2},x_{j}]\\\ V_{j}&\mbox{for}\
x\in[a_{j},b_{j}].\end{array}\right.$

The above calculations show that we can find the speed $v=v(x)$ from the
position $x$ with no knowledge of the elapsed journey time $t$. Nevertheless
$x$ and $t$ are related by

$t=t_{j}+\int_{x_{j-1}}^{x}d\xi/v(\xi)$ (42)

for all $x\in[x_{j-1},x_{j}]$. If $x$ is known we can determine $t=t(x)$
directly from (42). If $t$ is known we can find $x=x(t)$ by solving (42). The
ideas underlying the above discussion remain true for all sections of the
journey and all combinations of optimal controls.

###  11.2 An elementary stochastic model

The Energymiser® system [Albrecht, Howlett, and Pudney (2020), Section 1.2]
and other modern Driver Advisory Systems (DAS) assist drivers to follow an
optimal speed profile by displaying the current position
$x\in[x_{j-1},x_{j}]$, the recommended speed $v=v(x)$ and the recommended
applied acceleration $u=u(x)$. In practice, for various reasons,
implementation errors will occur and the actual speed profile will differ
slightly from the planned speed profile with
$v_{\theta}(x,\omega)=v(x)+\delta_{\theta}(x,\omega)$ where the error depends
on some scale parameter $\theta\in{\mathbb{R}}$ and the outcome
$\omega\in\Omega$ of a random process. The driver will always try to correct
these errors and there will typically be a succession of intervals $[c,d]$
with $v=v(c)$ at $x=c$ and $v=v(d)$ at $x=d$. However we may also have

$t_{\theta}(d,\omega)-t_{\theta}(c,\omega)=\int_{c}^{d}dx/v_{\theta}(x,\omega)\neq\int_{c}^{d}dx/v(x)=t(d)-t(c)$
(43)

Thus the train speed will be correct at $x=c$ and $x=d$ but the elapsed travel
time may be wrong. This means we could model the errors by assuming that the
driver implements the correct speed at the wrong time. Hence we propose a
model where the elapsed time function
$t_{\theta}(t,\omega)=t+\epsilon_{\theta}(t,\omega)$ is a random walk with
drift defined by the stochastic differential equation

$dt_{\theta}=dt+\theta dW(t)$ (44)

where $t\in[t_{j-1},t_{j}]$ is the true time, $[t_{j-1},t_{j}]$ is the
prescribed time interval and $W(t)=W(t,\omega)$ is a standard Wiener process.
We have followed convention in (44) and suppressed the dependence on
$\omega\in\Omega$. The constant $\theta>0$ is determined by the observed
standard deviation in journey times. This constant may depend on the train,
the train driver, the DAS or any other relevant factor. The equation (44) has
an analytic solution given by

$t_{\theta}(t)=t_{\theta,j-1}+t-t_{j-1}+\theta\int_{s=t_{0}}^{t}dW(s).$ (45)

for all $t\in[t_{j-1},t_{j}]$. In this model the equations of motion (1) and
(2) do not change and the solutions to these equations do not change. If we
want to match a particular outcome $t_{\theta}(t,\omega)$ to a position then
we simply solve

$t_{\theta}(t,\omega)=t_{\theta}(t_{j-1},\omega)+\int_{x_{j-1}}^{x_{\theta}}d\xi/v(\xi)$
(46)

to find $x_{\theta}=x_{\theta}(t,\omega)=x[t_{\theta}(t,\omega)]$. Now we can
calculate the corresponding speed
$v_{\theta}=v_{\theta}(t,\omega)=v[x_{\theta}(t,\omega)]$. Each realization of
the random process generates a different elapsed journey time
$t_{\theta}(t,\omega)-t_{\theta}(t_{j-1},\omega)$. In general $t_{\theta}\neq
t$ with $x_{\theta}\neq x$ and $v_{\theta}\neq v$. The essence of the
disparity is that the driver implements the planned speed $v(x)$ at the right
point $x$ but at the wrong time $t_{\theta}$. From (44) it is known that the
random variable $\rho=\theta\cdot
z=(t_{\theta}(t)-t_{\theta}(t_{j-1}))-(t-t_{j-1})$ is generated by a normal
probability density

$f(\rho)=(1/\theta\sqrt{2\pi t})\exp[-\rho^{2}/(\theta^{2}t)].$ (47)

with mean $0$ and standard deviation $\theta\cdot t^{1/2}$. The times
generated by (45) follow a Wiener distribution. The Wiener process
$W(t)=W(t,\omega)$ can be simulated by a random walk with small discrete time
steps defined by the random function

$S_{n}(t,\omega)=\left(1/\sqrt{n}\right)\sum_{1\leq k\leq\lfloor
nt\rfloor}\xi_{k}(\omega)$ (48)

where $\\{\xi_{k}\\}_{k\in{\mathbb{N}}}$ are independent identically
distributed normal random variables with mean $0$ and variance $1$ and
$n\in{\mathbb{N}}$ is large. Some basic facts about the Wiener process are
outlined in Appendix A.3.

###  11.3 Application of the stochastic model to an existing schedule

We will use the stochastic model to examine implementation of the Schedule in
Case Study 4.

###### Case Study 6

We assume that an on-board DAS provides continually updated driving advice to
train drivers to encourage energy-efficient driving strategies and assist in
on-time arrival. For this reason, in normal operation, we expect variations to
section traversal times to be relatively small. For the sake of argument we
assume that on the GLQ to EDB service the observed standard deviation for a
scheduled journey time $T=3120$ s is $s_{T}\approx 30$ s. If $t+\epsilon(t)$
denotes the actual time that train ${\mathfrak{T}}$ reaches position $x$ when
the scheduled arrival time is $t=t(x)$ and if the error $\epsilon(t)$ is a
Wiener process with scale parameter $\theta$ then the increments
$\epsilon(t+\Delta t)-\epsilon(t)$ are independently distributed normal random
variables with mean $\mu_{\epsilon}=0$ and standard deviation
$\sigma_{\epsilon}=\theta(\Delta t)^{1/2}$. We write $\epsilon(t+\Delta
t)-\epsilon(t)=\theta(\Delta t)^{1/2}\cdot
z\sim{\mathcal{N}}(0,\theta^{2}\Delta t)$. In our simulation
$\theta=s_{T}/T^{1/2}\approx 0.5371$.

We will use the timetable obtained in Case Study 4. The general form of the
timetable is displayed in Table 7 with departure times defined by the
parameter $\mbox{$\mbox{\boldmath$h$}$}=[h_{1},\ldots,h_{12}]$ with value

$\mbox{$\mbox{\boldmath$h$}$}=[505,841,1412,1664,2107,2970,2258,2580,3858,3213,3458,4703].$

The scheduled departure times are displayed in Table 9. When the timetables
are implemented in practice we assume that updated optimal strategies will be
calculated using an on-board computer [Albrecht et al. (2015d), Section 9, pp
534–535] in order to reach the next target on time. In general the updated
strategies will take the same form as the strategies calculated in Case
Studies 3 and 4 but the optimal driving speeds and control switching locations
may change. Let
$\mbox{$\mbox{\boldmath$z$}$}_{i}\sim{\mathcal{N}}(0,1)^{7}\in{\mathbb{R}}^{7}$
for each $i=1,\ldots,4$ and
$\mbox{$\mbox{\boldmath$z$}$}_{1,\star}\sim{\mathcal{N}}(0,1)^{7}$ be random
vectors with independently generated standard normal components. The scheduled
signal locations are defined by the vector
$\mbox{$\mbox{\boldmath$x$}$}_{s}=[x_{0},x_{2},x_{3},x_{4},x_{5},x_{6},x_{8},x_{9}]$.
The scheduled times for the trains are defined by

$\displaystyle\mbox{$\mbox{\boldmath$h$}$}_{1}$ $\displaystyle=$
$\displaystyle[0,h_{1},h_{2},h_{3},h_{4},h_{5},h_{6},T_{1}]$ (49)
$\displaystyle\mbox{$\mbox{\boldmath$h$}$}_{2}$ $\displaystyle=$
$\displaystyle[900,h_{3}+60,h_{4}+60,h_{7},h_{8},h_{6}+60,h_{9},900+T_{2}]$
(50) $\displaystyle\mbox{$\mbox{\boldmath$h$}$}_{3}$ $\displaystyle=$
$\displaystyle[1800,h_{7}+60,h_{8}+60,h_{10},h_{11},h_{9}+60,h_{12},1800+T_{3}]$
(51) $\displaystyle\mbox{$\mbox{\boldmath$h$}$}_{4}$ $\displaystyle=$
$\displaystyle[2700,h_{10}+60,h_{11}+60,h_{1}+3540,h_{2}+3540,h_{12}+60,h_{5}+3540,2700+T_{4}]$
(52) $\displaystyle\mbox{$\mbox{\boldmath$h$}$}_{1,\star}$ $\displaystyle=$
$\displaystyle[h_{1,\star,j}]=\mbox{$\mbox{\boldmath$t$}$}_{1}+3600\cdot\mbox{$\mbox{\boldmath$1$}$}$
(53)

where $\mbox{$\mbox{\boldmath$1$}$}=[1]\in{\mathbb{R}}^{1\times 7}$. We write
$\mbox{$\mbox{\boldmath$h$}$}_{i}=[h_{i,j}]_{j=1}^{8}$ and define

$\Delta^{1/2}\mbox{$\mbox{\boldmath$h$}$}_{i}=\left[0,(h_{i,2}-h_{i,1})^{1/2},(h_{i,3}-h_{i,2})^{1/2},\ldots,(h_{i,8}-h_{i,7})^{1/2}\right]$
(54)

for each $i=1,\ldots,4$. The actual departure times will be generated
according to the formulæ

$\mbox{$\mbox{\boldmath$h$}$}_{i,a}=[h_{i,a,j}]_{j=1}^{8}=\mbox{$\mbox{\boldmath$h$}$}_{i}+\theta\mbox{$\mbox{\boldmath$z$}$}_{i}\circ\Delta^{1/2}\mbox{$\mbox{\boldmath$h$}$}_{i}=\mbox{$\mbox{\boldmath$h$}$}_{i}+\mbox{$\mbox{\boldmath$\epsilon$}$}_{i}$
(55)

for each $i=1,\ldots,4$ and

$\mbox{$\mbox{\boldmath$h$}$}_{1,\star,a}=\mbox{$\mbox{\boldmath$h$}$}_{1,\star}+\theta\mbox{$\mbox{\boldmath$z$}$}_{1,\star}\circ\Delta^{1/2}\mbox{$\mbox{\boldmath$h$}$}_{1}=\mbox{$\mbox{\boldmath$h$}$}_{1,\star}+\mbox{$\mbox{\boldmath$\epsilon$}$}_{1,\star}.$
(56)

where $\mbox{$\mbox{\boldmath$h$}$}_{i}$ for each $i=1,\ldots,4$ and
$\mbox{$\mbox{\boldmath$h$}$}_{1,*}$ are the vectors of scheduled departure
times defined above and where we remind readers that
$\mbox{$\mbox{\boldmath$x$}$}\circ\mbox{$\mbox{\boldmath$y$}$}$ denotes the
Hadamard product of the vectors
$\mbox{$\mbox{\boldmath$x$}$},\mbox{$\mbox{\boldmath$y$}$}$.

We ran $10000$ simulated trials to calculate actual journey times subject to
the normal stochastic variations described above. There were $48$ trials where
the separation conditions were violated. The mean value of the minimum
separation over all $10000$ trials was $m_{\mbox{\scriptsize\rm msep}}\approx
32.2513$ s and the standard deviation was $s_{\mbox{\scriptsize\rm
msep}}\approx 10.3963$ s. The minimum observed value was
$min_{\mbox{\scriptsize\rm msep}}\approx-26.9082$ s. The histogram of observed
minimum separations (measured in seconds) is shown on the left in Figure 9.

Figure 9: Case Study 6. Histogram of simulated minimum separation times from 10000 trials (left) and probability density function for the minimum separation time (right). In $10000$ trials there were $48$ violations of the required separation conditions due to normal stochastic variation in journey times. Time is measured in seconds. The maximum observed violation was approximately $27$ s. The probability calculated for a violation using the probability density function is ${\mathbb{P}}[r<0]\approx 0.0051$. Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$ | ${\mathfrak{T}}_{1,\star}$
---|---|---|---|---|---
GLQ | $t_{1,0}=0000$ | $t_{2,0}=0900$ | $t_{3,0}=1800$ | $t_{4,0}=2700$ | $t_{1,\star,0}=3600$
BBG | — | — | — | — | —
LNZ |  ($t_{1,2}=0487)$ | $(t_{2,2}=1472)$ | $(t_{3,2}=2347)$ | $(t_{4,2}=3266)$ | $(t_{1,\star,2}=4106)$
CRO | $t_{1,3}=0844$ | $(t_{2,3}=1716)$ | $t_{3,3}=2636$ | $(t_{4,3}=3511)$ | $t_{1,\star,3}=4454$
FKK | $t_{1,4}=1408$ | $t_{2,4}=2260$ | $t_{3,4}=3205$ | $t_{4,4}=4034$ | $t_{1,\star,4}=5012$
PMT | $(t_{1,5}=1666)$ | $t_{2,5}=2587$ | $(t_{3,5}=3443)$ | $t_{4,5}=4390$ | $(t_{1,\star,5}=5265)$
LIN | $(t_{1,6}=2103)$ |  ${\dagger}$ $t_{2,6}=3025$ | $(t_{3,6}=3923)$ | $t_{4,6}=4753$ | $(t_{1,\star,6}=5688)$
WGJ | — | — | — | — | —
HYM |  ${\dagger}$ $t_{1,8}=3034$ | $t_{2,8}=3872$ | $t_{3,8}=4697$ | $t_{4,8}=5652$ | $t_{1,\star,8}=6548$
EDB | $t_{1,9}=3182$ | $t_{2,9}=4149$ | $t_{3,9}=4861$ | $t_{4,9}=5818$ | $t_{1,\star,9}=6772$
Table 10: Case Study 6. Trial $\\#107$ departure times. Trial $\\#107$ was the
first trial with a violation of the separation conditions. The daggers † mark
the violated separation condition $t_{1,8}\leq t_{2,6}$. Train
${\mathfrak{T}}_{2}$ would be required to delay departure from LIN until train
${\mathfrak{T}}_{1}$ has departed from HYM. This delay would not impact any
other scheduled times.

Trial $\\#107$ was the first trial where the separation conditions were
violated. The departure times for this trial are shown in Table 11. We also
include the results of Trial $\\#1$ which is typical of a trial with no
violations of the separation conditions. The minimum separation in Trial
$\\#1$ was $r\approx 34$ s.

Station | ${\mathfrak{T}}_{1}$ | ${\mathfrak{T}}_{2}$ | ${\mathfrak{T}}_{3}$ | ${\mathfrak{T}}_{4}$ | ${\mathfrak{T}}_{1,\star}$
---|---|---|---|---|---