Hybridised ant colony optimisation for convoy movement problem

The convoy movement problem (CMP) is a routing and scheduling problem for military convoys across a network where encounters of vehicles in the network are restricted and the movements of vehicles must occur within given time windows. This problem finds applications in many real-world problems such as scheduling and routing freight trains along a single line network, scheduling aircraft landings on runways, routing of automated guided vehicles in an FMS environment, handling baggage along a common automated conveyor belt system. The CMP is known to be hard computationally. Therefore, heuristic algorithms are the key to obtain quick and reliable solutions. This paper proposes a novel hybridised ant colony algorithm that combines a local search procedure with the ant colony optimisation to solve large and dense instances of the problem. We generate a new dataset which includes small to large instances with a wide range of arc densities to simulate real-world instances. We run a comprehensive computational experiment on our generated dataset to examine the efficiency of our approach. Our experiments show that our approach well handles large and dense instances with reasonably fine solutions. Furthermore, we show the importance of using a good seed solution for initialisation of the algorithm. We analyse the convergence of the algorithm for this seed solution and hybridising the ant colony algorithm with a local search procedure.

Automated summary

This paper proposes a hybridised ant colony algorithm to solve the convoy movement problem, which combines a local search procedure with the ant colony optimisation. It can effectively handle large and dense instances, and obtain reasonable solutions. Furthermore, the importance of using a good seed solution for algorithm initialization is also emphasized.