An Improved Ant Colony Optimization algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice

摘要

This article addresses a Periodic Vehicle Routing Problem with Time Window and Service Choice problem. This problem is basically a combination of existing Periodic Vehicle Routing Problem with Time Window and Periodic Vehicle Routing Problem with Service Choice. We model it as a multi objective problem. To solve this problem, we develop a heuristic algorithm based on Improved Ant Colony Optimization (IACO) and Simulate Annealing (SA) called Multi Objective Simulate Annealing - Ant Colony Optimization (MOSA-ACO). Improvements are made in following respects: a) a Euclidean distance based solution acceptance criterion is developed; b) a parameter control pattern is designed to generate different initial solutions; c) several local search strategies are added. Benchmark instances generated from Solomon's benchmark instances and Cordeau's benchmarks instances are applied. Comparison algorithms include four population based heuristics and IACO. Computation experiment results show that MOSA-ACO algorithm has a good performance on solving this problem.