Distribution centers (DCs) play important role in maintaining the uninterrupted flow of goods and materials between the manufacturers and their customers.This paper proposes a mathematical model as the bi-objective capacitated multi-vehicle allocation of customers to distribution centers. An evolutionary algorithm named non-dominated sorting ant colony optimization (NSACO) is used as the optimization tool for solving this problem. The proposed methodology is based on a new variant of ant colony optimization (ACO) specialized in multi-objective optimization problem. To aid the decision maker choosing the best compromise solution from the Pareto front, the fuzzy-based mechanism is employed for this purpose. For ensuring the robustness of the proposed method and giving a practical sense of this study, the computational results are compared with those obtained by NSGA-II algorithm. Results show that both NSACO and NSGA-II algorithms can yield an acceptable number of non-dominated solutions. In addition, the results show while the distribution of solutions in the trade-off surface of both NSACO and NSGA-II algorithms do not differ significantly, the computational CPU time of NSACO is considerably lower than that of NSGA-II. Moreover, it can be seen that the fast NSACO algorithm is more efficient than NSGA-II in the viewpoint of the optimality and convergence.