\chapter{Analysis of Sample Transportation Scenarios}

In this chapter we exercise the framework and mass transit system
model by computing vehicle fleet performance
for a variety of network configurations,
combinations of loads, and vehicle fleet sizes.

\section{Verification of Simulation Engine}
\label{sec:Verification-of-Simulation-Engine}

Before the simulation environment can become fully operational,
we need to verify that the underlying behaviors
and coservation principles are strictly adhered to.
For example, if a passenger declares the need to travel from locations
A to B, we should verify that nomatter what,
the passenger will eventually arrive.
Similarly, the number of passengers waiting at a station at any time
needs to be consistent with flows of passengers arriving/leaving the station.

Several arbitrary transit networks such as the
one shown in Figure \ref{fig:Arbitrary-transit-graph} provides
a variety of test cases for different combinations of
connections between stations and waypoints
used 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 one or more waypoints.
Additionally it provides multiple equal length routes
linking several stations (such as n1--n2 and n0--n3) to encourage use 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}

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

\begin{figure}[t]
\epsfxsize=6.0truein
\centerline{\epsfbox{figures/state2transferEv.eps}}
\caption{System Snapshot in yEd GraphML Viewer}
\label{fig:yEd-sample}
\end{figure}

We could also attempt to model a regular 2D grid network.  By applying
several simplifications to allow our prototype fleet scheduler to scale
up to a 25-node 2D triangular grid, we could model a PRT-like network.
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.

\begin{figure}[t]
\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}

\section{Simulation Requirements Verification}
\label{sec:Simulation-Requirements-Verification}

\vspace{0.0truein}\noindent
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
should remain at their point of origin (and not stranded in the
middle of the transit network)
\item
Connectivity constraints are not violated.  Vehicles and
passengers should only move between nodes that are connected on
the connectivity matrix.
\item
Vehicle capacity constraints are not violated.  Passengers should
not be able to move independently between nodes without enough
vehicles to carry them.
\end{enumerate}

The simulation itself served as an invaluable verification tool for the
schedule optimizer, as it was quick to point out inconsistencies in the
number of passengers and vehicles available at stations while trying to
follow the schedule.  Tracing errors and crashes in the simulation
helped debug the schedule optimizer's performance.

\section{Validation of Analysis Data}
\label{sec:Validation-of-Analysis-Data}

During validation testing, desired behaviors and unwanted problems were
found by taking some of the following measures:

\begin{description}
\item{\bf 1.}
Tracing 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{\bf 2.}
Checking for optimality by attempting to find improvements to or
deficiencies in the schedule.  This task should be hard, or even
impossible if the solver had found an optimal solution.
       
\begin{itemize}
\item
Scenarios with multiple vehicle sizes and a high enough
load should show a ``preference'' for using larger, more
economical vehicles, supplemented by a few small vehicles
running around feeding the larger ones to full capacity.
\end{itemize}
\end{description}

\section{Sample Scenarios}
\label{sec:Sample-Scenarios}

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

Scripts produce sets of results for two types of system topologies,
meant to represent different paradigms in constructing transit networks:
(1) A simple 1D linear light-rail system, and
(2) A 2D hexagonal cluster unit on a triangular grid.

