Assessing the fairness of water resource allocation and structural water shortage risks is an urgent problem that needs to be solved for the optimal allocation of water resources. In this study, we established a new multi-objective optimization model of water resources based on structural water shortage risks and fairness. We propose an improved NSGA-III based on the reference point selection strategy (ARNSGA-III) to solve the optimization model. The superiority of this method was proven by comparing it with three other methods, namely, NSGA-III, MOSPO, and MOEA/D. The model was applied to optimize the allocation of water resources in Wusu City in China. The results show that the new multi-objective optimization model provides reasonable and feasible solutions for solving water conflicts. The convergence and stability of ARNSGA-III are better than those of the other three algorithms. Allocation schemes of water resources for Wusu City in normal years, dry years, and extremely dry years are proposed. In normal years, the structural water shortage risk index is reduced by 50.1%, economic benefits increased by 0.2%, and fairness is reduced by 60.5%. This study can provide new ideas for solving the multi-objective optimization of regional water resources.