\chapter{Simulation and Analysis Framework Systems Design}

The previous chapter has outlined a way to decompose and organize an
urban area and the transportation network that serves as its circulatory
system.  This chapter will discuss the design and structure of a
simulation framework suitable for executing and analyzing a model of an
arcology, as well as introducing some of the technical considerations
and design goals of a mass transit system based around this framework.
Finally, the ensuing chapters will discuss the specifics of the mass
transit system model program developed for this project to model and
analyze several types of transit scenarios.

We again exercise the systems engineering framework described in figure
\ref{fig:system-development1} to organize our efforts to decompose the
design of our simulation framework.

\section{Simulation Tool Use Cases}
\label{sec:Sim-Tool-Use-Cases}

Potential use cases for the simulation model include:

\begin{itemize}
\item Set up a modeling scenario using input data.

\begin{itemize}
\item Build bottom-up scenario: Since the arcology is designed from the
ground-up, starting at the individual level, the structure of our
model would allows us to calculate the aggregate performance at higher
levels of organization, such as a the city and national level.

\begin{itemize}
\item Define \# of simulation units, connectivity between units,
      schedule of transaction events, schedule of reaction events,
      initial conditions. 
\item Output aggregate performance for groups of units.
\end{itemize}
\item Build top-down scenario: The present day scenario is built in a
      top-down fashion from various data sources. Statistics are only
      tracked from relatively high levels on the organizational
      hierarchy, so we must extrapolate some data to flow down to fill
      the detailed subcells of the structure.

\begin{itemize}
\item Define high-level consumption rates for groups (using publicly
      tracked and available data), provide distribution histograms for
      each type of resource and transaction rates for each subunit.
\item Output unit-level quality of life, performance.
\end{itemize}
\end{itemize}
\item Execution of simulation model to produce output data.  The ability
      to perform multiple scenario simulations in parallel would greatly
      increase our data analysis throughput.
\item Postprocessing and analysis of output data into performance metrics.
\item Design-of-Experiments methodology for parametric analysis of solution
      space exploration and optimization.
\end{itemize}

What potential uses could this transportation network simulation have?
One of the main types of problems it shall address is passenger demand
generation.  Different types of transportation infrastructures could be
evaluated against each other to determine how well they meet that
demand. Many existing transportation problems tackle ways to increase
throughput or capacity. But the task of urban planning should also focus
on arranging its physical layout to minimize demand loads in addition to
building out transit infrastructure to maximizing capacity. For example,
instituting staggered work hours or telecommuting programs can relieve
peak rush hour traffic congestion without spending a fortune widening
highways and building additional infrastructure just to increase
throughput for a few hours of peak usage a week. It would be nice to
know how much incentives to provide to encourage employers to implement
flexible work hours, or how much to invest in telecommuting
infrastructure (such as municipal broadband) in order to provide
productivity benefits similar to simply adding highway lanes or
additional thoroughfares.

Also, by simulating demand, we can create a transportation system
that is more sensitive to individual needs rather than the aggregate
flow of travelers. This would allow us to create schedules around
the traveler's itinerary rather than forcing the traveler to always
plan around fixed train, bus, ferry, and aircraft timetables. For
instance, if everyone starts work exactly at 8:30, but buses only
run hourly on the hour to that particular stop, then the extra half
hour everyone spends waiting per day essentially counts as extra commuting
time in their books, even though the bus operators might only measure
the time the passenger spends sitting on the bus and perhaps waiting
for known connections.

