\chapter{Multimodal Mass Transit Simulation}

This chapter describes specific details of the schedule optimization problem formulation
and modeling components used in the simulation of commuters traveling from their
residences to their places of employment.
Commuting makes a good starting scenario,
since it accounts for a large proportion of the trips 
handled by present-day mass transit systems.
Furthermore, the commute simulation may easily be adapted
into other types of scenarios for analysis
such as shopping errands or stadium events.

\section{Framework Capabilities}

\vspace{0.1truein}\noindent 
The primary features that this optimization framework sought to achieve include:

\begin{itemize}
\item Demand-responsive routing rather than operation on a fixed
       schedule. This is necessary for us to worry less about generating
       transit designs around peak demand levels that do not function as
       efficiently with nominal demand levels. We also hope that the
       system would utilize command and control networks that take
       advantage of available communications infrastructure to book
       requests and guide passengers through the system.
\item Allow optimal transfer strategies to emerge. At different loading
       levels, the system vehicles may organize themselves like ``hub \&
       spoke'' / ``feeder \& trunk'' networks for efficiency, or begin
       to resemble more direct point-to-point routing during lighter
       loading or when existing hubs become constrained.
\item Multi-objective goal functions, including terms for maximizing
       service quality such as:
       \begin{enumerate}
	\item high throughput
	\item low average latency from sources to destinations
	\item efficiency terms that would minimize general operating
	      costs associated with the number of vehicles operating in
	      the fleet and the number of segments they would have to
	      travel
       \end{enumerate}
\end{itemize}

\section{Concept Requirements}

This section describes the pathway from high-level goals to specific
use-cases for the transit system, the mass transit optimization goals,
fleet schedule optimization objectives, and transit use cases.

\subsection{Mass Transit Optimization Goals}

This simulation constructs a simple transit network with passengers
traveling from source nodes to destination nodes. The scheduler attempts
to provide an optimal or quasi-optimal schedule of transit fleet vehicles
with various capacities, operating costs, and nodes serviced that
will transfer the passengers to their final destination. Through parametric
analysis of different demand loading and network topologies, we hope
to define some characteristics of urban areas that enable the system
to meet the opposing passenger demand and vehicle utilization objectives efficiently.

\subsection{Fleet Schedule Optimization Objectives}

The objective function of the transit vehicle schedule optimization is a
weighted composite of the number of passengers served, the time they are
delivered, and a flat cost incurred per vehicle leg traveled. The weight
on each objective typically puts them on different orders of magnitude,
such that a secondary objective should not be considered a factor until
the primary objective reaches an optimal configuration.

\vspace{0.1truein}\noindent
The relative weighting of objectives is arranged as follows:

\centerline{ $Objective\;1\gg Objective\;2\gg Objective\;3\gg
Objective\;4$ }

\begin{description}

 \item{\emph{Objective 1}:} Maximize the number of passengers delivered
	    to their final destinations. All passengers are currently
	    weighted equally, which means during instances where the
	    system is operating beyond capacity, the optimizer will
	    favor passengers who are close to their destinations. There
	    is currently no zone tracking to ensure that passengers
	    traveling long distances can {}``pay more'' to compensate
	    for the higher transit cost. The objective function also
	    provides no reward for moving passengers partway, so a
	    feasible solution will either move a passenger all the way
	    to their destination node or not at all.

 \item{\emph{Objective 2}:} Minimize the amount of time the passengers
	    spend in the transit system. This is accomplished by adding
	    a linear bonus term to the objective function that rewards
	    the system for delivering passengers to their destinations
	    at earlier times. These terms push the schedule ``left''
	    towards earlier arrival times.  Otherwise the system would
	    allow people to wait unnecessarily during the time window
	    under consideration.

 \item{\emph{Objective 3}:} An optional objective to minimize deviation
	    from a desired fleet size can be activated. We could simply
	    minimize the number of vehicles in use, but we'd have to
	    find some way to balance this with the passenger service
	    objectives. Plus, most service operators have a fixed number
	    of vehicles and drivers to employ. The optimizer could take
	    advantage of extra vehicles to improve passenger service
	    quality, as well as make recommendations at to when the
	    operator might want to rent additional vehicles and drivers
	    temporarily to meet demand.

 \item{\emph{Objective 4}:} Minimize the operating cost of moving
	    vehicles. This is currently expressed by a simple flat cost
	    incurred by each segment a vehicle travels. Each size
	    vehicle could have a different cost per segment traversed,
	    such that a vehicle with a higher capacity would presumably
	    have a greater cost per time unit.  Currently the system
	    deducts no cost for vehicles idling at stations, but we
	    could insert this term easily enough if called for.
