Professor Luca Maria Gambardella
Ant Colony OptimisationAbstract
Most problems faced by logistics operators have been known for centuries, think of the Chinese postman problem, first formulated by Euler in 1736. These problems have the ugly characteristic of being combinatorial, that is, all the possible combinations of the decisions and variables must be explored to find a solution of the problem. Recently, to rapidly solve these problems, heuristics methods have been devised to explore only parts of the search space, concentrating in those parts that appear to promise a probable improvement of the solutions. One of the most recent and powerful heuristic is Ant-Colony Optimization (ACO). ACO is based on the observation that real ants find the optimal path between a food source and their nest food by depositing chemical traces (pheromones) on the floor. A computer analogy has been implemented where a large number of simple artificial ants are able to build good solutions to routing and sequencing problems via low-level based communications based on artificial pheromone. We present the basic ACO principles and we review the most recent running industrial applications in the domain.
Luca Maria Gambardella is director at IDSIA, Istituto Dalle Molle di Studi sull'Intelligenza Artificiale in Lugano, a research institute affiliated to SUPSI (University of Applied Science of Southern Switzerland, DTI Department of Technology and Innovation) and to USI (University of Lugano). He is Professor at SUPSI and Adjunct Professor at the Informatics Faculty at USI. He teaches at SUPSI, at Milan Polytechnics and University of Lugano. He is Chief Scientific Officer of AntOptima, the spin-off company of IDSIA. His major research interests and publications are in the area of optimization, simulation, swarm robotics, multi-agent learning, applied to academic and real-world problems.
He has invented and developed several Ant Colony Optimization algorithms able to compute best-known solutions for many benchmark instances: Sequential ordering problems (SOP), Vehicle routing problems (VRP), Travelling salesman problems (TSP), Quadratic assignment problems (QAP).
He leads several research and applied projects, funded among other by the Swiss National Science Foundation, the European Commission, the Swiss Technology and Innovation Commission, the Swiss Hasler Foundation and private companies on topics such as: On-line Fleet Management, Resource Allocation and Scheduling in Flexible Manufacturing Systems, Simulation and Optimization for intermodal transport, Theory and practice of Metaheuristics, Ad-Hoc Networks, Swarm Intelligence and Cooperative Robotics.