A multi-objective multigraph A* algorithm with online likely-admissible heuristics using walk-based shallow embeddings

The multi-objective multigraph Shortest Path Problem (SPP) is intractable, necessitating efficient solution approaches. To address general multi-objective multigraph SPPs, this article introduces a Multi-Objective Multi-Graph A* (MOMGA*) algorithm and develops a learning-based heuristic function to expedite the search. MOMGA* generalises the Airport Multi-Objective A* (AMOA*), which was designed for a specific application on multigraphs, and further modifies its path selection and expansion procedures. Theoretical analysis demonstrates that the modifications in MOMGA* yield advantages over AMOA*, including higher search efficiency, more effective use of admissible heuristics for accelerating search, and seamless integration with likely-admissible heuristics without sacrificing solution quality. The admissibility proof of MOMGA* is also provided. The developed heuristic function is likely-admissible. It embraces node embedding techniques to extract node characteristics, based on which shortest path costs (heuristics) for every two nodes are estimated through neural networks. In particular, we present an extensive review of walk-based shallow embedding methods and experimentally validate their superior ability in capturing the characteristics of nodes for accurately predicting heuristics. Evaluation based on randomly generated multi-objective multigraphs confirms: (i) MOMGA* comprehensively outperforms AMOA*, consistent with the theoretical analysis; (ii) walk-based sampling for node embeddings is key to preserving distance-related information in graphs; (iii) the proposed likely-admissible heuristics, even learnt with a limited amount of training data, can empower MOMGA* to efficiently obtain a collection of optimal and near-optimal solutions; and (iv) a good balance between optimality and tractability in MOMGA* is controllable by tuning the predictive accuracy of learning heuristics.