\end{description}

\vspace{0.1truein}\noindent
The objective function is subject to the following constraints:

\begin{description}
 \item{\bf Conservation of passengers and vehicles} moving between
	    nodes. Passengers and vehicles should be neither created or
	    destroyed during the course of the schedule.  The MIP
	    schedule optimization follows a classic inventory management
	    problem formulation.
 \item{\bf Passenger movement} between nodes is constrained by the
	    capacity provided by vehicle movements between
	    nodes. Passengers can only move around in the network when
	    carried by vehicles. The optimization problem currently
	    allows passengers to wait and transfer freely between
	    vehicles at station nodes.
 \item{\bf Vehicle movement} about the transit network is constrained by
	    several factors:

       \begin{itemize}
	\item Connectivity matrices allow certain types of vehicles to
	      travel only between connected nodes. This allows us to
	      connect nodes together with one or more modes of transit.
	      For example, a certain subset of nodes could be served by
	      a rail system, while the rest of the nodes would only be
	      accessible via bus service. The connectivity matrix
	      provides enough flexibility to model a transit system as a
	      collection of directed graphs, so stations could be
	      connected by one way or bi-directional links.
	\item Station and waypoint capacity constraints could prevent
	      too many vehicles from visiting the same station or route
	      simultaneously.
	\item A hard maximum fleet size might prevent some unrealistic
	      solutions.
       \end{itemize}
\end{description}

We could add some arbitrary constraints somewhat easily.  For instance,
we could limit the maximum number of vehicles on a group of segments or
waypoints that have been grouped together to represent a constrained
resource, such a bottle-necked intersection.  This concept is discussed
in more detail in Section \ref{sub:Constraint-Pooling}.

This optimization make no attempt to handle meeting passenger required
times of arrival (RTA).  It only optimizes based on the reported time
passengers first become available to depart. Oftentimes people would
want to arrive at their destination just before the fixed start of their
work day, or at an airport in time to catch a flight. Because this
optimizer uses an inventory management approach, adding this information
would result in an exponential increase in decision variables. This
added complexity would make the schedule take much longer to
generate. Combined with the fact that several of the passengers would
not even make use of this functionality (such as the ones who are
\emph{leaving} work and just want to get to their destination as soon as
possible), the schedule optimizer declines to consider this constraint.

To add an RTA handling feature, an algorithm external to this schedule
optimizer would need to provide a rough estimate of the required time of
departure (RTD) necessary to meet a passenger's RTA, and submit a
transit request with that RTD into the optimization. If the itinerary
provided back to the passenger falls behind (or too far ahead) of their
desired arrival time, the algorithm could redact the transit request and
try again with a slightly adjusted RTD. A few cycles of this incremental
optimization on a much simpler schedule optimizer for the subset of
passengers who actually need it should provide an acceptable solution
more quickly than if the scheduling problem was reformulated to include
variables and objectives to take everyone's RTAs into account.

\subsection{Transit Use Case Diagram}

A passenger begins by submitting a transit request for sometime in the
future to the global scheduler. The scheduler collects requests and
generates an optimized vehicle schedule that separates passengers into
several pools based on their current and final destination node.  When
the time comes to act upon the schedule, a station master at each
station loads waiting passengers into the proper vehicle, and then sends
the vehicles on their way towards their next destination. When the
passenger reaches their final destination, they exit the transit
system.

