The Geometric Firefighter Routing Problem Project

Institute of Computing / University of Campinas

Citing this page


Use the BibTeX entry:

@misc{gfp-unicamp-page,
      author = {Mauricio J. O. Zambon and
                Pedro J. de Rezende and
                Cid C. de Souza},
      title = {The {Geometric Firefighter Routing Problem} Project},
      year = {2018},
      howpublished = {\url{www.ic.unicamp.br/~cid/Problem-instances/Geometric-Firefighter-Routing}}
}

Abstract


Our objective is to develop algorithms for the Geometic Firefighter Routing Problem (GFRP) from preprocessing, to primal algorithms, to Integer Programming Models that enable solving the problem to optimality.

Problem Description


Based on the Geometric Firefighter Problem (GFP) and proposed by Zambon et al. [1], the GFRP seeks to maximize the total area shielded from a fire that radiates from a point inside a polygonal region by constructing polygonal paths comprised of a subset of a given set of barriers. To decide which barriers to construct, a solution must take into account the speed of the circularly spreading fire and the barriers construction speed. A barrier is considered successfully constructed if the fire does not burn any still unconstructed point on it. In this work, we consider the case where the initial set of barriers is comprised of line segments within the polygon. We are also interested in the 1-GFRP, which requires the constructed paths to be pairwise interior disjoint.

Instances


Instances GFRP solutions 1-GFRP solutions
U.S. national forests instances (Set 1) ([1]) Complete set Complete set
U.S. national forests instances (Set 2) ([1]) Complete set Complete set

File format of the instances

Each instance file is formatted according to the following template:

<vf> <vb>
<nfires>
<firesourceslist>
<polygon>
<nbarriers>
<barrierslist>

The fields are detailed below. A point field is comprised of two rational numbers representing the x and y coordinates, respectively. Each rational number is given in the form p/q, such that p and q are integer numbers. A segment field is composed of two points representing the endpoints of the line segment. A polygon type is described by an integer n, the number of points on the boundary of the polygon, followed by the n points defining the boundary.

Field Type Description
<vf> float the fire speed
<vb> float the barrier construction speed
<nfires> integer number of fire sources (currently 1 for all instances)
<firesourceslist> list of points list of fire sources (one by line)
<polygon> polygon the polygon boundary
<nbarriers> integer number of barriers
<barrierslist> list of segments list of barriers (one by line)

File format of the results

Each result file is formatted according to the following template:

<bestlb>
<bestub>
<nbarriers>
<solution>
The fields are detailed below.
Field Type Description
<bestlb> float the fire speed
<bestub> float the barrier construction speed
<nbarriers> integer number of barriers constructed
<solution> list of segments list of barriers constructed in the solution with the best known lower bound. The barriers are given in the order that they are to be constructed and the order of their endpoints determines the construction direction.

References


Contacts


Research supported by