\documentclass[twoside]{book}

\usepackage{graphicx}

\input ICCSsty.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\yy#1{{\bf[[#1]]}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\titletext{TRANSIMS for transportation planning}

%\shtitle{short title}
\title{\titletext}
\author{%
%
Kai Nagel\affil{Los Alamos National Laboratory and Santa Fe Institute,
kai@santafe.edu}
%
~\\
%
Richard L.\ Beckman\affil{Los Alamos National Laboratory, rjb@lanl.gov}
%
~\\
%
Christopher L.\ Barrett\affil{Los Alamos National Laboratory, barrett@tsasa.lanl.gov}
%
%
}
\date{\today}
\abstract{%
%
  The TRANSIMS (TRansportation ANalysis and SIMulation System) project
  at Los Alamos National Laboratory attempts to model all aspects of
  human behavior related to transportation in one consistent
  simulation framework.  The key to the TRANSIMS design is a radically
  microscopic simulation of the travelers.  In consequence, as the
  first step, a synthetic population is created from demographic data.
  Next, another module of TRANSIMS generates synthetic activities
  (such as sleeping, eating, working, shopping, etc.) and activity
  locations for each synthetic individual.  Each individual in the
  simulation then plans her transportation, making modal and routing
  choices.  Finally, the plans of each individual are executed in a
  detailed transportation micro-simulation.  Relaxation iterations are
  necessary to achieve consistence between the modules.  Since this
  means running all modules, especially the micro-simulation, many
  times, this makes the already considerable computational challenges
  even harder.  Results from micro-simulation runs can be used to
  extract data, for example for stake-holder analysis or for emissions
  calculations.  In this way, different transportation alternatives
  can be compared in detail.\footnote{To appear in: Proceedings of the
    ``International Conference on Complex Systems, Nashua, NH, 1999''}
%
}



\begin{document}
%%  %%%%%%%%%%%%%%%%% LA-UR page begin %%%%%%%%%%%%%%%%%%%%%%
%%  {\pagestyle{empty}
%%  %\hsize8.5in \advance\hsize by-1.8in
%%  %\advance\hoffset by-1in
%%  %
%%  %\vsize11in  \advance\vsize by-2in
%%  %
%%  %
%%  %
%%  \noindent {\sf Los Alamos Unclassified Report LA-UR 98-5628
%%  (This version: \today)}
%%  
%%  \smallskip
%%  
%%  \noindent {\sf Approved for public release; distribution is unlimited}
%%  
%%  \vfill
%%  
%%  \begin{center}
%%  
%%  {\huge\sf\baselineskip1.0em\titletext\par}
%%  
%%  \vfill
%%  
%%  
%%  
%%  {\large\sf Kai Nagel, Richard J.\ Beckman, and Christopher L.\ Barrett}
%%  
%%  \vfill
%%  
%%  {\large\sf\baselineskip1.5em
%%  To appear in: Proceedings of the International Conference on Complex
%%  Systems, New England Complex Systems Institute (NESCI), Boston, MA\par}
%%  
%%  \vfill
%%  
%%  \centerline{%
%%  \includegraphics
%%  [width=5in]
%%  {transims-bubbles.eps}
%%  }
%%  
%%  \end{center}
%%  
%%  \vfill
%%  
%%  \noindent {\huge\sf LOS ALAMOS}
%%  
%%  \noindent {\sf NATIONAL~LABORATORY}
%%  
%%  \baselineskip1.0em
%%  
%%  \noindent {\footnotesize\sf 
%%  Los Alamos National Laboratory, an affirmative action/equal
%%  opportunity employer, is operated by the University of California for
%%  the U.S. Department of Energy under contract W-7405-ENG-36.  By
%%  acceptance of this article, the publisher recognizes that the U.S.\
%%  Government retains a non-exclusive, royalty-free license to publish or
%%  reproduce the published form of this contribution, or to allow others
%%  to do so, for U.S.\ Government purposes.  Los Alamos National
%%  Laboratory requests that the publisher identify this article as work
%%  performed under the auspices of the U.S. Department of Energy.  The
%%  Los Alamos National Laboratory strongly supports academic freedom and
%%  a researcher's right to publish; as an institution, however, the
%%  Laboratory does not endorse the viewpoint of a publication or
%%  guarantee its technical correctness.}%
%%  \eject
%%  ~\vfill
%%  \centerline{This page intentionally left blank for duplex printing.}
%%  
%%  \vfill\eject}
%%  \setcounter{page}{1}
%%  %%%%%%%%%%%%%%%%%%%% LA-UR page end %%%%%%%%%%%%%%%%%%%%%%

