In disaster relief logistics, timely and adaptive routing is critical to meet fluctuating demands and disrupted infrastructure. This paper proposes a Hybrid GRG–Neighbourhood Search (NS) model for solving the Multi-Depot Vehicle Routing Problem with Capacity and Time Dependency (MDVRP-CTD). The model integrates the Generalized Reduced Gradient (GRG) method for handling nonlinear capacity constraints and NS for local route refinement. The objective is to minimize total travel distance, delay penalties, and maximize vehicle utilization under dynamic disaster scenarios. Tested using the SVRPBench dataset, the hybrid model achieved up to 96.5% demand fulfillment, an 11% improvement in vehicle utilization, and a reduction in total distance by 7%, outperforming Tabu Search and ALNS in three simulation scenarios. The model demonstrates enhanced adaptability and responsiveness to time-sensitive, capacity-constrained environments. Its novelty lies in the integration of nonlinear optimization with adaptive local improvement tailored for disaster contexts, providing a robust decision-support tool for real-time humanitarian logistics.