A simulated annealing algorithm and a heuristic for war-time convoy movement problem

Abstract Convoy movement problem (CMP) involves the routing and scheduling of military convoys during war time, peacekeeping, or related operations. Although this study focuses on wartime CMP, the underlying methodologies have potential relevance for peacetime logistics and civilian emergency mobility planning. Wartime convoy routing is subject to stringent strategic constraints such as no road crossing, no halts enroute, and maintaining minimum headway distances. Existing literature faces challenges related to scalability, computational complexity, and limited use of search heuristics, highlighting the need for faster and reliable solution approaches. This study proposes 2 methodologies: (1) a heuristic based on the breadth first search [BFS] principal principle and (2) a Simulated Annealing [SA] meta-heuristic algorithm. Two categories of instances [CAT1 and CAT2] are generated using realistic parameters derived from minimum and maximum arc densities. The methodologies are tested on 70 hypothetical cases across both categories, and results are analyzed. Both approaches solve the problem within reasonable computation times. On average, the BFS heuristics yields solutions 6.20% from optimal for CAT1 and 19.43% for CAT2. SA What forms comparatively better, with deviations of 3.86% for CAT1 and 5.78% for CAT2. Overall, the findings indicate that BFS and SA each provide strong performance for specific classes of CMP instances when compared with optimal solutions obtained through conventional global optimization techniques.