A combined Tabu search and 2-opt heuristic for multiple vehicle routing

In this paper, the authors consider the problem of assigning multiple agents to perform several tasks under restrictions limiting which agents are permitted to perform each task and restrictions dictating the order of completion of specific tasks. A unique solution description is introduced that allows for the direct satisfaction of these constraints. A two phase optimization procedure is used. A Tabu search method is used to optimize the task assignments and an exchange heuristic is used to refine the completion order of the tasks in the presence of precedence constraints.