\chapter{Conclusions and Future Development}

The fleet schedule optimizer's work grows exponentially with the number
of nodes, so I hit a scalability limit with about 8 near fully-connected
stations... beyond that, it takes more than 30 minutes for my 1.87Ghz
AMD K7 PC to find any feasible suboptimal solution. Trying CPLEX instead
of LP\_solve might help here, especially if CPLEX can do better
preprocessing to eliminate variables.


\section{Analysis of Additional Design Factors}

We could easily take the opportunity to design new groups of experiments
for factorial analysis on additional design parameters.

\subsection{Spatial Load Distribution}
\label{sub:Spatial-Load-Distribution}

Rather than use a uniform random distribution of residences commuting to
equal size employment centers scattered throughout the network, we could
introduce ramp distributions that would give us separate employment and
residence core sectors.  We'd expect this asymmetry to reflect current
city layouts, and reduce our vehicle utilization as empty vehicles must
backfill those departing from residential stations.

Furthermore, we could also make use of job codes and skill codes to
model different distributions of employee or employer types throughout a
population.  For example, if the skill codes were to correlate to
residents' socioeconomic status, we could set up a model to study the
impact of efforts to integrate rich and poor neighborhoods. %FIXME: \cite{}

\subsection{Temporal Load Distribution}
\label{sub:Temporal-Load-Distribution}

Passengers seldom appear at all source stations at exactly the same
time.  We could vary the shape of the demand input pulse to gradually
inject passengers into stations over time.

\subsection{Timeliness of Input Data}
\label{sub:Timeliness-of-Input-Data}

The amount of time in advance that a passenger submits a transit request
to the global optimizer could affect how well the system can have a
vehicle ready to pick that passenger up at their requested departure
time.  In the worst case scenario, the system does not find out about
the passenger until the last moment, when they enter the station and buy
a TransitToken to a specific destination.  The more advance notice the
global scheduler has, they better it can budget vehicles to reduce
passenger wait times.

\subsection{Multiple Vehicle Sizes}

The simulation and optimization formulation are capable of handling
multiple vehicle types, so it can provide solutions using a mixed fleet
of small and large vehicles.  The vehicles might even have different
connectivity matrices.  We'd need to adjust the factorial design
generation and simulation monitor taps to allow data collection on
multiple vehicle types so we can investigate what pairings of relative
vehicles sizes work well.



\section{Usability Enhancements}
These additional user interface features would aid debugging and assist
in further development.

\subsection{Simulation Visualization Tool}
We need a way to animate schedule results to help verify the simulation
visually.  Currently the only way to piece together passenger and
vehicle movements is to compare schedule spreadsheets at each time step
and to trace individual travel histories at the end of the simulation.

\subsection{Scenario Editor GUI}
In concert with developing an output visualization tool, we'd also want
a visual tool for manipulating input data.  We currently define
scenarios programmatically.

\subsection{LiveCD Packaging}
The build and execution environment for this project is moderately
involved with respect to software dependencies.  To this end, we could
create a bootable LiveCD based on KNOPPIX that could turn any compatible
PC into a full development and compute node \cite{knoppixremastering}.



\section{Feature Completion}
The core simulation engine and modeling language lacks some important
features that prevent this project from achieving nominal functionality
and modeling realism.  Implementing the following features would go a
long way towards applying this simulation to practical problems.


\subsection{Schedule Optimization State Initialization}
The simulation currently has limited support for initializing the state
of a schedule optimization.  As discussed in section
\ref{sub:Assumptions-and-Limitations}, we currently do not take the
trouble to initialize the current positions of vehicles or existing
passengers in the transit network.  Adding this internal transfer of
initial data constraints would allow us to update and re-optimize a
continuously evolving scenario, allowing us to achieve a rolling time
horizon type of schedule optimization.

Without this enhancement, we can only run one schedule optimization per
scenario with the assumption that the vehicles magically appear where
they need to start, and no new information can affect the execution of
the schedule once it begins to run.


