In this work, we consider combinatorial multi-agent optimization problems, i.e., problems presenting a combinatorial set of solutions, and each solution is evaluated through a vector. An element of the vector corresponds to the utility that an individual agent receives from the solution. Given potential conflicts, it is improbable that a single feasible solution will be optimal for all agents. Consequently, a relevant objective is to identify solutions that are fair to all agents. There are several approaches to defining fairness in the context of optimization problems, and here we focus on Lorenz-optimal solutions. However, in some cases, in addition to the search for a fair solution, an economic criterion comes into play, i.e., we also seek to find a least-cost solution. Since the optimal solution for the cost function is not necessarily fair (i.e., Lorenz-optimal in our case), our aim is to generate a Lorenz-optimal solution with minimum cost. We propose a new exact method to solve this problem, and apply it to the multi-agent assignment problem and to the multi-agent knapsack problem. Results show that the new method is much more efficient than a method based on a complete enumeration of Lorenz-optimal solutions.

We propose a new approach consisting in combining genetic algorithms and regret-based incremental preference elicitation for solving multi-objective combinatorial optimization problems with unknown preferences. For the purpose of elicitation, we assume that the decision maker's preferences can be represented by a parameterized scalarizing function but the parameters are initially not known. Instead, the parameter imprecision is progressively reduced by asking preference queries to the decision maker during the search to help identify the best solutions within a population. Our algorithm, called RIGA, can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function is linear in its parameters and that a (near-)optimal solution can be efficiently determined when preferences are known. Moreover, RIGA runs in polynomial time while asking no more than a polynomial number of queries. For the multi-objective traveling salesman problem, we provide numerical results showing its practical efficiency in terms of number of queries, computation time and gap to optimality.

In this paper, we develop a general interactive method to solve multi-objective combinatorial optimization problems with imprecise preferences. Assuming that preferences can be represented by a parameterized scalarizing function, we iteratively ask preferences queries to the decision maker in order to reduce the uncertainty over the preference parameters until being able to determine her preferred solution. To produce informative preference queries at each step, we generate promising solutions using the extreme points of the polyhedron representing the admissible preference parameters and then we ask the decision maker to compare two of these solutions (we propose different selection strategies). These extreme points are also used to provide a stopping criterion guaranteeing that the returned solution is optimal (or near-optimal) according to the decision maker's preferences. For the multi-objective spanning tree problem with a linear aggregation function, we provide numerical results to demonstrate the practical efficiency of our approach and we compare our results to a recent approach based on minimax regret, where preferences are asked during the construction of a solution. We show that better results are achieved by our method both in terms of running time and number of questions.

This article deals with the bi‐objective pollution‐routing problem (bPRP), a vehicle routing variant that arises in the context of green logistics. The two conflicting objectives considered are the minimization of the CO2 emissions and the costs related to driver's wages. A multi‐objective approach based on the two‐phase Pareto local search heuristic is employed to generate a good approximation of the Pareto front. During the first phase of the method, a first set of potentially efficient solutions is obtained by solving a series of weighted sum problems with an efficient heuristic originally developed to solve the single‐objective PRP. A dichotomous scheme is used to generate the different weight sets in an automatic way. In the second phase, the set is improved with an efficient Pareto local search (PLS) procedure. The use of PLS allows to limit the number of computational demanding weighted sum problems solved in the first phase, while keeping high‐quality results. Extensive computational experiments over existing benchmark instances show that the proposed approach leads to better results in less CPU time when compared to those obtained by state‐of‐the‐art methods.

In this paper, we propose a new method called ND-Tree-based update (ND-Tree) for the dynamic nondominance problem, i.e., the problem of online update of a Pareto archive composed of mutually nondominated points. It uses a new ND-Tree data structure in which each node represents a subset of points contained in a hyperrectangle defined by its local approximate ideal and nadir points. By building subsets containing points located close in the objective space and using basic properties of the local ideal and nadir points we can efficiently avoid searching many branches in the tree. ND-Tree may be used in multiobjective evolutionary algorithms and other multiobjective metaheuristics to update an archive of potentially nondominated points. We prove that the proposed algorithm has sublinear time complexity under mild assumptions. We experimentally compare ND-Tree to the simple list, Quad-tree, and M-Front methods using artificial and realistic benchmarks with up to ten objectives and show that with this new method substantial reduction of the number of point comparisons and computational time can be obtained. Furthermore, we apply the method to the nondominated sorting problem showing that it is highly competitive to some recently proposed algorithms dedicated to this problem.

We first present a method, called Two-Phase Pareto Local Search, to find a good approximation of the efficient set of the biobjective traveling salesman problem. In the first phase of the method, an initial population composed of an approximation of the extreme supported efficient solutions is generated. We use as second phase a Pareto Local Search method applied to all solutions of the initial population. We show that using the combination of these two techniques: good initial population generation and Pareto Local Search gives good results, without numerical parameters. As the computational time of the second phase grows exponentially according to the instances size, speed-up techniques are used to considerably reduce the computational time of the second phase. It makes it possible to find good approximation of the efficient set of large-scale biobjective traveling salesman problems, in a reasonable resolution time.