Matrix-Learning Particle Swarm Optimization for Multiobjective Multiagent Pickup and Delivery With Time Windows

Multiple heterogeneous agents are popular for executing pickup and delivery tasks for multiple pairs of customers. The scheduling solutions of agents are expected to complete each task within time windows, even under disturbances. Existing problem models tend to evaluate solutions through multiple simulations based on disturbances. This is time-consuming and implicit. In contrast, this article defines a robustness optimization objective based on the relationship between the agent's arrival time and the time windows for explicit evaluation. Taking robustness together with makespan and cost, the problem is modeled as a triobjective optimization problem. To solve the problem, this article proposes matrix-learning particle swarm optimization (MLPSO) to obtain diversified and high-quality solutions for decision-makers. In MLPSO, solutions are represented as an adjacency matrix of task sequences and an allocation matrix of agents to tasks. Corresponding to the matrix-based representation, solutions are constructed by planning the task order for execution and assigning agents to tasks. A matrix-distance-based learning (MDL) strategy is developed to select neighbors in the decision space for particle update. In this way, good task segments and allocation pairs can be extracted from learning exemplars and current positions to provide stable updating directions for generating high-quality solutions. To further enhance solution convergence and diversity, a dual-space local search (DSLS) is performed on elite and sparse nondominated solutions. Experimental results on 36 instances with various scales show that the proposed MLPSO is significantly better than state-of-the-art algorithms in terms of solution quality and diversity.