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


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.


temporal-TSPTW, VRPMTW, Heterogeneous fleet, Periodic constraint


  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).