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.
Addressing temporally constrained Delivery Problems with the Swarm Intelligence approach
BADALONI, SILVANA;FALDA, MARCO;SAMBO, FRANCESCO;
2008
Abstract
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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
