A Min-Max Tchebycheff based Local Search Approach for MOMKP

The multi-objective multidimensional knapsack problem (MOMKP) which is one of the hardest multiobjective combinatorial optimization problems, presents a formal model for many real world problems. Its main goal consists in selecting a subset of items in order to maximize m objective functions with respect to q resource constraints. For that purpose, we present in this paper a resolution approach based on a Min-Max Tchebycheff iterated Local Search algorithm called Min-Max TLS. In this approach, we propose designing a neighborhood structure employing a permutation process to exploit the most promising regions of the search space while considering the diversity of the population. Therefore, Min-Max TLS uses Min-Max N(s) as a neighborhood structure, combining a Min-Extraction-Item algorithm and a Max-Insertion-Item algorithm. Moreover, in Min-Max TLS two Tchebycheff functions, used as a selection process, are studied: the weighted Tchebycheff (WT) and the augmented weighted Tchebycheff (AugWT). Experimental results are carried out with nine well-known benchmark instances of MOMKP. Results have shown the efficiency of the proposed approach in comparison to other approaches.