Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems

Multi-objective and multi-stage decision-making problems require balancing multiple objectives at each stage and making optimal decision in multi-dimensional control variables, where the commonly used intelligent optimization algorithms suffer from low solving efficiency. To this end, this paper proposes an efficient algorithm named non-dominated sorting dynamic programming (NSDP), which incorporates non-dominated sorting into the traditional dynamic programming method. To improve the solving efficiency and solution diversity, two fast non-dominated sorting methods and a dynamic-crowding-distance based elitism strategy are integrated into the NSDP algorithm. The proposed algorithm has been verified on 12 benchmark test functions and a multi-objective travelling salesman problem. The results demonstrate that the NSDP algorithm achieves better outcome in multiple performance metrics and higher solving efficiency, compared with non-dominated sorting genetic algorithm II and multi-objective particle swarm optimization.