Hybridised ant colony optimisation for convoy movement problem
- PDF / 606,895 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 189 Views
Hybridised ant colony optimisation for convoy movement problem Alan J. Maniamkot1 · P. N. Ram Kumar2 · Mohan Krishnamoorthy3 · Hamid Mokhtar3 · Sridharan Rajagopalan4 Accepted: 28 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keyword Convoy movement problem · Combinatorial optimisation · Ant colony optimisation · Metaheuristics · Local search · Hybridisation
B
P. N. Ram Kumar [email protected]
1
Department of Mechanical Engineering, Indian Institute of Technology Bombai, Mumbai 400076, India
2
QM & OM Area, Indian Institute of Management Kozhikode, Kozhikode 673570, India
3
School of IT and Electrical Engineering, Faculty of Engineering, Architecture and IT, The University of Queensland, St Lucia, QLD 4072, Australia
4
Department of Mechanical Engineering, National Institute of Technology Calicut, Kozhikode 673601, India
123
Annals of Operations Research
1 Introduction The convoy movement problem (CMP) is a routing and scheduling problem of military convoys across a network subject to a host of constraints. Convoys are a group of military vehicles which may contain sensitive materials and must travel together. Some of the constraints include restrictions on encounters of vehicles in the network, movements of convoys within given time windows and the length of the convoys. In the CMP, convoys are not allowed to overtake each other or to cross each other while travelling in opposite directions along an arc. Regardless of the context, be it peacetime or wartime, this is followed strictly for security reasons. The ‘headway time’ of each conv
Data Loading...
