\chapter{Multimodal Mass Transit Simulation}

\section{Overview}

This programming project serves to realize an urban multi-modal transit
simulation designed during the course of the systems engineering master's
program. The program will take a systems approach to modeling human
habitats and the transportation networks that keep them running. We
would use such a simulation framework to create a baseline model of
current day capacity, and then create future models to compare the
effects and quantify the benefits of investments in future infrastructure.
These kinds of tools would be instrumental in making a case for the
development and construction of highly efficient arcologies or other
forms of well-integrated compact cities. But nominally, we could apply
it towards evaluating and tracking the effectiveness of present-day
city growth philosophies.

\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}
The SimPy discrete event simulation framework in the Python scripting
language forms the core of the system model. Including the Psyco Python
runtime optimizer helps certain routines run closer to native speed
and gives the model a 1-2 order of magnitude increase in computation
speed. The LP\_Solve package performs schedule optimization tasks
and feeds the results back to the simulation for execution.


\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 or canal.

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}

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.

\begin{figure}[htp]
\epsfxsize=4.5truein
\centerline{\epsfbox{figures/CommuteSim.eps}}
\caption{Neighborhood Class Structure}
\label{fig:iNeighborhood-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 jobcode (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 skillcodes. 

This skillcode-jobcode 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 workschedule paradigm allows
us to adjust the demand on the network to create or reduce peak congestion.


\subsection{Transit Network}

The transit network operates within the same cell hierarchy 


\subsubsection{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.


\subsubsection{Waypoints }

Waypoints are typically one-way nodes in the transit network that
allow the system to preserve state of vehicles and passengers 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 have any meaningful parents, since theirs not
much reason to interact with them. They are typically attached to
the master city cell since they would typically exist between neighborhoods.

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

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}

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}

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}

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}

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}

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.

