Retrofit of heat exchanger networks (HEN) is an important subject in the heat integration field. Several studies on the matter use Pinch-based techniques and mathematical models solved with deterministic methods. This work aims at providing an alternative method based on a model derived from a broad superstructure solved with a meta-heuristic approach. The referred superstructure comprises features not present in most HEN studies based on mathematical programming. Structural options such as the possibility of streams sub-splitting, partial mixing, serial units at a single stream branch and the allocation of heaters/coolers at intermediate positions are possible. The methodology was applied to three large-scale industrial case studies from the literature, based on oil refineries. Two of them contained streams with variable heat capacity. In all examples, the present methodology was able to outperform previous studies regarding total annual costs, proving an interesting alternative to methods that are currently applied in the literature. (C) 2019 Elsevier Ltd. All rights reserved.