Synthesizing simultaneously heat integrated and thermally coupled distillation sequences (HITCDSs) is a complex combinatorial optimization problem and it is difficult to solve this problem, especially when considering nonsharp splits. Based on stochastic optimization, we propose an efficient approach to synthesize nonsharp HITCDSs. First, an implicit mathematical formulation for the HITCDS optimization is presented. Next, encoding strategies are used tactfully to represent HITCDS structures and evolving rules are developed to generate neighboring HITCDS structures. Finally, simultaneously optimizing the distillation sequences, thermal coupling structures, heat integrated networks, and operating parameters of the columns is easily attained through an improved simulated annealing algorithm. Three cases are studied to validate the high solution efficiency of the approach. The optimization results show that nonsharp HITCDSs are more energy efficient than the sharp ones. Besides, HITCDSs have lower total annual cost than conventional distillation configurations, configurations only employing heat integration, and configurations only employing thermal coupling. (C) 2019 Elsevier Ltd. All rights reserved.