This paper discusses a dynamic evacuation network optimization problem that incorporates lane reversal and crossing elimination strategies. These two lane-based planning strategies complement one another by increasing capacity in specific directions through the evacuation network. A bi-level network optimization model is formulated, in which the upper level aims at optimizing the network evacuation performance subject to the lane-reversal and crossing-elimination constraints and the lower level conveys a cell transmission-based dynamic traffic assignment problem. An integrated Lagrangian relaxation and tabu search method is devised for approximating optimal problem solutions through an iterative optimization-evaluation process. The numerical results of implementing the developed modeling and solution approach to a synthetic network and a real-world example application justify its theoretical and practical value.