\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{Verification of Simulation Engine}
\label{sec: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}

\section{Simulation Requirements Verification}
\label{sec: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}


\section{Validation of Analysis Data}
\label{sec: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}
\label{sec:Sample-Scenarios}

The program generates histograms plotting the transit system response to
an input demand ``pulse''. The demand pulse is currently a one-time
uniform random distribution across all source and destination nodes.
This distribution is created by creating one employer cell in each
neighborhood that employs a fixed number of commuters.  The employees
originate from any node in the network with a uniform random
probability.  This arrangement for defining transit demand was chosen to
mirror the fact that municipalities often have more control of where and
how many jobs are created than where people choose to set up residences.

A script produces parametric analysis sets of results for three types of
systems: 

\begin{enumerate}
 \item a simple 1D linear light-rail system
 \item a 2D triangular grid limited to PRT-type vehicles without
       transfers
 \item a 2D hexagonal cluster unit on a triangular grid.
\end{enumerate}

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

\subsection{1D Rail Transit Network}

The light rail system has two types of operation: a strictly linear rail
network where trains must stop at every station, and an express rail
network where stations are off the main line and trains can save time by
bypassing stops.

\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 analyze a
basic cluster unit that we could later use to decompose larger problems
hierarchically and solve them 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 (depicted by figure \ref{fig:2D-hexagonal-cluster}) where every
vehicle must stop for transfers at every station node it passes along
its way, and a network with express routes (depicted by figure
\ref{fig:2D-hexagonal-express}) in which vehicles could bypass stations
to save time and berthing constraints.

\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{3D hexagonal cluster with express bypass routes}
\end{figure}


\subsection{Assumptions and Limitations}
\label{sub:Assumptions-and-Limitations}

The simulation currently does not specify all of the initial 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{Scenario Performance Data and Histograms}
\label{sec:Scenario-Performance-Data-and-Histograms}

SimPy monitors trace and collect perforamnce metrics experienced by
individual entities in the simulation.

Performance metrics perceived by passengers of the system often balance
against vehicle fleet performance.  Improvements to passenger
performance often come at the expense of increased vehicle operator
costs.


\subsection{Passenger Performance Metrics}
\label{sub:Passenger-Performance-Metrics}

The red histograms pertain to the transit system performance from the
point of view of the passengers.

% example data from data/256j/1Dlinrail_1v/v0_04b_128s_0f/303952

	    




\begin{description}
 \item{\bf Transit Time:}
	    \begin{figure}[htp]
	     \epsfxsize=4.5truein
	     \centerline{\epsfbox{figures/hist_transitTime.ps}}
	     \caption{Passenger Transit Time}
	     \label{fig:Passenger-Transit-Time}
	    \end{figure}
	    
 \item{\bf Departure Latency:}
	    \begin{figure}[htp]
	     \epsfxsize=4.5truein
	     \centerline{\epsfbox{figures/hist_deptTime.ps}}
	     \caption{Passenger Departure Time}
	     \label{fig:Passenger-Departure-Time}
	    \end{figure}

 \item{\bf Number of Stops / Transfers:}
	    \begin{figure}[htp]
	     \epsfxsize=4.5truein
	     \centerline{\epsfbox{figures/hist_transfers.ps}}
	     \caption{Passenger Stops / Transfers}
	     \label{fig:Passenger-Stops-Transfers}
	    \end{figure}



\end{description}


\subsection{Vehicle Fleet Performance Metrics}
\label{sub:Vehicle-Fleet-Performance-Metrics}

The blue histograms relate to vehicle fleet activity. 

\begin{description}
 \item{\bf Segments Traveled:}

	    \begin{figure}[htp]
	     \epsfxsize=4.5truein
	     \centerline{\epsfbox{figures/hist_vehInTransit.ps}}
	     \caption{Vehicles In Transit}
	     \label{fig:Vehicles-In-Transit}
	    \end{figure}


 \item{\bf Utilization per Time Step:}

	    \begin{figure}[htp]
	     \epsfxsize=4.5truein
	     \centerline{\epsfbox{figures/hist_vehSegUtilization.ps}}
	     \caption{Vehicle Fleet Utilization}
	     \label{fig:Vehicle-Fleet-Utilization}
	    \end{figure}


\end{description}



\section{Parametric Analysis}
\label{sec:Parametric-Analysis}

Each row of output data represents a different network configuration and
demand level.


\subsection{Design of Experiments}
\label{sub:Design-of-Experiments}

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

The graphs show the response of the metrics of interest with respect to
timesteps and averages :

\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}


\subsection{Data Reduction}
\label{sub:Data-Reduction}

FIXME: insert Pareto optimal curves

% LocalWords:  truein PRT ymax xmax timestep MIP LP FIXME
