Back to the program.
Ant Colony System for variants of TSP and VRP with time windows
Paola Pellegrini
Universitą  Ca' Foscari di Venezia
Dipartimento di Matematica Applicata
paolap@pellegrini.it

Abstract

Two classical problems of Operations Research have been analyzed. A new variant of Travel Salesman Problem with Time Windows (temporal-TSPTW) and a formulation of Vehicle Routing Problem with Multiple Time Windows, heterogeneous fleet and periodic constraint are presented. Two meta-heuristics based on Ant Colony System have been implemented and tested on benchmark problems, when comparison with literature was possible. A case study has been analyzed for each problem, obtaining interesting results.

Keywords

temporal-TSPTW, VRPMTW, Heterogeneous fleet, Periodic constraint

References

  1. Gendreau M., Pesant G., Potvin J.-Y., Rousseau J.-M.. (1998) An exact constraint logic programming algorithm for the traveling salesman problem with time windows, Transportation Science, 32(1):12-29.
  2. Gambardella L.M., Taillard E., Agazzi G.. (1999) MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. In Corne D., Dorigo M., Glover F. (ed.) New ideas in optimization. McGraw-Hill.
  3. Dorigo M., Gambardella L.M.. (1997) ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE transaction on Evolutionary Computation, 1(1).