We introduce a novel characterization of the efficient solutions to the Multi-objective Assignment Problem (MAP), relying solely on Network Flow theory. This result establishes that the set of efficient assignments restricted to the first $k$ origin-destination pairs in the associated bipartite graph can be derived incrementally from the efficient solutions corresponding to the first $k-1$ pairs. We formalize this as a Generalized Optimality Construction Principle, which serves as the basis for the development of a new algorithm.
Building on this principle, we propose the Multi-objective Successive Shortest Path Algorithm, a fully combinatorial approach for solving the MAP using exclusively network flow techniques. A key computational challenge involves solving the Multi-objective One-to-One Shortest Path Problem with cost vectors that may contain negative components. We address this by employing a label-correcting path algorithm using global and soft local dominance relationship instead classical local dominance, ensuring that all efficient augmenting paths are correctly computed, thus enabling the identification of the maximal complete set of efficient assignments.
The algorithm’s behavior is illustrated through a detailed example. Additionally, we conduct computational experiments on benchmark instances from the literature to demonstrate the method’s effectiveness.
generalizing the successive shortest path algorithm to solve the multi-objective assignment problem
\(\)