Finding all Pareto Optimal Paths for Dynamical Multi-Objective Path optimization Problems

摘要

Path optimization plays a fundamentally important role in computational intelligence and operational researches. Single-objective path optimization on static route network is often considered in theoretical research, but in reality, multiple objectives and dynamical routing environments make the problem much more complicated. In a multi-objective path optimization problem (MOPOP), there is usually not just one best path, but a set of Pareto optimal solutions, which together are important to decision-makers. Another challenge is dynamical routing environment, which makes it difficult even to find a single-objective best path. This paper puts multi-objective path optimization and dynamical routing environment together, and aims to develop an effective method to calculate the complete (not just a partial or approximated) Pareto front for MOPOP in dynamical routing environments. To this end, a novel nature-inspired method, so called ripple-spreading algorithm (RSA) is completely re-designed, in order to resolve the proposed problem with a theoretical optimality guarantee. Comprehensive experimental results clearly demonstrate the effectiveness and efficiency of the reported method.