Fouling of the inside of tubes in crude oil preheat systems increases pressure drop and pumping costs. In this paper, a method is proposed for optimizing crude oil velocity to reduce fouling of the heat exchanger tubes thereby maintaining heat transfer rates and reducing pressure drop. A simulated annealing algorithm is proposed to describe and optimize the interactions between heat transfer, pressure drop and fouling by adjusting fluid velocity. A specific crude oil heating system is used as a case study to verify the application of the algorithm. Results from case study showed that total annual cost is reduced by 6.4%, indicating that a better performance can be obtained by velocity redistribution using proposed method. (C) 2015 Elsevier Ltd. All rights reserved.