Problem difficulty of real instances of convoy planning

Abstract

Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.