An advanced busing system that dynamically generates routes and
schedules based on individual source and destination requests from each
passenger could achieve efficiencies and meet customer requirements far
better than what we have today, and could make public transportation
more attractive to people who drive their own vehicles in order to
maintain that degree of flexibility. During peak commuting hours, this
has the potential to reduce individual commute times, as buses could be
scheduled more like express routes and fill up at one location and
proceed directly to stops at a common destination with minimal stops or
transfers or jaunts down back roads along the way. During off-peak
hours, buses would not run nearly empty along the same routes with very
low frequency, but would run on demand, cutting down wait times and
making them a more convenient option for midday or late night errands. A
more effective public transportation system should succeed in making the
world \char`\"{}smaller\char`\"{} by making each district of a municipal
area more readily accessible, allowing people to travel between places
where they live, work, run errands, and seek entertainment. Under the
trunk and feeder paradigm often used to organize mass transit in
metropolitan areas today, travel through the system can take
considerable time unless your source and destinations happen to be near
major hubs or just down the street from each other on an established
route. The worst case scenario for many trips off of a main trunk line
would consist of catching a local feeder bus route to the nearest
trunkline light rail station, making a transfer at a major hub or two,
and finally catching another feeder route to your ultimate
destination. Each transfer would typically consist of at least 5-20
minutes of waiting for the next connection.  Compared to driving your
independently owned vehicle, public transit would often take two to four
times longer, even with traffic. Commuters would travel twice per day,
so the time savings of taking a personally-owned vehicle could add up to
an additional 1-2 hours of personal or family time at home each
day. Public transportation systems could use much improvement to make
mass transit preferable to driving, but often it becomes an alternative
to escape congestion on the roadways rather than the primary mode of
travel. Drivers support investment in public transportation only insofar
as it gets other cars off the road.

\subsection{Performance Metrics}

\label{sub:Performance-Metrics}What defines a good inter-modal transit
system? The conflicting goals might be characterized as: speed, response,
coverage, and efficiency.

\begin{itemize}
\item \char`\"{}Speed\char`\"{} refers to how fast the transit system can
get a passenger or cargo item from point A to point B. Unfortunately,
this does not depend entirely on the cruise speed of the vehicle alone,
but also time spent making transfers and additional preparations (such
as passenger check-in and luggage screening at airports)
\item \char`\"{}Response\char`\"{} refers to the frequency of service,
particularly how well it matches and meets demand. Extra time that
people have to wait at their source or destination should be counted
against the system\ldots{} though this is almost always overlooked in
transit performance metrics today. The data just isn't available, or
people have relegated themselves to adjust their schedules around the
system's timetables. This \char`\"{}response\char`\"{} metric will
usually be at odds with efficiency due to economies of scale, since
making passengers wait longer times between pickups can cluster them
into larger groups.
\item \char`\"{}Coverage\char`\"{} refers to how well the transit system
covers the service area, which should include how far people have
to walk from their doorstop to enter the system. Broad coverage is
more difficult to achieve for a mass transit system, especially as
population density decreases and residences and businesses are more
spread apart.
\item \char`\"{}Efficiency\char`\"{} might refer to two terms: that in terms
of frugal monetary spending on operating costs and fixed infrastructure
investments, as well as in terms of conservation of fuel and resource
utilization. Efficiency pretty much always counterbalances against
each of the three other goals, so we often must express how much extra
money or fuel we are willing to expend for whatever modest gains in
speed, response, or coverage.
\end{itemize}

\subsection{Transit Schedule Optimization}
\label{sub:Transit-Schedule-Optimization}

To reasonably achieve improvements these multiple competing performance
goals, we must employ some manner of vehicle fleet optimization in order
to fully investigate the potential performance of a transit platform.
An intelligent transit system would take advantage of existing and
emerging ubiquitous computing and communications networks to be more
responsive to customer requests and deliver passengers in a more
coordinated manner.  While fixed route schedules might work for normal
demand based on projections, the true performance of a transit system
should take into account all available information.  This could include
advance knowledge of special events that create spikes in demand to
certain stations, or even unforseen events such as breakdowns that close
transit lines and trigger a failure mode of operation with an altered
schedule.

An optimization problem should be formulated to dynamically take in data
about the arrangement of stations, passenger requests for transit
between available stations, and properties describing the vehicle fleet
and constraints pertaining to their movements between stations, and
provide an optimized plan for delivering passengers to their
destinations.  This would allow us to identify and focus on the
performance impacts of physical design parameters independently of often
arbitrary logical routing methods.  The optimization could proceed in
real time, incorporating updates from the evolving system state in a
rolling-horizon fashion. It would incrementally compute the next few
interchanges in the future, at first working on projected future demand
data, and filling itself in with more solid data collected from vehicle
and station sensors. 