\maketitle

\def\Large{\large}
\def\LARGE{\large}
\def\huge{\large}
\def\Huge{\large}

\section{Introduction}

Nobody likes traffic jams.  For this and other reasons, most developed
economies set aside a significant part of resources to reduce
transportation bottlenecks.  However, it has become increasingly clear
that expansion of capacity may be limited, for example by safety
concerns, by concerns about emissions and pollution, by restrictions
to open space availability, etc.  This means that detailed
quantitative techniques would be useful, for example to analyze
trade-offs between options.

In addition, it is now clear that increasing capacity increases traffic,
often leading to the same bottlenecks as before.  This means that
transportation is {\emph{not}} a simple infrastructure problem, where to
find a good or optimal solution to move a given demand, but a problem where
individual people's values and preferences play an enormously important
role.  In consequence, any quantitative technique needs to be able to
represent aspects of human decision-making.

This leads, maybe naturally, to the idea to approach the problem with
an \emph{agent-based} micro-simulation.  Each traveler is an agent;
agents make plans about what to do during a day; in order to get from
one activity location to another, agents can, for example, walk, use
bicycles, drive cars, or use busses.
%
This is exactly the idea of the TRANSIMS (TRansportation Analysis and
SIMulation System%
%, \cite{TRANSIMS}
) project: to represent each individual
agent in a metropolitan region and to simulate all aspects of his/her
decision-making as long as it is related to transportation. 

\Fig{bubbles}
{\includegraphics[angle=0,width=\textwidth]{transims-bubbles.eps}}
{Modules of an agent-based simulation approach to transportation.}

In principle, this sounds like a straightforward simulation approach
(see \fig{bubbles}): Derive synthetic individuals from demographic
data and locate them on the network; use the demographic information
together with land use information to derive activities (working,
sleeping, eating, shopping, etc.) and activities locations for them;
and let them decide about mode and routing of their transportation.
So far, all these are \emph{plans}, i.e.\ intentions of the simulated
individuals.  These plans can then all be fed into a realistic
transportation micro-simulation, which can be used as the basis for
analysis, such as emissions calculations.

However, this approach encounters challenges from several
directions:\begin{itemize}

\item
{\bf Size of the problem:} Metropolitan regions typically consist of
several millions of travelers.  Executing a second-by-second transportation
micro-simulation on a problem this size within reasonable computing time is
only possible with the use of advanced statistical and computational
techniques.

\item
{\bf Behavioral foundation:} We are far from understanding human behavior.
For that reason alone, we are unable to predict the behavior of
\emph{individual} travelers.  However, there seems to be a realistic
chance that the \emph{macroscopic} (emergent) behavior that is generated by
thousands or ten-thousands of interacting individuals is considerably more
robust than the behavior of an individual agent.  This would be similar to
Statistical Physics, where the trajectory of a single particle is
unpredictable, yet, useful macroscopic properties of gases such as
equations of state can still be derived.

\item
{\bf Consistency problem:} The approach outlined above is not as
straightforward as it sounds because the plans depend on
\emph{expectations} about traffic conditions during execution.  For
example, if a person expects congestion, he or she may make different
plans than when no congestion is expected. Yet, congestion occurs only
when plans \emph{interact} during their simultaneous execution.  --
This problem is not unknown in traditional economic theory and is
traditionally overcome by the assumption of rational agents.  Both
with and without the assumption of rationality, this problem of
consistency between plans and micro-simulation makes the computational
challenge even bigger.

