TAGN-IDC: Implicit Discrete Constraints for Tsunami Aware Graph Neural Networks in Spatial Evacuation Routing

Abstract

Tsunami evacuation route requires rapid identification of safe evacuation paths under dynamically changing hazard conditions. A major challenge is incorporating hard binary road-blockage constraints caused by tsunami inundation while maintaining end-to-end differentiability for deep learning models. Existing approaches commonly rely on continuous relaxations or stochastic sampling techniques, which either compromise physical feasibility or increase computational complexity. This study proposes the Tsunami-Aware Graph Network with Implicit Discrete Constraints (TAGN-IDC), a novel graph neural network framework that integrates discrete combinatorial optimization into spatial evacuation routing. The proposed architecture combines a spatio-temporal graph convolutional encoder with gated recurrent units to process static road-network topology and dynamic hydrodynamic tsunami data. A differentiable combinatorial optimization layer is introduced to solve a regularized binary linear program representing road traversability and evacuation flow decisions. Gradients are computed through implicit differentiation of the Karush Kuhn Tucker (KKT) optimality conditions, allowing end-to-end gradient backpropagation through the optimization layer while producing near-binary solutions during training and physically admissible binary decisions during inference. A route decoder subsequently transforms optimized flows and blockage states into node-level evacuation policies. The framework is trained end-to-end using a loss function that jointly optimizes evacuation-time prediction and constraint satisfaction. By preserving hard infrastructure constraints while maintaining differentiability, TAGN-IDC learns physically admissible blockage patterns and generates reliable evacuation routes under tsunami hazards. Experimental evaluation on 200 simulated tsunami scenarios demonstrates that TAGN-IDC achieves a Mean Absolute Error (MAE) of 3.87 minutes, a Constraint Violation Rate (CVR) of 0.023, and a Feasible Route Ratio (FRR) of 0.941, outperforming state-of-the-art learning-based baseline methods in both routing accuracy and physical feasibility. The proposed framework provides a robust foundation for incorporating discrete optimization within deep learning systems for disaster response and emergency evacuation planning.