Supply chains express the sequence of steps related to the production process, from procurement of raw materials to deliver final products to the customer market. The complexity of the impacts caused by supply chains has given rise to the problem of planning sustainable supply chains (SSCs). SSCs are commonly formulated as multi-objective optimization problems to better approach the trade-offs among economic, environmental and social criteria. Nevertheless, most studies consider only the environmental and economic objective functions, ignoring the social criterion. Moreover, they are usually case-specific and lack in defining parameters and constraints that may be present in other SSCs. This paper attempts to describe a generic SSC by introducing a multi-objective formulation that includes the three pillars of sustainability: the economic, the social and the environmental criteria. Additionally, as optimizing multi-objective SSC problems by exact-based methods is time-consuming and often impracticable in realistic scenarios, this paper proposes a matheuristic to obtain approximations of the Pareto frontier within a reasonable time. The computational experience indicated that the proposed matheuristic was from 3.54 to 21.70 faster than the exact-based method for large instances and was on average 2% within of the ideal point.