Abstract
The main focus of this thesis is to solve a combinatorial optimization problem called the Tour Planning Problem (TPP).The solution of TPP are tours for people meeting some specific objectives. TPP is a variant of the multiple traveling salesman problem (mTSP). We are dedicated to solve TPP to get a better surveillance of a disaster affected area. We learnt that asking volunteers to travel through specific tours, and send back observations made at certain locations with mobile devices will get much better awareness of the area. Hence, better TPP solutions leads to a clearer the view of the area. We present a divide and conquer algorithm utilizing clustering methods such as k-means clustering, as well as an integer linear programming formulation. Performance of the two ways of solving TPP are compared. We hope to show some insights of what can be done by a simple heuristic on a complex problem. Keyword: combinatorial optimization, multiple traveling salesman problem, divide and conquer, k-means clustering, integer linear programming.