***Friam Group Applied Complexity Lecture ***
http://www.santafe.edu/sfi/events/abstract/182Date and Time: Friday, March 12, 2004 3:30 - 4:30 p.m.
Location: Medium Conference Room
Speaker: Alberto Donati
Affiliation: Dalle Molle Institute for Artificial Intelligence (IDSIA)
Title: Time Dependent Vehicle Routing Problem with a Multi Ant Colony System
Abstract: The Time Dependent Vehicle Routing Problem, TDVRP, consists in
optimally routing a fleet of vehicles of fixed capacity when travel times
are time dependent, that is, they depend on the time when the trip
originates. The speed distributions, from which the travel times can be
calculated, are supposed to be known at the beginning of the optimization.
This version of the VRP is motivated by the fact that in an urban context
traffic conditions play an important role and can not be ignored in order to
perform a feasible and realistic optimization. In fact when dealing with
time constraints, like the delivery time windows for the customers, the
optimal solutions known for the classic case become unfeasible and the
degree of unfeasibility increases with the variability of traffic
conditions, while on the other hand, if no time constraints are present, the
classic solutions become suboptimal. The optimization consists in finding
the solution that minimizes two objectives: the number of tours first and
the total travel time. Since the total travel time of a tour depends, in the
time dependent context, also on the time of the day the tour was
initiated,an optimization procedureis also required to find the best
starting times.
The optimizations algorithms are all based on the Ant Colony System
(ACS)that has been shown to be a suitable technique for the classic VRP. New
local search procedures that allow searching for the feasible moves in
constant time, are introduced. Relevant aspects of this model and various
experiments are discussed, and finally the application of the model to a
real context.
Locked
