\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]
\noindent
\epsfysize=7.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}

Periodic dumps of the system state in graphML format allow us to
visually inspect the object tree using the yEd graph layout tool.  These
snapshots show us the location of individual vehicles and passengers,
along with records of their transit history.  The entities are
represented as nested UML objects, and are color coded by station.  A
portion of one of these zoomable diagrams is shown in figure
\ref{fig:yEd-sample}.

\begin{figure}[htp]
\noindent
\epsfxsize=6.0truein
\centerline{\epsfbox{figures/state2transferEv.eps}}
\caption{System snapshot in yEd graphML viewer}
\label{fig:yEd-sample}
\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 sequentially-routed
``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
sequentially-routed 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 space
in the intermediate stations.

\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.  The total number of vehicles in the fleet is left unbounded.
A more realistic study would consider setting the maximum number of
vehicles in the fleet as a design parameter to explore.

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.

As noted in the scenario description in begging of section
\ref{sec:Sample-Scenarios}, each scenario has a uniform distribution of
employers and residents spread out among its nodes, making the problem
highly (and uncannily) symmetric.  Future studies could easily vary the
distribution of demand to model a network with business and residential
centers.

Each segment between waypoints and stations represents 2 simulation time
units.  Typically, the last segment entering a station represents the
time penalty for stopping at that station.  As seen in the network
models, bypassing a station results in a 1 time segment gain.  This
means that we're assuming that the amount of time a vehicle spends
slowing down, stopping, waiting for passenger transfers, and getting
back up to speed again is roughly the same amount of time taken to
travel between stations at speed.  This ratio might be adjusted by
adding additional segments to increase the visit penalty at stations, or
to increase the travel time between stations, but for these scenarios we
will assume a ratio of $1:1$.

We impose a maximum number of time units allowed by a schedule.  More
possible time units translates to a higher possible capacity over that
time.  On the 1D linear rail networks, we limit schedules to 18
time steps, which works out to 1.5 times the diameter of the sequential
network ($6*2$ segments between the 7 stations).  On the 2D hexagonal
networks, we chose a limit of 12 time units, which works out to 3 times
the diameter of the sequential network ($2*2$ segments between an outer
station to any other outer station).4

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
solver iterations.


\section{Scenario Performance Data and Histograms}
\label{sec:Scenario-Performance-Data-and-Histograms}

SimPy monitors trace and collect performance metrics experienced by
individual entities in the simulation.  By plotting several of these
metrics as histograms, we can gain some deeper insight into what the
system is doing over time.

We present an set of example histograms in figures
\ref{fig:Passenger-Transit-Time} through
\ref{fig:Vehicle-Fleet-Utilization}.  This data was taken from one of
the 1D rail networks with linear sequential routing serving a moderate
load of passengers.


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