\subsection{Monte Carlo Analysis}
We currently use a random seed to provide some entropy in our
simulations and create randomized distributions for some input
parameters.  This means that to properly conduct an analysis, we'd want
to run a scenario at least 20 times each with a varying random seed, and
perform statistical data reduction on the observed output metrics.

\subsection{Constraint Pooling}
\label{sub:Constraint-Pooling}

The system lacks a way to apply capacity constraints to groups of nodes
or links, indicating that they share the same physical resource. This
would allow multiple routes to share common bottlenecks.

\begin{figure}
\epsfxsize=6.0truein
\centerline{\epsfbox{figures/constraintpools.eps}}
\label{fig:Constraint-Pooling}
\caption{Constraint Pooling}
\end{figure}

Without the ability to apply a single constraint to a group of nodes,
each route linking pairs of nodes would either unintentionally add more
capacity between station nodes, or would not allow one route to make
full use of the unused capacity of other available routes sharing
passage through an intended bottleneck.


\subsection{Proper Handling of Long Distance Passengers}
\label{sub:Handling-of-Long-Distance-Passengers} 

The objective function is weighted such that the number of passengers
served (objective 1) takes priority over minimizing the number of
segments traveled by all vehicles (objective 4). In turn, objective 2
results in ``compression'' of the schedule to the left, in order to
complete the schedule as early as possible.  The compression is achieved
by rewarding the system for sending passengers to their destinations at
earlier times during the interval under consideration.

If optimization objectives 1 and 4 were of the same magnitude, we could
better balance the conflicting goals between serving passengers at
low-volume stations and keeping vehicles filled with paying passengers.
The fleet optimizer could possibly even refuse to provide service to
low-volume stations to increase total operating efficiency. However,
this may also cause high volume routes to become unprofitable for cases
where the cost of a long route exceeds the fixed reward for sending a
passenger to their destination.

To remedy this, we'd need a more sophisticated reward system that would
increase the fare value for long distance travelers.  This would involve
establishing another dimension to the set of passenger variables that
would help track their starting point in addition to their final
destination. However, this could easily increase the $O^{3n}$ complexity
of the optimization problem to $O^{4n}$. We could limit the impact of
this additional term by grouping starting nodes together, so we'd end up
with a zone-based pricing system.  This would reduce the number of
decision variables introduced into the MIP while still preserving the
effect of variable fares.

Since this project's optimization formulation does not implement a
zone-based fare system, the reward for objective 1 must always exceed
the possible cost minimized in objective 4, such that no passenger will
get ignored for being unprofitable. To ensure this condition holds true,
the passenger reward constant must always be greater than the cost of
running a vehicle the diameter of the network by a comfortable margin.

The next section (\ref{sub:Hierarchical-Optimization}) addresses a means
by which we could provide zone-based service.


\section{Scalability Enhancements}

Once we've fully defined the scope of the schedule optimizer, we can
begin looking for ways to improve its performance.  The following
measures will allow us to harness the power of parallel processing to
tackle larger problems in less time.

\subsection{Hierarchical Optimization}
\label{sub:Hierarchical-Optimization} 

The current scheduler has problems finding solutions for more than 8 to
10 station nodes.  One way to increase the scalability of our schedule
optimizer would involve breaking up the problem hierarchically into
smaller sets which we can solve in parallel. The structure of our
Arcology model already supports this kind of organization, so we would
only have to find a way to map the stations and segments of the transit
network into this hierarchy.

This scheme would work by grouping all of the stations into well
interconnected clusters of no more than a handful of stations each. We'd
need to choose an optimal cluster size that we could solve relatively
quickly.  E. Christian's HCPPT system employs a similar arrangement that
optimizes across hexagonal clusters of 7 regions.\cite{HCPPT} In our
scheme, each cluster of stations will again be grouped into hexagonal
super clusters. Splitting the problem space into this self-similar,
recursive hierarchy of cell clusters ensures that we apply TSP style
optimizations to no more than a handful of nodes at a time to keep
computational requirements within reason.