\begin{figure}[htp]
\epsfxsize=4.5truein
\centerline{\epsfbox{figures/uc_transit.eps}}
\caption{Transit use case diagram}
\label{fig:Transit-use-case-diagram}
\end{figure}

For simplicity, this simulation unboards all passengers at each station
so the station master can re-sort them into their next/final destination
pools. Another logistics layer could be implemented to provide the
convenience of maximizing the number of passengers that could stay
aboard their vehicles during stops at transfer stations.


\section{Mass Transit System Structure}

The model is arranged in a hierarchy allowing the partitioning and
relocation of units at different levels of the structure as described in
section \ref{sub:GeneralClasses}.  This allows us to use flexible
recursive algorithms to facilitate a lot of searching and reporting
tasks.  For example, we recursively walk the tree to produce the
incremental state snapshots of the system hierarchy in graphML format
for viewing in yFiles's yEd application.

\subsection{Generic Cell Class}

All simulation entities inherit from the Cell class, which provides a
sub cell container for any children classes. The cell class stores a
handle to its own parent cell as well, so algorithms may traverse the
tree in either direction. Subroutines allow child cells to move about
the tree, updating associations so cells never have more than one
parent.  Each cell also has a className to distinguish between different
types of children.  They also inherit filtering functions that can
search for and return a list of child cells meeting certain criteria.

\begin{figure}[p]
\epsfxsize=4.5truein
\centerline{\epsfbox{figures/cell-class-diagram.eps}}
\caption{Cell Class Diagram}
\label{fig:Cell-Class-Diagram}
\end{figure}

\subsection{Neighborhood Nodes}
\label{sub:Neighborhood-Nodes}

All of the elements in the model are comprised of various incarnations
of the generic cell class. A master city cell forms the root of the tree
hierarchy and contains several neighborhood node cells representing
clusters of employers and residences that share a transit station. This
hierarchy represents a realization of the general class template
described in Figure \ref{fig:cd-general}.  Each neighborhood can contain
any number of employers or residences that share the same transit
station in a pattern reminiscent of J.H Crawford's reference
districts. \cite{carfreecities}


\begin{figure}[htp]
\epsfxsize=4.5truein
\centerline{\epsfbox{figures/CommuteSim.eps}}
\caption{Neighborhood Class Structure}
\label{fig:Neighborhood-Class-Structure}
\end{figure}


An employer would have a number of job vacancies associated with a
particular job code (representing the particular skill required of a
worker) and additionally a work schedule that would dictate the
employee's commute schedule. Assuming that each vacancy could draw a
qualified employee into the metropolitan area, an individual would be
instantiated to fill that job vacancy and proceed to look for a
residence somewhere in the city.

Since we're not interested in modeling real estate trends, the
individual simply creates a new residence cell in any neighborhood of
the city. Currently we use a simple uniform random distribution to
allocate residences, but we could use different distributions to study
other urban design factors, as suggested in Section
\ref{sub:Spatial-Load-Distribution}.

This job code and skill code accounting allows us to model the impact of
specialized job centers and mixed populations in the urban area caused
by development initiatives and zoning policies.  The work schedules
allow us to control and adjust the demand on the transit network in
order to create loads and investigate peak congestion effects.

\subsection{Transit Network}
\label{sub:Transit-Network}

The transit network operates within the same cell hierarchy as the rest
of the model. However, it behaves somewhat independently, serving to
pick up passenger cells at {\bf station} nodes and transport them to
other station nodes through one or more layers of {\bf vehicle} containers.

\begin{figure}[t]
\epsfxsize=4.0truein
\centerline{\epsfbox{figures/StationConceptualModel.eps}}
\caption{Station Conceptual Model}
\label{fig:Station-Conceptual-Model}
\end{figure}

\subsubsection{Stations}
\label{sub:Stations}