\item
{\bf Robustness:} Any approach to a problem needs to have 
reproducibility of the results under a wide enough range of changes, or
otherwise the results are useless for practical purposes. 

\end{itemize}
%
In the remainder of this paper, we want to give information on how the
basics of such a transportation simulation can look like.  Because of our
own experiences, we will focus on the TRANSIMS project; however, there are
other projects in the area (e.g.~\cite{FVU-NRW}).


\section{Traditional approach}

Before writing about TRANSIMS, let us introduce the approach that is
currently in use in many transportation planning organizations.  It is
called the ``four step process'' because it consists of the following
four steps (e.g.~\cite{Sheffi:book}): 
%
(i)~{\bf Trip generation} -- determine sources and sinks of traffic.
Note that this only counts departures and arrivals, but not where
traffic comes from or goes to.
%
(ii)~{\bf Trip distribution} -- connect sources and sinks via traffic
streams.  The result of this procedure is sometimes called
origin-destination (OD-) matrix.
%
(iii)~{\bf Modal split} -- determine which fraction of travel is done
by the respective modes of transportation (walk, transit, car, etc.)
%
(iv)~{\bf Traffic assignment} -- assign traffic streams on the
network, i.e.\ determine routes for the streams.

This method has several shortcomings, some of which we want to mention
here.  The most important \emph{fundamental} shortcoming is probably
that the mathematical foundation of the traffic assignment is only
valid for time-independent problems.  A consequence of this is that
time-dependent dynamics, such as time-dependent queue-buildup from
bottlenecks, or the sequential ``chaining'' of trips, cannot be
represented easily.  Probably as a consequence of the resulting
difficulty to represent time-dependent processes in detail, practical
implementations of the four step process decouple the modules from
each other, with for example the consequence that congestion does not
reduce the overall number of trips, or that analysis by
sub-populations is not possible because there is no information on
demographic characteristics of travelers available in step~(iv).
Also, the representation of the driving dynamics is too unrealistic to
for example calculate emissions.

In spite of these shortcomings, the four-step process has the advantage
that it has more than 30~years of history, during which the theoretical
foundations have been well developed, and much practical experience has
been gained.  It is therefore understandably a difficult and slow process
to build similar confidence in a new technology based on agent-based
simulation. 




\section{Synthetic population generation module}

The idea behind the TRANSIMS approach is that it simulates
\emph{individual} travelers.  However, the typically available
demographic input data is aggregated over geographical zones.  The
synthetic population generation module~\cite{Beckman:etc:populations}
of TRANSIMS generates instances of stochastic populations.  These
stochastic populations have the property that, if one would take a
census off them, they would result in the same demographics as the
original input data.  The synthetic population can include information
about household membership, home location, income, vehicle
availability, etc.
%
A functional implementation of such a module is currently available as part
of TRANSIMS.


\section{Activities planning module}

The geographical and demographic information of the synthetic individuals
is then used to generate activities for them.  This can for example be done
via complicated activities models with hundreds of free parameters obtained
from the estimation of surveys (e.g.~\cite{bowman:thesis}), or via
simplified ``toy'' models for research purposes
(e.g.~\cite{Wagner:Nagel:acts}).  Such models should include activity
\emph{location} because that is where the travel demand is derived from.


\section{Modal and route planning module}

Activities at different locations need to be connected by transportation.
Synthetic travelers need to select their modes (walk, drive, transit,
etc.), and their routes.  Again, the methods can range from simple,
Dijkstra-type fastest-path algorithms~\cite{Jacob:etc:comp} to
sophisticated formal language constrained path
problems~\cite{Barrett:etc:formal-language}.  

\Fig{usim}
{\centerline{\includegraphics[angle=-90,width=\textwidth]{cloverleaf.ps}}}
{
%
Zoomed-in snapshot of a micro-simulation run.  
%
}

\section{Micro-simulation module}

