New Ripple-Spreading Algorithm for Multi-objective Path Optimization

This paper proposes a novel Ripple-Spreading Algorithm（RSA）to calculate the complete（not partial or approximated）Pareto front for Multi-Objective Path Optimization Problem（MOPOP）. Basically, the proposed RSA carries out a one-off ripple relay race in the route network, and then the complete Pareto front will be identified by backtracking those Pareto Non-Dominated Ripples（PNDRs）which reach the destination node. Like most other nature-inspired methods, RSA is actually an agent-based bottom-up simulation model. By defining micro agent behavior, i.e., how a node will generate a new ripple according to the Pareto dominance state of an incoming ripple, the complete Pareto front will emerge at the macro level of ripple relay race, with guaranteed optimality. All complete Pareto fronts of a one-to-all MOPOP can also be found in just a single run of ripple relay race. Since RSA exhibits a good capability of dealing with various complicated routing environments, such as time-window networks and dynamical networks, the reported method has a great potential of extending to many complicated MOPOPs. The effectiveness and efficiency of the proposed method is demonstrated by comparative experimental results. © 2024 Journal of Computer Engineering and Applications Beijing Co., Ltd.; Science Press. All rights reserved.