\documentstyle{report}
\begin{document}
\title{The Train Slowing Problem}
\author{David S. Lawyer}
\maketitle

\section*{Introduction}

Suppose a vehicle such as a train must make a trip where it has a
scheduled arrival time and also has enough excess power so that it has
a continuous choice of speeds at which it may travel.  To simplify the
situation, assume that the route is level with a high speed limit.  What
is the optimal speed at which the train should travel?  The answer to
this question depends on the costs.  Most costs may be put into two
categories: 1. time costs.  2. energy costs.  As the train goes faster
time costs decrease (the train is likely to arrive sooner) but energy
costs increase since the resistance force (drag) opposing the  forward
motion of a train increases with velocity. (This force is approximately
a quadratic in velocity.)  Time costs may either be assumed to be a
fixed cost per hour or may depend on whether the train arrives early or
late.  If the train is scheduled the time cost of being say ten minutes
late is normally greater than the benefit of being ten minutes early so
that two different time costs are needed: \\1. the time cost (in
dollars per hour) of being late and \\2. the time cost (in \$/hr) of
being early.

The model of fixed time costs (not dealt with in this report) has
relevance in some cases:  In actual rail operation trains are
frequently not scheduled and are run on an "as needed" basis.  Another
situation is where one is planning the speeds which trains should run
at (prior to the establishing of a schedule).  In both of these cases
there is no schedule to consider and there is no such thing as a train
arriving "late" or "early".  This report will deal only with the
opposite case where trains are scheduled and where the time penalty for
arriving late is greater than the time benefit for arriving early
(measured in \$/hr).

If there is no possibility of a breakdown or other unexpected delays,
the answer to the optimal velocity question for this simplified problem
is to simply travel at a constant velocity so that the train will
arrive at its destination exactly on time.  Constant velocity is optimal 
because it will minimize the energy consumption for a fixed travel time 
since train resistance increases at least linearly with velocity.

If there is some chance of a breakdown, then it might be wise for the
train to purposely get "ahead of schedule" so as to provide for a time
reserve so that in the case of a breakdown it will not arrive too late
(or perhaps still arrive on time in spite of a breakdown).  The optimal
speed policy will be to travel fast at first so as to get "ahead of
schedule" and then to slow down as the train gets closer to its 
destination.  This is called the train slowing problem and is the
subject of this report.

The model presented here will be for a train but the principle of
getting ahead of schedule may be applicable to other types of vehicles
as well.  However, the model developed here is applicable only to
trains.  Highway motor vehicles (cars, trucks, and busses) are often
restricted in speed by speed limits and have rather high time costs due
to both driver "wages" and the relatively high value freight normally
hauled by trucks.  The optimal policy is usually to travel at (or even
above ---if we allow this in the model) the speed limit (as most
highway motor vehicles actually do).  A major policy question for
trucks (if they have a scheduled arrival time at their destination) is
how early they should depart on their trip so as to insure a reasonable
high probability of arriving on time (or earlier).

For a scheduled bus which is subject to traffic delays the problem is
still different.  The optimal policy in this case is likely to be that
of normally travelling under the speed limit so that should the bus
fall behind schedule it may travel faster than normal in order to catch
up to its scheduled trajectory.

An aircraft has a low probability of breaking down in flight and if it
does fail in flight it usually cannot be repaired without landing, in
which case the passengers would probably catch another another flight.
However, it may be optimal for a plane to fly faster on the first part
of its journey (if it has the reserve power) to provide a time reserve
in case it is later delayed by adverse winds or storms.

A long freight train on a long trip has a high probability of breakdown
since it may consist of about 100 cars, each of which has a small
probability of breaking down.  Common failures are due to defective
wheel bearings which overheat, serious brake defects (such as dragging
brakes or defective brake hoses), and loose components under the car
which may even drag along the track.

One may calculate the optimal speed based on the tradeoff of energy for
time.  The value of time should often be low enough so that it is
optimal to travel below the speed limit in order to conserve energy.
The labor cost of operating a train should be low (a one-man crew for
example but labor union rules often prohibit this).  The time value of
what it is carrying is also often low (for example a freight train
carrying ores, coal, scrap, etc.).  Thus the optimal speed is often
well under the speed limit.  Due to the control of access to the
railroad track and the possibilities of improving safety at high speeds
by advanced signalling systems and computer control of motion, the
"speed limits" are often high (or could be made high).  Thus railroad
freight transportation is the one mode of scheduled land transportation
where there is often a real choice of speeds (or could be if the the
physical plant and operating polices were modernized).  Thus the
vehicle slowing problem is perhaps more applicable to trains than it is
to any other mode of transportation.

