💻 computer science

Scheduling and Routing with Degradation-Triggered Job Arrivals: An Application to Forest Firefighting with an Unmanned Aerial Vehicle Fleet

This paper addresses the intertwined scheduling and routing problem of forest firefighting with unmanned aerial vehicles, where delaying intervention triggers new job arrivals due to fire spread, by developing mixed-integer programming and hybrid models to maximize retained value in threatened regions.

Original authors: Erdi Dasdemir, Esther Jose, Rajan Batta

Published 2026-08-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Erdi Dasdemir, Esther Jose, Rajan Batta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the high-stakes world of disaster response, timing is often the difference between a contained incident and a catastrophe. This is particularly true for wildfires, where the behavior of a fire is not static but a living, breathing entity that changes the moment it is left alone. If a fire is not addressed immediately, it does not just sit there; it grows larger, consumes more value, and eventually spreads to new areas, creating fresh emergencies that demand attention. This creates a complex puzzle for commanders on the ground: they must decide not only where to send their resources but also when, knowing that every second of delay alters the landscape of the problem itself. The challenge is to balance the immediate need to fight a fire with the strategic necessity of preventing it from igniting new blazes nearby, all while managing a fleet of vehicles that must refuel to keep working.

A team of researchers has tackled this intricate problem by developing a new way to schedule and route unmanned aerial vehicles, or drones, for forest firefighting. Their work focuses on a specific, difficult reality: fires that trigger new fires. In their model, a fire starts at a specific location with a designated window of time to be extinguished. If the fire is left to burn too long, it grows until it reaches a critical size, at which point it naturally spreads to neighboring areas, creating new jobs that must be fought. The goal is not just to put out the initial flames but to intervene early enough to stop this chain reaction, thereby preserving the value of the land, homes, and infrastructure in the region. The researchers created a mathematical framework that acts as a decision-making engine, calculating the optimal path for a fleet of drones to maximize the amount of value saved across an entire forested area.

The researchers tested their approach using a computer model that simulates a forest grid, where each square represents a patch of land with its own value and potential for fire spread. They programmed the model to understand that a drone must visit a water source to refill its tank between missions, adding another layer of complexity to the routing. In their simulations, they introduced various scenarios, including different numbers of drones, varying flight speeds, and different patterns of initial fires. They found that their new method, which combines a precise calculation with a flexible, step-by-step refinement process, was significantly faster and more reliable than previous methods. While older models often struggled to find the best solution within a reasonable time, especially when the number of fires was high, the new approach consistently found high-quality plans quickly. It successfully navigated the trade-off between rushing to the nearest fire and waiting to prevent a more valuable area from burning, ensuring that the drones were used where they could save the most.

To prove the practicality of their work, the team applied their model to realistic scenarios based on the diverse landscapes of California. They created digital maps representing different types of terrain, from densely populated urban areas with heavy vegetation to sparse, uninhabited regions. In these simulations, the model successfully directed fleets of drones to suppress fires and prevent them from spreading to critical zones. The results showed that by using this optimized scheduling, the total value of the protected region remained significantly higher compared to less coordinated efforts. The researchers also made their computer code available to the public, allowing other experts to test the system with their own data and refine the strategies for real-world deployment. This work offers a tangible tool for disaster managers, providing a way to turn the chaotic, spreading nature of wildfires into a manageable set of decisions that can save lives and property.

Technical Summary: Scheduling and Routing with Degradation-Triggered Job Arrivals

Problem Definition
This paper addresses a novel variant of the integrated Vehicle Routing Problem (VRP) and Job Scheduling Problem (JSP), termed "Scheduling and Routing with Degradation-Triggered Job Arrivals." The core challenge involves a network of potential job locations where new jobs do not appear randomly but are dynamically triggered by the degradation of existing jobs.

In the specific context of aerial forest firefighting using Unmanned Aerial Vehicles (UAVs), the problem is defined as follows:

Network Structure: A grid-based graph representing a forested region containing fire-prone nodes, fire-proof nodes (barriers), water sources, and a UAV base.
Job Dynamics: Each ignited area (job) has a designated time window. During this window, the fire grows (degrades in size) and the value of the node degrades.
Degradation-Triggered Arrivals: If a fire is not suppressed before it reaches a critical size threshold ( $t_m$ ), it spreads to adjacent nodes, triggering new job arrivals. This creates a two-way interaction: routing and scheduling decisions determine when fires spread (and thus when new jobs arrive), while the arrival of new jobs impacts subsequent routing decisions.
Objective: To maximize the total remaining value of the region. This involves suppressing fires before they cause total value loss and preventing the spread of fires to high-value adjacent nodes. The model accounts for UAV constraints, including the need to visit water resources to refill tanks between tasks and the requirement to release full water loads regardless of fire size.

