Search

Neural solvers based on attention mechanism have demonstrated remarkable effectiveness in solving vehicle routing problems. However, in the generalization process from small scale to large scale, we find a phenomenon of the dispersion of attention scores in existing neural solvers, which leads to poor performance. To address this issue, this paper proposes a distance-aware attention reshaping method, assisting neural solvers in solving large-scale vehicle routing problems. Specifically, without the need for additional training, we utilize the Euclidean distance information between current nodes to adjust attention scores. This enables a neural solver trained on small-scale instances to make rational choices when solving a large-scale problem. Experimental results show that the proposed method significantly outperforms existing state-of-the-art neural solvers on the large-scale CVRPLib dataset.

Multipoint dynamic aggregation is a meaningful optimization problem due to its important real-world applications, such as post-disaster relief, medical resource scheduling, and bushfire elimination. The problem aims to design the optimal plan for a set of robots to execute geographically distributed tasks. Unlike the majority of scheduling and routing problems, the tasks in this problem can be executed by multiple robots collaboratively. Meanwhile, the demand of each task changes over time at an incremental rate and is affected by the abilities of the robots executing it. This poses extra challenges to the problem, as it has to consider complex coupled relationships among robots and tasks. To effectively solve the problem, this article develops a new metaheuristic algorithm, called adaptive coordination ant colony optimization (ACO). We develop a novel coordinated solution construction process using multiple ants and pheromone matrices (each robot/ant forages a path according to its own pheromone matrix) to effectively handle the collaborations between robots. We also propose adaptive heuristic information based on domain knowledge to promote efficiency, a pheromone-based repair mechanism to tackle the tight constraints of the problem, and an elaborate local search to enhance the exploitation ability of the algorithm. The experimental results show that the proposed adaptive coordination ACO significantly outperforms the state-of-the-art methods in terms of both effectiveness and efficiency.

The multipoint dynamic aggregation (MPDA) problem of the multirobot system is of great significance for its real-world applications such as bush fire elimination. The problem is to design the optimal plan for a set of heterogeneous robots to complete some geographically distributed tasks collaboratively. In this article, we consider the dynamic version of the problem, where new tasks keep appearing after the robots are dispatched from the depot. The dynamic MPDA problem is a complicated optimization problem due to several characteristics, such as the collaboration of robots, the accumulative task demand, the relationships among robots and tasks, and the unpredictable task arrivals. In this article, a new model of the problem considering these characteristics is proposed. To solve the problem, we develop a new genetic programming hyperheuristic (GPHH) method to evolve reactive coordination strategies (RCSs), which can guide the robots to make decisions in real time. The proposed GPHH method contains a newly designed effective RCS heuristic template to generate the execution plan for the robots according to a GP tree. A new terminal set of features related to both robots and tasks and a cluster filter that assigns the robots to urgent tasks are designed. The experimental results show that the proposed GPHH significantly outperformed the state-of-the-art methods. Through further analysis, useful insights such as how to distribute and coordinate robots to execute different types of tasks are discovered.

Multi-Point Dynamic Aggregation (MPDA) is a novel task model to determine task allocation for a multi-robot system. In an MPDA scenario, several robots with different abilities aim to complete a set of tasks cooperatively. The demand of each task is time varying. It increases over time at a certain rate (e.g. the bush fire in Australia). When a robot executes a task, the demand of the task decreases at another certain rate, depending on the robot's ability. In this paper, the objective is to design a task plan for minimising the maximal completed time of all tasks. But coupling cooperative and time-varying characteristics of MPDA brings great challenges to modelling, decoding, and optimisation. In this paper, a multi-permutation encoding is used to represent every robot's visiting sequence of tasks, and an implicit decoding strategy with heuristic rules is designed to simplify the problem from a hybrid variable optimisation to a multi-permutation optimisation. Memetic algorithms for the task allocation of MPDA with two local search methods are designed: equality one-step local search with a better exploration ability and elite multi-step local search with a better exploitation ability. Computational experiments show that the proposed decoding method leads to a better performance given the same computational time budget. Experimental results also show that the proposed memetic algorithms outperform the state-of-the-art method in solving the task planning problems of MPDA.