Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (23): 81-90.DOI: 10.3778/j.issn.1002-8331.2103-0272

• Theory, Research and Development • Previous Articles     Next Articles

New Ripple-Spreading Algorithm for Multi-objective Path Optimization

HU Xiaobing, CHEN Shunian, ZHANG Yingfei, GU Shenghao   

  1. 1.College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
    2.College of Economics and Managementc, Civil Aviation University of China, Tianjin 300300, China
    3.Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China
  • Online:2021-12-01 Published:2021-12-02



  1. 1.中国民航大学 电子信息与自动化学院,天津 300300
    2.中国民航大学 经济与管理学院,天津 300300
    3.中国民航大学 中欧航空工程师学院,天津 300300


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.

Key words: ripple-spreading algorithm, multi-objective optimization, path optimization, complete Pareto front



关键词: 涟漪扩散算法, 多目标优化, 路径优化, 完整的Pareto前沿