Once we identify transit scheduling paradigms that perform well, we
might simplify the network somewhat by establishing fixed routes.
However, we see no reason why a fully dynamically-reoptimized transit
system couldn't guide their passengers through a constantly updating and
changing network or vehicles through the use of mobile phone text
messages or some other digital assistant.


\subsection{Comparison Framework for Multiple Urban System Models}
\label{sub:Multiple-Model-comparison}

So what can we do once we have coupled an urban model to generate demand
on a transit network, a system simulation engine, and a schedule
optimization algorithm that could direct the action? We can set up yet
another iterative optimization -- this time of the design parameters for
each particular simulation scenario. This will help us evaluate urban
design and infrastructure in ways that should help drive progress
towards efficient and sustainable societies that serve the people who
live in them.  We could propose a new construction or infrastructure
project, show its benefits in a simulated model, and later validate
those benefits using data collected from the real system. Competing
models for improvements might even have the chance to provide benchmarks
using this analysis platform.

The ability to compare several optimization components, several system
structures, different modeling methodologies, all using the same data
interchange format to facilitate direct comparisons between both real
and simulated evolution of the scenarios, allows us to take a systematic,
objective approach to tackling urban improvement projects. Adapting
such a simulated and real system performance comparison framework
will allow us to have more complete impact assessments by making sure
every study or proposal is analyzed consistently, using the same inputs,
and doesn't sweep away or ignore unwanted side effects and consequences.
Urban planners could use these studies to provide ammunition for driving
changes toward the way they envision their communities. An intensified
focus on operational efficiency and continuous improvement driven
by pervasive measurement and analysis will lead towards a leaner,
sustainable society where we could direct a higher ratio of resources
towards forward progress instead of mere subsistence.


\subsection{Transit Simulation Requirements}
\label{sub:Transit-Simulation-Requirements}

With that, we proceed to develop the outline for what our simulation
must accomplish:

%
\noindent
\shadowbox{\parbox[t][1\totalheight]{1\columnwidth}{%
\begin{enumerate}
\item Read scenarios as inputs

\begin{enumerate}
\item[1.1.] Hierarchical layout of transit stations and connectivity
\item[1.2.] Initialize simulation entities involved (people, vehicles,
	    residences and workspaces, \emph{etc.})
\item[1.3.] Load demand schedules for passenger movement
\end{enumerate}

\item Simulation execution to evolve state of system entities

\item Output metrics defined and calculated

\begin{enumerate}
\item[3.1.] Passenger measures of performance
\item[3.2.] Vehicle measures of performance
\end{enumerate}
\end{enumerate}
%
}}% 


\section{Implementation of Simulation System Structure}


We used the Umbrello UML tool to create diagrams in this and subsequent
chapters\cite{umbrello}. While its code generation capabilities are not
as comprehensive as that of the commercial tools such as I-Logix
Rhapsody, it can generate class stubs for several languages including
Python as well as an XML Schema that might be used to help validate data
interchange.


\subsection{Discrete Event Simulation Framework}

\begin{figure}[htp]
\epsfxsize=6.0truein
\centerline{\epsfbox{figures/Components.eps}}
\caption{Simulation Framework Component Data Dependencies}
\label{fig:Simulation-Components}
\end{figure}

The prototype framework depicted in figure
\ref{fig:Simulation-Components} consists of three major parts. The
simulation code is written in Python makes heavy use of the SimPy
module, while the solution of the schedule optimization problem occurs
using the LP-solve mixed integer linear program
capability\cite{simpy,lpsolve}. These components are wrapped around a
scenario generation and post-processing framework that creates a
directory tree of scenarios with slightly different initial parameters.

