\chapter{Multi-modal Mass Transit Simulation}

This chapter describes the specific schedule optimization problem
formulation and modeling components used to create a simulation of
several commuters traveling from their residences to their places of
employment.


\subsection{Framework Capabilities}

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 make
      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 loads
      or when existing hubs become constrained.
\item Multi-objective goal functions, including terms for maximizing
      service quality such as low average latency from sources to
      destinations, high throughput, and 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{itemize}


\section{Concept Requirements}


\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. The
weight on each objective typically puts them on different orders of
magnitude, such that a secondary objective will not be considered
until the primary objective reaches an optimal point.

Relative weighting of $Objective\;1\gg Objective\;2\gg Objective\;3\gg Objective\;4$

\textbf{Objectives:}

\begin{enumerate}
\item 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
      particular solution will either move a passenger all the way to
      their destination node or not at all. 
\item 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 towards earlier towards the left, otherwise the
      system would not have any incentive to allow people to wait
      unnecessarily throughout the entire time window under consideration.
\item 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 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 no cost is
      deducted for vehicles simply idling at stations or for prepping a
      vehicle entering service, but we could insert those terms easily
      enough for further studies.
\end{enumerate}
\textbf{Subject to the following constraints:}

\begin{itemize}
\item Conservation of passengers and vehicles moving between
      nodes. Passengers and vehicles should be neither created or
      destroyed during the course of the schedule. 
\item Passenger movement between nodes constrained by the capacity
      provided by vehicle movements between nodes. Passengers can only
      move in the network when carried by vehicles. The optimization
      problem currently allows passengers to wait and transfer freely
      between vehicles at station nodes.
\item The transit system constrains vehicle movement by many factors: 

\begin{itemize}
\item A connectivity matrix allows vehicles of a certain type to only
      travel between connected nodes. This allows us to model different
      modes of transit that are only available from certain nodes. 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
      nodes 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{itemize}

We could add some arbitrary constraints somewhat easily. These could
include a maximum number of vehicles on a group of segments or waypoints
that have been grouped together to represent a constrained resource,
such a bottlenecked intersection.

One notable constraint that this optimization does not attempt to
handle is a required time of arrival (RTA) for passengers, it only
optimizes based on the time people specify that they are 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 would add a lot of complexity to the problem
and make it take much longer to solve. Combined with the fact that
many of the passengers wouldn't have need of this functionality (such
as the ones who are leaving work or the airport and just want to get
to their destination as soon as possible), the schedule optimizer
declines to consider this constraint. 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 to the passenger falls behind their RTA or even significantly
ahead (making them wait too long at their destination), the algorithm
could redact the transit request and try again with a slightly different
RTA. 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.

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

\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 to execute the schedule comes around, a station master
at each station loads passengers from each bucket into its pool of
available vehicles, and then assigns the vehicles to travel to their
next destination node. When the passenger reaches their final destination,
they depart the transit system.

For simplicity, all passengers deplane at each station so they can
be sorted 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
transfers.


\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. This allows
us to use flexible recursive algorithms to facilitate a lot of searching
and reporting tasks, including incremental exports of state snapshots
of the system hierarchy in graphML format for viewing in yFiles's
yGraph application.


\subsection{General Cell Class}

All simulation entities inherit from the Cell class, which provides a
subcell 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 as well as filtering functions that can search for and
return subcells 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}

The rest of the elements in the model are comprised of various
incarnations of the general 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}.

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

Each neighborhood can contain any number of employers or residences.

An employer would have a number of job vacancies associated with a
particular job code (indicating the skill required by an employee)
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 attach themself
to fill that job vacancy, and proceed to look for a residence elsewhere
in the city.

Since we're not interested in modeling real estate trends, we simply
have the individual create a new residence cell in any neighborhood
in the city. Currently we use a simple uniform random distribution
to allocate residences, but we could add additional factors to study
by using different distributions, \emph{e.g.} perhaps tied to the
individual's socioeconomic status relative to their available set
of skill codes. 

This skill code and job code accounting allows us to model the distribution
of diversity in the urban area relative to zoning policies in relation
to their impact on transit demand. The work schedule paradigm allows
us to adjust the demand on the network to create or reduce peak congestion.


\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 station nodes and transport them to other
station nodes through one or more layers of vehicle containers.


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

Each neighborhood contains one station cell that corresponds to a
node in the transit network. 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.

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


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

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 to vehicles at the
same waypoint, so to prevent passengers from train-hopping or
plane-hopping en route, we apply and 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, however, which might allow us to delay vehicles en route or
put them in congestion or holding patterns outside of a station. In the
future we may want to ease those constraints somewhat to allow these
other types of behaviors.

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

Waypoints serve a dual purpose.  While they are primarily used to
represent the time and space traversed by vehicles between stations,
they can also represent only 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 employs 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 necessary for rail
service that includes express routes or most PRT-like transit proposals.

\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.
Each vehicle type is represented as a completely separate transit
layer, each with its own connectivity matrix that details the segments
and waypoints that type of vehicle can traverse. Each type of vehicles
has only two properties of importance to the schedule optimizer: a
maximum passenger capacity and a cost per segment traversed.


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

TransitTokens are used to identify passengers and cargo within the
transit system, storing information on their final destination. This
is used to sort them at each through station. Additionally, they log
the path taken and timestamps for each passenger, so they come in
handy for collecting transit times and wait times during post processing
analysis.


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

The simulation model 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 model executes by populating the global time queue with scheduled
events and firing those 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 stops 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.

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


\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
or residence cell in that neighborhood.


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

Vehicles of the same type are basically interchangeable, so the only
state information of any importance for them is their capacity and
their immediate destination node (either a station or a waypoint).
Vehicles simply wait to receive a transitEvent and then they pick
up as many people as they can from the station's PassengerPool and
all leave for the next destination, which they'll arrive in a predetermined
amount of time.

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


\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 each grouped by a common next destination.
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. Then the global scheduler fires
a succession of transferEvents and transitEvents at regular intervals
to synchronously push the Vehicles and StationMasters through their
state actions.


% LocalWords:  PassengerPool en timestep TransitTokens timestamps sim
% LocalWords:  TransitRequest TransitToken transitEvent StationMaster
% LocalWords:  transferEvent GlobalScheduler transferEvents transitEvents
% LocalWords:  StationMasters
