Optimizing Wildfire Suppression: A branch-and-price-and-cut approach

In periods of intense, synchronous wildfire activity, fire system managers must make rapid fire prioritization decisions over a disperse geographic area with limited suppression resources. This thesis defines the Wildfire Suppression and Crew Assignment Problem, which optimizes resource allocation to triage fires based on damage risk, crew availability and spatiotemporal dynamics. We formulate a two-sided set partitioning model on time-space-rest networks for crew assignments and time-state networks for fire damage, with linking constraints between both; this representation can encode a broad class of non-linear wildfire spread models and diverse suppression objectives. To solve it, we develop a two-sided column generation algorithm that generates fire suppression plans and crew routes iteratively. We embed it into a branch-and-price-and-cut algorithm to retrieve an optimal integer solution, using novel special-purpose cuts that augment generalized-upper-bound cover cuts and a novel branching rule that leverages dual information from the linking constraints. Extensive computational experiments show that the algorithm scales to practical problems that remain otherwise intractable. The optimization methodology can provide high-quality solutions by jointly optimizing wildfire triaging and crew assignments, resulting in enhanced wildfire suppression effectiveness.In periods of intense, synchronous wildfire activity, fire system managers must make rapid fire prioritization decisions over a disperse geographic area with limited suppression resources. This thesis defines the Wildfire Suppression and Crew Assignment Problem, which optimizes resource allocation to triage fires based on damage risk, crew availability and spatiotemporal dynamics. We formulate a two-sided set partitioning model on time-space-rest networks for crew assignments and time-state networks for fire damage, with linking constraints between both; this representation can encode a broad class of non-linear wildfire spread models and diverse suppression objectives. To solve it, we develop a two-sided column generation algorithm that generates fire suppression plans and crew routes iteratively. We embed it into a branch-and-price-and-cut algorithm to retrieve an optimal integer solution, using novel special-purpose cuts that augment generalized-upper-bound cover cuts and a novel branching rule that leverages dual information from the linking constraints. Extensive computational experiments show that the algorithm scales to practical problems that remain otherwise intractable. The optimization methodology can provide high-quality solutions by jointly optimizing wildfire triaging and crew assignments, resulting in enhanced wildfire suppression effectiveness.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Wachspress, Jacob

Advisor dc:contributor.advisor

• Jacquillat, Alexandre

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/157098

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/157098