\chapter{Analysis of Sample Transportation Scenarios}

The simulation framework we have gives us the flexibility to model
several combinations of loads, vehicle fleet sizes, and network topologies
connecting the nodes together.

\section{Scenario Descriptions}
\section{Verification of Simulation Engine}

Several arbitrary transit networks such as the one shown in figure
\#\ref{fig:Arbitrary-transit-graph} provided a variety of test cases for
different combinations of connections between stations and waypoints for
use in system verification and validation.  The graph demonstrates the
functionality of both bidirectional station-station links, and different
combinations of unidirectional station links connected via 1 or more
waypoints. Additionally it provides multiple equal-cost routes linking
several stations to encourage utilization of alternate pathways during
congestion. Several simulation runs with different demands and initial
conditions provided test feedback during development.

\begin{figure}[htp]
\epsfxsize=5.0truein
\centerline{\epsfbox{figures/tg0_begin1_1.eps}}
\caption{Arbitrary transit graph used for Verification and Validation.
Yellow nodes indicate stations, red nodes indicate waypoints.}
\label{fig:Arbitrary-transit-graph}
\end{figure}

\subsection{Simulation Requirements Verification}

Throughout the test cases, we checked the following criteria to look for inconsistencies:

\begin{enumerate}
\item Passengers get sent to their destinations.  Passengers that cannot
      receive service due to capacity or other constraints will remain
      at their point of origin (and not stranded in the middle of the
      transit network)

\item Connectivity constraints not violated.  Vehicles and passengers
      should only move between nodes that are connected on the
      connectivity matrix.

\item Vehicle capacity constraints not violated.  Passengers should not
      be able to move independently between nodes without enough
      vehicles to carry them.
\end{enumerate}


\subsection{Simulation Specification Verification}

\section{Validation of Analysis Data}

Behaviors and problems searched for during validation testing included:

\begin{itemize}
\item Following the paths of individual passengers and vehicles to ensure
they make sense. 

\begin{itemize}
\item Vehicles shouldn't move on their own when they're empty, unless they
do so to make way for vehicles carrying passengers.
\item Passengers should travel on a reasonably direct path towards their
final destination.
\end{itemize}
\item Check for optimality. Attempt to find improvements to the schedule.
It should be hard, even impossible if the solver had found an optimal
solution.

\begin{itemize}
\item Scenarios with multiple vehicle sizes should show a {}``preference''
for larger, more economical vehicles, supplemented by a few small
vehicles running around feeding the larger ones to fill capacity.
\end{itemize}
\end{itemize}

\section{Sample Scenarios}

The program generates histograms plotting the transit system response
to an input demand \char`\"{}pulse\char`\"{}. The demand pulse is
currently a uniform random distribution across all source and destination
nodes. 

A script produces parametric analysis sets of results for two types
of systems: a light-rail system and a PRT type grid.

Blank rows in the chart summaries indicate where the optimal fleet
scheduler was unable to find a feasible solution in under 30 minutes of
real computing time. 

\subsection{1D Rail Transit Network}

The light rail system has two types of operation, strict linear rail
(trains stop at every station) and an express rail (where stations
are off the main line and trains can save time by bypassing stops).
The system is constrained such that a maximum of 4 passenger trains with
a maximum capacity of 200 each can stop at each station at a time.

\begin{figure}[p]
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_linearrail.eps}}
\caption{1D Rail}
\label{fig:1D-Rail}
\vspace{0.3 truein}
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_expressrail.eps}}
\label{fig:1D-Express}
\caption{1D Rail with express bypass routes}
\end{figure}

\subsection{2D PRT Transit Network}
\label{sub:2D-PRT-Transit-Network}
Next we'd try to extend our 1D line into a 2D grid network.

We could model a simple PRT-type system by applying several
simplifications to allow our prototype fleet scheduler to scale up to a
25-node 2D triangular grid. We simplified the model by restricting it to
single passenger (or small party) vehicles, which eliminates transfers.
The simulation will still unload and reload passengers as they traverse
station nodes, but we can safely assume the passengers simply stay in
the same vehicle they arrived on. Otherwise, the structure and behavior
of this model follows the exact same rules used by any other scenario
based on this mass transit framework.

\begin{figure}
\includegraphics[width=0.8\columnwidth]{figures/tg0_PRT.eps}
\begin{itemize}
\item width ymax = 4 station nodes
\item length xmax = 5 station nodes
\end{itemize}
\caption{\label{fig:PRT-Triangular-mesh}20-node PRT Triangular mesh network}
\end{figure}


