Multitask n-vehicle exploration problem: Complexity and algorithm

This paper extends the single-task n-Vehicle Exploration Problem to Multitask n-Vehicle Exploration Problem (MTNVEP), by combining n-Vehicle Exploration Problem with Job Scheduling Problem. At first, the authors prove that MTNVEP is NP-hard for fixed number of tasks, and it is strongly NP-hard for general number of tasks. Then they propose an improved accurate algorithm with computing time O(n3 ⁿ ), which is better than O(n!) as n becomes sufficiently large. Moreover, four heuristic algorithms are proposed. Effectiveness of the heuristic algorithms is illustrated by experiments at last.