Each neighborhood contains one station cell that corresponds to a
node in the transit network.
As illustrated in Fiture \ref{fig:Station-Conceptual-Model},
all passengers transferring through a station
are sorted into PassengerPool containers, one for each other
station node in the network. While every passenger in a PassengerPool
has the same final destination, they might take separate vehicles
or even entirely different paths to get there. 
Additionally stations have a fixed number of vehicle berths that serve
to constrain the maximum number of vehicles that can dock simultaneously.
Figure \ref{fig:Station-Conceptual-Model} depicts a conceptual model of
what a station node might look like for the purposes of our scenarios.

\subsubsection{Waypoints}
\label{sub:Waypoints}

Waypoints are sets of coordinates that identify a point in physical space.
To make the modeling language a little more realistic, we added
``non-station'' waypoint between stations. Waypoints allow for
the modeling of systems where stations separated by varying distances
(albeit in terms of integer units of time).  Waypoints also allow
passengers and vehicles to have a defined state while en route between
stations while only moderately increasing the number of variables added
to the optimization problem.

In the context of this project, waypoints act as one-way nodes in the
transit network that allow the system to preserve the state of vehicles
and passengers while traveling in-between stations. There are no
constraints that prevent passengers from transferring between vehicles
at the same waypoint, so to prevent passengers from train-hopping or
plane-hopping en route, we apply an additional constraint that all the
passengers and vehicles that enter a waypoint at one timestep must leave
it the next timestep.

For some models, we might desire this kind of behavior.  We could
eliminate these waypoint constraints and allow vehicles to effectively
enter a holding pattern at a waypoint just outside of a station.  And
there have been studies and patents filed to allow vehicles to transfer
passengers at speed.
%FIXME \cite{}
In the future we may want to ease those constraints somewhat to allow
these other types of behaviors.

Waypoints don't really belong to any parent cell in any meaningful way,
since they are an artifact of the separate transportation infrastructure
overlay as depicted in Figure \ref{fig:cd-general}.  Other entities in
the simulation have little reason to interact with them. We typically
attach all waypoints directly to the master city cell since they would
typically exist between neighborhoods.

We use waypoints to serve two purposes.  While they are primarily used
to represent the time and space traversed by vehicles between stations,
they can also represent only the time spent waiting at a station.  In
this mode, they would account for time spent slowing down and docking at
a station berth, loading and unloading passengers, and -- to some extent
-- the walking time of passengers between platforms or gates while
transferring within the station.

All of the scenarios in this work employ at least one waypoint between
stations in order to provide a time savings advantage to a vehicle
bypassing a station.  We use this measure to study the possible
performance benefits of having offline stations, which is a feature
necessary for rail service with express routing or almost any PRT-like
transit proposal.

\subsubsection{Vehicles}
\label{sub:Vehicles}

The vehicles in the various transit fleets traverse the network picking
up passengers from stations and dropping them off at the next station.
A completely separate transit layer represents each type of vehicle,
with their own connectivity matrix that defines the segments and
waypoints that each set of vehicles can traverse.  The schedule
optimizer only cares about two properties for each vehicle type: the
maximum passenger capacity and the cost per segment traversed.


\subsubsection{TransitTokens}
\label{sub:TransitTokens}

The station master issues TransitTokens to identify passengers and cargo
within the transit system, using them to store a customer's final
destination. TransitTokens provide a handle used to sort passengers at
each transfer station. Additionally, they log the path taken and
timestamps for each passenger, so they come in handy for collecting data
on transit times and wait times during post processing analysis.

\begin{figure}[t]
\epsfxsize=6.0truein
\centerline{\epsfbox{figures/ad_TransitSim.eps}}
\caption{Transit Simulation Activity Diagram}
\label{fig:Transit-sim-activity-diagram}
\end{figure}

\section{Mass Transit System Behavior}
\label{sub:Mass-Transit-System-Behavior}

Behavior of individuals travelling on the mass transit
system is defined by the sequence of activities shown
in Figure \ref{fig:Transit-sim-activity-diagram}.
The four parties (or actors) that participate in 
transit behavior are: passenger, station manager,
vehicle, and scheduler. Swimlanes show their
roles and responsibilities in enabling behavior.