Methodology
The authors develop a mathematical optimization framework consisting of two primary models:

Exact Mixed-Integer Programming (MIP) Model (EM):
- The EM formulates the problem using binary variables for vehicle routing, job selection, and fire spread logic, alongside continuous variables for time and value.
- It incorporates linear approximations for fire size growth and value degradation to balance realism with computational tractability.
- The model explicitly links scheduling decisions (arrival times) with fire progression logic. It uses "Big-M" constraints to model four distinct cases of fire spread based on whether a node has a fire, whether a vehicle arrives, and the timing of that arrival relative to the fire's critical growth phase.
- The objective function maximizes the sum of collected node values, penalizing the time taken to return to base.
Hybrid Model: Exact Model-Guided Refill Deferred Model (E-RDM):
- Recognizing that the EM struggles with scalability due to weak linear programming (LP) relaxations and the complexity of water refill constraints, the authors propose a hybrid approach.
- Refill-Deferred EM (RDM): A relaxed version of the EM that omits the specific constraints requiring water resource visits between consecutive tasks and the associated time coupling constraints.
- Branch-and-Cut with Deferred Constraints: The E-RDM algorithm first solves the RDM to generate high-quality feasible solutions. It then employs a branch-and-cut framework with a deferred constraint callback. If a solution violates the omitted water refill or time-coupling constraints, the corresponding constraints are dynamically added as cuts.
- Two-Stage Strategy: The algorithm allocates a portion of the total time limit to solving the full EM (to find optimal solutions quickly if possible) and the remainder to the RDM with dynamic constraint generation (to improve bounds and handle larger instances).

Key Contributions
The paper identifies three primary contributions:

Theoretical Advancement: It introduces the concept of degradation-triggered job arrivals to the scheduling and routing literature. Unlike standard dynamic VRPs where arrivals are stochastic or independent of decisions, this model features a two-way interaction where decisions directly influence the arrival of new jobs.
Disaster Management Application: It provides a prescriptive decision-making model for aerial forest firefighting. The model integrates logistics (routing, refilling) with operational planning (fire suppression timing) to address the "Asset Protection Problem" (APP) in wildfire scenarios.
Reproducibility and Tooling: The authors developed a software interface (spreadsheet-based) linked to their Python/Gurobi codebase, allowing practitioners to generate problem instances and find optimal solutions without interacting with the raw code. The codebase is shared via GitHub to facilitate reproducibility.

Results
Computational experiments were conducted on a 2-core, 28-thread workstation using Gurobi Optimizer 10.0.1.

Performance Comparison: The hybrid E-RDM model significantly outperformed the exact EM. While the EM often failed to prove optimality within the time limit (3,600 seconds) for instances with high job arrivals or limited fleet capacity, the E-RDM consistently achieved an optimality gap of less than 3% across 1,260 runs.
Scalability: The E-RDM demonstrated robustness across varying fleet sizes (2 vs. 4 UAVs) and speeds (60 vs. 120 km/h). It solved instances with an average runtime of 47 seconds.
Impact of Job Arrivals: The study confirmed that as the number of job arrivals increases (driven by initial fires and spread rates), the computational difficulty for the EM increases sharply. The E-RDM effectively mitigated this by leveraging the relaxed formulation to guide the search.
Case Study: A case study based on California wildfire characteristics (using SILVIS land classification data) demonstrated the model's ability to handle diverse landscapes, from high-density urban interfaces to uninhabited vegetated areas. The model successfully generated suppression plans that maximized value retention across seven different scenario types.

Significance and Claims
The paper positions its work as a practical application of the adage "a stitch in time saves nine," emphasizing that early, well-coordinated intervention prevents disproportionate damage. The authors claim that their model offers a significant improvement over existing approaches by explicitly modeling the causal link between suppression delays and the generation of new fire tasks (spotfires).

The study does not claim to solve the continuous physics of fire behavior but rather strikes a balance between realism and tractability by using linear approximations for fire spread and value degradation. The significance lies in providing a decision support system that can handle the dynamic, interdependent nature of wildfire suppression, where delaying a single task can exponentially increase the workload and reduce the total value of the protected region. The authors conclude that their hybrid approach offers a viable path for solving complex, real-world disaster response logistics problems that were previously computationally intractable.

Technical Summary: Scheduling and Routing with Degradation-Triggered Job Arrivals

More like this