A survey and annotated bibliography of multiobjective combinatorial optimization (Q1841810)

The paper gives a structured overview of the field of MultiObjective Combinatorial Optimization (MOCO) with a focus on recent developments (since 1994) while referring to earlier survey articles for most of the previous work. After an introduction and formulation of the problem, including an outline of different notions of optimality, theoretical properties of MOCO problems are discussed. Solution methods applied to MOCO problems are reviewed, covering exact methods as well as approximation methods such as simulated annealing, tabu search, genetic algorithms and other recent developments. The subsequent annotated literature review is organized according to the combinatorial structure of MOCO problems and using a classification scheme based on four categories, namely the combinatorial structure, the type of objective function, the problem type and the suggested solution method. Problems included are shortest path problems, assignment problems, transportation and transshipment problems, network flow problems, spanning tree problems, matroids and matroid intersections, the travelling salesman problem, knapsack problems, location problems, set covering problems, and others.