Methods for optimizing large scale thermal imaging camera placement problems

Sammanfattning: The objective of this thesis is to model and solve the problem of placing thermal imaging camera for monitoring piles of combustible bio-fuels. The cameras, of different models, can be mounted at discrete heights on poles at fixed positions and at discrete angles, and one seeks camera model and mounting combinations that monitor as much of the piles as possible to as low cost as possible. Since monitoring all piles may not be possible or desired, due to budget or customer constrains, the solution to the problem is a set of compromises between coverage and cost. We denote such a set of compromises a frontier. In the first part of the thesis a way of modelling the problem is presented. The model uses a discrete formulation where the area to monitor is partitioned into a grid of cells. Further, a pool of candidate camera placements is formed, containing all combinations of camera models and mounting positions. For each camera in this pool, all cells monitored are deduced using ray-casting. Finally, an optimization model is formulated, based on the pool of candidate cameras and their monitoring of the grid. The optimization model has the two objectives of minimizing the cost while maximizing the number of covered cells. In the second part, a number of heuristic optimization algorithms to solve the problem is presented: Greedy Search, Random Greedy Search, Fear Search, Unique Search, Meta-RaPS and Weighted Linear Neighbourhood Search. The performance of these heuristics is evaluated on a couple of test cases from existing real world depots and a few artificial test instances. Evaluation is made by comparing the solution frontiers using various result metrics and graphs. Whenever practically possible, frontiers containing all optimal cost and coverage combinations are calculated using a state-of-the-art solver. Our findings indicate that for the artificial test instances, the state-of-the-art solver is unmatched in solution quality and uses similar execution time as the heuristics. Among the heuristics, Fear Search and Greedy Search were the strongest performing. For the smaller real world instances, the state-of-the-art solver was still unmatched in terms of solution quality, but generating the frontiers in this way was fairly time consuming. By generating the frontiers using Greedy Search or Random Greedy Search we obtained solutions of similar quality as the state-of-the-art solver up to 70-80% coverage using one hundredth and one tenth of the time, respectively. For the larger real world problem instances, generating the frontier using the state-of-the-art solver was extremely time consuming and thus sometimes impracticable. Hence the use of heuristics is often necessary. As for the smaller instances, Greedy Search and Random Greedy Search generated the frontiers with the best quality. Often even better full coverage solutions could be found by the more time consuming Fear Search or Unique Search.