The schedule optimizer formulation was first prototyped in Perl before
being ported to Python.  Ironically, Perl's in-line variable output
syntax made its code much easier to read and debug than equivalent
Python code. 

Being the ``brains'' of this framework, the more complicated
optimization problem imposes a few major constraints that help simplify
the way we'd model our transit network. The transit system must consist
of a network of ``station'' nodes representing the entry, exit, and
transfer points for passengers and cargo. Passengers and cargo can only
move between nodes on vehicles, which can transfer them between any two
connected stations or waypoints at regular, synchronized
intervals. Several vehicle types can be made available, and can differ
in passenger capacity per vehicle, cost per transit event, connectivity
graph between nodes, the maximum number of vehicles allowed to visit a
station at the same time, and a host of other measures and constraints.

The most crippling part of the model deals with timing. Time is dealt
with in terms of synchronized discrete timesteps, during which the
state of the entire system can be represented at one point in time
by a complete set of variables. At each time step, the state of the
system must be such that every vehicle is stopped at a node. By the
next time step, all passenger transfers must have been made and all
vehicles must have completed their transit to the next station node
(or else stayed in place at their current station). When the simulation
translates this to events in continuous time, this means that all
stations synchronously act in unison, where every vehicle departs
simultaneously, travel all at the same time, and offload passengers
at their destinations simultaneously, and all wait together for passengers
to transfer to make connections. While this obviously constrains the
flexibility of the model in a big way, this arrangement allows the
schedule optimizer the flexibility it needs to balance hub-and-spoke
transfers with more direct paths, depending on the capacity and economics
of the vehicles made available.

Therefore, the model used in this analysis is that of transit stations
that are an equal distance apart (at least in terms of transit time)
and that each and every vehicle waits the same amount of time for
passenger transfers to complete before they disembark for their next
destination. The result is that, in reality, a fair amount of time
is bound to be wasted under this model as all vehicles must stop and
wait for transfers at all intermediate stations on their paths, even
if they are not transferring passengers.

To make the modeling language a little more realistic, we also added
``non-station nodes'' referred to as waypoints in between stations, and
enforcing conditions that prevent passengers from inadvertently
transferring off of their vehicles. By adding these waypoint nodes to
the transit network, we could create more realistic models that take
into account varying distances (by time) between stations and add
modeling detail by allowing passengers and vehicles to have a defined
state while en route between stations.


\section{Simulation System Behavior}

The Scenario Generator runs first and generates a directory hierarchy of
scenario data and a makefile that allows us to run simulations and
parallel and only on scenario data that has not yet been computed.  This
allows us to add data points to large data sets without having to spend
a lot of time recomputing existing results.

Snapshots of the simulation occur regularly and trigger the creation of
new optimization formulation files, which might be solved by python's
LP-Solve module several times throughout the evolution of the
simulation.  The simulation reads the results returned by LP-Solve
through its Python interface, which creates a schedule result object
referenced by all of the actor entities in the simulation.

After the runs are complete, the yEd graph view can neatly organize and
display state snapshots of the transit entities in its pseudo-UML object
view\cite{yed}.  These visualizations of the simulation's graphml state
dumps greatly assisted development and debugging.

Finally, a post processing script assembles the raw output of SimPy
data monitor taps into histograms for collective display on a summary
web page for comparison.  It also condenses a spreadsheet of input
parameters and output metrics for each scenario to allow further data
reduction as described in section
\ref{sub:Design-of-Experiments-for-Parametric-Analysis}.

The program uses the Psyco and SciPy modules to greatly increase
the execution speed of most operations\cite{psyco,scipy}.


\subsection{Statistical Scenario Comparison}
\label{sub:Statistical-Scenario-Comparison}

The simulation uses some pseudo-random distributions to initialize
demand curves. In order for our simulation runs to maintain repeatability,
each of the scenarios include an initial random seed. A simulation
run with the same seed will always generate the same random variables.
Conversely, we can also vary the initial random seed across several
runs of the same scenario in order to do Monte Carlo type simulations
that gives us a proper distribution of output metrics as well.