\subsection{1D Light 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.  Note that the additional routes made
available indicate temporal paths and not separate physical paths
between stations.

\begin{figure}[p]
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_linearrail.eps}}
\caption{1D Light-Rail System Connecting Four Neighborhoods`}
\label{fig:1D-Rail}
\vspace{0.25 truein}
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/tg0_expressrail.eps}}
\label{fig:1D-Express}
\caption{1D Light-Rail System Connecting Four Neighborhoods,
but with Local and Express Bypass Routes}
\end{figure}

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

In order to scale up our schedule optimization to tackle larger, more
practical transit networks, we'll have to start by concentrating our
efforts on a simple triangular grid organized into hexagonal units.
Building upon this basic unit, we could eventually decompose larger
problems hierarchically into clusters of hexagonal units and solve them
in parallel, as described in Section \ref{sub:Hierarchical-Optimization}.

As in the 1D rail scenario, we 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 stations passed.

\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  exagonal 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.  In particular, the beginning locations of
vehicles are currently left free.  This gives the transit systems used
in our scenarios an unfair advantage, as vehicles can initially be
``magically'' created anywhere in the network.  The total number of
vehicles in the fleet is also 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 considers
all vehicles of the same type as interchangeable, this repeatability
constraint does not force all vehicles to make complete round-trips.
They might operate in rotation with other vehicles of the same type.

As noted in the scenario description at the beginning 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, as noted in Sections \ref{sub:Spatial-Load-Distribution} and \ref{sub:Temporal-Load-Distribution}.

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 could be adjusted by
adding additional segments to increase the visit penalty at stations, or
to increase the travel time between stations.  For these scenarios we
sill stick to a ratio of $1:1$, which seems reasonable for several forms
of transit.

We impose a maximum number of time units allowed by a schedule.  Having
more time units translates to a higher possible capacity over that time.
On the 1D linear rail networks, we limit schedules to 18 time segments,
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 segments, which works out to 3 times the
diameter of the sequential network ($2*2$ segments between an outer
station to any other outer station).

Due to the high computing time required to exhaustively search the
entire schedule optimization solution space, 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 calculation time.  In a real
transit network this timeout would prevent vehicles from idling while
waiting for further instructions from the global scheduler.  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 probes monitor 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 a 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}

Improving system performance perceived by passengers of the system often
comes at the expense of vehicle fleet operating costs.  Improving
passenger service goals typically increases the number of vehicles
operating and the distance they must travel during the course of a
schedule.  Since our optimization goal favors the fulfillment of
passenger goals first, we expect to see some fairly straightforward
trends.

Histograms in red 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 segment 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 after
	    roughly every other time segment, since all stations are
	    separated by one waypoint. The quantity of passengers
	    delivered diminishes with time, as fewer combinations of
	    station pairs are that number of segments 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}[t]
\epsfxsize=5.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 amount of 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=5.5truein
\centerline{\epsfbox{figures/hist_deptTime.ps}}
\caption{Passenger Departure Time}
\label{fig:Passenger-Departure-Time}
\vspace{0.2truein}
\epsfxsize=5.5truein
\centerline{\epsfbox{figures/hist_transfers.ps}}
\caption{Passenger Stops / Transfers}
\label{fig:Passenger-Stops-Transfers}
\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.
\end{description}

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

\vspace{0.1truein}\noindent
Histograms in blue 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.  In our scenarios, 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 vehicles receive
	    from the ability to magically appear 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 surges of activity.  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 make transfers.

\begin{figure}[htp]
\epsfxsize=5.5truein
\centerline{\epsfbox{figures/hist_vehInTransit.ps}}
\caption{Vehicles In Transit}
\label{fig:Vehicles-In-Transit}
\vspace{0.2 truein}
\epsfxsize=5.5truein
\centerline{\epsfbox{figures/hist_vehSegUtilization.ps}}
\caption{Vehicle Fleet Utilization}
\label{fig:Vehicle-Fleet-Utilization}
\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. Also, some empty vehicles
	    may move to restore the fleet's initial state at the end of
	    the scenario, which offsets some of the advantage gained by
	    their ``magical'' initial positioning 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 present
	    passengers with unreasonable wait times and transfers in
	    order to fill its vehicles up to capacity.


\end{description}

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

To evaluate different transit paradigms, 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 tree
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] All topologies
	    consist of 7 station nodes.  The ``express'' routes indicate
	    that vehicles may bypass offline stations to gain a 1 time
	    segment advantage over stopping.
 \item{\bf Load} [4, 64, 128, 256] Passenger demand per station.  The
	    total number of passengers on the network would work out to
	    $\frac{6}{7} {Load}$, since $\frac{1}{7}$ of the employees
	    would live in the same neighborhood where they worked.
 \item{\bf Vehicle berths per station} [2,4,8] Maximum vehicles that can
	    visit and transfer passengers in a station simultaneously
	    per time step.  2 could represent a typical rail station
	    with cars running on 1-way tracks.  4 might represent a rail
	    station with two tracks where cars at the platform could
	    depart in either direction.  Finally, 8 could represent a
	    station with many individual, independent berths, such as a
	    bus transfer station.
 \item{\bf Vehicle capacity} [16, 64, 128] Maximum number of passengers
	    that can ride in each vehicle
\end{description}

\noindent

A post processing script collects the following output metrics
(condensed forms of the histogram data 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, to summarize how
       'full' the vehicles are running during each segment they travel.
       This metric gives some indication as to the system's 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 highlighting correlations and 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 the
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 vehicle
capacity has little impact on passenger service for our optimized
schedules.  However, the type 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 average
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.
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
