As an essential part of Heat Integration, the heat exchanger network (HEN) plays a vital role in large-scale industrial fields. The optimisation of HEN can increase energy efficiency and considerably save the operating and investment cost of the project. This study presents a novel approach for simultaneous optimisation of plant operating variables and the HEN structure of an existing natural gas purification process. The objective function is the total energy consumption of the studied process. A two-stage method is developed for optimisation. In the first stage, a particle swarm optimisation (PSO) algorithm is developed to optimise variables including tower top pressure, tower bottom pressure, and reflux ratio on the HEN, thereby changing the initial temperatures of cold and hot streams in the HEN. In the second stage, a shifted retrofit thermodynamic grid diagram (SRTGD)-based model and the corresponding solving algorithm was applied to retrofit the HEN. The case study shows that the optimal operating conditions of towers and temperature spans of heat exchangers can be solved by the proposed method to reduce the total energy consumption. The case study shows that the total energy consumption is reduced by 41.5 %.