\section*{Problem definition}

Here is a simplified model (and solution) for the train slowing problem:
\\Let us consider a railroad line of length $L$ and a train which departs at
the start of the line to travel to its destination distance $L$ away.
Let the scheduled time allocated for this trip be $T$.  Assume that the train has a
Poisson failure rate (breakdown rate) of $\lambda$ in units of
breakdowns per kilometer (on average).   The train may instantly change
speed but upon solving the problem one will find that such instant
speed changes infrequently occur.  Thus the solution found will not be
too far from the optimal one which would occur if such speed jumps were
not allowed.  Once the train breaks down, it takes a fixed time $t_{r}$
to repair it and it then travels at its maximum velocity $v_{max}$ for
the rest of the trip.  It is assumed to always arrive late after such a
breakdown.

The costs are as follows:  An energy cost $f$ such that the cost per
unit distance travelled is $fv$.  The implication of this is that the
drag force against the train is directly proportional to v.  The
constant drag term may be neglected since it is the same for all
speeds (and velocity policies).  The term in $v^{2}$ has been neglected
to simplify the problem but could be included in a more realistic
model.  A late Penalty per unit time of $p$ and an early Reward per
unit time of $r$.  The energy costs for the trip are thus $\int_{0}^{L}
fv(x)  \, dx$ .  If the train is $t$ hours late, it must pay a penalty
of $pt$ dollars.  If it arrives $t$ hours early, it receives an early
reward of $rt$ dollars.

The problem is to find the optimal velocity to travel at prior to
breakdown so as to minimize the total cost.  The resulting solution: 
$v(z)$ decreases with increasing distance $z$ from the start of the
trip (as will be shown).

\section*{Table of Variables and Parameters}

\subsection*{Variables}
\begin{description}
\item[$x$] Distance to go to destination in km.  The time-like variable in the
	optimization model.
\item[$z$] The location of the train from the origin = $L-x$.   
\item[$t$] Time to go before scheduled arrival time.  The time remaining
	to complete the trip (negative if train is late).  The state
	variable.
\item[$v$] Velocity in km/hr.  The control variable.

\end{description}

\subsection*{Parameters}

\begin{description}
\item[$L$] Length of the railroad line (= trip Length) in km.
\item[$T$] scheduled Time for trip in hrs.
\item[$f$] $fv$ is the energy cost due to vehicle drag Force in dollars 
	per km where $v$ is velocity in km/hr.
\item[$p$] Penalty in dollars per hour for arriving late.
\item[$r$] Reward in dollars per hour for arriving early.
\item[$t_{r}$] Time required to Repair the train after breakdown.
\item[$v_{max}$] Maximum velocity of the train in km/hr.
\item[$\lambda$] Poisson failure rate of train in breakdowns/km.
\end{description}
\section*{Mathematical formulation}

If a train fails (breaks down) it will take time $t_{r}$ to repair it
and then it will take time $x/v_{max}$ for it to reach its
destination.  The sum of these should be greater than the time to go
$t$ since it is assumed to arrive late due to the breakdown.  Thus it
will arrive with lateness $x/v_{max} + t_{r} - t$ hours, but it may
breakdown again and each such breakdown will delay the train $t_{r}$
more hours.  Since the expected number of such breakdowns is $\lambda
x$ the expected future repair time (additional delays) is $\lambda x
t_{r}$.  This gives an expected lateness after a breakdown of
$x/v_{max} + t_{r} + \lambda x t_{r} - t$ resulting in an expected cost
of 
\[p(x/v_{max} + t_{r} + \lambda x t_{r} - t)  + fv_{max}x\] 
where the last term is the energy cost for the rest of the journey.

We may now write the formula for the total expected cost of a single 
trip by conditioning on the first failure.  The density of the first 
failure is exponential with density $\lambda e^{-\lambda (L-x)}$.  
Thus the total expected cost is: 
\[\int_{0}^{L} \lambda e^{-\lambda (L-x)}
[(p/v_{max} + \lambda t_{r} + fv_{max})x +pt_{r} -pt(x)] \,dx \]
\[ +\: \int_{0}^{L} e^{-\lambda(L-x)}fv(x) \,dx
\:-\: r t(0)e^{-\lambda L} \]

