Hybridized Ant Colony Algorithm for Convoy Movement Problem

Convoy movement problem is the problem of routing and scheduling military convoys across a limited route network while satisfying some strategic constraints. The problem bears lot of similarities with other real-life applications such as scheduling passenger and freight trains along a single line network, scheduling aircraft landings on runways, routing of automated guided vehicles in a FMS environment, handling baggage along a common automated conveyer belt system, to name a few. Being a proven NP–complete problem, this problem warrants the usage of meta-heuristics to obtain quick solutions. This work focuses on the development of a hybridized ant colony algorithm that combines local search with ant colony optimization to solve the problem. By testing the methodology on a wide range of hypothetical problem instances, we establish the efficacy and practical relevance of the proposed approach. The importance of using a good seed solution for initializing the trail intensities is analyzed and found that it leads to quicker convergence of the algorithm. The need to hybridize the ant colony algorithm with a local search procedure for obtaining superior results is also demonstrated.