Approximation Algorithms for Vehicle-Routing Problems
Speaker: | Chaitanya Swamy |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics 3 (M3) 3103 |
Abstract:
Vehicle-routing
problems
(VRPs)
constitute
a
broad
class
of
combinatorial-optimization
problems
that
have
been
widely
studied
in
both
the
operations
research
and
computer
science
literature.
Despite
this,
there
remain
significant
gaps
in
our
understanding
of
these
problems,
especially
from
the
perspective
of
designing
efficient
algorithms
with
worst-case
approximation
guarantees.
A
fundamental
difficulty
here
stems
from
our
lack
of
understanding
of
linear-programming
(LP)
relaxations
for
VRPs.
I
will
describe
how
to
leverage
LP-based
techniques
to
successfully
tackle
two
classes
of
VRPs
and
obtain
strong
approximation
guarantees
for
these
problems.
These
are:
(a)
the
classical
minimum-latency
problem
and
its
multi-vehicle
and
multi-depot
extensions,
wherein
we
seek
routes
for
one
or
more
vehicles
that
together
visit
all
nodes
and
minimize
the
sum
of
the
node-waiting
times;
and
(b)
regret-bounded
VRPs,
wherein
regret
of
a
node
measures
its
waiting
time
relative
to
its
shortest-path
distance
from
the
depot,
and
we
seek
routes
that
ensure
bounded
node
regret.
Our
techniques
show
how
to
exploit
so-called
configuration
LPs
and
bidirected
LP-relaxations,
which
are
two
classes
of
LPs
that
are
often
believed
to
be
quite
powerful
(in
theory
and
practice),
but
have
only
sporadically
been
leveraged
for
vehicle-routing
and
network-design
problems.
The
talk
will
be
self-contained.