Local search approaches are often used to find solutions for optimisation problems. However, these approaches easily get stuck in local optima, who are not yet globally optimal. More complex variants of those approaches cannot always escape those local optima easily. Thus, the need for another effective technique arises. This thesis proposes such a technique: potential KPIs. A potential KPI is an addition to the objective function such that the local search algorithm accepts solutions with `potential', i.e., solutions that are closer to the global optimum in some sense.
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known.