The bottom integral represents the expected energy cost for the
optimal trajectory $v(\cdot)$ before the first breakdown occurs.  Note
that the probability of no breakdown having occurred from the start of
the trip to location $x$ is $e^{-\lambda (L-x)}$ The last term (without
the negative sign) is the expected reward for early arrival assuming
that $t(0) \geq 0$.  Otherwise (if $t(0)<0$) the train will always
arrive late and there is always a penalty at the end of the trip so
that $r$ becomes $p$.  Integrating the above is straightforward and the
result may be partitioned into two parts, one a constant (depending
only on the parameters) and the other depending on $v(\cdot)$ and
$t(\cdot)$, the control variable and the state variable.  Only this
later part need be minimized.  Thus we must find a control $v(x)$
(which in turn determines the state variable $t(x)$) so as to:  \[
\stackrel{\rm\textstyle Minimize}{v(x)\:\Rightarrow t(x)} \int_{0}^{L}
e^{-\lambda(L-x)}[fv(x)-\lambda pt(x)]\,dx - rt(0)e^{-\lambda L} \]
provided $t(0)\geq 0$.  If $t(0)<0$ then $p$ must be substituted for
$r$.  The differential equation of motion is \[
\frac{dt}{dx}=\frac{1}{v} \mbox{  by definition of velocity} \] \[
t(L)=T \mbox{  initial [final ?] state at "time" L (boundary
condition)} \]

The meaning of [final ?] will be clarified in the next paragraph.
Note that as the train proceeds, both $dt$ and $dx$ are negative
which results in $v=+dx/dt$.  The state is $t$, the time to go.  The
"time" (the variable which is the same as the $t$ (time) variable in
books on control theory) is $x$, the distance to go.  Both "time" $x$
and the state variable $t$ run backwards.  There are many other ways
which this problem could be posed but the one used here appears to be
one of the simplest.

However, there is an equivalent interpretation of this problem which we
will use.  Why not let both $t$ and $x$ move forward and start the
problem at the end of the line (with the train running backwards)?
Then the problem starts at initial "time" $x=0$ and with a free initial
"state" $t(0)=?$.  The process stops when "time" $x=L$ where the final
state must be $t(L)=T$.  Henceforth we will use this interpretation.

\section*{Problem solution}

The problem as stated is a simple problem in optimal control.
\footnote {See for example "Applied Optimal Control" by Bryson and
Ho.}  The Hamiltonian is:
\begin{equation}
H=\frac{\psi}{v} + e^{-\lambda (L-x)} (fv-\lambda pt) \label{hamil}
\end{equation}
where $\psi (x)$ is the Lagrange multiplier function (sometimes called
the costate varaible).  Minimizing $H$ 
with respect to the control variable $v$ gives (by setting $H_{v}=0$ 
where $H_{v} \doteq \partial H/ \partial v$ ) and then solving for $v$) 
gives: 
\begin{equation}
v_{opt}^{2}=\frac{\psi}{f}e^{\lambda(L-x)} 		\label{vopt2}
\end{equation}
The adjoint differential equation is: 
\begin{equation}
\dot{\psi}=-H_{t}=\lambda pe^{-\lambda(L-x)}\mbox{ with solution }
\psi=pe^{-\lambda(L-x)} -c 			\label{psi}
\end{equation} 
where $c$ is the constant of integration and must be selected so that
the boundary condition: $t(L)=T$ is satisfied.  One merely substitutes
this value of $\psi$ into equation \ref{vopt2} for the optimal velocity 
$v_{opt}$ obtaining: 
\begin{equation}
v_{opt}=\sqrt{\frac{p-ce^{\lambda z}}{f}}  		\label{vopt}
\end{equation}
where $z=L-x$ is the distance from the start of the trip.

The optimal solution determines the scheduled time of arrival (assuming
no breakdowns).  There are three cases for this solution: \\1. The
train is scheduled to arrive exactly on time: $t(0)=0$ \\2.  It is
scheduled to arrive early:  $t(0)>0$ \\3.  It is scheduled to arrive late:
$t(0)<0$.  \\ The case where it is scheduled to arrive late does not make
much sense since the policy of having a train travel at maximal
velocity $v_{max}$ after a breakdown implies that the train should
travel at maximum speed if it is known that it will be late.  Let us
examine these three cases.

\subsection{Case "early": Train scheduled to arrive early. $t(0)>0$ }

