Deep Attention Over Vertices and Edges to Solve Team Orienteering Problems

Combinatorial optimization problems are an essential class of problems often encountered in the real world involving a combinatorially growing set of feasible solutions as the problem size increases. Examples include vehicle routing in a supply chain and resident rotation scheduling in a healthcare system. As exact approaches can be computationally expensive, practitioners often use approximate approaches such as metaheuristics. However, sophisticated approximate methods that yield high-quality solutions require expert help to fine-tune the solution process to suit a given problem distribution. In recent years, artificial intelligence (AI) approaches have shown tremendous success with challenging tasks, like natural language processing and autonomous driving. Solving combinatorial optimization problems is an ideal use case for AI approaches. In this talk, I briefly introduce the use of AI for combinatorial optimization. Further, I will present a novel encoder-decoder-based deep reinforcement learning model that incorporates edge weights and handles multi-agent collaboration decoding without a combinatorial explosion of the decision space to solve combinatorial optimization problems such as the Team Orienteering Problem (TOP). I also discuss future research directions.

Dr. Prashant Sankaran is an assistant professor in the industrial and systems engineering department at the University at Buffalo. He received an MS in industrial and systems engineering and a PhD in mechanical and industrial engineering from the Rochester Institute of Technology, Rochester, NY. His research interests include exploiting synergies between operations research and artificial intelligence for better defense, transportation, health care, energy management, and space exploration; artificial intelligence for reasoning under uncertainty; and explainable artificial intelligence.