Optimization will start from the highest level first, and will determine
how many vehicles would need to be exchanged between regional clusters.
These regional fleet schedule numbers will feed down as boundary
conditions to the next lower level in the hierarchy. Now we can solve
each sub cluster in parallel, each of them reading the regional schedule
in as constraints for their own local schedule optimization. In turn,
these sub clusters would recursively split into smaller sub-sub clusters
until the schedules they produce finally route vehicles directly between
individual stations. This optimization scheme allows us to reduce the
computation time for a network of $n$ nodes from $O^{3n}$ to
$\frac{n}{m}*O^{3m}$, where the constant $m$ represents the cluster size
and $\frac{n}{m}$ is approximately the number of levels in the
hierarchy.  The cells at each level could be solved in parallel provided
enough CPU resources were made available.

The catch is that the higher level regional scheduling takes precedence
over local scheduling. On the bright side, this also nicely takes care
of the zoned transit problem discussed in the previous section
\ref{sub:Handling-of-Long-Distance-Passengers}. However, we must use
caution while rationing out station and vehicle capacity constraints so
the higher level schedules leave some capacity to serve local
passengers.

One possible self-similar recursive structure we could use to partition
large problems is a modified heptree.  Originally introduced by Bell in
1989 \cite{Bell1989}, it has several useful properties for our
purposes. First of all, the cluster size $m=7$ is near the maximum limit
of conveniently computable TSPs. The hexagonal form has also been chosen
for other mass transit optimization works, such as for local pick-up and
delivery in Cristi$\acute{a}$n Cort$\acute{e}$s' proposed HCPPT network
\cite{HCPPT}. Here, each vertex serves as a node. Each level of the
hierarchy has a slightly different radial orientation relative to its
immediate children, but this does not present a major problem for our
purposes (compared to others who have considered using this structure).
\cite{Kardos2005} We would overlay the entire structure top of a
triangular grid created with waypoints, the segments of the grid
representing possible transit network links.  The distinguishing feature
of our structure from conventional heptrees is the additional padding
space that we can place between clusters, as depicted by the white space
in figures \ref{fig:heptree}-b and \ref{fig:heptree}-c.

%
\begin{figure}
\caption{\label{fig:heptree}Recursive self-similar 2D space-filling Heptree Hierarchy}
Counter-clockwise from top left:
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item Cluster of 7 station nodes
\item 2 level hierarchy of 49 station nodes
\item 3 level hierarchy of 343 station nodes
\end{enumerate}
\includegraphics[scale=0.8]{figures/heptree_mod}
\end{figure}


This structure has some interesting properties that gives it some
flexibility.  First of all, not all nodes or sub clusters in the
hierarchy need be fully populated or connected, so we can remove
elements until we have a reasonable approximation of local conditions
due to geographical or other constraints imposed on development.

Furthermore, the padding between distance between clusters on the same
level of the hierarchy is configurable.  We have our clusters separated
by 1 segment, but this could be uniformly be increased to provide more
open space separating the clusters.  The padded area might make good
undeveloped area to turn into parks, easements, and greenways.  If all
transit links crossing these padding areas were constrained to bridges
or tunnels, pedestrians and migratory wildlife would have free passage
across the land via virtually unbroken natural woodlands.

Clusters might be connected to each other in some combination of two
different paradigms.  We might enforce hub-and-spoke connectivity, where
clusters are only joined by high capacity arterial lines (represented by
the bold lines in figure \ref{fig:heptree}) linking their central hub
nodes together.  Alternatively, clusters might also be joined by the
fine individual segments of the triangular mesh linking their adjacent
sub-clusters together.  Traffic could filter through that lattice in a
highly distributed fashion.

Whether the arborized or reticulated mode of connectivity dominates
likely depends on the scale.  Clusters at a neighborhood level would
likely follow the hub-and-spoke model, channeling all traffic to a
central mass transit station or a highway on-ramp, limiting through
traffic through more restricted access.  At a regional level, we'd want
a more fully connected lattice so we could travel directly toward our
destination without going out of our way to transfer at downtown hub
stations.  However, at the intraurban level, we'd again expect to see
more arborization again as we'd funnel our access through consolidated
airports or central high speed rail stations.



