Handling Degeneracy in Multi-objective Transportation Problem: An Efficient Branch-and-Bound Algorithm

Abstract

In today’s competitive market, practically all models are designed to address transportation problems involving multiple, often conflicting, objectives, such as minimizing transportation cost, minimizing transportation time, maximizing reliability, minimizing environmental impact, maximizing social equity, and minimizing product deterioration. In this respect, this paper proposes a method to optimize a multi-objective transportation problem (MOTP). We developed a branch-and-bound-based algorithm coupled with a classical transportation method to find the non-dominated points in the criteria space, in a finite number of steps. The algorithm utilizes reduced costs of all the criteria cost matrices to define the promising regions that may contain
non-dominated points. This algorithm is strengthened by efficient bounds allowing us to prune a large number of nodes in the search tree and hence eliminate many dominated points. Efficient bounds further enhance the algorithm by pruning a large number of search tree nodes and eliminating dominated points. The suggested approach effectively addresses the non-degenerate case as well as the degenerate case, the latter of which, to our knowledge, has not been discussed in prior studies on MOTP. To handle degeneracy, we integrated the improved N-tree method into our approach. The effectiveness of our algorithm was assessed by comparing it to Isermann’s method for the non-degenerate case, where it was noticed that our approach gives better results. Additionally, computational experiments confirmed its efficiency in handling degenerate cases. Two numerical
examples are presented to illustrate the step-by-step application of the proposed method.