The simulation is based on a discrete event simulation engine.
This means that state changes in the system structure are
triggered by the firing of events which occur
along the global time line queue.
The simulation engine runs a model by populating the global time queue with
scheduled events and executing instructions triggered by events in order.
The system global time advances to the time of the last event,
and any state transitions triggered by that event are executed so they
can perform their operations, sometimes scheduling additional events in
the future event queue.
Thus, the simulation perpetuates events and
continues in time until the program reaches a time limit or there are no
more events left on the simulation queue.

This transit simulation consists of a conglomeration of relatively
simple entities working together. We'll introduce them roughly in order
of increasing complexity.

\subsection{Individual}
\label{sub:Individual}

The simulated people entities exist purely to create demand on the
transit system. In the current simple commuting scenario, they simply
live in a residence at one node and work at an employer at a possibly
different node. They will enter the transit system based on their work
schedule. Some configurable time in advance of their travel, they will
submit a TransitRequest to the global transit scheduler system. By
having advance knowledge of when the passenger needs to travel, the
fleet schedule optimizer can ostensibly do a better job reducing
passenger waiting time.

They enter the transit system by traveling to their local Station and
procuring a TransitToken programmed with their final destination.  From
there on, they are shuffled around by the other entities of the transit
system until they reach their destination station. Once they arrive at
their final stop, they are placed into the appropriate employer cell in
that neighborhood.

\subsection{Vehicle}
\label{sub:Vehicle}

Vehicles of the same type are considered completely interchangeable, so
the only state information of any importance for them is their capacity
and their next immediate destination node (either a station or a
waypoint).  Vehicles simply wait to receive a transitEvent and then pick
up as many people as they can from the station's PassengerPools before
leaving for their next destination.

When vehicles arrive at a station, they will dock in an available berth
and immediately empty out all of their passengers into the station for
sorting back into PassengerPools.

\subsection{StationMaster}
\label{sub:StationMaster}

Each station has a StationMaster process that reads the global fleet
schedule distributed with each transferEvent and organizes all
passengers and vehicles. It first sorts all passengers into
PassengerPool queues and all vehicles into rosters grouped by their
final and next destinations, respectively.  After a brief period of time
allowing passengers to make their connections onto the next vehicle, the
firing of the transitEvent signals that all transfers have completed and
the vehicles disembark to their next destination.

\subsection{GlobalScheduler}
\label{sub:GlobalScheduler}

The global scheduler receives incoming passenger requests, occasionally
triggering the generation of a new optimized schedule. Then it gradually
advances the global clock until the time comes to serve the first
passengers arriving at the station. The global scheduler begins firing a
succession of transferEvents and transitEvents at regular intervals to
synchronously push the Vehicles and StationMasters through their state actions.

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

The schedule generation MIP is formulated using the following sets of
variables to track the inventory and movement of passengers and
vehicles:

\begin{description}
 \item [$pp_{tik}$ :] pool of passengers at node $i$ at time $t$ whose
	     final destination is node $k$
 \item [$ppi_{tik}$ :] pool of new passengers initialized at
	    node $i$ at time $t$ with destination node $k$
 \item [$p_{tijk}$ :] passengers from node $i$ going to node $j$ at time
	    $t$ with final destination $k$
 \item [$ap_{tsi}$ :] pool of vehicles of type $s$ at node $i$ at
 	    time $t$
 \item [$f_{tsij} \in$ integers :] vehicles of type $s$ from node $i$ going to
	    node $j$ at time $t$
\end{description}

All variables are integers, but only the vehicle movement variables must
explicitly be declared as integer.


% LocalWords:  PassengerPool en timestep TransitTokens timestamps sim FIXME bi
% LocalWords:  TransitRequest TransitToken transitEvent StationMaster waypoint
% LocalWords:  transferEvent GlobalScheduler transferEvents transitEvents RTA
% LocalWords:  StationMasters RTD truein graphML yFiles's yGraph className PRT
% LocalWords:  themself offline MIP RTAs unboards yEd PassengerPools
