Selection of the appropriate braking release time is the key to the safe operation of heavy haul trains on long down-slope. However, such various factors as line inclination, interval speed limit, auxiliary air cylinder recharging time and so on should be taken into consideration comprehensively for train cyclic braking. The existing train driving optimization algorithms are characterized with such flaws as slow convergence speed and insufficient local search ability. Therefore, an improvement has been made of the non-dominated sequencing genetic algorithm (NSGA-II), with the shortest air braking distance and the highest operating efficiency being the optimization objectives, an optimization model has been formed of heavy haul trains on long down-slope cycle braking on the basis of INSGA - II (improved NSGA-II) algorithm. On the other hand, variable neighborhood search (VNS) has been introduced into NSGA-II algorithm to solve the problem of insufficient local search ability found in NSGA-II algorithm. Finally, the actual line data of a section of long down-slope of ShuoHuang Railway is selected, followed by a simulation of the optimal condition conversion sequence, thus generating the train driving curve, which verifies the validity of the proposed method.