Industrial sites are being built increasingly more complex, thus making it difficult to effect rapid and safe evacuations. The optimal evacuation plan depends on the types and locations of threats in addition to the site's layout; moreover, it is necessary to determine the plan in real time when the events are detected. In such emergency scenarios, determining an optimal or near optimal plan, in terms of the egress time, entails the evaluation of numerous alternative evacuation routes. This problem is highly convoluted because of its combinatorial nature; thus, it is highly desirable or even essential, to have access to optimization techniques to solve it. In the present contribution, an algorithmic optimization method is presented to plan evacuation strategies in the chemical industry, in terms of the egress time, supported by software tools. This method uses the graph-theoretic approach based on P-graphs, which exploits the combinatorial nature of the problem, thus providing optimal solutions with high computational efficiency. The method is illustrated by applying it to the evacuation of various industrial site configurations.