Title: The chance-constrained vehicle routing problem
| Speaker: | Ricardo Fukasawa |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
A
classical
combinatorial
optimization
problem
is
the
capacitated
vehicle
routing
problem
(CVRP),
where
one
seeks
to
find
a
minimum
cost
way
to
serve
a
set
of
clients,
using
a
given
fleet
of
vehicles
for
visiting
each
client
exactly
once.
Each
vehicle
is
assumed
to
have
a
given
capacity
and
each
client
a
given
demand.
The
total
sum
of
the
demands
of
the
clients
served
by
a
vehicle
must
not
exceed
the
vehicle's
capacity.
This
important
problem
has
natural
practical
applications
and
has
been
studied
for
decades.
In
this
work
we
consider
the
variation
of
the
CVRP
called
the
chance-constrained
vehicle
routing
problem,
where
demands
are
no
longer
assumed
to
be
known
in
advance,
but
rather
they
are
assumed
to
be
random
variables
with
given
probability
distributions
and
the
vehicle's
capacity
must
be
satisfied
with
high
probability.
We
propose
two
formulations
to
obtain
the
optimal
solution
to
such
problem.
A
key
distinguishing
feature
of
our
work
over
previous
works
on
the
problem
is
that
we
consider
arbitrary
probability
distributions,
while
most
previous
works
assumed
independent
normal
distributions.
Our
computational
results
show
that
our
formulations
are
promising
steps
towards
the
solution
of
larger
scale
instances
of
our
problem.
This
is
joint
work
with
Thai
Dinh
and
James
Luedtke.