The traditional location models only seek to minimize logistics cost without regard to the quality and efficiency of service．It sets the time to satisfy customers as a measurement of the location of logistics distribution centers，proposes the method of calculating the customer-satisfying time，and establishes the multi-objective optimization model with the goal of minimizing the logistics cost and maximizing customers’satisfaction．A multi-objective evolutionary algorithm，based on NSGA-11，was proposed to solve the problem．The optimal solutions to the model were obtained by selecting the appropriate encoding method and genetic operators．A practical example shows the validity of the model and algorithm．This model makes it possible to get several efficient solutions，thus providing a more comprehensive decision support for decision-makers．