This paper models a sustainable reverse logistics process for polystyrene disposable appliances as an MINLP, with uncertain demand and cost of recovery of the used products. Three heuristics, cross-entropy, genetic algorithm and simulated annealing, are used to generate the initial solution for the MINLP model. Next, robust optimization is applied to solve the resulting problem. The response surface method and the Taguchi method are then applied to tweak the choice of parameter values and enhance the performance of the algorithm. The best-worst technique is used to assess the performance of the heuristics against the robust optimization method. An actual case study is used to validate the model.