The use of randomized initial distributions has another useful feature,
in that it prevents the optimization problem from becoming too symmetric.
Too much symmetry would result in multiple equal-cost branches to
search exhaustively. So adding a touch of entropy to the our system
allows our MIP solver to converge on a better solution slightly faster.



\subsection{Computational Considerations}
\label{sub:Computational-Considerations}

Large scale global optimization can require a lot of computing power. It
falls under the class of NP hard problems that scale exponentially with
the number of transit nodes we add to the transportation system. Let's
look at some of the ways in which problems of this size can be tackled.

The simulation is set up to run in parallel across several CPUs,
scalable to a massive clustering system with a shared data
filesystem. Some linear and mixed integer solvers also have the
capability to partition and solve problems in parallel.  LP-Solve does
not, but it does have the ability to export its model into other
modeling languages such as CPLEX or the industry standard MPS MIP format,
so we do not have to worry directly about parallel problem solving.

We still would need to resort to a host of other tricks to reduce
the computational complexity enough to approach any problems of any
appreciable size. Most of them involve introducing some sort of constraint
to reduce the number of branch and bound paths search in the solution
space.  But primarily we resort to LP-Solve options that allow us to
accept suboptimal but feasible solutions.

\begin{itemize}
\item The easiest way to reduce the computational complexity is to
      partition the problem into smaller parts. Since these types of
      \char`\"{}traveling salesman\char`\"{} problems scale
      exponentially with respect to the number of nodes, the number of
      branches to search would be drastically reduced.
\item Adding link constraints is also another way of reducing the search 
      space. Not every node needs to be linked to every other node. So
      often we will resort to building a connectivity matrix to define
      which source nodes can get to which destination nodes. With road
      and rail, only adjacent nodes are directly connected. Distant
      nodes would require transit through other city or station
      \char`\"{}nodes\char`\"{} 
\item With aircraft, of course, most vehicles can travel directly from
      any node to just about any other node in the network. In this
      case, it may be helpful to add \char`\"{}max connections\char`\"{}
      constraints, to keep the system for searching through
      impractically long schedules. An itinerary that made a passenger
      jump between more than two or three connecting airports would
      likely be rejected by that person. Of course, low priority bulk
      cargo may find some advantage through waiting for these multiple
      connections, filling in otherwise \char`\"{}empty\char`\"{} space
      leftover on any flight where the opportunity arose to get it
      slightly closer to its destination. But at some point all of the
      extra handling and transfer overhead ought to outweigh whatever
      small price break.
\item Just about any schedule constraint that would help \char`\"{}lock
      down\char`\"{} otherwise free-floating variables would help reduce
      the search space. Feeding in initial conditions - like the current
      locations of the vehicles in the fleet, or stops that must be made
      by a certain time (for example, to ensure buses take all
      passengers to a stadium well before a game starts) may help speed
      the optimization solution search along.
\item Sometimes it may be necessary to simply add other heuristic or
      even arbitrary constraints to help the system converge on a
      solution. Many of these constraints probably won't even affect the
      solution, but constrain the search space enough to allow a much
      quicker answer. 

\end{itemize}
All else failing, many mixed-integer programming solvers also allow
\char`\"{}good enough\char`\"{} solutions to be given without a complete
exhaustive search of the solution space. Modern MIP solvers can be
pretty clever about searching the \char`\"{}most promising\char`\"{}
paths first, so completing the entire exhaustive search would yield
little incremental gap improvement over the previously discovered
feasible objective. Of course, this technique only applies if a feasible
solution is found at all.

LP-Solve specifically has a host of options that can allow it to return
suboptimal solutions before completing an exhaustive branch-and-bound
search of the solution space.  It can simply provide the first MIP
solution it finds after locating the relaxed linear solution via its
simplex solver.  We can also converge upon solutions faster by
increasing its MIP gap tolerance between improved suboptimal solutions
it finds along the way, which reduces the depth of its branch-and-bound
search.  Finally, it also offers a wall clock timeout that stops an
optimization from running virtually forever and returns the current best
suboptimal solution. For reasons discussed in section
\ref{Assumptions-and-Limitations}, this last method is not employed for
our analysis.

