A multi-strategy genetic algorithm for solving multi-point dynamic aggregation problems with priority relationships of tasks

The multi-point dynamic aggregation problem (MPDAP) that arises in practical applications is characterized by a group of robots that have to cooperate in executing a set of tasks distributed over multiple locations, in which the demand for each task grows over time. To minimize the completion time of all tasks, one needs to schedule the robots and plan the routes. Hence, the problem is essentially a combinatorial optimization problem. The manuscript presented a new MPDAP in which the priority of the task was considered that is to say, some tasks must be first completed before others begin to be executed. When the tasks were located at different priority levels, some additional constraints were added to express the priorities of tasks. Since route selection of robots depends on the priorities of tasks, these additional constraints caused the presented MPDAP to be more complex than ever. To efficiently solve this problem, an improved optimization algorithm, called the multi-strategy genetic algorithm (MSGA), was developed. First of all, a two-stage hybrid matrix coding scheme was proposed based on the priorities of tasks, then to generate more route combinations, a hybrid crossover operator based on 0-1 matrix operations was proposed. Furthermore, to improve the feasibility of individuals, a repair schedule was designed based on constraints. Meanwhile, a $q$-tournament selection operator was adopted so that better individuals can be kept into the next generation. Finally, experimental results showed that the proposed algorithm is feasible and effective for solving the MPDAP.