Daily Arxiv

This page organizes papers related to artificial intelligence published around the world.
This page is summarized using Google Gemini and is operated on a non-profit basis.
The copyright of the paper belongs to the author and the relevant institution. When sharing, simply cite the source.

Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs

Created by
  • Haebom

Author

Filip Rydin, Attila Lischka, Jiaming Wu, Morteza Haghir Chehreghani, Bal azs Kulcs ar

Outline

This paper proposes two graph neural network-based methods for solving routing problems in multi-objective multi-graphs. The first method autorecursively selects edges from the multi-graph to complete a path. The second, more scalable method, simplifies the multi-graph using a learned pruning strategy and then performs autorecursive routing on the simplified graph. Experimentally evaluating both models across a variety of problems and graph distributions, we demonstrate competitive performance compared to robust heuristics and neural network-based baseline models. Our goal is to overcome the limitations of existing single-objective or multi-objective routing methods in adapting to multi-graphs.

Takeaways, Limitations

Takeaways:
An effective graph neural network-based solution to the multi-objective routing problem on multi-graphs is presented.
Two approaches (direct and pruning-based) increase applicability to various situations.
Experimentally verified competitive performance compared to existing methods.
Providing a multi-graph routing model more suitable for real-world problems.
Limitations:
Further analysis of the complexity and computational cost of the proposed model is needed.
Additional experiments using more diverse and complex real-world datasets are needed.
There is room for optimization and improvement of pruning strategies.
Potential performance degradation for certain graph structures or problem types.
👍