This is the second part of a series that applies optimization to maximize the productivity and minimize operating costs of existing heat-integrated crude oil distillation systems. This paper presents a two-level retrofit approach for heat exchanger networks. In the first level, simulated annealing proposes topology modifications to the existing network (e.g., adding, removing, and relocating heat exchangers; changing the heat loads of heat exchangers, adding and removing stream splitters, and changing the split fraction of stream splitters). In the second level, a repair algorithm addresses the violation of constraints. These constraints consider the minimum temperature approach, stream enthalpy balances, and existing heat transfer areas. The repair algorithm is formulated as a nonlinear least-squares problem. Temperature-dependent thermal properties are considered in this work for the accurate prediction of stream temperatures. Two case studies illustrate the application of the proposed methodology to decrease total annualized costs.