Abstract: The multi-agent task allocation problem is a fundamental issue in the field of intelligent warehousing.It involves continuously assigning continuously incoming tasks to available agents to minimize the average cycle time of overall tasks.For suchlifelong multi-agent task allocation problem,the problem is first mathematically modeled as a graph coloring problem,using a graph that considers conflict relationships to characterize the correlation between tasks and agents.Based on this problem model,in order to minimize the average cycle time of all tasks,this paper proposes a graph coloring hybrid evolutionary algorithm(GCHEA) that combines heuristic algorithm,tabu search algorithm,and genetic algorithm,using the heuristic algorithm to ge-nerate initial solutions to effectively guide the search process;introducing tabu lists to avoid candidate solutions falling into local optima during the optimization process;utilizing the selection,crossover,and replacement operations of genetic algorithm to enhance population diversity,and obtaining the global optimal solution through iterative optimization.Finally,the proposed GCHEA obtains the graph coloring scheme and further decode it into a specific task-agent allocation solution.Tested on a simulation system,the experimental results show that,compared with existing task allocation algorithms,GCHEA achieves significant improvements in terms of the performance indicators of average cycle time and total system delay time.Specifically,using the GCHEA results in approximately a 49% reduction in the average cycle time of the task,and a 50% decrease in the average total system delay time.

Key words: Intelligent warehousing, Lifelong multi-agent task allocation, Graph coloring problem, Hybrid evolutionary algorithm