System performance metrics perceived by passengers of the system often
act in opposition to vehicle fleet operational costs.  Improvements to
passenger service often come at a greater expense in terms of the
numbers of vehicles operating and the distance they must traverse during
the course of the schedule.  Since our optimization goal favors the
fulfillment of passenger goals first, however, we should see some fairly
straightforward data.

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:} In figure \ref{fig:Passenger-Transit-Time}, we
	    see the total number of passengers served by the system, and
	    time they were delivered to their final station.  Thus, we
	    can view this graph as the system response to the demand
	    impulse at time $t=0$.  Each time step takes 2 units of
	    time.  Therefore the width of each histogram bin is 2 time
	    units long, and we don't see our first arrivals until $t=4$,
	    since passengers must travel through 2 segments via a
	    waypoint before arriving.  Large groups of passengers
	    continue to get dropped off at their destinations roughly
	    every other time unit, since all stations are separated by
	    one waypoint. The quantity of passengers delivered
	    diminishes with time, as fewer combinations of station pairs
	    are farther apart.  We do notice that some deliveries are
	    also made on the ``odd'' time steps in between the ``even''
	    peaks, where the scheduler has shuffled some of the overflow
	    passengers to take advantage of unused station capacity.
	   
	    \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:} Figure
	    \ref{fig:Passenger-Departure-Time} shows us the time most
	    passengers spend waiting at their station of departure.
	    Most passengers can board vehicles right away, whereas a
	    small number of passengers must wait for the next time
	    step.  This helps shed light on the ``even'' peaks and
	    ``odd'' valleys we saw in the passenger transit time
	    histogram of figure \ref{fig:Passenger-Transit-Time}.

	    \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:} Finally, figure
	    \ref{fig:Passenger-Stops-Transfers} shows us how many stops
	    passengers had to endure to get to their destinations.
	    Since we only had 7 stations in our linear network that
	    passengers must visit in sequence, we get a very predictable
	    ramp down to 6 stops for passengers that traversed the
	    entire line from one end to the other.

	    \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:} Figure \ref{fig:Vehicles-In-Transit}
	    shows the system response of vehicles to the demand impulse.
	    Again, we see a gradual ramp down, as fewer passengers
	    remain in the system as time passes.  The second bin tends
	    to have the most traffic.  The first bin likely is lower
	    because the initial location of the vehicles is free, so
	    vehicles can essentially be created anywhere.  Therefore,
	    the difference in the first bin and the second bin might be
	    attributed to the advantage of vehicles magically appearing
	    exactly where they are needed for these scenarios.

	    A more difficult feature to explain is the valley right
	    after the first peak of activity (and to some extent the
	    less pronounced valleys following subsequent peaks).  The
	    system appears to operate in fits and starts, and it
	    actually appears to rest between spurts of deliveries.  This
	    is observed in all of the linear sequential routing
	    scenarios.  The optimization function attempts to deliver
	    passengers as early as possible, so we would expect the
	    system to push deliveries to the left and not waste time
	    ``resting''.  Perhaps the system is maxing out its capacity
	    in a highly coordinated fashion during a delivery peak, and
	    then uses the ebb of the rest period to do some
	    ``housekeeping'', moving a small number of vehicles out of
	    the way for the next coordinated surge.  In this fashion,
	    the system could deliver large numbers of people faster in
	    two pulses with a gap between them as opposed to spreading
	    the deliveries out evenly, especially if these coordinated
	    pulses were necessary to allow passengers to transfer.

	    \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:} Finally, we look at how full the
	    vehicles were as they traveled their routes in figure
	    \ref{fig:Vehicle-Fleet-Utilization}.  Since minimizing
	    vehicle travel is the lowest priority goal, the vast
	    majority of vehicles operate nearly empty.  In this
	    scenario, the empty vehicles are likely moving out of their
	    way of the ones with passengers, and restoring the fleet
	    initial state at the end of the scenario to remove some of
	    the advantage gained by their magical initial positioning,
	    as discussed in section
	    \ref{sub:Assumptions-and-Limitations}.

	    Gains in vehicle utilization and thus efficiency could be
	    achieved by cutting back on the number of vehicles in the
	    fleet and performing a new optimization.  This would allow
	    us to still emphasize passenger performance over vehicle
	    efficiency.  Otherwise, the scheduler would likely presenter
	    passengers with unreasonable wait times and transfers in
	    order to fill its vehicles up to capacity.

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

To evaluate different transit paradigms against each other, we'd want to
reduce the relationship between system design variables and performance
metrics into a series of parametric equations.  We could then compare
the projected levels of investment necessary for infrastructure and
operations under competing transit paradigms to meet similar performance
goals.


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

We set up a factorial experiment to determine the impact of several
design factors.  By individually varying each independent variable and
observing its effects on our performance metrics, we can establish
correlations between our design inputs and system outputs across a
variety of conditions.

The scenario generation script populates a full factorial directory
structure of 144 scenarios using the following input values for each
parameter of interest:


\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] passenger demand per station
 \item{\bf Vehicle berths per station} [2,4,8] maximum vehicles that can
	    visit and transfer passengers in a station simultaneously
	    per time step
 \item{\bf Vehicle capacity} [16, 64, 128] maximum number of passengers
	    that can ride in each vehicle
\end{description}

A post processing script collects the following output metrics (as
described in section \ref{sec:Scenario-Performance-Data-and-Histograms})
and summarizes them into rows on a spreadsheet.

