A Multiple Ant Colony System for Dynamic Vehicle Routing Problem with Time Window

MACS-DVRPTW, an Ant Colony Optimization based approach useful to solve dynamic vehicle routing problems with time windows, is presented. MACS-DVRPTW is organized with a hierarchy of artificial ant colonies designed to successively optimize a multiple objective function: the first colony minimizes the number of vehicles while the second colony minimizes the traveled distances. Cooperation between colonies is performed by exchanging information through pheromone updating. The algorithm is tested on the well-known 56 benchmark instances of Solomon (1987). These instances are composed of three different problem types, each containing eight to twelve hundred-node problems .We have tested type 1 problems. No. of vehicles is same on the average with the known best. Moreover it solves the Dynamic Vehicle Routing Problem with time window with Multiple Ant Colony System.