Title: A branch-and-cut-and-price algorithm for the pollution routing problem
| Speaker: | Fernando Afonso |
| Affiliation: | Federal University of Itajuba |
| Room: | MC 6486 |
Abstract:
A
classical
combinatorial
optimization
problem
is
the
Vehicle
Routing
Problem
with
Time-windows
(VRPTW).
In
such
problem,
a
fleet
of
identical
vehicles
must
visit
customers
to
deliver
goods
such
that
the
total
amount
of
delivered
goods
is
not
more
than
the
truck's
capacity
and
each
customer
is
served
within
its
pre-specified
time-window.
The
aim
is
to
minimize
the
cost
of
visiting
all
customers
exactly
once.
The
Pollution
Routing
Problem
(PRP)
is
a
variant
of
the
VRPTW
where
in
addition
to
the
routes,
the
speeds
with
which
the
vehicle
will
travel
can
also
be
determined.
The
main
motivation
in
the
PRP
is
that
speeds
will
affect
the
amount
of
pollution
that
is
generated.
In
fact,
several
models
have
been
proposed
to
translate
speeds
into
greenhouse
gas
emissions
and
further
into
dollar
amounts.
Using
those
models,
the
goal
of
the
PRP
then
is
to
minimize
the
total
dollar
amount
as
a
(nonlinear)
function
of
the
speeds
and
the
routes.
The
goal
of
this
talk
is
to
introduce
a
Branch-and-cut-and-price
algorithm
for
the
PRP.
We
propose
a
dynamic
programming
algorithm
to
price
out
negative
reduced
cost
routes
that
derives
novel
dominance
rules
in
order
to
prune
out
unpromising
labels
and
perform
faster.
Extensive
computational
experiments
are
conducted
to
assess
the
performance
of
the
proposed
algorithm.
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~deolivei/reading.htm