Finally, a sophisticated optimization would involve pre-computing most of
the possible schedules in advance, and then have the ability to account
for the effects of small changes with only minimal recalculation of the
final optimal solution. This type of incremental adjustment may be
necessary to recover from small, unexpected schedule breakdowns.
Suppose a vehicle suddenly announces that it will be arriving 30 minutes
late to a hub node. If recomputing the entire optimal solution taking
this new information into account would take a few hours of number
crunching, we obviously don't want everything to grind to a halt while
waiting for the scheduler to tell us what to do next. An
\char`\"{}incremental update\char`\"{} to the solution performed with
minimal recalculation might be achieved by determining which vast
majority of system variables shouldn't be affected, and formulate a
highly-constrained optimization problem that only searches through a
small set of variables affected by the unexpected change in one or two
schedule input values. We'd need to develop a heuristic to determine
exactly how far out this limited set of \char`\"{}affected
variables\char`\"{} should reach.

Another scheme might involve jumping back into a snapshot of the state
of the large optimization and only recalculate internal values that
have changed with the modified inputs. Perhaps some solvers have this
ability.


\subsection{Multiple Schedule Optimization Algorithm comparison}
\label{sub:Multiple-Schedule-Optimization} 

The main way we'll be able to improve efficiency (aside from simply
improving fuel efficiency) would be to use existing resources smarter
through extensive use of optimization. With enough planning and
foresight, optimal scheduling is straightforward to perform. However,
things never quite go as planned, due to a variety of unpredictable
factors such as weather and accidents and just plain last-minute changes
in schedules. In order for the optimal plan to be of much use, we ought
to continually collect enough data in real-time to monitor and
reevaluate schedules as able. This requires that we have a
communications system in place that allows us to poll the status of our
cargo, passengers, and transportation vehicles. Equipage for this type
of system would have been cost prohibitive in the not-too-distant past,
but now that geo-location devices, mobile computing, wireless networking,
and cellular data network backbones have become nearly ubiquitous, we'd
be silly to not put all this capability to good use.

So instead of having fixed timetables locked down and set weeks, months,
or even years in advanced, based only on projections from previous
observations of seasonal, aggregate flows of the past, and barely ever
followed to the minute, we could perform schedule optimization on actual
data. This data would factor in individual requests from each customer,
including their destination and schedule constraints (or better yet,
their schedule flexibility). Vehicles could report their current
location and status, meaning they'll always be right on time -
especially since they could report their arrival time themselves.
Monitoring and reporting of deteriorating road or weather conditions
could automatically update the schedules of every vehicle in the network
to account for and mitigate the effects of new delays.

\subsection{Dealing with Unforseen Events}
\label{sub:Dealing-with-Unforseen-Events}

We live in an uncertain world. How will the system deal with uncertainty
and unexpected events in schedules? Probability should be built in to
the optimization problem formulation, and one of the goals of the
optimizer might be to minimize the impact of unfavorable (but probable)
events. Analysis of historical records can generate performance metric
associated with each vehicle, route, weather prediction, \emph{etc.}  A
useful way of representing on-time performance probabilistically is to
reconstruct the data from the cumulative distribution function (CDF)
associated with the prediction as shown in figure
\ref{fig:Cumulative-Distribution-Function}.  This would work much better
than simply providing means and standard deviations, since most transit
data is so skewed towards being late than being early. It's much easier
to break down and be several hours late, than to speed across a
transportation link in record time. The CDF can be quantized to reduce
computational complexity, at the cost of adding larger conservative wait
time buffers between connections.

\begin{figure}[htp]
\epsfxsize=4.5truein
\centerline{\epsfbox{figures/cdf.eps}}
\caption{Cumulative Distribution Function of Vehicle Arrival Times}
\label{fig:Cumulative-Distribution-Function}
\end{figure}

