As decontamination is an important means to reduce public contamination during off-site nuclear emergency response, it is necessary to set up appropriate decontamination stations and make reasonable personnel allocation plans. To date, studies on public decontamination location and allocation problems (PDLAPs) are limited and the response time is mostly expressed as the transportation time of sending people to stations. However, the response time for public decontamination contains transportation time and service time to perform decontamination. A multi-objective optimization model for PDLAP is established to minimize the maximum decontamination time and the economic cost with transportation and construction. Since the optimization goals are conflicting, it is unlikely to find a single optimal solution. An improved non-dominated sorting genetic algorithm-II (NSGA-II) is developed to solve optimal pareto solutions of assignment plans. A hypothetical nuclear leakage accident of Changjiang Nuclear Power Plant in Hainan, China is carried out. To show the good performance of the proposed method, NSGA-II and three representative multi-objective optimization algorithms are used for comparison. The simulation results show that the improved NSGA-II has better diversity and convergence. TOPSIS method can offer best assignment plans under different decision purposes to decision makers. The proposed model is helpful to protect public safety and improve off-site decontamination efficiency.