Finding Sets of Solutions for Temporal Uncertain Problems

The multi-objective pathfinding problem is a complex and NP-hard problem with numerous industrial applications. However, the number of non-dominated solutions can often exceed human comprehension capacity. This paper introduces a novel methodology that leverages the concept of a Pareto graph to address this challenge. Unlike previous approaches, our method constructs a graph that relates paths where there is potential for change between them and applies a graph community algorithm to identify solution subsets based on specific aspects defined by a decision-maker. We describe the construction of a Route Change Graph (RCG) to represent possible route changes. A matrix is constructed to save the number of possible change opportunities between two routes, which is then used to construct the RCG. We propose using a threshold value for edge weights in the graph construction, balancing between minimising the number of edges and maintaining connectivity. Following the construction of the RCG, we apply a community detection algorithm to identify closely related solutions, using Leiden algorithm due to its efficiency and refinement phase. We propose calculating various metrics on these communities, including Density, Average Cluster Coefficient, Group Betweenness Centrality, and Graph Degree Centrality, to provide insights into the network structure and interconnectivity. This methodology offers a more manageable set of solutions for decision-makers, enhancing their ability to make informed decisions in complex multi-objective pathfinding problems.