Effective firefighting and evacuation as integral parts of emergency response in petrochemical plants play a key role in protecting human lives in the event of major tank fires. Compared to firefighting, however, studies devoted to planning and optimizing evacuation plans in the event of tank fires, and particularly concurrent tank fires, have been very few. In the present study, considering the thermal dose as the main cause of casualties in outdoor fires, an innovative methodology is developed to identify proactive evacuation plans for credible fire scenarios. The methodology consists of three main parts: (1) For a given fire scenario (e.g., a single or multiple tank fires), the tank terminal is modelled as a thermal graph in which the weight of each node presents the corresponding heat flux, and the weight of each edge presents the thermal dose between the connected nodes; (2) Dijkstra’s algorithm is used to find the shortest paths (a series of connected edges with the least total thermal dose) to the safe spots (e.g., shelters); (3) Considering the limited capacities of safe spots, mathematical programming is used to identify the number of evacuees to be assigned to each safe spot so as to minimize the total risk of casualties during evacuation. Application of the methodology to an illustrative process plant resulted in intuitive evacuation plans, which is indicative of the methodology’s validity, particularly in the absence of similar studies for comparison and validation purposes.