Multi-objective Multigraph A∗ Search with Learning Heuristics based on Node Metrics and Graph Embedding

Abstract

To solve general multi-objective multigraph shortest path problems, this paper proposes an algorithm (MOMGA*) that incorporates an online likely-admissible learning-based heuristic function to accelerate the solution-finding process. MOMGA∗ is an extended and generalised version of the airport multi-objective A∗ (AMOA*) algorithm that is tailored for a specific application problem. The online heuristic function is added and developed using artificial neural networks that estimate the costs between two nodes based on their metrics. To implement this metric-based prediction, a graph embedding technique is adopted to learn node feature representations. Results on a range of benchmark multi-objective multigraphs show that (i) in the absence of heuristic information, MOMGA∗ can deliver the same Pareto optimal solutions as AMOA∗ does, while requiring less computational time, and (ii) empowered by the likely-admissible learning- based heuristics, MOMGA∗ is able to provide a set of optimal and near-optimal solutions and strike a good balance between optimality and tractability.