Supply Chains are complex networks that demand for decision supporting tools that can help the involved decision making process. Following this need the present paper studies the supply chain design and planning problem and proposes an optimization model to support the associated decisions. The proposed model is a Mixed Integer Linear Multi-objective Programming model, which is solved through a Simulated Annealing based multi-objective meta-heuristics algorithm – MBSA. The proposed algorithm defines the location and capacities of the supply chain entities (factories, warehouses and distribution centers) chooses the technologies to be installed in each production facility and defines the inventory profiles and material flows during the planning time horizon. Profit maximization and environmental impacts minimization are considered. The algorithm, MBSA, explores the feasible solution space using a new Local Search strategy with a Multi-Start mechanism. The performance of the proposed methodology is compared with an exact approach supported by a Pareto Frontier and as main conclusions it can be stated that the proposed algorithm proves to be very efficient when solving this type of complex problems. Several Key Performance Indicators are developed to validate the algorithm robustiveness and, in addition, the proposed approach is validated through the solution of several instances.