All agents' plans are executed simultaneously in a transportation
micro-simulation.  This is the only place where interactions between
agents are actually computed, although they could be
\emph{anticipated} in the other modules.  Micro-simulations, too, can
reach from relatively simple queue models~\cite{Simon:Nagel:queue} to
arbitrarily realistic implementations; the currently maybe most
realistic implementation that still fulfills the computing
requirements is based on a cellular automata technique for car
following and lane changing, enhanced by additional rules for elements
such as signals, unprotected turns, turn pockets and weaving lanes,
etc.~\cite{Nagel:etc:flow-char}.



\Fig{replan}
{\centerline{\includegraphics[angle=0,width=\textwidth]{repl.eps}}}
{
%
Example of re-planning.  The traveler first drives to workplace~A via
route~1.  Eventually, he/she decides to switch to a supposedly better
route~2.  Again later, he/she decides that this results still in too much
driving time, and moves to a different workplace~B closer to home.  The
street network shows Portland/Oregon.  The example is taken from an actual
feedback series.
%
}


\section{Feedback and re-planning}

As stated in the introduction, for recurrent situations such as
rush-hour traffic, the conditions expected during plans-making need to
be consistent with conditions during the execution of the plans.  If
they are not consistent, people are likely to change their plans.  For
example, if congestion turns out to be much worse than expected when
the plans were made, people may drop less important destinations from
their trip.  That means that a situation where expected conditions are
not consistent with conditions during execution are transient.  Since
we are currently interested in ``average'' (i.e.\ non-transient)
results, such inconsistency is undesirable.

Yet, when the plans are made for the first time, no information about the
resulting dynamics is available.  This is true both for models and for
reality.  In our simulations, we currently solve this problem by a
relaxation method, i.e.\ by iterating between the plans-making modules and
the micro-simulation until expectations during plans making and conditions
during plans execution are consistent
(\cite{Nagel:Barrett:feedback,Rickert:phd}, see \fig{replan}).  Such
an approach does not seem implausible in behavioral terms. However, it is
worth noticing that conventional economics solves the same problem by
assuming complete rationality and in consequence assumes that agents will
be able to find non-transient plans without ever executing them.


\section{Analysis}

Once expected and encountered conditions are consistent, we can assume that
we are simulating non-transient scenarios.  Such scenarios can
be analyzed in detail in any way one wishes.  Note that,
because of the nature of the microscopic approach, all microscopic
variables are still accessible at this stage.  For example, information can
be separated out by income of the travelers, by trip purpose, by age, etc.
Since one can run the simulations for different alternative scenarios
regarding the transportation infrastructure, it is straightforward to for
example consider the effects of certain infrastructure alternative on
certain sub-populations~\cite{Beckman:etc:case-study}.  Also, since driving
is --at least in principle-- realistically modeled, vehicular emissions
can be calculated~\cite{Williams:etc:98}.  All this is perhaps not
surprising for people used to thinking microscopically about their
problems, but it is a huge step for transportation which traditionally does
not have access to these quantities as output from the four step process.


\section{Summary}

An agent-based simulation approach to transportation is 
possible with current technology, although it is still a significant
computational challenge, especially when one strives for a realistic
representation of the outside world.  It is possible to break up the
problem into modules for ``population generation'', ``activities plans
generation'', ``transportation plans generation'', ``micro-simulation,
and ``analysis''.  The computational challenge stems from the
necessity to simulate realistic second-by-second driving of
metropolitan regions with many millions of travelers.  It is made
even harder by the fact that the micro-simulation needs to be run
several times so that the plans from the plans generation modules can
relax towards ``consistency'' with the micro-simulation.

\smallskip

\noindent
{\bf Acknowledgment} -- This work was performed at Los Alamos National
Laboratory, which is operated by the University of California for the
U.S.\ Department of Energy under contract W-7405-ENG-36 (LA-UR
98-5628).



\tolerance10000
%\bibliographystyle{plain}
\bibliography{ref,kai,xref}

\noindent
%Preprints and other information about TRANSIMS can be found via
%http://www.santafe.edu/{\tt ~}kai.

\end{document}
