Cooperative Routing for an Air–Ground Vehicle Team—Exact Algorithm, Transformation Method, and Heuristics

Abstract

This paper considers a cooperative vehicle routing problem for an intelligence, surveillance, and reconnaissance mission in the presence of communication constraints between the vehicles. The proposed framework uses a ground vehicle and an unmanned aerial vehicle (UAV) that travel cooperatively and visit a set of targets while satisfying the communication constraints. The problem is formulated as a mixed-integer linear program, and a branch-and-cut algorithm is developed to solve the problem to optimality. Furthermore, a transformation method and a heuristic are also developed for the problem. The effectiveness of all the algorithms is corroborated through extensive computational experiments on several randomly generated instances. Furthermore, this paper is motivated by an intelligence, surveillance, and reconnaissance mission involving a single unmanned aerial vehicle (UAV) and a ground vehicle, where the vehicles must coordinate their activity in the presence of communication constraints. The combination of a small UAV and a ground vehicle is an ideal platform for such missions, since small UAVs can fly at low altitudes and can avoid obstacles or threats that would be problematic for the ground vehicle alone. This paper addresses the coordinated routing problem involving these two vehicles and presents an algorithm to obtain an optimal solution for this problem, fast heuristics to obtain good feasible solutions, and also a transformation method to transform any instance of this cooperative vehicle routing problem to an instance of the one-in-a-set traveling salesman problem.