Crude fouling is a long-standing operational problem in a refinery, which can seriously affect crude preheat train efficiency and its operation. Plate heat exchangers (PHEs) are considered to mitigate fouling. Meanwhile, velocity is an important factor that can simultaneously correlate fouling rates, heat transfer and pressure drop. Therefore, in this work, a methodology is carried out to optimize the velocity distribution and find the best places to replace shell and tube heat exchangers by PHEs. To achieve this, a velocity correlation model suitable for PHEs is established. The problem is analyzed in the entire operation time horizon, which is divided into several time intervals to describe the dynamic nature of fouling. Simulated Annealing (SA) is used in this optimization method. A case study is illustrated to show the capacity of the method and the optimization results are analyzed in detail. (C) 2020 Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.