\subsection{Optimization Heuristics}
\label{sub:Optimization-Heuristics}
Finally, after we've ensured that we've achieved all of our desired
functionality, we can look into other ways of optimizing computational
time. Breaking the problem down into smaller, more manageable chunks
will give us our largest performance boost, but there are still other
ways we could trim decision variables out of consideration. By strategically
pruning MIP branches that provide little performance benefits in comparison
with the original algorithms, we could reduce the number of dead ends
that the optimization engine wastes time exploring. We would want
to continue to optimize the algorithms until the scheduler could complete
a replan for unexpected events in advance of the next time step. This
would allow the system to react to service disruptions as soon as
practicable.


\section{New Modeling Features}

\subsection{Holding Pattern Waypoints}
\label{sub:Holding-Pattern-Waypoints}
Waypoints currently exist to give vehicles and passengers a state
of existence while in transit in between stations. In order to prevent
passengers and vehicles from mixing while they are grouped in the
same waypoint bins, however, we must apply some additional constraints
to effectively prevent mid air passenger transfers between vehicles.
The constraints stipulate that all vehicles and passengers that enter
a waypoint during one time step must leave the waypoint the next. All
waypoints are constructed as parts of one-way routes, so there is
no possibility of capturing passengers en passant. This has the effect
of

To be fair, there have been proposals for improving transit efficiency
by docking moving vehicles together and transferring passengers en
route\cite{transferbogies}. So isn't it comforting to know that we
could model some of those scenarios by simply removing some of these
constraints.

However, sometimes we do want to allow vehicles to wait or enter {}``holding
patterns'' at waypoints while en route, so they can create a buffer
into another constrained resource, such as a runway or station. This
provides additional storage holding capacity outside of the station
which can be put to use to increase network capacity. Mostly these
buffers are used to help deal with uncertainty. Since our schedules
are fairly deterministic, unperturbed by mechanical failures or passengers
and vehicles turning up later than they're expected, we would gain
little by allowing vehicles to hold at waypoints. Each waypoint would
also require roughly twice as many decision variables to hold the
new possible states as vehicles decide to hold or proceed with their
passenger load. Due to these factors, waypoint holds have been skipped
at this time, but could add an additional useful modeling element
later.


\subsection{Continuous Time Model Definition}
\label{sub:Continuous-Time-Model-Definition}
Currently a model must be expressed in synchronous discrete time steps
in order to work with the optimization formulation. We'd find it quite
useful to define a modeling language that allows us to construct the
model with constraints and distances expressed in terms of continuous
time. Rather than having to manually convert a physical model to fit
into the discrete time step paradigm, we could then use algorithms
to convert the continuous model into a discrete time step model. This
would likely introduce a lot of rounding and aliasing artifacts, the
effects of which must be quantified and tracked. However, we'd gain
the ability to run the same model at varying levels of detail in the
time step, that would allow us to study and set an optimal time step
length that keeps these errors in check.

A continuous time modeling language would allow us to define constraints
in more familiar fractional units, such as vehicles per unit time.
The main benefit is that we could now parametrically adjust the resolution
of time steps, so detailed models could run with fine grained time steps
over an interval of interest, while coarse models could be solved
much faster. Similarly, the constraint values also must scale with
shorter or longer time periods of action, such that twice the capacity
could pass through a constraint point in twice the time.

This flexibility would greatly help address some of the issues introduced
by the synchronous time step paradigm by allowing us to analyze the
same scenario with different timing parameters and observe and minimize
the aliasing artifacts. This would help couple together the optimization
of global transit networks with different paces of operation. Best
of all, this language might allow us to more easily link together
schedules of transit systems to operate on different time intervals,
such that high frequency rail transit could serve low frequency but
higher capacity airplanes or ships at port.


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

