Based on stochastic optimization, a new method is proposed to synthesize heat integrated distillation sequences (HIDiSs), which are basic configurations and allow nonsharp splits with at most two middle components. Distillation sequences and heat integration networks are simultaneously optimized to minimize the total annual cost (TAC) of HIDiSs. First, the synthesis problem is formulated as an implicit mixed-integer nonlinear programming problem. Discrete variables are distillation sequences. Continuous variables include operating pressures, key component recoveries and ratios of the actual reflux ratios to the minimum reflux ratios in columns. Next, solution strategies are presented, including representing distillation sequences through a novel encoding method, randomly generating neighboring distillation sequences, automatically determining heat integration networks by the pinch method, and calculating the TAC based on shortcut design of columns. Then, the optimization problem is solved by an improved simulated annealing algorithm. Finally, correctness verification for the method is made in two case studies. The optimization algorithm is proved to be computationally efficient and capable to obtain high quality optimal solution. The results demonstrate that heat integration between columns significantly reduces the energy consumption compared to the non-integrated distillation sequences. Moreover, nonsharp HIDiSs can further reduce the TAC compared to those with only sharp splits. (C) 2018 Elsevier Ltd. All rights reserved.