While this type of data will be monitored and collected, only the
late arrival cutoff tail will impact the scheduler and trigger a new
optimization run to take care of the passengers or vehicles that would
have missed their transfer.

We're primarily interested in what time the vast majority of the vehicles
will arrive, as well as what hopefully small percentage are beset
by schedule-impacting delays. There's no fixed \char`\"{}magic percentile\char`\"{}
that would determine how much extra buffer time to schedule to make
sure everyone makes their connections. This will likely be set arbitrarily
at the beginning, as all of these factors contribute to an overall
\char`\"{}confidence in planned schedule volatility\char`\"{} metric
(maybe more easily expressed as an opposing \char`\"{}schedule stability\char`\"{}
metric). With the optimizer system, we can recompute new schedules
whenever an unexpected event comes up - such as when a vehicle is
delayed enough to fall on the tail end of the CDF and it misses its
connection. The optimizer can take that new information into account
and simply create a new schedule based on these existing conditions
- which will likely result in diverting other vehicles over to take
care of the late straggling passengers. So the risk analysis that
determines how aggressively to schedule extra buffers into the system
would depend on how much impact a schedule recovery plan would have.
Planning in large buffers to reduce risk likelihood means extra wait
time for passengers and more idle time for vehicles in order to ensure
that the schedule stays stable. The ability to drastically reduce
these buffers means the whole system could run at a faster pace. If
the cost of recovering from missed connections is low - say to catch
a subway train that runs every 5 minutes - then the scheduler can
comfortably deal with smaller buffers and higher schedule volatility
risk. In the case of an airplane network where flights run between
cities maybe once or twice a day, a missed connection would mean putting
people up in hotels or chartering additional make-up flights. In this
case, increased schedule awareness can also help by figuring out the
total impact on whether it's even worth holding flights for latecomers
to make their connections.

So in addition to the overall transit system performance optimization
goals we discussed in section \ref{sub:Performance-Metrics}, we also
want to introduce some practical optimization goals that will help
the scheduler intelligently create and maintain buffers to deal with
uncertainty. Now, how to formulate and computer this enhancement is
beyond me, since it would likely require the optimizer to do risk-impact
assessments on every combination of missed connection. But that's
no reason to shirk away from providing the necessary information about
on-time performance in the data protocol now, so that future generations
of engineers could tackle it.

\subsection{Multiple Operator Collaboration}
\label{Multiple-Operator-Collaboration}

The final category of optimization constraints would come from the
operators of the various transit networks. This would allow them to
add crew and maintenance schedules, such that they can pick up and
drop off drivers, pilots, and other staff at certain locations, or
make sure that a vehicle ends up in a certain maintenance bay every
so often for refueling and service.

These constraints are typically easy to add without a lot of heartburn,
since they tend to help reduce the number of branch and bound paths
that a mixed integer programming optimizer needs to search through
to converge on a solution - at least as long as the solution remains
feasible. The challenge comes in that expressing these constraints
should be the job of the separate transit network organizations, and
the abstract protocols needed to express these constraints would likely
require extensive knowledge of how the global optimization problem
is formulated and solved. It is undesirable to have this information
format coupled too closely to the formulation, since it will make
it more difficult to change and upgrade the optimization engine in
the future. We don't want to force everyone to have to radically change
their code at the same time throughout the system every time we want
to introduce an incremental upgrade. We also don't want the entire
systems upgrade to fail because of one or two late development efforts.
We want enough abstraction built in so that they might make changes
at their own pace to take advantage of new scheduling and optimization
features and capabilities. Their abstract representation of their
constraints needs the ability to compile itself so it can be applied
to both the old and the new versions of the optimization formulation.

