A Heuristic for Task Allocation and Routing of Heterogeneous Robots while Minimizing Maximum Travel Cost

The article proposes a new heuristic for task allocation and routing of heterogeneous robots. Specifically, we consider a path planning problem where there are two (structurally) heterogeneous robots that start from distinctive depots and a set of targets to visit. The objective is to find a tour for each robot in a manner that enables each target location to be visited at least once by one of the robots while minimizing the maximum travel cost. A solution for Multiple Depot Heterogeneous Traveling Salesman Problem (MDHTSP) with min-max objective is in great demand with many potential applications, because it can significantly reduce the job completion duration. However, there are still no reliable algorithms that can run in short amount of time. As an initial idea of solving min-max MDHTSP, we present a heuristic based on a primal-dual technique that solves for a case involving two robots while focusing on task allocation. Based on computational results of the implementation, we show that the proposed algorithm produces a good quality of feasible solution within a relatively short computation time.