% ...................
\documentclass[10pt,twoside,english]{article}
\usepackage{helvet}
\renewcommand{\familydefault}{\sfdefault}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage[a4paper]{geometry}
\geometry{verbose,tmargin=0.98in,bmargin=0.98in,lmargin=1.57in,rmargin=0.98in}
\setlength{\parskip}{\medskipamount}
\setlength{\parindent}{0pt}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[authoryear]{natbib}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\makeatletter
\renewcommand\section{\@startsection{section}{1}{\z@}%
{-10\p@ \@plus -4\p@ \@minus -4\p@}%
{5\p@ \@plus 4\p@ \@minus 4\p@}%
{\normalfont\bfseries\boldmath\rightskip=\z@ \@plus 8em\pretolerance=10000}}
\makeatother
\bibpunct{(}{)}{,}{a}{,}{,}
\makeatother
\usepackage{babel}
\begin{document}
\title{Proactive Empty Vehicle Redistribution for Personal Rapid Transit and Taxis}
\date{}
% For Czech spell check:
% Poté, co mezi nejčastější motýlů v Evropě a mírné Asii, motýl je ve velmi rychlým poklesem, alespoň v západní Evropě.
\maketitle
\begin{abstract}
This is my testing. This is my abstract. This is my abstract. This is my abstract. I can still edit? I can edit in RT mode...
This is my abstract. Testing. again. Here are some edits with the auto preview. It's still reasonably fast. Too bad about the flash. Woot is not a word.
\[\alpha x^2+\beta x+\gamma=0\]
% Here is a citation with duplicate keys: \cite{Bar2004Test}
This is my abstract. This is my abstract. This is my abstract. This is my abstract. This is my abstract. This is my abstract% * <jdleesmiller@gmail.com> 2014-09-03T07:48:52.958Z:
%
% test
%
% ^ <jdleesmiller@gmail.com> 2014-09-03T07:48:56.650Z:
%
% blah
%
% ^ <jdleesmiller@gmail.com> 2014-09-03T07:48:58.685Z.
This is my abstract. This is my abstract. \(a^2 + b^2 = c^2\)This is my abstract. This is my abstract. This is my abstract. This is my abstract. This is my abstract. Here is some more text.
\end{abstract}
\section{Introduction}
\label{sec:intro}
\cite{lees2009ride}
Personal Rapid Transit (PRT) is a new urban transport mode. It will use small, computer-guided vehicles to carry individuals and small groups between pairs of stations on a dedicated network of guideways. The vehicles will operate on-demand and provide direct service from origin station to destination station, much like conventional taxis...
\section{Testing....}
\includegraphics[width=0.99\textwidth]{kalman_error}
\includegraphics[width=0.99\textwidth]{worship_songs}
\subsection{Blah}
\label{sec:blah}
\ref{sec:blah}
The world\textquoteright{}s first PRT system is in the final stages
of commissioning at London\textquoteright{}s Heathrow Airport \citep{ULTraPRT2010ULTra}.
It is a ``last mile'' circulator with
three stations and twenty-one driverless vehicles (Figure \ref{fig:vehicle}),
connecting a business car park with Terminal 5. Many other recently
proposed PRT systems provide connections between train stations, bus
stations or off-site car parks and a wide range of destinations \citep{Bly2005Three}.
Used in this way, PRT can increase the efficacy of other public transport
modes and create new possibilities for urban planning. In order for
PRT to play this role, it must provide a high-quality service, which
means low passenger waiting times, low travel times and high levels
of safety and comfort.
%
\begin{figure}
\includegraphics[width=0.99\textwidth]{n3-station}
\caption{\label{fig:vehicle}Photograph of PRT vehicle and at-grade station
at London Heathrow Airport. PRT vehicles, stations and infrastructure
are smaller than typical Automated People Mover and urban rail systems.
Vehicle length, width and height are 3.7m, 1.4m and 1.8m, respectively.
Photo courtesy of ULTra PRT Ltd}
\end{figure}
The focus of this paper is on methods for moving empty vehicles to
provide low passenger waiting times. Deciding which vehicles to move
and where to move them is known as the empty vehicle redistribution
(EVR) problem. It is assumed that passengers request immediate service
(they do not book ahead) from their origin station to their chosen
destination station. A central control system can move empty vehicles
either \emph{reactively}, in response to a request that has just been
received, or \emph{proactively}, in anticipation of future requests.
Without proactive movements, empty vehicles tend to wait idle at stations
where there is a net inflow of occupied vehicles. This leads to long
passenger waiting times at stations where there is a net outflow of
occupied vehicles, because a passenger's waiting time is often equal
to the travel time of the empty vehicle assigned to serve him \citep{LeesMiller2010Theoretical}.
Clearly, proactive movement of empty vehicles in anticipation of future
arrivals can reduce waiting times, but there is a risk of unnecessary
empty vehicle travel.
This paper proposes two EVR heuristics that can move vehicles proactively,
and it develops methods for assessing the performance of EVR heuristics
absolutely, both in terms of throughput and in terms of passenger
waiting times. The proposed heuristics are evaluated using these methods
and in simulation, and they provide lower waiting times than other
algorithms in the literature. The results show that proactive movement
of empty vehicles significantly reduces mean passenger waiting times,
typically with a modest increase in empty vehicle travel.
The basic PRT system model is adapted from the urban taxi model of
\citet{Bell2005Rolling} (section \ref{sec:model}). When a request
is received, the vehicle that minimizes the request\textquoteright{}s
waiting time is immediately assigned to serve the request. This is
a reactive algorithm, and it assumes no knowledge of future requests.
In order to improve on this, it is assumed that, while future requests
are not known with certainty, the average request rates between each
pair of stations are known from historical data, in the form of an
origin-destination demand matrix. In vehicle routing terminology,
this makes the EVR problem \emph{dynamic} (because requests are received
while the system is operating) and \emph{stochastic} (because statistical
information about future requests is available).
However, it proves useful to first consider two deterministic versions
of the EVR problem. In the \emph{fluid limit} problem, the variables
are long run average flows of vehicles, rather than individual vehicle
movements. Analysis in the fluid limit gives a way of benchmarking
EVR algorithms in terms of throughput (section \ref{sec:fluid}).
In the \emph{static }problem, all future requests are assumed to be
known in advance. An optimal solution to the static problem provides
a benchmark in terms of passenger waiting time (section \ref{sec:static}).
The two proposed heuristics are extensions of the basic model to allow
proactive movements. The Sampling and Voting (SV) heuristic works
by generating an ensemble of possible sequences of future requests
from the demand matrix over a given finite horizon. Each sequence,
together with the current state of the system, defines an instance
of the static EVR problem whose (approximate) solution suggests a
plan of empty vehicle movements. Features of these plans that are
common across the ensemble are then extracted to determine which empty
vehicles should actually be moved (section \ref{sec:sv}). The Dynamic
Transportation Problem (DTP) heuristic works by attempting to maintain
a given \emph{target }number of vehicles inbound to each station.
The problem of satisfying the targets with minimum empty vehicle movement
is a classical transportation problem (section \ref{sec:dtp}). The
SV algorithm was first introduced in \citet{LeesMiller2011Sampling},
but the presentation here is different; the DTP algorithm has not
been described previously......
(TODO MORE ON RELATED WORK...) PRT has much in common with a conventional
hackney service, and the principle of proactively moving empty vehicles
is applicable to conventional taxis. Moreover, the PRT system model
used to implement the algorithms described in this paper is exactly
the urban taxi model of \citet{Bell2005Rolling}, with zones replaced
by PRT stations. So, these conclusions may also be of interest to
taxi operators. On proactively moving empty taxis: Rank Homing (Horn,
2002): special case of TP. Random roaming (Lee et al., 2004), or in
macroeconomic model (taxi). Alshamsi (2009) \textendash{} maybe \textendash{}
must review notes. Seow et al. (2010) mention it as future work. The
Li (2006) thesis. The static problem is to decide how to move empty
vehicles when all requests are known in advance. Whereas the dynamic
problem models a pure hackney service, the static problem models a
pure livery service, in which every request is \textquoteleft{}phoned
in\textquoteright{} before any vehicles are moved.
\section{The Model\label{sec:model}}
The three main factors that determine passenger waiting times are
congestion on the guideway, congestion in stations and the availability
and location of empty vehicles. For very large systems with many vehicles,
congestion effects are often significant, but most systems proposed
for the near and medium term will operate well below the congested
limit. This motivates the following simplifying assumptions.
\begin{enumerate}
\item Congestion on the guideway is ignored, so vehicles take quickest paths,
and the travel times between stations are constants.
\item Congestion in stations is ignored; any delays in stations are constants
included in the travel times.
\item The requested average flows of occupied vehicles between stations
are known, in the form of an origin-destination matrix derived from
historical data, and these averages are steady (they do not change
with time).
\end{enumerate}
The relevant input data are then as follows. Let $S$ be the set of
stations. For each pair of stations $i$ and $j$, let $T_{ij}$ be
the travel time from $i$ to $j$, in minutes, with $T_{ij}=0$ if
$i=j$. Similarly, let $D_{ij}$ be the number of occupied vehicle
trips per minute from $i$ to $j$, with $D_{ij}=0$ if $i=j$.
The PRT system model used in this paper is based on the urban taxi
model of \citet{Bell2005Rolling}. Let $K$ be the set of vehicles,
and let $n_{K}$ be the fleet size ($n_{K}=|K|$). Each vehicle $k\in K$
has a planned route, which consists of a list of stations that it
must visit in order. Each pair of adjacent stations defines a \emph{trip},
during which the vehicle may be occupied or empty. A vehicle's route
changes over time: completed trips are deleted from the head, and
new occupied or empty vehicle trips are appended to the tail as they
are assigned. If a vehicle completes all of the trips in its list,
it becomes \emph{idle} at the last station on its route. For simplicity,
it is assumed that the lists are not reordered, so for each vehicle
$k\in K$, it is enough to know the last station, $d_{k}$, that vehicle
$k$ was assigned to visit, and the time, $a_{k}$, at which the vehicle
will arrive (or has already arrived) at $d_{k}$. With this notation,
an idle vehicle is one whose $a_{k}$ is in the past.
When a new \emph{request} for travel is received, a vehicle is immediately
assigned to serve it. Each request, $r$, has associated with it an
origin station $i_{r}$, a destination station $j_{r}$ and the time
$e_{r}$ at which the system receives the request. It is assumed that
each request is for immediate travel from its origin station, so the
\emph{waiting time} of the request is the delay between $e_{r}$ and
when the assigned vehicle \emph{picks up} the request at $i_{r}$.
The following heuristic, here called Bell and Wong nearest neighbours
(BWNN), is used to decide which vehicle to assign. When a request
$r$ is received at time $e_{r}$, BWNN immediately assigns the vehicle
\begin{equation}
k^{*}=\underset{k\in K}{\mathrm{argmin}}\left[\max\left\{ 0,a_{k}-e_{r}\right\} +T(d_{k},i_{r})\right]\label{eq:bwnn}\end{equation}
where the travel times $T_{ij}$ are written $T(i,j)$ here for readability.
The first term, $\max\{0,a_{k}-e_{r}\}$, is the earliest time that
the vehicle can start a new trip; note that the vehicle cannot begin
its trip in the past, before $e_{r}$. The second term, $T(d_{k},i_{r})$,
is the required empty vehicle trip time; if $k$ is already going
to the request's origin station ($d_{k}=i_{r}$), then the empty vehicle
trip time is zero, because no empty trip is required. Figure \ref{fig:bwnn}
gives an illustrated example.
%
\begin{figure}
%\includegraphics{bwnn_example_one_conc_veh}
\caption{\label{fig:bwnn}Illustration of the BWNN algorithm. There are four
off-line stations (labeled \emph{A} - \emph{D}) in a ring and two
vehicles (labeled \emph{1} and \emph{2}). Traffic flow is counter-clockwise.
(\emph{a}) Vehicle \emph{1} is initially moving to station \emph{B},
and vehicle \emph{2} is idle at station \emph{A}. (\emph{b})\emph{
}When a request for travel from \emph{C} to \emph{D} is received,
vehicle \emph{1} is assigned, because it gives a smaller waiting time
than vehicle \emph{2}. The new request is appended to vehicle \emph{1}'s
request list; this requires an empty vehicle trip (dashed line) from
\emph{B} to \emph{C} and an occupied trip (solid line) from \emph{C}
to \emph{D}. Note that vehicle \emph{1} stops at station \emph{B}
and station \emph{C} (filled circles), but it does not become idle
at either station, because it has not finished with its request list.
(\emph{c}) However, vehicle \emph{1} does become idle at \emph{D},
because no further requests are assigned to it. (\emph{d}) When another
request is received from \emph{C} to \emph{A}, vehicle \emph{2} is
assigned, and it begins an empty trip to \emph{C}. Vehicle \emph{2}
was idle at \emph{A}, so it could have moved to \emph{C} proactively,
if the request from \emph{C} had been anticipated; this would have
reduced the passenger's waiting time.}
\end{figure}
The BWNN algorithm is \emph{reactive}, because it moves vehicles only
in response to requests. This tends to result in idle vehicles accumulating
at stations with a net inflow of occupied vehicles, which in turn
causes long waiting times at stations with net a outflow of occupied
vehicles. The following sections motivate and describe heuristics
for extending this basic reactive model to move idle vehicles proactively.
\section{The Fluid Limit EVR Problem\label{sec:fluid}}
The \emph{fluid limit} deals with long run average flows of vehicles,
rather than individual vehicle trips. In particular, the aim here
is to find the flows of empty vehicles, $X_{ij}$, that are needed
to balance the given flows $D_{ij}$ of occupied vehicles. The result
is a classical transportation problem that is well-known in the PRT
literature \citep{Anderson1978Transit} and can also be derived from
the urban taxi economics model of \citet{Yang2002Demandsupply}. The
main output of this fluid limit analysis is a measure of the theoretical
maximum throughput of the system, which provides a benchmark against
which EVR algorithms can be compared \citep{LeesMiller2010Theoretical}.
The transportation problem in the fluid limit is formulated as follows.
Let $s_{i}=\sum_{j}(D_{ji}-D_{ij})$ be the occupied vehicle flow
\emph{surplus }at station $i$, and partition the stations into $S^{+}=\{i\in S:\; s_{i}\ge0\}$
and $S^{-}=\{i\in S:\; s_{i}<0\}$. The stations in $S^{+}$ have
a net inflow of occupied vehicles on average, and the stations in
$S^{-}$ have a net outflow on average. The flows of empty vehicles
($X_{ij}$) required to balance the total inflows and outflows can
then be found from the following transportation problem: \begin{flalign}
\mathrm{min} & \sum_{i\in S^{+}}\sum_{j\in S^{-}}T_{ij}X_{ij}\label{eq:fluid-tp}\\
\mathrm{s.t.} & \sum_{j\in S^{-}}X_{ij}=s_{i} & \forall\; i\in S^{+}\label{eq:fluid-tp-flow-1}\\
& \sum_{i\in S^{+}}X_{ij}=-s_{j} & \forall\; j\in S^{-}\label{eq:fluid-tp-flow-2}\\
& X_{ij}\ge0 & \forall\; i\in S^{+},\; j\in S^{-}\nonumber \end{flalign}
The objective \eqref{eq:fluid-tp} is to minimise the average number
of moving empty vehicles (minutes, times vehicles per minute, gives
vehicles), and constraints (\ref{eq:fluid-tp-flow-1}, \ref{eq:fluid-tp-flow-2})
ensure that the empty vehicle flows balance the inflows and outflows
of occupied vehicle flows. This problem can be solved efficiently
using standard techniques \citep{Bertsimas1997Introduction}.
An important use of this analysis is to define the \emph{intensity}
of the demand \citep{LeesMiller2010Theoretical}, which is the total
number of vehicles (occupied and empty) required, according to the
fluid limit analysis, divided by the number of vehicles actually available,
$n_{K}$. In particular, the objective \eqref{eq:fluid-tp} gives
the number of empty vehicles required, and the number of occupied
vehicles required can be computed similarly to give the intensity
of the demand as\begin{equation}
\rho=\frac{1}{n_{K}}\left(n_{X}^{*}+\sum_{i,j}T_{ij}D_{ij}\right)\label{eq:intensity}\end{equation}
where $n_{X}^{*}$ is the optimal objective value \eqref{eq:fluid-tp}.
Intensity one corresponds to maximum throughput. When $\rho>1$, requests
are arriving faster than the system can serve them, because it does
not have enough vehicles. This means that both the number of passengers
waiting and their waiting times will grow indefinitely, so long as
the demand is held constant. When $\rho<1$, the system may (depending
on how efficiently it uses empty vehicles) be able to keep up with
demand. So, while this fluid limit analysis does not give a direct
measure of passenger waiting times, the intensity of the demand is
an important factor. The term intensity is motivated by similar definitions in the theory of queueing systems.
The fluid limit problem provides a benchmark for throughput, but it
does not provide much information about waiting times; this requires
a more detailed model, such as the one in the next section.
\section{The Static EVR Problem\label{sec:static}}
In the static problem, it is assumed that all requests are known in
advance instead of being revealed while the system is operating. This
problem is of interest because an optimal solution for an instance
of the static problem provides a benchmark for waiting times, and
also because the static problem motivates the SV method for the dynamic
problem (section \ref{sec:sv}).
The static EVR problem can be formulated as a \emph{multivehicle truckload
pickup and delivery problem with time windows}, which is a well-studied
\citep{Yang2004RealTime} vehicle routing problem. An instance of
the static EVR problem requires that the initial state of the vehicles
and all requests over a given finite horizon be known. For simplicity,
let the current time be time zero, adjust the vehicles' $a_{k}$ times
accordingly, and set $a_{k}=0$ for vehicles that are currently idle.
Let $R$ be the set of requests with $e_{r}$ within the horizon.
All of the $i_{r}$, $j_{r}$ and $e_{r}$ are known at time zero,
and $e_{r}$ is the earliest time that request $r$ can be picked
up.
To translate the static EVR problem into a vehicle routing problem,
we construct an auxiliary \emph{vehicle-request graph}, $G$, with
one node for each vehicle, one node for each request, and a \emph{sink
}node, $s$. The routing problem is to find the best routes in $G$
that serve all of the requests. Each route must start from a vehicle
node, go through zero or more request nodes, and end at the sink node.
More formally, the node set of $G$ is $K\cup R\cup\{s\}$, and the
edge set is $\{(u,v):u\in K\cup R,v\in R\cup\{s\},u\ne v\}$. The
routing objective is to minimize mean request (passenger) waiting
time, which is known as a \emph{minimum latency} objective. The requirement
that request $r$ be picked up only after $e_{r}$ is a \emph{one-sided
time window} constraint. The edge costs encode the required travel
times in the PRT network, with\begin{equation}
c_{uv}=\begin{cases}
a_{u}+T(d_{u},i_{v}) & u\in K,\; v\in R\\
T(i_{u},j_{u})+T(j_{u},i_{v}) & u,v\in R,\; u\neq v\\
0 & \mathrm{otherwise}\end{cases}\label{eq:edge-costs}\end{equation}
The cost \eqref{eq:edge-costs} of an edge from vehicle $k$ to request
$r$ includes the time required for $k$ to finish serving previously
assigned requests (if any) plus the required empty vehicle trip time
(if any). Similarly, when both $u$ and $v$ are requests, the cost
includes the occupied travel time $T(i_{u},j_{u})$ for request $u$
and any empty travel time $T(j_{u},i_{v})$ required in order to serve
$v$ directly after $u$.
The static EVR problem is NP-hard, because the corresponding routing
problem on $G$ generalises the minimum latency version of the asymmetric
travelling salesman path problem (ATSPP), which is NP-hard \citep{Nagarajan2008Directed}.
In particular, the routing problem is a minimum latency ATSPP when
there is one vehicle and $e_{r}=0$ for all requests. Small instances
can be solved exactly using standard techniques, but very large instances
must be solved in order to benchmark EVR algorithms, because waiting
times must be averaged over thousands of requests. These large instances
can only be solved approximately, at present.
In this paper, large instances of the static EVR problem are
solved using the following\emph{ }static nearest neighbours\emph{
}(SNN) heuristic \citep{LeesMiller2011Sampling}. For each request
$r$, in ascending order by $e_{r}$, SNN chooses the vehicle\begin{equation}
k^{*}=\underset{k\in K}{\mathrm{argmin}}\max\left\{ 0,\; a_{k}+T(d_{k},i_{r})-e_{r}\right\} \label{eq:snn}\end{equation}
that minimizes the waiting time for request $r$. SNN is similar to
BWNN \eqref{eq:bwnn}, and in fact for vehicles with $a_{k}\ge e_{r}$,
the objective values in \eqref{eq:bwnn} and \eqref{eq:snn} are the
same. However, if a vehicle has $a_{k}<e_{r}$, SNN allows the vehicle
to start its empty trip before $e_{r}$, whereas BWNN does not. In
this sense, SNN moves empty vehicles proactively. If there are several
vehicles that minimize \eqref{eq:snn}, one is chosen using the tie-breaking
rules in \citet{LeesMiller2011Sampling}. The vehicle state for $k^{*}$
($a_{k^{*}}$ and $d_{k^{*}}$) is then updated accordingly, and the
next request is considered. Testing.
The solutions produced by SNN are not provably optimal, so other methods
may produce lower mean waiting times for a given instance; in this
sense, the solutions are not, strictly speaking, benchmarks. However,
nearest neighbour heuristics have been found to produce high quality
solutions to other minimum latency routing problems \citep{Fischetti1993Delivery,Larsen2004Priori,Swihart1999Stochastic}.
This is particularly true when the fleet size is large, because each
vehicle's route tends to be short, and fleet sizes in PRT are large
relative to those usually studied in the vehicle routing literaturearst
(the case study systems in section \ref{sec:results} have 200 vehicles).
The intensity of the demand is also important in determining the difficulty
of a given instance; when the intensity of the demand is low, there
are long delays between requests, so most requests will simply be
served in the order in which they are received. In fact, the SNN heuristic
finds solutions with zero waiting time (which are clearly optimal)
when the intensity of the demand is below about 80\% on the case study
systems.
Another use for the static problem is in the proposed Sampling and
Voting heuristic, below. Here are some new words.
\section{New EVR Heuristic: Sampling and Voting (SV) \label{sec:sv}}
The sampling and voting (SV) heuristic moves idle vehicles proactively
by generating an ensemble of static problems, solving them approximately
using SNN, and extracting common features from the solutions in order
to decide which idle vehicles should actually be moved.
When a new request is received at time $t$, SV assigns a vehicle
using the BWNN algorithm. Immediately after a vehicle has been assigned
to serve the request, SV may then move idle vehicles proactively.
To decide which idle vehicles to move, an ensemble of $n_{E}$ possible
sequences of $n_{R}$ future requests each is generated from the demand
matrix. Each sequence in the ensemble, together with the current state
of the system, defines an instance of the static EVR problem. Each
of these instances is solved approximately using the SNN algorithm,
and each resulting solution prescribes a sequence of empty vehicle
trips, which constitutes `advice' on which idle vehicles the system
should actually move. However, because each solution is computed for
a (probably) different sequence of requests, they may offer conflicting
advice. To determine which action should actually be taken, a voting
system is used. The system adopted here is that at most one idle vehicle
at each station may be moved. So, each solution casts one vote on
the best destination (as defined below) for an idle vehicle at each
station $i$ with idle vehicles; note that it may vote for $i$, which
means that it votes not to move any idle vehicles from $i$ at this
decision point. If the destination with the most votes is not $i$,
an idle vehicle at $i$ is selected (breaking ties on minimum vehicle
index) and moved.
For each station $i$ with idle vehicles, the destination to vote
for are determined as follows. If all vehicles now idle at $i$ were
used for requests from $i$, vote for $i$. Otherwise, if a vehicle
now idle at $i$ was moved empty to another station, $j$, vote for
$j$ (for the first such trip). Otherwise, if any vehicle was moved
empty from $i$ to another station, $j$, vote for $j$ (for the first
such trip). Otherwise, vote for $i$. These voting rules are discussed
in more detail in \citet{LeesMiller2011Sampling}....
\section{New EVR Heuristic: Dynamic Transportation Problem (DTP) \label{sec:dtp}}
The dynamic transportation problem (DTP) heuristic requires a \emph{target}
for the number of vehicles that should be inbound\emph{ }to each station
at any given time. If the number of vehicles inbound to a station
is below its target, idle vehicles should be moved there; conversely,
if a station has inbound vehicles in excess of its target, some of
its idle vehicles may be moved elsewhere. The problem of moving idle
vehicles to meet targets with minimum empty vehicle running time is
a classical transportation problem.
The idea of maintaining a target number of vehicles at each station
is common in the PRT literature \citep{Andreasson1998QuasiOptimum,Anderson1998Control}.
The decision on which vehicles to move is typically made according
to rules that can be viewed as approximation algorithms for the transportation
problem. For example, when a station has a deficit, it may call the
nearest idle vehicle at a station with a deficit not greater than
its own \citep{Andreasson1998QuasiOptimum}. The targets may be treated
as parameters to be tuned, or they may be set adaptively based on
the history of past empty vehicle movements \citep{Andreasson1998QuasiOptimum}.
In this paper, the targets are treated as parameters to be set using
meta-heuristics, and the results are compared with a heuristic based
on these existing algorithms (section \ref{sec:results}).
More formally, for each station $i,$ let $\theta_{i}$ be the target
number of inbound vehicles at station $i$. Let $t$ be the current
time. Let $b_{i}$ be the number of vehicles that are inbound to $i$
(that is, $d_{k}=i$), and let $l_{i}$ be the number of vehicles
that are idle at $i$ (that is, $d_{k}=i$ and $a_{k}\le t$); note
that $b_{i}\ge l_{i}\ge0$. We can now define\[
u_{i}=\min\left\{ b_{i}-\theta_{i},l_{i}\right\} \]
as the \emph{surplus} of vehicles at station $i$. If $u_{i}>0$,
station $i$ has a surplus of inbound vehicles, but only $l_{i}$
of these are currently idle at $i$, so at most $l_{i}$ vehicles
can be moved now. If $u_{i}<0$, station $i$ has a \emph{deficit}
of inbound vehicles. In general, the surpluses and deficits need not
balance, so we introduce an extra dummy node $q$ with $u_{q}=-\sum_{i}u_{i}$.
Let $S'=S\cup\{q\}$ and partition $S'$ into sets $S_{t}^{+}=\left\{ i\in S'\;:\; u_{i}\ge0\right\} $
and $S_{t}^{-}=\left\{ i\in S'\;:\; u_{i}<0\right\} $. Note that
this partition may change over time. For each $i\in S_{t}^{+}$ and
each $j\in S_{t}^{-}$, let $x_{ij}$ be the number of vehicles to
send from node $i$ to node $j$, which is to be solved for. If $i$
and $j$ are both stations, then $x_{ij}>0$ means that $x_{ij}$
vehicles which are currently idle at $i$ are to move to station $j$.
If either $i=q$ or $j=q$, then no vehicles are actually moved, regardless
of the value of $x_{ij}$; in other words, a decision to move idle
vehicles from or to the dummy node means that they should be left
where they are until the next decision point. The costs for sending
vehicles to and from the dummy node are zero (define $T_{iq}=T_{qi}=0$),
because none of these vehicles are actually moved.
The transportation problem to be solved has the same form as that
in the fluid limit \eqref{eq:fluid-tp}, but the variables are $x_{ij}$
instead of $X_{ij}$, the surpluses are $u_{i}$ instead of $s_{i}$,
and the stations (and $q$) are partitioned into $S_{t}^{+}$ and
$S_{t}^{-}$ instead of $S^{+}$ and $S^{-}$. When the targets $\theta_{i}$
are integers, there is an optimal solution in which all of the $x_{ij}$
are integer, because it is a special case of the minimum cost network
flow problem and the $u_{i}$ are integers \citep[ch. 7]{Bertsimas1997Introduction}.
The problem is solved exactly with the integer RELAX IV code \citep{Bertsekas1988Relaxation}.
The DTP heuristic is embedded in the PRT system model (section \ref{sec:model})
as follows. When a request is received, a vehicle is assigned using
BWNN \eqref{eq:bwnn}, as usual. Immediately after this, the DTP transportation
problem is formulated and solved to decide on proactive empty vehicle
trips. The transportation problem is also solved every time a vehicle
becomes idle.....
\section{Results\label{sec:results}}
In this section, the proposed algorithms are evaluated in simulations
on two case study systems. The main simulation outputs are passenger
waiting times and empty vehicle use. The steady state distributions
of these outputs are estimated by running long simulations with the
demand matrix held constant for each run. Passenger requests from
station $i$ to station $j$ are generated from a Poisson process
with rate $D_{ij}$. For convenience, passenger arrival and travel
times are rounded to the nearest integer second.
The input data used here are the `Grid' and `Corby' networks and their
corresponding demand matrices from \citet{LeesMiller2010Theoretical}
(for the Grid network, the demand matrix with dispersion parameter
$\theta=0.01$ is used). The fleet size is set at $n_{K}=200$ vehicles.
Intensity one corresponds to a total demand of $1414$ requests/hour
for the Corby system and $2035$ requests/hour for the Grid system.
The targets for the DTP algorithm are chosen using simulated annealing,
as implemented in the GNU Science Library \citep{Galassi2003Gnu}.
An initial estimate of the levels targets is obtained from the fluid
limit problem \eqref{eq:fluid-tp}, namely\[
\hat{\theta}_{i}=\left(\sum_{\begin{subarray}{c}
j\\
i\ne j\end{subarray}}(D_{ji}+X_{ji}^{*})T_{ji}\right)\left(\sum_{\begin{subarray}{c}
j\\
i\ne j\end{subarray}}\frac{D_{ij}}{D_{ij}+X_{ij}^{*}}\right).\]
The first factor is the number of vehicles that are expected to be
inbound to station $i$ on average, and the second factor is the fraction
of vehicles that leave station $i$ occupied. The rationale for the
second factor is that if most of the vehicles leaving station $i$
are empty, on average, then the station should not attempt to retain
very many vehicles. Neighbouring solutions were generated by adding
-1, 0 or 1 with equal probability to each target. The initial temperature
was set to 10; the temperature decay factor was 1.01; the final temperature
was 0.1; 10 evaluations were performed at each temperature; the Boltzmann
constant was set to 1. Each energy evaluation was a simulation with
20000 requests. Two trials were performed for each point Figure \ref{fig:results},
for a total of around 9200 energy evaluations per point.
For comparison, another EVR algorithm, here called the Surplus / Deficit
(SD) algorithm, is also evaluated. It is an algorithm for the dynamic
EVR problem that moves vehicles proactively. The general approach
in SD is similar to several other published EVR algorithms \citet{Anderson1998Control};
it is most similar to that of \citet{Andreasson1998QuasiOptimum}.
Each station $i$ has an associated call time $\tau_{i}$, which is
the cumulative average of all previous empty vehicle trip times to
that station. The surplus of vehicles at station $i$ is the number
of inbound vehicles minus the expected number of requests over the
call time, namely $\tau_{i}\sum_{j}D_{ij}$. When a new request is
received, a vehicle is assigned using BWNN. Immediately afterward,
SD may move idle vehicles proactively, as follows. For each station
$i$ with idle vehicles, in descending order by number of idle vehicles,
if the surplus of vehicles at $i$ is greater than or equal to one,
an idle vehicle at $i$ is sent to the nearest station with surplus
less than zero (if any). Additionally, when a vehicle becomes idle
at station $i$, the above actions are taken for station $i$ only.
%
\begin{figure}
%\includegraphics[width=0.99\textwidth]{utsg_2011_compare}
\caption{\label{fig:results}Mean passenger waiting times (\emph{a}, \emph{b})
and vehicle fleet utilization (\emph{c}, \emph{d}) for the Grid and
Corby networks for the five heuristics. The SV and DTP heuristics
move idle vehicles in anticipation of future requests, which reduces
waiting times significantly below the BWNN baseline and below the
SD heuristic from the literature. The SNN algorithm operates with
perfect information about future requests in order to estimate how
much further waiting times might be reduced. Here there are $n_{E}=50$
sequences, each with $n_{R}=300$ requests for SV. Each point is averaged
over 10 independent runs of 50,000 simulated passengers each.}arst
\end{figure}
Figure \ref{fig:results}(\emph{a}) compares the mean waiting times
observed for the five heuristics on the Corby system. An important
observation is that waiting times increase rapidly as intensity approaches
one, regardless of which EVR algorithm is used, as is expected based
on the definition of intensity \eqref{eq:intensity}. In practice,
we are most interested in the system's performance at around 70\%
to 90\% intensity, because in this range the system is well-utilized,
but acceptably low passenger waiting times may still be obtained.
At intensity 0.8, for example, mean waiting times are 355s for BWNN,
41s for SD, 20s for DTP, 15s for SV. By moving vehicles proactively,
SV reduces mean waiting times by 96\% from the BWNN baseline. The
relative reduction decreases as intensity increases, however, and
in fact the SV, DTP and SD algorithms become increasingly similar
to the BWNN algorithm at higher intensities, because there are fewer
idle vehicles to redistribute.
Figure \ref{fig:results}(\emph{c}) shows that the reduction in passenger
waiting times comes from a modest increase in the average number of
moving empty vehicles, or equivalently in empty vehicle travel time.
The largest increase occurs at intensity 0.91, and this is from 47
concurrently moving empty vehicles with BWNN to 51 with SV (out of
200 vehicles). With perfect information about future arrivals, SNN
finds routes with average waiting times less than those for the dynamic
case, as expected; at intensity 0.8, the mean waiting time for SNN
is 3s. Only mean waiting times are reported, but the ranking of the
four algorithms is the same at the 90th percentile of the waiting
distribution; at intensity 0.8, 90\% of passengers wait less than
51s with SV and less than 106s with SD.
Results for the Grid network are qualitatively similar, as shown in
Figure \ref{fig:results}(\emph{b}, \emph{d}). However, it is notable
that waiting times diverge at around intensity 0.95, which is below
the theoretical maximum (intensity one). It thus appears that nearest
neighbor algorithms of the type studied here do not deliver maximum
possible throughput; it is not yet known whether there is any practical
algorithm that does.
The results and conclusions presented here are consistent with simulations
that have been conducted on nine case study systems in total, with
between 15 and 60 stations, between 50 and 600 vehicles, and total
demand at intensity one between 360 and 5050 requests/hour. However,
it is possible to construct pathological systems in which the SV and
DTP heuristics perform poorly; details of these will be documented
in (FORTHCOMING THESIS).
\section{Conclusions}
Future work: rerouting, MDP approach....
\bibliographystyle{plainnat}
\bibliography{jdleesmiller}
% \bibliography{duplicates}
\end{document}