Unfortunately, development of an abstraction language lies beyond the
scope of this work.  Such a language might allow the businesses to
express what additional criteria a generic schedule optimizer must meet,
without ``cheating'' and taking advantage of direct and specific
knowledge of the optimization formulation and of its variables. A
sophisticated abstraction language processor would have to take the
expression and transform them into equations that relate particular
variables to each other and existing variables in the global problem
formulation.  This processor would be nontrivial to implement without a
lot of prior experience, and even still could give way to unexpected
errors and behaviors. A more practical way to handle operator-specific
crew and vehicle maintenance schedule requirements might have the
operators compute maintenance schedules separately from the main
globally optimized schedule, and insert them as fixed constraints using
a scheduling interface that could also be used to importing legacy fixed
routes. The end result of would not be as optimal as possible if the
global scheduler could directly search for solutions that also fulfilled
operator schedule requirements, but at least we start closer to an
optimal solution. The iterations would proceed something like:

\begin{enumerate}
\item Transit network operator would provide the number and current locations
of available vehicles at the beginning of the day
\item The global optimizer takes the customer demands and those initial
conditions, and furnishes the schedule desired of that transit system.
\item The operators manually (or semi-heuristically) tweak the schedule
to ensure that particular vehicles end up in nearby maintenance bays
when they're due. These get fed back into the global optimization
as constraints.
\item The global optimizer find a new solution taking these new constraints
into account, filling in new gaps in the schedule and hopefully not
straying too far from the original optimal objective function result.
\end{enumerate}
This would let us converge on a solution set somewhat near the optimal
one that takes maintenance factors into account without tying down
the programming to a particular implementation of the optimizer.

A global optimizer that could include operator goals and scheduling
constraints certainly isn't out of the realm of possibility. The party
maintaining the global schedule formulation might allow third parties to
add their own set of constraint statements, even weighted objective
functions.  We'd still need to exercise some discipline to keep the
system stable. In the original single-operator paradigm, the problem is
formulated in advance, and all the input data provided by passengers and
schedules only add constraints in a consistent manner -- the worst thing
that could come about by faulty data might be infeasibility. However, by
allowing third parties deeper control of objective functions and
constraint statements, we're exposing the system to a host of potential
problems and vulnerabilities:

\begin{itemize}
\item Malformed or even malicious statements can make the problem
      intractable.  There may be ways to identify some offending
      statements and automatically detect and flag them to somehow alert
      or even filter them out of the calculations - but the latter
      approach could likely create unpredictable results. 

\item We'd need ownership and permissions on variables to separate the
      components provided by different parties. This would ensure that
      operators don't introduce constraints that could penalize their
      competitors. 

\item Many companies pride themselves on their own optimization
      capabilities. We may need a mechanism to protect proprietary
      information about their mode of operation revealed in their
      contributed code statements. We could allow them to submit
      \char`\"{}black box\char`\"{} modules that manage to interact
      properly with the rest of the global optimization. An alternative
      method may be to partition the problem such that they're entirely
      responsible for optimizing their segment of the global
      calculation, interacting with the rest of the system through the
      input and output protocols.
\end{itemize}

Hopefully these considerations have helped to articulate why we haven't
addressed these issues in the current incarnation of this thesis. But
this section might provide an outline for tackle these issues in the
future.


\section{Model Validation Against an Actual System}

Ultimately we would want to calibrate our simulation against an actual
transit system modeled by it. Due to the discrete timestep nature of our
schedule optimization model, the simulation would only be capable of
providing an approximation of the live system performance. However, if
the live system uses the same schedule optimization algorithm used in
our simulation, we wouldn't expect simulated versus live performance to
differ appreciably unless passengers miss connections. The simulation
currently does not model these types of unexpected events, but adding
such probabilistic failures to the simulation shouldn't pose much of a
challenge.  The challenge lies in calibrating those probabilities
against those that might occur in the live system due to factors
discussed in section \ref{sub:Multiple-Schedule-Optimization}.


% LocalWords:  subcells Postprocessing trunkline MIP geo CDF truein Umbrello LP
% LocalWords:  infeasibility UML Logix XML SimPy timesteps waypoint en yEd MPS
% LocalWords:  Psyco SciPy filesystem CPLEX pre timestep sim
