Efficient Task Assignment for Multiple Vehicles with Partially Unreachable Target Locations

This article studies the task assignment problem for a fleet of dispersed vehicles to efficiently visit a set of target locations where some target locations might be unreachable for one or several vehicles. The objectives are to visit as many target locations as possible by using the minimum number of vehicles while minimizing the vehicles' total travel time. We first propose a target merging strategy to deal with the optimization problem, which is in general NP-hard, and show that for the special case of a single vehicle, it requires linear time to calculate the maximum number of targets to be visited. Second, we design a longest path-based algorithm and analyze the cases in which the objective to visit the maximum number of targets by using the minimum number of vehicles can be obtained through the proposed algorithm within linear running time. Once the targets to be visited and the corresponding employed vehicles are determined, the marginal-cost-based target inserting principle to be discussed guarantees that the chosen targets will be visited within a computable finite maximal travel time, which is at most twice of the optimal when the cost matrix is symmetric. Integrating the longest path-based algorithm with two target inserting principles used to minimize the vehicles' total travel time, we design two two-phase task assignment algorithms. Furthermore, we propose a one-phase algorithm to optimize the multiple objectives simultaneously by improving a co-evolutionary multipopulation genetic algorithm. Numerical simulations show that the proposed task assignment algorithms can lead to satisfying solutions against popular genetic algorithms.