Optimization under uncertainty is an important line of research having today many successful real applications in different areas. Despite its importance, few works on multi-objective optimization under uncertainty exist today. In our study, we address combinatorial multi-objective problem under uncertainty using the possibilistic framework. To this end, we firstly propose new Pareto relations for ranking the generated uncertain solutions in both mono-objective and multi-objective cases. Secondly, we suggest an extension of two well-known Pareto-base evolutionary algorithms namely, SPEA2 and NSGAII. Finally, the extended algorithms are applied to solve a multi-objective Vehicle Routing Problem (VRP) with uncertain demands.