\documentclass[12pt]{article}
 
\def\notestitle{
        \noindent{\rule{\textwidth}{.25mm}}
        \begin{center}
        {\LARGE \bf A Mixed Linear Programming Model for Dynamic Route Guidance}
        \end{center}
        \noindent {\bf Namit Chaturvedi (99005005)} \hfill {\bf Pravin Paratey (99005009)\\}
        \noindent {\bf Santosh Bag (99005035)} \hfill {\bf Karthik N. (99005101)\\}
	  \noindent {\bf Ramakant Akhairamka (99005102)\\}
        \noindent \raisebox{8pt}{\rule{\textwidth}{.25mm}}
        }
 
\begin{document}
\notestitle
 
\section{Abstract}
One of the major challenges facing ITS (Intelligent Transportation Systems) today
is to offer route guidance to vehicular traffic so as to reduce trip time experienced.
In a cooperative route guidance system, the problem becomes one of assigning routes
to vehicles departing at given times from a set of origins to a set of
destinations so as to minimize the average trip time experienced. Since the time
to traverse a link will depend upon
traffic volume encountered on that link, the link times are dynamic. The complex
interaction resulting between objective function and constraints makes the
dynamic problem significantly more difficult to formulate and solve than the
static version.
 
\section{Introduction}
The problem of cooperative route guidance in the context of Intelligent Transportation Systems
is the problem of assigning vehicular traffic to paths or routes from given origins to
given destinations in such a way that average trip time is minimized.
\par
We will formulate a macroscopic model that implicitly views the assignment
problem as decomposed into two stages. First is the selection of time dependent link volumes,
and second is the assignment of routes that optimally utilize those volumes. Since link
volumes and speeds are related in a one to one fashion through link impedance functions,
the first choice is equivalent to selecting a time dependent number of time periods corresponding
to desired link travel times. This choice is modeled by integer valued variables.
The resulting assignment problem then becomes a multicommodity network flow problem
which we formulate as an ordinary linear program.
 
\section{Model Definition}
We discretize the finite interval of time to be studied and model traffic as a continuous-valued
multicommodity flow in a time-expanded version of the spatial network. Traffic congestion is
modeled by simple capacity constraints on the links.
\par
We model the flows that would occur under cooperative behavior, i.e., dynamic system
optimality, by attaching total network travel time (or equivalently average trip time) as an
objective function to be minimized. Vehicle movements are assumed to be static within links
 but dynamic across links. The fundamental assumption
is that travel time along a link is that which would be experienced were the current link
loading in steady state conditions.
 
\subsection{Network definition}
Let G = (N, A) be the traffic network with node set N and link set A. We model the
problem with h periods, each of duration $\Delta$t, as a time-expanded version of G,
G(h) = (N, A).
\par
\noindent
Corresponding to each node x of N, N has h+1 nodes $x(\tau), \tau = 0 \ldots h$.
\par
\noindent
Corresponding to arc (x,y) of A, A has arcs $(x(\tau), y(\tau+s))$, $\tau = 0 \ldots h-1$,
$s = 1 \ldots h$.
\par
\noindent
N is assumed to contain no self loops.
\par
We represent vehicle flows by nonnegative continuous-valued flow variables
$f_{d} (x(\tau), y(\tau + s))$,
representing the flow volume of traffic with final destination $d \epsilon N$ which enters link (x,y)
at time $\tau$ and exits at time $\tau + s$. We represent the total such flow volume irrespective of
destination by,
\vspace{0.2in}
\\
$f(x(\tau), y(\tau + s)) = \sum_{d \epsilon N} f_{d}(x(\tau), y(\tau + s))$
 
 
\section{Constraints}
The traffic modeling assumptions and implied constraints are as follows
\begin{enumerate}
\item We assume that all vehicles entering a link in a single period tau experience the same link travel time.
\vspace{0.2in}
\\
$f(x(\tau), y(\tau+s)) \leq M \delta(x(\tau), y(\tau+s))$
\vspace{0.2in}
\\
$(x(\tau), y(\tau+s))$ $\epsilon$ $A$, M is an arbitrary large constant and delta is a 0-1
function such that delta is 0 if no vehicle enters link (x,y)
 
\item We assume that vehicles do not pass one another, i.e the vehicle that enters first exits first.
\vspace{0.2in}
\\
$\tau + \sum_{s=1}^{h-\tau}$$s$ $\delta (x(\tau), y (\tau+s)) \leq \omega + \sum_{s=1}^{h-\omega}$
$s$ $\delta(x(\omega), y(\omega + s)) + M (1 - \delta(x (\omega), y(\omega + S)))$
\vspace{0.2in}
\\
   for all $(x,y) \epsilon A, 0<= \tau < \omega < h$ for a suitably large value M.
\end{enumerate}
Thus our objective function is,
\vspace{0.2in}
\par
$min \sum_{\tau=0}^{h-1}\sum_{(x,y) \epsilon A} f(x(\tau -$ \={S}$), y(\tau + S))$
\vspace{0.2in}
\par
\noindent
where h = total time intervals, $S = \{1,2,3 \ldots\}$ and \={S} = S $\bigcup$ \{0\}
 
\section*{References}
\begin{enumerate}
\item David E. Kaufmann, Jason Nonis and Robert L. Smith. 1998. A mixed integer linear
programming model for dynamic route guidance. {\it Transportation Research Part B:
Methodological}, vol. 32, no. 6, pp. 431-440.
\end{enumerate}
 
\end{document}