A Mixed Integer Linear Programming method for the optimal valorisation of regional waste heat, formulated for energy service companies, is proposed in this work. The model provides a framework to simultaneously optimise the multi-period exchange of waste heat between regional thermal sources and sinks, as well as the selection of the backup heating technology. Given the pre-defined cost contributions of the involved sources, the sinks, the heat transport infrastructures and the heating technologies, the configuration is optimised by maximising the system profitability. The approach accounts for variations of temperature levels and heat loads across periods for the same sources and sinks, considers specific energy prices for multiple competing sinks and provides a predesign of the waste heat distribution network considering standard pipe sizes. The method is applied to the southern region of Luxembourg, composed of two steel production plants (heat sources), as well as three factories and nine towns (heat sinks). The impact of the waste heat buying price on the profits, revenues, valorised heat and electricity production quantities is assessed. For prices between 0 and 5 €/MWh, electricity production is a viable solution, while for prices between 0 and 25 €/MWh, the heat can be valorised in the urban systems.