Heat exchanger network (HEN) synthesis methodologies aim at developing cost effective designs with the best possible topology and optimal values of the decision variables. Although most of the HEN synthesis approaches have focused on obtaining network designs with utilities placed in extreme positions, several works have recently tackle the synthesis problem pursuing an optimal placement of utilities within the heat exchange sequences of the process streams. To this purpose, extended HEN superstructures with sophisticated mixed-integer nonlinear programming models and solution algorithms have been developed. However, due to the combinatorial and nonconvex nature of the problem, sub-optimal designs are frequently obtained even for relatively small synthesis problems. In this work the optimal placement of utilities within HEN designs is reconsidered as a final stage of HEN synthesis methodologies in which a base network design has already been produced. An optimization and utilities relocation approach is presented to explore the generation of improved network designs, with modified topologies that place heaters and coolers in alternative challenging positions with respect to their original placement in the base network design. Four illustrative examples are presented to show that enhanced designs with reduced total annual costs can be developed with the proposed methodology. (C) 2020 Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.