Session: DAC-03-02-Novel AI or ML Frameworks for Design or Systems Science

Paper Number: 90123

90123 - A Scalable Graph Learning Approach to Capacitated Vehicle Routing Problem Using Capsule Networks and Attention Mechanism 

This paper introduces a new graph neural network architecture for learning solutions of a class of Combinatorial Optimization (CO) problems as policies over graphs, with the specific aim being advancement in real-time executability and scalability. The latter is accomplished without the need to retrain the model for test scenarios that are larger than those used in training. While partly drawing motivation from recent graph learning methods that learn to solve CO problems prototypical of optimal planning applications, such as multi-Traveling Salesman Problem (mTSP) and Vehicle Routing Problems (VRP), the proposed neural architecture presents a novel encoder-decoder architecture. Here the encoder is based on Capsule networks, which enables better representation of local and global information with permutation invariant node embeddings; and the decoder is based on the Multi-head attention (MHA) mechanism allowing sequential decisions. This architecture is trained using a policy gradient Reinforcement Learning process. The performance of our approach is favorably compared with state-of-the-art learning and non-learning methods for a benchmark suite of Capacitated-VRP (CVRP) problems. A further study on the CVRP with demand uncertainties is also explored to demonstrate how this Capsule-Attention Mechanism or CapAM architecture can be extended to handle these uncertainties by embedding them through the encoder.

Presenting Author: Steve Paul University at Buffalo

Presenting Author Biography: PhD Student from the Department of Mechanical and Aerospace Engineering, University at Buffalo

Authors:

Steve Paul University at Buffalo
Souma Chowdhury University At Buffalo