\begin{itemize}
 \item Total number of passengers handled
 \item Mean passenger transit time
 \item Mean passenger departure delay from time available to depart
 \item Mean passenger number of stops / transfers experienced 
 \item Total number of each vehicle type utilized
 \item Total number of vehicle segments traveled (to give an estimate
       of operating costs)
 \item Mean vehicle capacity utilization percentage (how 'full' the
       vehicles are running during each segment they travel to give some
       indication of their operating efficiency)
\end{itemize}

Each row of input and output data on the summary spreadsheet represents
a different demand level and transit network configuration. We can then
use this spreadsheet to generate several families of plots that
characterize the performance impact of a range of design input
variables.  Each of these plots include data regression curves useful
for creating an approximate parametric model of transit system design.
By applying data filters to the spreadsheet, we can quickly create
several plots that compare the different major design paradigms.


\subsection{Comparison of Linear and Express Routing}
\label{sub:Comparison-of-Linear-and-Express-Routing}

We can use our factorial analysis to perform a quick comparison of
design factors.  In this case, we'd like to highlight some of the
performance differences between a transit network with sequential
routing and one built to accommodate express routes that can bypass
intermediate stations.

Figures \ref{fig:linvsexp-vehicle-size} and \ref{fig:linvsexp-berth-cap}
plot both the linear sequential routing scenarios and the express
routing scenarios on the same set of factorial sensitivity plots for two
other design factors (vehicle capacity and station capacity,
respectively).  A regression line through the data indicates a
correlation between the design factor and the performance metric of
interest averaged over all of the scenario conditions.  A positive or
negative slope indicates a correlation, a relatively horizontal
regression line suggests that other factors dominate.

The top four charts in each set concern the impact of the design factors to
passenger metrics, the bottom three charts affect the vehicle fleet
performance.

\begin{figure}[htp]
\epsfysize=8.0truein
\centerline{\epsfbox{figures/linvsexp_vehicle_size.eps}}
\caption{Effect of vehicle size on passenger and fleet performance metrics: a comparison of linear vs. express routing}
\label{fig:linvsexp-vehicle-size}
\end{figure}

\begin{figure}[htp]
\epsfysize=8.0truein
\centerline{\epsfbox{figures/linvsexp_berth_cap.eps}}
\caption{Effect of station size on passenger and fleet performance metrics: a comparison of linear vs. express routing}
\label{fig:linvsexp-berth-cap}
\end{figure}

The charts in figure \ref{fig:linvsexp-vehicle-size} show that, using
our schedule optimization, vehicle capacity has little impact on
passenger service.  However, the typing of routing used does have a
profound impact on the average transit time and number of stops
experienced by passengers.  Allowing express routing to bypass stations
can cut transit time almost in half, while practically eliminating most
stops and transfers.

The number of vehicles necessary to run a schedule and the amount of
segments they run is also reduced.  The reduction in segments comes
about in large part because stops and transfers count as segments, which
we're attempting to compare to travel segments.  While this may not be
an accurate portrayal in terms of mileage saved, this could still
represent savings of fuel and vehicle wear-and-tear, as braking and
accelerating at a station can be every bit as taxing as cruising at a
constant speed for many types of vehicles.

Figure \ref{fig:linvsexp-berth-cap} tells a similar story, though this
time showing that increasing the number of vehicles that can dock at a
station simultaneously can get passengers to their destinations more
rapidly by easing congestion.

An additional curiosity shows that higher station berthing capacity can
result in much a higher fleet size and operating costs in the linear
sequential routing case which does not affect the express routing
network much.  This highlights some of the inefficiency of forcing
vehicles to stop at every station along a route, especially when there's
extra capacity to handle these stopovers.

This design factor analysis supports notion that, all inputs being equal
and subject to our assumptions, an intelligently scheduled mass transit
system designed around a larger quantity of smaller vehicles running
direct point-to-point routes between offline stations could provide much
faster passenger service while meeting and exceeding the fleet
operational efficiency of more conventional systems.

% LocalWords:  truein PRT ymax xmax timestep MIP LP FIXME graphML yEd UML SimPy
% LocalWords:  zoomable waypoint offline
