EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5593 ISSN 1307-5543 – ejpam.com Published by New York Business Global Handling Degeneracy in Multi-objective Transportation Problem: An Efficient Branch-and-Bound Algorithm Zineb Mezali1,∗, Mohamed El-Amine Chergui1 1 Department of Operations Research, Faculty of Mathematics, USTHB University , Algiers, Algeria Abstract. In today’s competitive market, practically all models are designed to address trans- portation problems involving multiple, often conflicting, objectives, such as minimizing trans- portation 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 elimi- nating 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 ap- proach. 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. 2020 Mathematics Subject Classifications: 90C08,90C29 Key Words and Phrases: Transportation problem, multi-objective optimization, non-dominated point, branch-and-bound 1. Introduction The transportation problem (TP) is a fundamental optimization problem that has been extensively studied since its formulation by Hitchcock in 1941 [17]. It involves determining the optimal allocation of goods from various sources to multiple destinations to minimize transportation costs. Exact algorithms, such as the simplex method [9], and stepping ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5593 Email addresses: mezalizineb@gmail.com (Z. Mezali), mchergui@usthb.dz (M.E.A.Chergui) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 2 of 21 stone algorithm [8], as well as heuristics ([31],[16], [20], [21], [23], [2]) have been developed to solve the TP efficiently. Multi-objective transportation problem (MOTP) considers multiple conflicting objec- tives, such as minimizing transportation costs, delivery times, and maximizing profits. Various approaches, including exact methods and heuristic algorithms, have been pro- posed to identify efficient solutions for the MOTP. These approaches can be classified into three main categories. The first category comprises methods designed to identify all efficient solutions, including those based on linear programming ([35], [10], [5], [19], [34], [11]) and dynamic programming ([13], [12]). The second category includes methods that focus on finding a single efficient solution or compromise solution, such as goal program- ming ([6], [25], [37], [27], [30]), interactive methods [32], lexicographic optimization ([36], [28]), the minimize distance method ([1], [22] ), and the decomposition approach ([3],[4]). Finally, the third category encompasses methods that compute a finite approximation of the non-dominated set, such as heuristic approaches ([14], [29], [40], [41], [26], [39]). While the existing literature on MOTP offers a variety of approaches, a common lim- itation is the lack of specific strategies to handle degeneracy that can pose significant challenges in identifying non-dominated points. To overcome this limitation, we propose a novel exact method based on the branch-and-bound principle that incorporates a spe- cialized procedure to handle degeneracy. In addition, the branch-and-bound method effec- tively explores the criteria space by eliminating states that cannot lead to non-dominated points. This is achieved through fathoming rules. The structure of this article is as follows: in section 2, we provide some definitions and notations, section 3 is devoted to a brief description of the method and a presentation of the algorithm that we named MOTP-Algorithm, which is followed by a numerical example to understand the different steps of the proposed method to solve the MOTP problem. Section 4 is about some theoretical results and proofs. Moreover, in section 5, our algorithm has been tested on a set of non-degenerate and degenerate instances, and then we terminate with a conclusion in section 6. 2. Definitions and notations We consider the following Mutli-Objective Transportation Problem (MOTP): min Zk(X) = ∑ i∈I ∑ j∈J ckijxij , ∀k ∈ K ∑ j∈J xij = ai, ∀i ∈ I ∑ i∈I xij = dj , ∀j ∈ J xij ≥ 0, ∀i ∈ I, j ∈ J (1) (2) (3) (4) Let I = {1, ...,m}, J = {1, ..., n}, and K = {1, ..., r} represent the sets of sources, destinations, and objectives, respectively. The cost matrix ck, for each objective k is Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 3 of 21 defined as ck = (ckij) ∀i ∈ I, ∀j ∈ J . We assume that the supply at source i is ai ≥ 0 and the demand at destination j is dj ≥ 0. Additionally, the total supply must equal the total demand ( ∑ i∈I ai = ∑ j∈J dj), which is necessary and sufficient for a transportation problem to have a feasible solution. Let D be the set of feasible solutions of the MOTP problem, which is assumed to be nonempty and compact, and Z(D) its image set in the criteria space Rr. Definition 1. A basic feasible solution to MOTP is a feasible solution that contains no more than m + n – 1 positive basic variables. Let X = (xij), i ∈ I, j ∈ J be a basic feasible solution to MOTP, the image of X in the criteria space is denoted by Z(X) such that Z(X) = ( Z1(X), . . . , Zr(X) ) . Definition 2. A basic feasible solution X = (xij), i ∈ I, j ∈ J , to MOTP is efficient if there is no other basic feasible solution Y = (yij) of MOTP such that: Zk(Y ) ≤ Zk(X) for all criteria k ∈ K, and Zk(Y ) < Zk(X) for at least one criterion k ∈ K. Definition 3. An efficient solution X = (xij), i ∈ I, j ∈ J is said alternative if there exists an efficient solution Y = (yij) such that: Z(Y ) = Z(X). Definition 4. The image of an efficient solution in the criteria space is called a non- dominated point. Definition 5. A non-degenerate solution is a basic feasible solution that has exactly m+ n− 1 positive basic variables. Definition 6. A degenerate solution is a basic feasible solution that contains less than m + n − 1 positive basic variables. In other words, one or more basic variables are zero- valued. Throughout this present paper, SND refers to the non-dominated points set in Z(D) and DE the efficient solutions set in D. Let (P0) be the transportation problem with c0 = (c0ij), i ∈ I, j ∈ J , being the sum of all criteria cost matrices: (P0) { min ∑ i∈I ∑ j∈J c 0 ijxij (xij)i∈I,j∈J ∈ D (5) The generation of the non-dominated points of MOTP is based on the resolution of the mono-criterion transport problem (P0) with the criterion c0, knowing that all the op- erations performed on the cost matrix of (P0) are also applied simultaneously to cost matrices of all the other criteria. A slave program is performed to determine whether a basic feasible solution of (P0) obtained at step l of our MOTP problem’s resolution approach, Xl = (xlij), i ∈ I, j ∈ J , is efficient. It is given as follows: (PXl )  max ∑ k∈K ek∑ i∈I ∑ j∈J c k ijxij + ek = ∑ i∈I ∑ j∈J c k ijx l ij ∀k ∈ K (xij)i∈I,j∈J ∈ D ek ≥ 0 ∀k ∈ K (6) Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 4 of 21 The optimal objective value of (PXl ) is 0 if and only if Xl is efficient (refer [7]). We associate the following parameters with any basic feasible solution Xl = (xlij), i ∈ I, j ∈ J : Bl: the set of indices of basic variables. Nl: the set of indices of non-basic variables. Hl: the set of the descent directions of the criteria at Xl, except the criterion c0 which is initially at the minimum. H1 l = {(i, j) ∈ Nl | ĉ0ij ≥ 0}. H2 l = {(i, j) ∈ Nl | ∃k ∈ K | ĉkij < 0}. H3 l = {(i, j) ∈ (H1 l ∩H2 l ) | ∃(s, t) ∈ (H1 l ∩H2 l ) | ∑ k∈K ĉkstxst ≤ ∑ k∈K ĉkijxij ∀k ∈ K∧∃k ∈ K | ∑ k∈K ĉkstxst < ∑ k∈K ĉkijxij}∪{(i, j) ∈ (H1 l ∩H2 l ) | ∃(s, t) ∈ (H1 l ∩H2 l ) | ∑ k∈K ĉkstxst =∑ k∈K ĉkijxij ∀k ∈ K}. Hl = (H1 l ∩H2 l ) \H3 l . ĉkij : the reduced costs of the non-basic variables determined using the following equations: ĉkij = ckij − (uki + vkj ), ∀(i, j) ∈ Nl, ∀k ∈ {0} ∪K (7) (uki , v k j ): the dual variables of the constraints (2) and (3) respectively for the basis Bl so that: (uki + vkj ) = ckij , ∀(i, j) ∈ Bl, ∀k ∈ {0} ∪K (8) The system of equations (8) is solved by substituting : uk1 = 0, ∀k ∈ {0} ∪K. MOTP is represented by a table (refer Table 1) having m rows and n columns. Each cell (i, j) at the intersection of row i and column j contains a vector of the criteria ckij , the value of the variable xij , referred to as allocation, and a vector of the reduced costs ĉkij . A cell with a positive xij value is called an occupied cell, while a cell with a zero xij value is called an unoccupied cell. Furthermore, the MOTP table is delimited by a column containing the supplies ai, a row containing the demands dj, and the last row and column containing the vector of uki values and vkj values respectively, for all k ∈ {0} ∪K. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 5 of 21 d1 . . . dn ( u0i , ..., u r i ) a1 ( c011, ..., c r 11 ) x11( ĉ011, ..., ĉ r 11 ) . . . ( c01n, ..., c r 1n ) x1n( ĉ01n, ..., ĉ r 1n ) ( u01, ..., u r 1 ) . . . . . . . . . . . . . . . am ( c0m1 . . . c r m1 ) xm1( ĉ0m1, ..., ĉ r m1 ) . . . ( c0mn, ..., c r mn ) xmn( ĉ0mn, ..., ĉ r mn ) ( u0m, ..., urm ) v0j ... vrj  v01 ... vr1  . . . v0n ... vrn  Table 1: MOTP table Using the vector notations: x = ( x11, x12, . . . x1n, x21, . . . , x2n, . . . , xm1, . . . , xmn )T , c =  c111 c112 . . . c11n c121 . . . c12n . . . c1m1 . . . c1mn c211 c212 . . . c21n c221 . . . c22n . . . c2m1 . . . c2mn ... ... ... ... ... ... ... ... ... ... cr11 cr12 . . . cr1n cr21 . . . cr2n . . . crm1 . . . crmn  , b = ( a1, a2, . . . am, d1, d2, . . . dn )T MOTP can be written as follows:  min cx Ax = b x ≥ 0 (9) ABl : regular matrix of columns of A corresponding to basic variables. ANl : matrix of columns of A corresponding to non-basic variables. P (Bl): pivot tableau of the form shown in Table 2, whereW denotes the matrix (ABl)−1ANl and x symbolizes the basic feasible solution, i.e., x = (ABl)−1b. Bl Nl x W Table 2: pivot tableau P (Bl) Definition 7. Let x be a degenerate solution, the column W.j = (ABl)−1ANl .j of the pivot tableau P (Bl) is called a transition column if it has positive entries in the rows where x equals zero and has at least one positive entry in a row where x is non-zero and therefore allows the degenerate solution to be left by a pivot step. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 6 of 21 Definition 8. A pivot tableau with at least one transition column is called a transition tableau. 3. Method and Algorithm This section is devoted to the illustration of the ideas developed in the framework of the exact method that we propose for the MOTP problem, exploiting the particularities of the classical transport problem. 3.1. Principle of the method A branch-and-bound-based method is described to find the set SND of non-dominated points of the MOTP problem. At the beginning of the search tree, the algorithm starts with the optimization of the cost matrix criterion c0, which corresponds to solving the problem (P0), through the Modified Distribution Stepping-Stone (MODI) method, also known as the method of multipliers (refer [38]), to obtain an optimal solution X0 for (P0), which is an efficient solution for the MOTP problem. The same MODI operations are alson applied to all cost matrix criteria to evaluate them at X0 , and the set SND is updated. Using the reduced cost matrices, we define the set H0 of the descent directions of the criteria at X0, except the criterion k = 0, which must increase, knowing that it was initially at the minimum. In this step, |H0| nodes are created. A basic feasible solution Xl is generated at each node l of the search tree by introducing a non-basic variable xij into the current basis such that (i, j) ∈ Hf and f is the parent node of node l, using the transportation problem’s pivoting procedure (refer [38]). If at any node l, Xl is degenerate, we solve the degeneracy as described in section 3.2 below. Finally, the efficiency test stated in (6) is used, the SND set is then updated, and the process is repeated until all nodes that have been created are fathomed. 3.2. Solving degeneracy in MOTP problem In the case of a single objective transportation problem with m origins and n destina- tions, if a basic feasible solution X is degenerate, the problem is said to be a degenerate transportation problem. To remove degeneracy, we utilize a fictitious quantity e, this quantity is assigned to one or more unoccupied cells with the minimum transportation costs, to make (m + n − 1) allocations (refer [33]). However, in the case of the MOTP problem, to find the non-dominated points neighboring a degenerate solution X, we must first solve the degeneracy, i.e., find out how to determine the cells to which e can be assigned to compute the reduced costs and identify the set Hl. A naive approach would be to enumerate all the possible cases to allocate e which is equivalent to treating all the possible bases associated with X and it can be very costly in time and memory space because one degenerate solution has more than one basis (refer [24]), and some of these bases don’t lead to a distinct solution. Starting from the pivot tableau of a degenerate solution, the idea suggested to solve the degeneracy in MOTP problem is to use the im- proved N-tree algorithm (refer [15]) to find the transition tableaux associated with it, i.e., Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 7 of 21 tableaux that possess at least one pivot that will yield a distinct solution and thus enables us to leave the degenerate solution. Next, each degenerate solution associated with each of the transition tableaux is put in the MOTP table by replacing the null basic variables of that solution with e, then we proceed as the non-degenerate case. All the ideas developed above are structured in the following algorithm named MOTP- Algorithm. 3.3. MOTP-Algorithm The steps of the proposed MOTP-Algorithm are as follows: Algorithm 1. MOTP-Algorithm Input: MOTP table. Output: SND (the non-dominated points set), DE (the efficient solutions set) Step 0: Initialize: DE := ∅, SND := ∅, l := 0. Step 1: Find X0, the optimal solution to (P0), and put it in the MOTP table. Update: DE := DE ∪ {X0}, SND := SND ∪ {Z(X0)}. Step 2: If Xl is degenerate, go to Step 3. Else, go to Step 4.2. Step 3: Apply the improved N-tree Algorithm (refer to [15]) to determine the set Tl of transition tables associated with Xl. Step 4: For each transition table T p l ∈ Tl, ∀p = 1, ..., |Tl|: 4.1 Let Xp l be the basic feasible solution associated with T p l and assign the value e to each null basic variable, then put the resulting solution in the MOTP table. 4.2 Determine the set Hl and create |Hl| nodes. 4.3 While there exists a non-fathomed node: 4.3.1 Set l := l + 1, use Depth First Search (DFS) to select node l, and let xij be a non-basic variable such that (i, j) ∈ Hl−1. 4.3.2 Consider the MOTP table of node l − 1 and enter the non-basic variable xij into the basis. Let Xl be the obtained basic feasible solution at node l. 4.3.3 Efficiency Test of Xl: If there exists k ∈ {1, ..., r} such that ĉkij > 0, ∀(i, j) ∈ Nl (i.e., Xl is the unique optimal solution according to criterion k), then Xl is efficient. Otherwise, solve the linear problem (PXl ). 4.3.4 If Xl is efficient, go to Step 4.3.5. Else, node l is fathomed. 4.3.5 If Xl ∈ DE or Hl = ∅, node l is fathomed. 4.3.6 If Xl has not been visited, update: DE := DE∪{Xl}, SND := SND∪{Z(Xl)}. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 8 of 21 Step 5: If Xl is degenerate, go to Step 3. Else, go to Step 4.2. In the following, we unroll our MOTP-Algorithm in the non-degenerate and degenerate cases. Example 1. Let’s consider the following non-degenerate instance for the MOTP problem with (m,n, r) = ( 3, 3, 3 ), c1 = ( 3 10 2 2 9 4 10 8 2 ) , c2 = ( 1 7 3 4 6 6 7 5 8 ) , c3 = ( 8 7 4 6 2 1 8 6 2 ) , a = ( 1 9 2 ) , d = ( 5, 3, 4 ). Then, the matrix c0 is given by : c0 = ( 12 24 9 12 17 11 25 19 12 ) . Step 0 : DE = ∅, SND = ∅. At node 0, the optimal solution X0 according to c0 is presented in Table 3. d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 (12, 3, 1, 8) 0 (2, 3, 0,−1) (24, 10, 7, 7) 0 (9, 3, 4, 2) (9, 2, 3, 4) 1 ( 0, 0, 0, 0 ) a2 = 9 (12, 2, 4, 6) 5 (17, 9, 6, 2) 3 (11, 4, 6, 1) 1 ( 2, 2, 3,−3 ) a3 = 2 (25, 10, 7, 8) 0 (12, 10, 1, 1) (19, 8, 5, 6) 0 (1, 1,−3, 3) (12, 2, 8, 2) 2 ( 3, 0, 5− 2 )  v0j v1j v2j v3j   10 0 1 9   15 7 3 5   9 2 3 4  Z(X0) = ( 47, 63, 45 ) X0 = 0 0 1 5 3 1 0 0 2  Table 3: Optimal solution X0 of (P0) X0 is an efficient solution because it’s a unique optimal solution according to c1. DE := DE ∪ {X0}, SND := SND ∪ {Z(X0)}, H0 = {(1, 1), (3, 2)}. So x11 enters the basis and we obtain a basic feasible solution X1 at node 1, in Table 4. X1 is an efficient solution because it’s a unique optimal solution according to c3. DE := DE ∪ {X1}, SND := SND1 ∪ {Z(X1)}, H1 = {(3, 2)}. The variable x32 enters the basis and we obtain a basic feasible solution X2 at node 2, in Table 5. By solving P (X2), we find that X2 is efficient, DE := DE ∪ {X2}, SND := SND ∪ {Z(X2)} and H2 = {(3, 1)}. So x31 enters the basis and we obtain a basic feasible solution X3 at node 3, in Table 6. By solving P (X3), we find that X3 is not efficient, node 3 is then fathomed. The variable x32 enters the basis and we obtain at node 4 a basic feasible solution X4 in Table 7. By solving P (X4), we find that X4 is efficient, DE := DE ∪ {X4}, SND := SND ∪ {Z(X4)} and H4 = {(1, 1), (3, 1)}. If x11 enters the basis, we obtain the solution X5 such that X5 = X2 at node 5 and since this efficient solution is already visited, node 5 is fathomed. Hence, x31 enters the basis and we obtain at node 6 a basic feasible solution X6 in Table 8. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 9 of 21 d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 ( 12, 3, 1, 8 ) 1 ( 24, 10, 7, 7 ) 0( 7, 0, 4, 3 ) ( 9, 2, 3, 4 ) 0 (−2,−3, 0, 1) ( 0, 0, 0, 0 ) a2 = 9 ( 12, 2, 4, 6 ) 4 ( 17, 9, 6, 2 ) 3 (11, 4, 6, 1) 2 ( 0,−1, 3,−2 ) a3 = 2 ( 25, 10, 7, 8 ) 0( 12, 10, 1, 1 ) ( 19, 8, 5, 6 ) 0( 1, 1,−3, 3 ) ( 12, 2, 8, 2 ) 2 ( 1,−3, 5− 1 )  v0j v1j v2j v3j   12 3 1 8   17 10 3 4   11 5 3 3  Z(X1) = ( 50, 63, 44 ) X1 = 1 0 0 4 3 2 0 0 2  Table 4: Solution X1 at node 1 d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 ( 12, 3, 1, 8 ) 1 ( 24, 10, 7, 7 ) 0( 7, 0, 4, 3 ) ( 9, 2, 3, 4 ) 0( −2,−3, 0, 1 ) ( 0, 0, 0, 0 ) a2 = 9 ( 12, 2, 4, 6 ) 4 ( 17, 9, 6, 2 ) 1 ( 11, 4, 6, 1 ) 4 ( 0,−1, 3,−2 ) a3 = 2 ( 25, 10, 7, 8 ) 0( 11, 9, 4,−2 ) ( 19, 8, 5, 6 ) 2 ( 12, 2, 8, 2 ) 0( −1,−1, 3,−3 ) ( 2,−2, 2, 2 )  v0j v1j v2j v3j   12 3 1 8   17 10 3 4   11 5 3 3  Z(X2) = ( 52, 57, 50 ) X2 = 1 0 0 4 1 4 0 2 0  Table 5: Solution X2 at node 2 By solving P (X6), we find that X6 is not efficient, node 6 is then fathomed. The MOTP-Algorithm terminates since all created nodes are fathomed and the set of non-dominated points is: SND = {(47, 63, 45), (50, 63, 44), (52, 57, 50), (49, 57, 51)}. The search tree corresponding to example 1 is shown in Figure 1. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 10 of 21 d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 (12, 3, 1, 8) 1 (24, 10, 7, 7) 0 (7, 0, 4, 3) (9, 2, 3, 4) 0 (−2,−3, 0, 1) ( 0, 0, 0, 0 ) a2 = 9 (12, 2, 4, 6) 2 (17, 9, 6, 2) 3 (11, 4, 6, 1) 4 ( 0,−1, 3,−2 ) a3 = 2 (25, 10, 7, 8) 2 (19, 8, 5, 6) 0 (−11,−9,−4, 2) (12, 2, 8, 2) 0 (−12,−10,−1,−1) ( 13, 7, 6, 0 )  v0j v1j v2j v3j   12 3 1 8   17 10 3 4   11 5 3 3  Z(X3) = (70, 65, 46) X3 = 1 0 0 2 3 4 2 0 0  Table 6: Solution X3 at node 3 d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 (12, 3, 1, 8) 0 (2, 3, 0− 1) (24, 10, 7, 7) 0 (9, 3, 4, 2) (9, 2, 3, 4) 1 ( 0, 0, 0, 0 ) a2 = 9 (12, 2, 4, 6) 5 (17, 9, 6, 2) 1 (11, 4, 6, 1) 3 ( 2, 2, 3,−3 ) a3 = 2 (25, 10, 7, 8) 0 (11, 9, 4,−2) (19, 8, 5, 6) 2 (12, 2, 8, 2) 0 (−1,−1, 3,−3) ( 4, 7, 6, 0 )  v0j v1j v2j v3j   10 0 1 9   15 7 3 5   9 2 3 4  Z(X4) = (49, 57, 51) X4 = 0 0 1 5 1 3 0 2 0  Table 7: Solution X4 at node 4 X0 X1 H1 = {(3, 2)} X2 H2 = {(3, 1)} X3 dominated point H0 = {(1, 1), (3, 2)} X4 H4 = {(1, 1), (3, 1)} X5 X5 ∈ DE X6 dominated point Figure. 1. Search tree 1 Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 11 of 21 d1 = 5 d2 = 3 d3 = 4 ( u0i , u 1 i , u 2 i , u 3 i ) a1 = 1 (12, 3, 1, 8) 0 (2, 3, 0− 1) (24, 10, 7, 7) 0 (9, 3, 4, 2) (9, 2, 3, 4) 1 ( 0, 0, 0, 0 ) a2 = 9 (12, 2, 4, 6) 3 (17, 9, 6, 2) 3 (11, 4, 6, 1) 3 ( 2, 2, 3,−3 ) a3 = 2 (25, 10, 7, 8) 2 (19, 8, 5, 6) 0 (−11,−9,−4, 2) (12, 2, 8, 2) 0 (−12,−10,−1,−1) ( 15, 10, 6,−1 )  v0j v1j v2j v3j   10 0 1 9   15 7 3 5   9 2 3 4  Z(X6) = (67, 65, 47) X6 = 0 0 1 3 3 3 2 0 0  Table 8: Solution X6 at node 6 Example 2. Let consider the following instance for the MOTP problem where degeneracy occurs with (m,n, r) = ( 3, 3, 2 ), c1 = ( 3 3 3 5 7 2 6 8 3 ) , c2 = ( 4 1 1 5 3 10 6 9 8 ) , a = ( 5 2 3 ) , d = ( 2, 4, 4 ). Let c0 = ( 7 4 4 10 10 12 12 17 11 ) . Step 0: DE = ∅, SND = ∅. At node 0 the optimal solution X0 is presented in Table 9. d1 = 2 d2 = 4 d3 = 4 ( u0i , u 1 i , u 2 i ) a1 = 5 (7, 3, 4) 1 (4, 3, 1) 4 (4, 3, 1) 0 (0, 3,−8) ( 0, 0, 0 ) a2 = 2 (10, 5, 5) 1 (10, 7, 3) 0 (4, 2, 1) (12, 2, 10) 1 ( 3, 2, 1 ) a3 = 3 (12, 6, 6) 0 (3, 0, 3) (17, 8, 9) 0 (12, 2, 9) (11, 3, 8) 3 ( 2, 3,−1 ) v0j v1j v2j  7 3 4  3 3 1  9 0 9  Z(X0) = (31, 47) X0 = 1 4 0 1 0 1 0 0 3  Table 9: Optimal solution X0 of (P0) Check degeneracy: X0 is non degenerate. By solving P (X0), we find that X0 is efficient, DE := DE∪{X0}, SND := SND∪{Z(X0)} and H0 = {(1, 3)}. So x13 enters the basis and we get at node 1, the basic feasible solution X1 = ( 0 4 1 2 0 0 0 0 3 ) , Z(X1) = (34, 39). By solving P (X1), we find that X1 is efficient, DE := DE ∪ {X1}, SND := SND ∪ Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 12 of 21 {Z(X1)}. Check degeneracy: X1 is degenerate then using the improved N-tree Algorithm, we find the transition tables shown in Table 10, hence T1 = {T 1 1 , T 2 1 }. B1 1 x11 x22 x31 x32 x11 x12 0 1 0 1 4 x13 1 −1 0 −1 1 x21 1 0 1 0 2 x23 −1 1 −1 0 0 x33 0 0 1 1 3 (a) T 1 1 B2 1 x11 x23 x31 x32 x21 x12 1 −1 1 1 4 x13 0 1 −1 −1 1 x21 1 0 1 0 2 x22 −1 1 −1 0 0 x33 0 0 1 1 3 (b) T 2 1 Table 10: Resulting transition tables from N-tree Algorithm In T 1 1 , the basic variable x23 = 0, then we assign the value e to the cell (2, 3) and the resulting solution X1 1 is shown in Table 11. d1 = 2 d2 = 4 d3 = 4 ( u0i , u 1 i , u 2 i ) a1 = 5 (7, 3, 4) 0 (0,−3, 8) (4, 3, 1) 4 (4, 3, 1) 1 ( 0, 0, 0 ) a2 = 2 (10, 5, 5) 2 (10, 7, 3) 0 (4, 5,−7) (12, 2, 10) e ( 3,−1, 9 ) a3 = 3 (12, 6, 6) 0 (3, 0, 3) (17, 8, 9) 0 (12, 5, 1) (11, 3, 8) 3 ( 2, 0, 7 ) v0j v1j v2j   7 6 −4  3 3 1  9 3 1  Z(X1 1 ) = (34, 39) X1 1 = 0 4 1 2 0 e 0 0 3  Table 11: Solution X1 1 at node 1 H1 1 = {(1, 1)}. If x11 enters the basis we obtain at node 2, the solution X2 = X0 which is already visited, then node 2 is fathomed. In T 2 1 , the basic variable x22 = 0, then we assign the value e to the cell (2, 2) and the resulting solution X2 1 is shown in Table 12. H2 1 = {(3, 1)}, so x31 enters the basis and we obtain at node 3 the basic feasible solution X3 in Table 13. Checking degeneracy: X3 is non degenerate. Since X3 is a unique optimal solu- tion according to c2, then X3 is efficient, DE := DE ∪ {X3}, SND := SND ∪ {Z(X3)}, H3 = ∅, then node 3 is pruned. The MOTP-Algorithm terminates because all created nodes are fathomed and the set of Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 13 of 21 d1 = 2 d2 = 4 d3 = 4 ( u0i , u 1 i , u 2 i ) a1 = 5 (7, 3, 4) 0 (4, 2, 1) (4, 3, 1) 4 (4, 3, 1) 1 ( 0, 0, 0 ) a2 = 2 (10, 5, 5) 2 (10, 7, 3) e (12, 2, 10) 0 (-4,-5,7) ( 3,−1, 9 ) a3 = 3 (12, 6, 6) 0 (7, 5,−4) (17, 8, 9) 0 (12, 5, 1) (11, 3, 8) 3 ( 2, 0, 7 ) v0j v1j v2j   7 6 −4  3 3 1  9 3 1  Z(X2 1 ) = (34, 39) X2 1 = 0 4 1 2 e 0 0 0 3  Table 12: Solution X2 1 at node 1 d1 = 2 d2 = 4 d3 = 4 ( u0i , u 1 i , u 2 i ) a1 = 5 (7, 3, 4) 0 (−3,−3, 5) (4, 3, 1) 2 (4, 3, 1) 3 ( 0, 0, 0 ) a2 = 2 (10, 5, 5) 0 (−7,−5, 4) (10, 7, 3) 2 (12, 2, 10) 0 (−4,−5, 7) ( 7, 4, 2 ) a3 = 3 (12, 6, 6) 2 (17, 8, 9) 0 (12, 5, 1) (11, 3, 8) 1 ( 2, 0, 7 ) v0j v1j v2j   10 6 −1  3 3 1  9 3 1  Z(X3) = (44, 31) X3 = 0 2 3 0 2 0 2 0 1  Table 13: Solution X3 at node 3 non-dominated points is: SND = {(31, 47), (34, 39), (44, 31)} and the search tree corre- sponding to example 2 is shown in Figure 2. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 14 of 21 X0 H0 = {(1, 3)} X1 X1 1 H1 1 = {(1, 1)} X2 X2 ∈ DE X2 1 H2 1 = {(3, 1)} X3 H3 = ∅ Figure. 2. Search tree 2 4. Theoretical Results The following results are established to support different steps of the MOTP-Algorithm. Lemma 1. Let Xl be a basic feasible solution of MOTP at a node l of the MOTP- Algorithm’s search tree, if Z(Xl) is a dominated point then node l is fathomed. Proof. Each couple of efficient solutions of MOTP is joined by a chain (refer [19]), this means that there is a sequence of intermediate efficient solutions (forming a chain) connecting any two efficient solutions, hence if Z(Xl) is a dominated point, any non- explored efficient solution could be reached by following the chain of intermediate efficient solutions. This concludes the proof. Theorem 1. Every optimal solution for problem (P0) is an efficient solution for MOTP. Proof. Assume that X is an optimal solution of (P0), but not an efficient solution for MOTP. This implies that there exists a feasible solution Y that dominates X, that is, Zi(Y ) ≤ Zi(X), ∀i ∈ {1, ..., r} and there exists j ∈ {1, ..., r} such that Zj(Y ) < Zj(X). When we sum up both sides of these inequalities, we get Z1(Y ) + . . .+Zr(Y ) < Z1(X) + . . .+Zr(X), this contradicts the fact that X is optimal for (P0). Hence, X is an efficient solution for MOTP. Theorem 2. If X1 l is a basic feasible solution of MOTP at a node l of the MOTP- Algorithm’s search tree, and H1 l is empty, then the node l is pruned. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 15 of 21 Proof. If H1 l is empty, then ĉ0ij < 0, ∀(i, j) ∈ Nl. The criterion c0 will decrease in all directions in the set Nl. Knowing that c0 was initially at the optimum and since we only consider increasing directions of c0, then after pivoting, the resulting basic feasible solution at the child node l + 1 will already be visited, therefore node l is pruned. Theorem 3. If Xl is a basic feasible solution of MOTP at a node l of the MOTP- Algorithm’s search tree, and H2 l is empty, then node l is pruned. Proof. Suppose that H2 l is empty and let Xm be a basic feasible solution obtained at the child node m, m = l + 1, then there are two cases: Case 1: If ĉkij ≥ 0, ∀k ∈ K with at least a strict inequality, then we have Z(Xm) = Z(Xl) + ∑ k∈K ĉkijxij , where ∑ k∈K ĉkijxij > 0. Then, Z(Xl) ≤ Z(Xm) with at least a strict inequality, so Z(Xm) is a dominated point and by the lemma 1, the node l is fathomed. Case 2: If ĉkij = 0, ∀k ∈ K then Z(Xm) = Z(Xl) which means that Xm is an alternative solution to Xl. And a consequence of Theorem 2 and Theorem 3 is the statement in the next corollary. Corollary 1. If the set Hl is empty, then corresponding feasible solutions set at the node l doesn’t contain efficient solutions. Proof. If Hl is empty, then H1 l ∩H2 l is empty. The case corresponding to one of the two sets is empty is proved in Theorems 2 and 3. If both sets are empty then, ∃(i, j) ∈ Nl such that ĉ0ij < 0 in which case any pivoting in this direction brings us back to a vertex already visited (refer Theorem 2), and ∃(i, j) ∈ Nl such that ĉkij >= 0, ∀k ∈ K in which case any pivoting in this direction leads us to a vertex which is not efficient (refer Theorem 3). Theorem 4. Let Xl be a basic feasible solution of MOTP at a node l of the MOTP- Algorithm’s search tree, then any basic feasible solution obtained at the child node l + 1 by entering a non-basic cell(i, j) ∈ H3 l into basis is either not efficient or an alternative solution. Proof. Suppose that (i, j) ∈ H3 l and let Xl be a basic feasible solution corresponding to a parent node l then using the definition of the set H3 l , we distinguish two cases: Case 1: let Z(Xij) and Z(Xst) be the criterion vector of obtained basic feasible solution if (i, j) and (s, t) enters the basis, respectively. Then Z(Xij) = Z(Xl) + ∑ k∈K ĉkijxij and Z(Xst) = Z(Xl) + ∑ k∈K ckstxst. As ∑ k∈K ĉkstxst ≤ ∑ k∈K ĉkijxij ,∀k ∈ K, with at least a strict inequality, then Z(Xst) ≤ Z(Xij), with at least a strict inequality, hence Xij is not an efficient solution. Case 2: If ĉkstxst = ĉkijxij , ∀k ∈ K, then Z(Xst) = Z(Xij), hence Xij is an alternative solution. Theorem 5. MOTP-Algorithm converges toward the set of non-dominated points of MOTP in a finite number of steps. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 16 of 21 Proof. D is a compact feasible region with a finite number of basic feasible solutions. In addition, at each node l of the search tree, three fathoming rules were applied: the first when a dominated point is found, the second when the set Hl is empty in other words the solution Xl is an ideal point since no criterion can be minimized and the third when an efficient solution has already been determined, hence MOTP’s non-dominated points set is returned after a finite number of iterations. 5. Computational results and comparative study This section contains a summary of the experimental results achieved while implement- ing both approaches, MOTP-Algorithm and Isermann’s method, on an Intel(R) Core (TM) i5-7300U CPU @ 2.60GHz 2.70GHz and 8GB RAM processor computer, we carried out the numerical implementation using MATLAB R2015 software. None of the optimization packages are used and all of the involved functions are programmed. 5.1. Data structure Assuming that m = n, ten instances of each triplet (m,n, r) are randomly generated, with m and n values in{10,11,12,15,20,25,30}, the number of criteria r in {3,4,5}, the ck coefficients are in in [1, 100] and the coefficients of a and d are in [1, 30]. For the non-degenerate case, MOTP-Algorithm is compared to Isermann’s method (refer [19]). The obtained results are shown in Table 14. Instance MOTP-Algorithm CPU(s) Isermann method CPU(s) SND m n r average min max average min max average min max 10 10 3 0.07 0.04 0.14 0.14 0.06 0.29 20.20 11.00 33.00 4 0.74 0.24 1.30 1.40 0.41 3.70 66.80 30.00 106.00 5 7.35 4.47 11.75 15.94 12.93 17.61 420.80 302.00 628.00 11 11 3 0.09 0.03 0.18 0.20 0.05 0.30 15.60 10.00 22.00 4 1.92 1.03 2.90 3.68 0.67 8.13 145.00 92.00 198.00 5 16.40 7.28 28.09 26.28 11.77 39.84 649.40 393.00 950.00 12 12 3 0.15 0.03 0.27 0.43 0.04 1.40 31.80 9.00 58.00 4 1.97 0.64 4.27 2.17 0.26 5.87 136.60 74.00 252.00 5 33.97 12.19 72.46 85.88 21.16 252.84 871.20 450.00 1440.00 15 15 3 0.15 0.03 0.27 0.26 0.03 0.64 25.00 7.00 39.00 4 4.47 3.47 6.23 8.75 6.28 10.30 213.80 180.00 265.00 5 310.46 186.66 678.24 492.60 359.50 836.53 2444.20 1755.00 4033.00 20 20 3 1.54 0.18 6.76 3.03 0.32 13.60 123.40 21.00 513.00 4 64.62 17.65 192.83 362.26 77.59 471.60 874.00 407.00 2058.00 5 4013.60 1179.10 7469.1 4679.35 1336.64 8538.04 7025.40 4014.00 9795.00 25 25 3 16.94 0.39 81.39 70.00 0.52 345.73 472.20 31.00 2165.00 4 1635.78 206.35 6963.50 5409.66 288.24 13466.44 4066.00 1495.00 12663.00 30 30 3 157.50 96.96 199.02 163.22 97.68 229.37 147.00 55.00 199.00 Table 14: Results for non-degenerate instances Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 17 of 21 The approach is also tested for the degenerate case such that for each triplet (m,n, r), five instances were generated where both m and n values are in {4, 5, ..., 15}, the number of criteria r in {3, 4, 5} and the ck coefficients are in [1, 100], the coefficients of a and d are in [1, 30], with a < m ∗ n (see Theorem 1 in [18]). Table 15 summarizes the acquired results. 5.2. Results analysis for the non-degenerate case We can notice in general that the CPU(s) time and the number of non-dominated points of the MOTP-Algorithm increase on average with the size of the instance (m,n, r), especially with the criteria number r, for non-degenerate instances. Due to this, we did not perform the computations for r = 5 from (m,n, r) = (25, 25, 5): • For r = 3: – minimum average: CPU = 0.07 s and SND = 20.20 for (m,n) = (10, 10), – maximum average: CPU = 157.50 s and SND = 147 for (m,n) = (30, 30). • For r = 4: – minimum average: CPU = 0.74 s and SND = 66.80 for (m,n) = (10, 10), – maximum average: CPU = 1635.78 s and SND = 4066 for (m,n) = (25, 25). • For r = 5: – minimum average: CPU = 7.35 s and SND = 420.80 for (m,n) = (10, 10), – maximum average: CPU = 4013.60 s and SND = 7025.40 for (m,n) = (20, 20). Among the 180 instances solved for the non-degenerate case, the results show that MOTP- Algorithm outperforms Isermann’s method for r = 3, r = 4 and r = 5 . The gap between the two methods exhibits a range from 8.59 seconds to over 600 seconds for r = 5 and from 0.07 seconds to 53.06 seconds for r = 3. The average gap for instances with r = 4 varies from 0.19 seconds to 3773.88 seconds, where the highest gap is recorded for the instance with (m,n) values of (25, 25) and a number of non-dominated points ranging from 1495 to 12663. we observe that the gap between the two methods, MOTP-Algorithm and Isermann’s method, varies notably depending on the number of criteria r and the problem instance (m,n), as the problem size increases the search tree grows, hence the significantly longer CPU time can be explained by two main factors: • Higher SND : Finding a greater number of solutions requires more computational efforts and, consequently, increases the CPU time significantly. • Higher Number of Variables: Additionally, the increase in computation time can be linked to the higher number of variables in the problem instances. As the number of variables increases, the complexity of the optimization problem grows exponentially, leading to longer execution times. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 18 of 21 5.3. Results analysis for the degenerate case Instance MOTP-Algorithm CPU(s) SND m n r average min max average min max 4 4 3 0.39 0.14 1.10 14.60 11.00 17.00 4 0.42 0.20 1.26 16.60 12.00 23.00 5 0.85 0.27 1.64 29.60 14.00 47.00 5 5 3 1.20 0.82 2.32 23.40 15.00 29.00 4 1.42 0.91 1.89 46.60 32.00 65.00 5 5.59 2.68 8.36 164.60 81.00 256.00 6 6 3 3.23 2.07 5.54 53.40 41.00 73.00 4 5.15 3.10 8.00 94.80 60.00 119.00 5 82.30 40.23 163.27 537.60 273.00 874.00 7 7 3 400.15 2.21 1982.12 166.40 46.00 613.00 4 100.83 5.84 197.23 280.20 87.00 475.00 5 1165.62 11.64 4431.39 511.60 118.00 975.00 8 8 3 222.32 6.79 1080.90 234.40 36.00 903.00 4 466.63 93.08 1412.21 347.80 212.00 522.00 5 1521.75 158.61 4966.90 718.00 150.00 1396.00 9 9 3 31.39 11.00 48.45 111.20 83.00 135.00 10 10 3 286.80 68.27 699.11 207.80 169.00 289.00 11 11 3 819.45 60.02 3389.23 173.40 114.00 208.00 12 12 3 76.32 9.97 278.86 89.00 16.00 166.00 13 13 3 1405.90 194.80 3365.21 232.40 44.00 344.00 14 14 3 2711.20 507.56 5265.53 312.00 276.00 375.00 15 15 3 3246.42 1503.65 6057.79 277.20 110.00 424.00 Table 15: Results for degenerate instances The degenerate case of the MOTP problem is much trickier to answer than the tradi- tional transportation problem since there are so many different combinations that might be examined in this case, one degenerate vertex has more than one basis (refer [24]) and some of these basis doesn’t lead to a distinct adjacent vertex. It takes a lot of time and memory to process all of the basis connected to a degenerate vertex since the set of non- dominated points of the MOTP problem is based on set Hl, which depends on basis. The handling of degenerate instances revealed that the MOTP-Algorithm is adversely affected by the additional calculations of the improved N-tree approach required in this situation. Consequently, instances of types (m,n, 5) have been omitted from (9,9,5). 6. Conclusion In this paper, a branch-and-bound approach for finding all non-dominated points for the multi-objective transportation problem is described for both degenerate and non- degenerate cases. The separation idea is based on the criteria’s improving directions at every possible extreme point. Additionally, numerous tests have been developed to fathom nodes whose corresponding domains do not contain efficient solutions allowing Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 19 of 21 entire branches of the search tree to be pruned. The experiment’s findings demonstrate that our algorithm can solve non-degenerate instances up to (30,30,3) in a fair amount of time; the smaller r, the faster the algorithm is. Solving degenerate instances has been made possible by using the appropriate approach that has been recommended for this purpose in the literature. Also, a comparative study concluded that our algorithm performs better than Isermann’s method. All of these factors make it seem conceivable to modify the strategy to deal with other difficult multi-objective transport problems. However, we do not guarantee that problems with large dimensions may be solved in a fair amount of time; in these situations, suitable approximation techniques must be used. Although the existing literature on Multi-Objective Transportation Problems (MOTP) presents a range of methodologies, a notable limitation is the absence of robust strategies to effectively address degeneracy, which can significantly complicate the identification of non-dominated points. To address this gap, we propose a novel exact method grounded in the branch-and-bound principle, enhanced by a tailored procedure specifically designed to manage degeneracy. Additionally, our approach integrates a cutting-plane mechanism to efficiently eliminate non-dominated feasible points, ensuring more precise and reliable outcomes. Future work could explore the extension of the proposed method to larger-scale prob- lems by adapting it to handle more complex instances of the multi-objective transportation problem (MOTP), thereby broadening its applicability to a wider range of real-world sce- narios. References [1] H. A. Abdelwali, M. Alardhi, A. M. Khalfan, and M. H. Abdelati. Using the minimize distance method to find the best compromise solution of multi-objective transporta- tion problem with case study. International Journal of Traffic and Transportation Engineering, 11(2), 2022. [2] M.M. Ahmed, A.R. Khan, M.S. Uddin, and F. Ahmed. A new approach to solve transportation problems. Open Journal of Optimization, 5(1):22–30, 2016. [3] J.A. Alkhulaifi, H.A. Abdelwali, M. Al-Ardhi, E.E.M. Ellaimony, and Khalid. An al- gorithm for solving bi-criteria large scale transshipment problems. The Global Journal of Researches in Engineering, 14(4), 2014. [4] J. Alrajhi, H.A. Abdelwali, E.E.M. Ellaimony, and S.A.M. Swilem. A decomposition algorithm for solving a class of bi-criteria multistage transportation problem with case study. International Journal of Innovative Research in Science, Engineering and Technology, 2(9), 2013. [5] Y.P. Aneja and K.P. Nair. Bicriteria transportation problem. Management Science, 25(1):73–78, 1979. [6] P. Anukokila, B. Radhakrishnan, and M. Rajeshwari. Multi-objective transportation problem by using goal programming approach. International Journal of Pure and Applied Mathematics, 117(11):393–403, 2017. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 20 of 21 [7] H.P. Benson. Optimization over the efficient set. Journal of Mathematical Analysis and Applications, 98(2):562–580, 1984. [8] A. Charnes and WW. Cooper. The stepping stone method of explaining linear pro- gramming calculations in transportation problems. Management science, 1(1):49–69, 1954. [9] G.B. Dantzig. A proof of the equivalence of the programming problem and the game problem. Activity analysis of production and allocation, 13, 1951. [10] J.A. Diaz. Solving multiobjective transportation problem. Ekonomicko-Matematicky Obzor., 14:267–274, 1978. [11] A. Elazeem, A. Mousa, M. El-Shorbagy, S. Elagan, and Y. Abo-Elnaga. Detecting all non-dominated points for multi-objective multi-index transportation problems. Sustainability, 13(3):1372, 2021. [12] E.M. Ellaimony, H.A. Abdelwali, J.M. Alrajhi, M.S. Al-Ardhi, and Y. Alhouli. So- lution of a class of bi-criteria multistage transportation problem using dynamic pro- gramming technique. International Journal of Traffic and Transportation Engineer- ing, 4:115–122, 2015. [13] R.J. Gallagher and O.A. Saleh. Constructing the set of efficient objective values in linear multiple objective transportation problems. European Journal of Operational Research, 73(1):150–163, 1994. [14] M. Gen, Y. Li, and K. Ida. Solving multi-objective transportation problem by span- ning tree-based genetic algorithm. IEICE transactions on fundamentals of electronics, communications and computer sciences, 82(12):2802–2810, 1999. [15] F. Geue. An improved n-tree algorithm for the enumeration of all neighbors of a degenerate vertex. Annals of Operations Research, 46:361–391, 1993. [16] M. Hakim. An alternative method to find initial basic feasible solution of a trans- portation problem. Annals of pure and applied mathematics, 1(2):203–209, 2012. [17] F.L. Hitchcock. The distribution of a product from several sources to numerous localities. Journal of mathematics and physics, 20(1-4):224–230, 1941. [18] M.S. Hung, W.O. Rom, and A.D. Waren. Degeneracy in transportation problems. Discrete applied mathematics, 13(2-3):223–237, 1986. [19] H. Isermann. The enumeration of all efficient solutions for a linear multiple-objective transportation problem. Naval Research Logistics Quarterly, 26(1):123–139, 1979. [20] M.A. Islam, A.R. Khan, M.S. Uddin, and M.A. Malek. Determination of basic fea- sible solution of transportation problem: a new approach. Jahangirnagar University Journal of Science, 35(1):101–108, 2012. [21] Z. Juman and M. Hoque. An efficient heuristic to obtain a better initial feasible solution to the transportation problem. Applied Soft Computing, 34:813–826, 2015. [22] L. Kaur, S. Singh, A. Bhandari, S. Singh, and M. Ram. An effective approach for solving multi-objective transportation problem. Journal of Reliability and Statistical Studies, pages 153–170, 2023. [23] A.R. Khan, A.Vilcu, N.Sultana, and S.S. Ahmed. Determination of initial basic feasi- ble solution of a transportation problem: a tocm-sum approach. Buletinul Institutului Politehnic Din Iasi, Romania, Secţia Automatica si Calculatoare, 61(1):39–49, 2015. Z. Mezali, M.E.A.Chergui / Eur. J. Pure Appl. Math, 18 (1) (2025), 5593 21 of 21 [24] H.J. Kruse. Degeneracy graphs and the neighbourhood problem. 2012. [25] S.M. Lee and L.J. Moore. Optimizing transportation problems with multiple objec- tives. AIIE transactions, 5(4):333–338, 1973. [26] L. Lemarchand, D. Massé, P. Rebreyend, and J. Hakansson. Multiobjective opti- mization for multimode transportation problems. Advances in Operations Research, page 13, 2018. [27] G. Maity and S.K. Roy. Solving two-stage multi-objective transportation problem using goal programming and its application to sustainable development. In Computa- tional Intelligence Methodologies Applied to Sustainable Development Goals. Springer, Switzerland, 2022. [28] D. Mardanya, G. Maity, and S. Roy. The multi-objective multi-item just-in-time transportation problem. Optimization, 71(16):4665–4696, 2021. [29] A.A. Mousa. Using genetic algorithm and topsis technique for multiobjective trans- portation problem: A hybrid approach. International Journal of Computer Mathe- matics, 87(13):3017–3029, 2010. [30] M.A. Nomani, I. Ali, and A. Ahmed. A new approach for solving multi-objective transportation problems. International Journal of Management Science and Engi- neering Management, 39:165–173, 2016. [31] N.V. Reinfeld and W.R. Vogel. Mathematical programming. (No Title), 1958. [32] J.L. Ringuest and D.B. Rinks. Interactive solutions for the linear multiobjective trans- portation problem. European Journal of operational research, 32(1):96–106, 1987. [33] A. Shafaat and S. Goyal. Resolution of degeneracy in transportation problems. Jour- nal of the Operational Research Society, pages 411–413, 1988. [34] Y. Shi. A transportation model with multiple criteria and multiple constraint levels. Mathematical and computer modelling, 21(4):13–28, 1995. [35] V. Srinivasan and G.L. Thompson. Algorithms for minimizing total cost, bottleneck time and bottleneck shipment in transportation problems. Naval Research Logistics Quarterly, 23(4):567–595, 1976. [36] T. Stewart and H.W. Ittmann. Two-stage optimization in a transportation problem. Journal of the Operational Research Society, 30(10):897–904, 1979. [37] C. Sutcliffe, J. Board, and P. Cheshire. Goal programming and allocating children to secondary schools in reading. Journal of the Operational Research Society, 35(8):719– 730, 1984. [38] H.A. Taha. Operations research: an introduction. Pearson Education India, Delhi, 2013. [39] J. Wu, C. Pu, S. Ding, G. Cao, C. Xia, and P. Pardalos. Multi-objective optimization of transport processes on complex networks. IEEE Transactions on Network Science and Engineering, 10(2):780–794, 2023. [40] S.A. Zaki, A.M. Abd Allah, H.M. Geneedi, and A.Y. Elmekawy. Efficient multiob- jective genetic algorithm for solving transportation, assignment, and transshipment problems. 2012. [41] Y.J. Zheng and S.Y. Chen. Cooperative particle swarm optimization for multiobjec- tive transportation planning. Applied intelligence, 39:202–216, 2013.