The final category of optimization constraints would come from the
operators of the various transit networks.  A global optimizer that
could include multiple independent operator goals and scheduling
constraints certainly isn't out of the realm of possibility.  A central
authority would maintain the global schedule formulation, and might
allow participating members to add their own sets of constraint
statements, or even weighted objective functions.  This would allow
individual fleet operators to cooperate with other fleets, while adding
crew and maintenance schedules that would allow them can pick up and
drop off drivers, pilots, and other staff at certain locations, or make
sure that their vehicles end up in a certain maintenance bays every so
often for refueling and service.

These types of constraints are typically easy to add, 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 translate into both old and 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 compared to a system
in which the global scheduler could directly search for solutions that
also fulfilled operator schedule requirements, but at least they would
start closer to an optimal solution. The iterations could proceed as
follows:

\begin{enumerate}
 \item The transit network operator provides 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 schedule somewhat near the optimal one
that takes maintenance factors into account without tying down the
program formulation to a particular implementation of the optimizer.

We'd still need to exercise some discipline to keep the system
stable. In a fleet run by one lone operator, the entire problem
formulated by one party, and all the input data provided by passengers
and schedules only add constraints in a consistent manner -- the worst
outcome some faulty data could possibly cause 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 pitfalls 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.  However, the latter
      approach could just as well create unpredictable results by
      orphaning some unbounded variables.

\item We'd need ownership and permissions on variables to separate the
      MIP components provided by different parties. This would ensure
      that operators don't introduce constraints that could penalize
      their competitors.  This could be accomplished by prefixing
      variable names with namespaces and restricting access to allowed
      or ``safe'' variables.

\item Many companies pride themselves on their own optimization
      capabilities.  We may need a mechanism to protect proprietary
      information about their business strategies revealed in operator's
      contributed code.  We might allow them to submit ``black box''
      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 particular segment of the global calculation, interacting
      with the rest of the system through a layer of input and output
      variables.
\end{itemize}

Hopefully these considerations have helped articulate the current
incarnation of this thesis does not address these issues.


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

Uncertainty is the antithesis to careful planning ahead, but we live in
an uncertain world. How will the system deal with unexpected events that
crop up during the execution of schedules?  While this thesis project
makes no allowance for the possibility of its virtual vehicles getting
help up by hail or high water, in a practical system, probability should
be built in to the optimization problem formulation.  One of the
additional 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 rather than
early. It's much easier to suffer a break down and end up 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 longer, more 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 should 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 ``magic
percentile'' that would determine how much extra buffer time to schedule
to make sure everyone makes their connections. This tolerance will
likely get set arbitrarily at the beginning, as all of these factors
contribute to an overall ``schedule volatility'' metric.  With the
optimizer system, we can recompute new schedules whenever an unexpected
event occurs -- such as when a vehicle is delayed enough to fall onto
the tail end of the CDF and its passengers wind up missing their
connections.  The optimizer can take that emerging information into
account and simply create a new schedule based on these new conditions
-- in this case it would likely divert other vehicles to pick up the
stragglers stranded by the late vehicle.  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 worth holding flights to allow latecomers to make their
connections.

In light of this, we want to introduce some practical optimization goals
to the list of transit system performance goals discussed in section
\ref{sub:Performance-Metrics}.  This performance metric would
characterize the system's stability in the face of unexpected
breakdowns and delays, meaning it would help the scheduler
intelligently create and maintain buffers to deal with uncertainty.  How
to actually formulate and compute this enhancement is beyond the scope
of this thesis.  The optimizer would likely need to do risk-impact
assessments on every combination of missed connection.  But we do wish
to ensure that the necessary on-time performance data is collected now,
so that future generations of engineers could tackle this issue.



% LocalWords:  Ghz AMD CPLEX LP GUI programmatically LiveCD bootable KNOPPIX en
% LocalWords:  truein MIP TSP heptree TSPs Cristi Cort HCPPT heptrees greenways
% LocalWords:  arborized intraurban arborization replan waypoint passant CDF
% LocalWords:  infeasibility namespaces sec FIXME TransitToken
