Heuristics for Two Depot Heterogeneous Unmanned Vehicle Path Planning to Minimize Maximum Travel Cost

Abstract

A solution to the multiple depot heterogeneous traveling salesman problem with a min-max objective is in great demand with many potential applications of unmanned vehicles, as it is highly related to a reduction in the job completion time. As an initial idea for solving the min-max multiple depot heterogeneous traveling salesman problem, new heuristics for path planning problem of two heterogeneous unmanned vehicles are proposed in this article. Specifically, a task allocation and routing problem of two (structurally) heterogeneous unmanned vehicles that are located in distinctive depots and a set of targets to visit is considered. The unmanned vehicles, being heterogeneous, have different travel costs that are determined by their motion constraints. The objective is to find a tour for each vehicle such that each target location is visited at least once by one of the vehicles while the maximum travel cost is minimized. Two heuristics based on a primal-dual technique are proposed to solve the cases where the travel costs are symmetric and asymmetric. The computational results of the implementation have shown that the proposed algorithms produce feasible solutions of good quality within relatively short computation times.