On the Amenability and Suitability of Ant Colony Algorithms for Convoy Movement Problem

Convoy Movement Problem (CMP) is a network optimization problem which consists of routing and scheduling military convoys between specific origin-and-destination pairs adhering to certain strategic constraints. This being an NP-hard problem intrinsically, the practical difficulty in obtaining exact solutions even for problems of modest size necessitates for quick solution procedures. As there is hardly any work related to the usage of Ant Colony Optimization (ACO) algorithms on CMP in the literature, this study examines the efficacy of ACO on CMP. The proposed version of ACO considers multiple ant colonies and introduces penalties while updating the trail as well as in the objective function whenever there is a violation of certain constraints. In this algorithm, a separate ant colony with unique pheromone deposits is assigned to each convoy and accordingly the trail of each colony is updated disregard to the pheromone trails of other colonies. The results obtained from this procedure are quite encouraging for a good number of problem instances. Sensitivity analysis is performed to assess the relationship between the number of ants (N) present in each colony, quality of the final solution and computational time. Lower the value of N, better the computational time but the quality of solution declines if N is chosen less than a certain threshold value due to insufficiency of ants.