Concern for the environment has been steadily growing in recent years, and it is becoming more common to include environmental impact and pollution costs in the design problem along with construction, investment and operating costs. To economically respond to the global environmental problems ahead, progress must be made both on more sustainable technologies and on the design methodology, which needs to adopt a more holistic approach. Heat pumps and, in particular systems integrating heat pumps and cogeneration units, offer a significant potential for greenhouse gas reduction. This paper illustrates the application of a multi-objective and multi-modal evolutionary algorithm to facilitate the design and planning of a district heating network based on a combination of centralized and decentralized heat pumps combined with on-site cogeneration. Comparisons are made with an earlier study based on a single objective environomic optimisation of the same overall model.