\subsection{2D Hexagonal Network}
\label{sub:2D-Hex-Network} 

In order to scale up our schedule optimization to tackle larger, more
realistic scenarios, we'll concentrate our efforts on a simple
triangular grid organized into hexagons.  This will allow us to break
down our problem hierarchically and solve it in parallel in the future,
as described in section \ref{sub:Hierarchical-Optimization}.

As in the 1D rail scenario, we will again distinguish between a linear
network, where each vehicle must stop for transfer at every station node
it passes along its way, and a network with express routes, where
vehicles could bypass stations for incremental time savings.

\begin{figure}[p]
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_linearhex.eps}}
\caption{2D hexagonal cluster}
\label{fig:2D-hexagonal-cluster}
\vspace{0.3 truein}
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_expresshex.eps}}
\label{fig:2D-hexagonal-express}
\caption{DD hexagonal cluster with express bypass routes}
\end{figure}


\subsection{Performance Metrics Gathered}


\subsection{Data and Histograms}

There are three red histograms that pertain to the transit system
performance from the point of view of the passengers (number of transfers
taken, their departure time relative to when they requested, and their
total transit time). The blue histograms relate to vehicle fleet activity
(number of vehicles in motion at a particular timestep, and the passenger
load percentage). Each row represents a different network configuration
and demand level. These independent variables are summarized in the
leftmost column. The second column summarizes how many active vehicles
are needed to meet the demand and the total network segments they
must traverse. 


\subsection{Assumptions and Limitations}
\label{sub:Assumptions-and-Limitations}
The simulation currently does not specify all of the initlal conditions
to the schedule optimizer.  Therefore, the beginning locations of
vehicles are currently left free.  This gives the schedule optimizer an
unfair advantage, as vehicles can initially be created anywhere in the
network.

To take away some of this advantage, in our scenarios we currently set
the final vehicle state to equal the initial vehicle state.  This means
that each schedule that meets a certain demand pattern is at least
repeatable for another run of the exact same demand pattern at the end
of its active time interval.  It also forces the vehicles to spend some
energy returning to their initial state.  Since the scheduler only sees
vehicles in terms of their capacity, this does not force all vehicles to
make full round-trips.  They might operate in rotation with other
vehicles of the same type.

Also, due to the high computing time required to exhaustively
branch-and-cut the entire schedule optimization search tree, we impose a
time limit on the wall clock time that the computer is allowed to spend
finding a solution.  When this time limit is reached, the MIP solver
will simply return the current best sub-optimal solution it has found.
This sub-optimal solution will typically fall close to the final optimal
solution, so we could argue that the diminishing improvements to the
schedule would not be worth the additional number crunching time,
especially when vehicles might be idling waiting for further
instructions.  While this tradeoff may be acceptable for practical
purposes, this optimizer timeout defeats the repeatability of our
simulation for academic purposes.  The CPU would stop computation at a
nondeterministic point in the MIP optimization and could return
different schedules depending on the speed of the CPU or even on how
much time was allocated to other processes in the background.  This is a
limitation of the LP\_Solve software's wall clock based timeout feature
and could be fixed in the future by adding a deterministic timeout
function that returns a sub-optimal result after a fixed number of
operations.  


\section{Post Processing and Analysis}
\label{sec:Post-Processing-and-Analysis}

FIXME: insert pareto optimal curves


\subsection{Design of Experiments for Parametric Analysis}
\label{sub:Design-of-Experiments-for-Parametric-Analysis}

The independent variables and their values are summarized in the far
left column include:
\begin{itemize}
\item Topology type [1D rail, 1D rail w/ express service, 2D hexagon, 2D hexagon w/ express service]
\item Load  [4, 64, 128, 256] passengers per station
\item Vehicle berths per station [2,4,8] vehicles max can visit and transfer passengers in a station simultaneously
\item Vehicle capacity [16, 64, 128] passengers max can ride in vehicles
\end{itemize}

The graphs show the response metrics of interest (with respect to
timestep, and average) :

\begin{itemize}
\item Passenger transit time
\item Passenger departure delay from time available to depart
\item Passenger number of stops / transfers experienced
\item Vehicle segments travelled and total vehicles used (to give an estimate of operating costs)
\item Vehicle utilization \% (to give some indication of how 'full' the
vehicles are running)
\end{itemize}

FIXME: insert content