In this case there is an early reward of $rt(0)$ and the expected cost
of this is $\phi =-rt(0)e^{-\lambda L}$ . By optimal control theory 
\[ \psi (0)=-\phi_{t}=re^{-\lambda L}  \]
(with a minus sign in front of $\phi_{t}$ since the reward is paid at the 
start of the process)  assuming "time" $x$ runs forward from zero.
Substitution of $\psi (0)$ into equation \ref{psi} results in 
\[ c=(p-r)e^{-\lambda L} \]
Substituting this into equation \ref{vopt} results in
\begin{equation} 
v_{opt}=\sqrt{\frac{p(1-e^{-\lambda x}) + re^{-\lambda x})}{f}} \label{v1}
\end{equation}
Note that the simplest model for optimal velocity with no possibility of
breakdown and the value of time equal to say $d$ results in a cost per
unit distance (the objective function to minimize) of:
\[ fv + d/v \mbox{ which after minimizing gives: }
v_{opt}=\sqrt{\frac{d}{f}} \]
Now equation \ref{v1} is basically the same as this except that $d$ is a
convex combination of the late penalty $p$ and the early reward $r$.
When $x=0$ at the end of the trip the velocity is as if the simple-case
time cost was only the early reward.  Note that $v_{opt}$ decreases as
the trip progresses (as $x$ gets smaller).

The next step is to solve for the time required for such a trip.  To do
this we merely integrate \footnote{See formula on p. 106 of Gradstein 
(Moskva l963).} $1/v_{opt}$ from $0$ to $L$.  The result is:
\begin{equation}
T_{early}=\frac{1}{\lambda}\sqrt{\frac{f}{p}}ln(
\frac{\sqrt{p} - \sqrt{r}} {\sqrt{p} + \sqrt{r}} \: \times \:
\frac{\sqrt{p} + \sqrt{p-e^{-\lambda L}(p-r)}} 
	{\sqrt{p} - \sqrt{p-e^{-\lambda L}(p-r)}} )
\end{equation}

This equation may be used to determine if the solution belongs to case
"early".  We merely calculate $T_{early}$ and then compare it to the time 
$T$ allocated for the trip.  If $T_{early}<T$ then we are in case "early".
Otherwise we are probably in the case "on-time".

\subsection{Case "late": Train scheduled to arrive late. $t(0)<0$ }

Although this is an unlikely case.  The formulation for it is similar
to the early case above.
Instead of an early reward of $rt(0)$ there is a late penalty of
$-pt(0)$ with a negative sign since t(0) is negative.  One sees that
this is the same as the previous case except that p should be
substituted for r.  The equation \ref{v1} becomes simply:
\begin{equation} 
v_{opt}=\sqrt{\frac{p}{f}}
\end{equation}
This is the steady state optimal velocity if time costs are $p$ and will
likely be higher than $v_{max}$ so that the optimal solution for this
case will usually be to travel at optimal velocity $v_{max}$.  If
the train will always arrive late even if $v_{max}$ (or the high value of
$v_{opt}$ as calculated above) is used, then we are in a case which
implies that there is something wrong with the parameters of the
problems as one would not normally plan to always arrive late (and in
case of breakdown(s) to arrive even later).
 
\subsection{Case "on-time": Train scheduled to arrive on time. $t(0)=0$ }

This is perhaps the most likely case.  If the situation does not fall
into the other two cases, then it must be in this case.  To solve it
one must find a constant $c$ for equation \ref{vopt} which will 
result in a velocity so that the train arrives exactly on time.  In a
manner similar to case "early" we must find the time $t(x)$ by integrating
$1/v_{opt}$ from $0$ to $x$ using the $v_{opt}$ from equation \ref{vopt}.
The result is
\begin{equation}
t(x)=\frac{1}{\lambda}\sqrt{\frac{f}{p}}ln(
\frac	{\sqrt{p} - \sqrt{p - ce^{\lambda x}} }
	{\sqrt{p} + \sqrt{p - ce^{\lambda x}} } \: \times \:
\frac	{\sqrt{p} + \sqrt{p-c}} 
	{\sqrt{p} - \sqrt{p-c}} )
\end{equation}
The trip time is just $t(L)$ (i.e. set $x=L$ in the above equation).  Then 
one must solve this for $c$ which gives:
\begin{equation} 
c = \frac{4p} {(y^{2} - 1)^{2}} [y(x-y)(1-xy)]  
\end{equation}
\[\mbox{ where }
x=e^{-\frac{\lambda L}{2} } \mbox{ and }
y=e^{\frac{ \lambda T}{2}  \sqrt{ \frac{p}{f} } } \]

We are not quite done because the initial velocity $v_{opt}$ found from
equation \ref{vopt} could exceed the maximum value allowed $v_{max}$.
For this situation we must reexamine the minimization of the
Hamiltonian keeping in mind that there is now an active constraint placed
on velocity $v$ (it cannot exceed $v_{max}$).  It is obvious that to
minimize the Hamiltonian in this case requires setting $v$ equal to
$v_{max}$.  The solution for this situation will be to travel at the maximum
velocity $v_{max}$ for the first portion of the trip and then switch to
an optimal velocity trajectory.
\end{document}
