Optimisation approaches for an orienteering problem with applications to wildfire management
Creators: name: Roozbeh, Iman
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 490108
subject: Operations research

description: During uncontrollable wildfires, Incident Management Teams (ITMs) dispatch vehicles for tasks aimed at reducing the hazard to key assets. The deployment plan is complicated by the need for vehicle capabilities to match asset requirements within time-windows determined by the progression of the fire. Assignment of the response vehicles to undertake protection activities at different assets is known as the asset protection problem. The asset protection problem is one of the real-life applications of the Cooperative Orienteering Problem with Time Windows (COPTW). <br><br>The COPTW is a class of problems with some important applications and yet has received relatively little attention. In the COPTW, a certain number of team members are required to collect the associated reward from each node simultaneously and cooperatively. This requirement to have one or more team members simultaneously available at a vertex to collect the reward, poses a challenging task. It means that while multiple paths need to be determined as in the team orienteering problem with time-windows (TOPTW), there is the additional requirement that certain paths must meet at some of the vertices. Exact methods are too slow for operational purposes and they are not able to handle large scale instances of the COPTW. <br><br>This thesis addresses the problem of finding solutions to COPTW in times that make the approaches suitable for use in certain emergency response situations. Computation of exact solutions within a reasonable time is impossible due to the nature of the COPTW. Thus, the thesis introduces an efficient heuristic approach to achieve reliable solutions in short computation times. Thereafter, a new set of algorithms are developed to work together as components of an adaptive large neighbourhood search algorithm. The proposed solution approaches in this work are the first algorithms that can achieve promising solutions for realistic sizes of the COPTW in a time efficient manner.<br><br>In addition to the COPTW, this thesis presents an algorithmic approach to solve the asset protection problem. The complexities involved in the asset protection problem are handled by a metaheuristic algorithm. The asset protection problem is often further complicated by a wind change that is expected but with uncertainty in its timing. For this situation a two-stage stochastic model is introduced for the optimal deployment of response vehicles. The model addresses uncertainty in the timing of changes in the problem conditions for the first time in the literature. It is shown that deployment plans, which improve on current practices, can be generated in operational times thus providing useful decision support in time-pressured environments.<br><br>The performance of the proposed approaches are validated through extensive computational studies. The computational results show that the proposed methods are effective in obtaining good quality solutions in times that are suitable for operational purposes. This is particularly useful for increasing the tools available to IMT's faced with making deployment decisions crucial to savings lives and critical assets.