Improved NSGA-II to solve a novel multi-objective task allocation problem with collaborative tasks

From the perspective of practical application, a novel task allocation problem for multi-vehicle systems is proposed. The goal is to allocate an optimal route for each vehicle to execute tasks. The planning result is a comprehensive decision considering the influence of time windows, collaborative tasks, and recharging. This problem is represented as a new extension of the classical vehicle routing problem and a multi-objective integer programming mathematical model is established. The objective functions are the total completion time and total penalty costs. A solution strategy hybridizing non-dominated sorting genetic algorithm-II and variable neighborhood search is proposed, and a feasibility recovery strategy and the concept of the immigrant population are introduced. Finally, the simulation results show that the proposed algorithm can solve the problem effectively and is robust to different complexity scenarios. To illustrate concretely the optimization process, an instance is given in the last.