Addressing temporally constrained Delivery Problems with the Swarm Intelligence approach

We present an application of Ant Colony Optimization metaheuristic to the Pick-up and Delivery Problem with Time Windows (PDPTW), a variant of the Vehicle Routing Problem with Time Windows (VRPTW) with additional constraints on pairs of source-destination nodes. We chose to apply the Multiple Ant Colony System (MACS) approach: two ant colonies minimize the number of vehicles to be routed and the travel lengths: cooperation between colonies is performed by exchanging information through pheromone updating. Besides, we studied a novel strategy to bias the attractiveness of a node depending on its nature, called pheromone post-treatment. The algorithm performances on the number of vehicles needed and the total tour length were comparable to those of the best algorithms in the state of art.