2D-Ptr: 2D Array Pointer Network for Solving the Heterogeneous Capacitated Vehicle Routing Problem

The heterogeneous capacitated vehicle routing problem (HCVRP) aims to optimize the routes of heterogeneous vehicles with capacity constraints to serve a set of customers with demands. Existing learning-based methods for solving HCVRP have the problem of weak generalization ability, which means that well-trained model cannot adapt well to new scenarios with different vehicle or customer numbers. To address this issue, by modeling the simultaneous decision-making of multiple agents as a sequence of consecutive actions in real time, we propose a pointer network extension model, which includes a static encoder and a dynamic encoder to map the current situation to node embeddings and vehicle embeddings, respectively. For each element in the consecutive actions sequence, the decoder of our model uses the probability distribution obtained from node embeddings and vehicle embeddings as a 2D array pointer to select a tuple from the combinations of vehicles and nodes (customers and depot). We call this architecture a 2D Array Pointer network (2D-Ptr). Instead of planning paths based on the priority order of vehicles, 2D-Ptr plans paths based on the priority order of actions. In addition, 2D-Ptr consists of a series of carefully designed attention modules, entitling the model to be generalizable in the scenarios where additional vehicles (or customers) are introduced or existing vehicles (or customers) are removed. We empirically test 2D-Ptr and show its capability for producing near-optimal solutions through cooperative actions. 2D- Ptr delivers competitive performance against the state-of-the-art baselines, and can solve arbitrary instances of the HCVRP without requiring re-training. ∗Corresponding authors. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org).

Authors

• Qidong Liu City University of Hong Kong Xi’an Jiaotong University
• Chaoyue Liu
• Shaoyao Niu Zhengzhou University
• Cheng Long Nanyang Technological University
• Jie Zhang University of Bath
• Mingliang Xu School of Computer Science and Artificial Intelligence, Zhengzhou University, Zhengzhou, 450001, China; Engineering Research Center of Intelligent Swarm Systems, Ministry of Education, Zhengzhou, 450001, China; National Supercomputing Center in Zhengzhou, Zhengzhou, 450001, China;

Keywords

• Attention Mechanism
• Combinatorial Optimization
• Heterogeneous
• CVRP
• Pointer Network
• Reinforcement Learning