sd-sample article C.O. Talaue and C.G. Tapia 1 SCIENCE DILIMAN (JANUARY-JUNE 2014) 26:1 1-24 Solving a Multi-objective Transportation Problem in a Group Decision-Making Setting Cherryl O. Talaue* Institute of Mathematics University of the Philippines Diliman Cesar G. Tapia Institute of Mathematics University of the Philippines Diliman _______________ *Corresponding Author ABSTRACT I n s o l v i n g t r a n s p o r t a t i o n p r o b l e m s , r e c e n t d e v e l o p m e n t s h a v e s e e n interest in including several kinds of attribute (other than the classical cost and prof it attributes) that may even be incommensurate with one a n o t h e r. T h e r e ex i s t s eve r a l a p p r o a c h e s i n s o l v i n g a t r a n s p o r t a t i o n p r o b l e m w i t h m u l t i p l e a t t r i b u t e s / o b j e c t i v e s . S o m e o f t h e a p p r o a c h e s allow a decision maker to input his/her preferences with respect to the multiple number of objectives that need to be concurrently optimized in a co m p r o m i s e d w a y. T h e l i te r a t u r e , h o w eve r, s e e m s t o l a c k s o l u t i o n techniques that would deal with a real life decision-making situation wherein a group of decision makers is involved but would probably have d i f f e r e n t ( e v e n c o n f l i c t i n g ) p r e f e r e n c e s i n s o l v i n g a t r a n s p o r t a t i o n problem with multiple objectives. In this research, we propose to utilize a fuzzy programming formulation and binary search technique (adopted from Tapia and Murtagh 1992) as a methodology to solve multi-objective t r a n s p o r t a t i o n p r o b l e m a s a g r o u p d e c i s i o n - m a k i n g c o n c e r n . F u z z y programming allows the decision makers to vary at any given iteration t h e i r f u z z y a s p i r a t i o n l e v e l s i n t e r m s o f p r e f e r e n c e c r i t e r i a a n d underachievement tolerance values. Since conflict in aspiration levels usually results in an infeasible situation, binary search is applied until a feasible and acceptable compromise solution is achieved. The main o b j e c t i ve o f t h i s p a p e r i s to p r o p o s e a v a l i d a n d n e w m e t h o d o l o g y. Inasmuch as comparing existing methodologies is not our primary aim, we believe this is another major and serious research undertaking. Keywords: Transportation problem, group decision-making, fuzzy programming ISSN 0115-7809 Print / ISSN 2012-0818 Online Solving a Multi-objective Transpor tation Problem 2 INTRODUCTION The classic transportation problem is a special class of linear program that deals with transporting a commodity from sources (e.g. , factories) to destinations (e.g. , warehouses) through a network of arcs (e.g. , highways). Each source has a given supply, each destination has a given demand, and each arc that connects the source- destination pair has a given transportation cost (or prof it) per unit of shipment. The objective is to determine the amount of commodity to be transported from each source to each destination so that the total transportation cost (or prof it) is minimized (or maximized) while satisfying the supply and demand constraints. However, in real-life applications, for each possible transportation, other than cost (or prof it), several kinds of attribute (e.g. , average delivery time of commodities, reliability of transportation, product deterioration, etc.) are also important to consider. Usually, these attributes are incommensurate with one another. Moreover, in a corporate setting where several decision makers actively participate in problem solving and each one can pick his/her own shipment goal different from the others, the group of decision makers may initially express a set of conflicting or incoherent goals. Hence, a number of researches have considered the transportation problem with multiple objectives and offered different solution approaches. Abd El-Wahed and Lee (2006) have classif ied the solution approaches to the multiple objective transportation problem (MOTP) into four categories: (1) interactive approaches, (2) non-interactive approaches, (3) goal programming approaches, and (4) fuzzy programming approaches. Ringuest and Rinks (1987) and Climaco and others (1993) have developed two interactive approaches that determine the satisfactory solution while maintaining the special structure of the transportation problem. The decision maker controls the search direction during the solution procedure through his/her own preferences. Therefore, the main advantage of these approaches is that the eff icient solution satisf ies the preferences of the decision maker. The shortcomings of these methods are on a) the convergence of the solution procedure, which is dependent on the decision maker’s rationale and consistency in expressing his/her preferences, and b) the diff iculty in enumerating the set of eff icient solutions in large-scale problems. Some of the non-interactive methods found in the literature are in Aneja and Nair (1979), Diaz (1976 and 1979), Isermann (1979), and Kasana and Kumar (2000). These authors have proposed different approaches to generate the set of eff icient solutions from where a decision maker chooses his/her preferred solution. One diff iculty with these techniques is that the solution process may take a long time in scanning the feasible region for the eff icient solutions. Another is the diff iculty C.O. Talaue and C.G. Tapia 3 of the decision maker in making trade-offs among the eff icient solutions due to his/her inexperience and/or the incomplete information about the decision environment. Lee and Moore (1973) and Aenaida and Kwak (1994) have used goal programming to solve the MOTP. With goal programming, a decision maker can obtain a satisfying solution and likewise analyze his/her aspiration levels. As mentioned in Tamiz and others (1998) and Romero (1991), goal programming also has some disadvantages. The naive setting of the weights in the formulation of goal programming models can lead to wrong results. Likewise, the goal programming formulation changes the well-known mathematical structure of the multi-objective transportation problem. Problems could also come up during the determination of the aspiration levels. Fuzzy programming is recommended as a tool to solve the MOTP where there is incomplete preference information provided by the decision maker. Abd El-Wahed (2001) and Li and Lai (2000) have used fuzzy programming to obtain a compromise solution to the MOTP. Other research works utilizing fuzzy programming are described in Chanas and others (1984), Bit and others (1992, 1993a, 1993b), Chanas and Kuchta (1998), Ehrgott and Verma (2001), Challam (1994), Abd El-Wahed and Abo-Sinna (2001), and Lai and Hwang (1996). Fuzzy programming has likewise some shortcomings. Abd El-Wahed (2001) has shown that using fuzzy programming in solving MOTP changes the standard form of a transportation problem. Li and Lai (2000) have proven that the min-operator does not guarantee a solution. Abd El- Wahed and Lee (2006) have combined categories 1, 3 and 4 (see paragraph 2 of this section for the categories) of the solution approaches. Some other solution approaches not mentioned in Abd El-Wahed and Lee (2006) are found in the works of Mistuo and others (1999), who used a spanning tree-based genetic algorithm for solving the MOTP; Hong-Wei and others (2009), who applied the thinking of lamarckina evolution based on Fuzzy-genetic algorithm and proposed the Lam-genetic algorithm technique; and Amirteimoori (2010), who utilized the concept of Data Envelopment Analysis to compute the eff iciency measure in his proposed approach. However, in our literature search, we have not found a study wherein group decision- making scenario is considered in MOTP. It is a given fact that group decision-making is a common feature in today’s corporate world. Hence, we feel the need to consider a decision-making situation involving a number of decision makers who are all concerned with determining a compromise solution to the MOTP. Solving a Multi-objective Transpor tation Problem 4 A number of papers have proposed to solve multi-objective problems under a group decision-making environment using fuzzy programming techniques. One of these is the work of Xiong and others (2013), which deals with group decision- making for multi-objective problem where the preferences of the decision makers are expressed by fuzzy reference points using a multi-objective evolutionary approach. A decision support model to consider consensus measure and robustness measure for fuzzy group decision-making for multi-objective problems has also been presented. Wang and others (2012) have proposed to solve the multi-criteria group decision-making by using intuitionistic interval information aggregation operators. Based on the intuitionistic interval, a method that applies the knowledge level of the experts to the group decision-making problem is developed. Wu and others (2007) have presented a method that integrates fuzzy multi-objective linear programming with fuzzy group decision-making techniques. Based on the method, a fuzzy multiple objective group decision support system is developed. Xu and Chen (2007) have proposed an interactive method that can be used in multi-objective group decision-making scenario where the information about attribute weights is partly known. The weights of the decision makers as well as the attribute values are expressed in triangular fuzzy numbers. The method constructs the normalized expected decision matrices by using two simple formulas and aggregates these normalized expected decision matrices into a complex decision matrix. The decision makers are then asked to provide their preference gradually in the course of interactions and by solving linear programming models, the method diminishes the given set gradually and f inds the most preferred alternative. Zhang and Lu (2003) have proposed an integrated fuzzy group decision-making method. This method allows group members to express fuzzy preferences for alternatives and individual judgments for solution selection criteria. The method likewise allows for the weighting of group members. The technique then aggregates these elements into a compromise group decision that is the most acceptable for the group as a whole. Herrera and others (1995) have utilized the linguistic ordered weighted averaging (LOWA) operator to solve group decision-making problems from individual linguistic preference relations. In most of the proposed approaches that use fuzzy techniques, the decision makers are asked to input certain preferences. Infeasibility is likely to occur if the preferences are highly conflicting. Asking the decision makers to input a new set of preferences usually becomes a waste of time. In this paper, we propose to obtain a satisfying solution to the MOTP under a group decision-making scenario that would reasonably be acceptable to all the decision makers by utilizing interactive group decision-making using fuzzy programming with preference criteria developed by Tapia and Murtagh (1992). C.O. Talaue and C.G. Tapia 5 ( = 1, 2, … , ) ( ) = 1 ( ), 2 ( ), … , ( ) Min ( ) subject to = , = 1, … , (1)= = , = 1, … , (2)=1 ≥ 0 , ( ) THE MULTI-OBJECTIVE TRANSPORTATION PROBLEM In the classic transportation problem, a commodity is to be transported from several sources to several destinations in such a way that the total transportation c o s t i s m i n i m u m . S u p p o s e t h e r e a r e m s o u r c e s S i ( i = 1 , 2 , . . . , m ) a n d n destinations D j (j = 1, 2, ..., n). Each source S i has available supply a i and each destination D j has demand b j . C ij is the cost of transporting a unit of the commodity from S i to D j . We let x ij as the number of commodity to be transported from S i to D j . In real life, most transportation problems are not single objective.The mathematical model of MOTP can be stated as follows : where f is a vector of K objective functions and ( ) = ==1 . Minf (x) f(x) The superscript on is used to identify the number of objective functions . A solution to this multi-objective problem is called a nondominated solution and we def ine it as follows: (1) (2) Solving a Multi-objective Transpor tation Problem 6 Definition 1 A feasible vector (S is the feasible region) yields a nondominated solution, of the MOTP if, and only if, there is no other vector such that: but A number of techniques have been proposed in the literature to solve the MOTP. As far as we know, none of the published approaches have considered a group decision- making situation involving several decision makers with different and usually conflicting preferences due to differences in their choice of nondominated solutions. In this paper, we wish to obtain a nondominated solution that would satisfy all the decision makers despite their incoherent preferences. We use fuzzy programming with preference criteria technique as proposed in Tapia and Murtagh (1992). Fuzzy programming enables the decision makers to vary at any given iteration their fuzzy aspiration levels in terms of input information, known as preference criteria and underachievement tolerance values. Should there be conflict in preferences, which usually results in infeasibility, a binary search method will be employed until a feasible, eff icient and acceptable solution is obtained. These concepts will be expounded in the next section. GROUP DECISION-MAKING In solving the MOTP involving a number of, say L decision makers, this research applies the interactive group decision-making technique utilizing fuzzy programming with preference criteria by Tapia and Murtagh (1992). Notions of preference criteria and percentages of achievement (concepts borrowed from Tapia and Murtagh 1989) and underachievement tolerance values are considered important to quantify for mathematical modeling purposes. These are used to define the membership function of a set of nondominated solutions. The value of the membership function of an element in a fuzzy set would indicate the degrees of satisfaction of the decision makers, which are expressed in terms of some aspiration levels. A solution with a high membership value signif ies that the solution is preferred compared to one with a low membership value. The proposed solution technique utilizes iteratively (a) fuzzy programming with preference criteria to obtain nondominated solutions to the MOTP, and (b) binary search algorithm to explore progressively nearer to a commonly desired solution. The binary search is used to arrive at a compromise ( ) 0 ∈ 0 ≤=1=1 =1=1 0 <=1=1 =1=1 , = 1,2, … , . C.O. Talaue and C.G. Tapia 7 ( ) 1,2, … , , ( ∗ ) 1,2, … , , . ( ) = ( ∗ ) = ( ) (3) ( ) = = max1≤ ≤ ( ∗ ) (4) (4) ( ) = ( ∗ ) (5) signifies the closeness of the k-th objective’s computed value at , to the true minimum, , over the range of values between and . ( ∗ ) ( ∗ ) 1,2, … , , 1,2, … , , ∗ = 1, … , ( ) = ( ) = 1 − ( ) − ( ∗ )− ( ∗ ) ∗ 100% ( ) , ( ) ( ) = solution at every iteration stage. The interaction of the group of L decision makers takes the form of (1) initially indicating their preference information and then (2) signifying their acceptance (or non-acceptance) of the results after each binary search for a feasible solution. In the course of the decision process, the binary search algorithm is expected to reduce the degrees of the interpersonal conflicts among L decision makers. The best acceptable compromise solution is the one that can be associated with the least possible degree of conflict. The following def initions of some concepts borrowed from Tapia and Murtagh (1989) are needed for the formulation of the fuzzy programming model and the binary search algorithm. Definition 2 The optimal functional value of the k-th objective function, of the MOTP denoted by is given by subject to (1) and (2) Definition 3 The worst functional value of the k-th objective function, of the MOTP denoted by is given by where are the K optimal decision support vectors given in (3). Definition 4 The preference criterion for the k-th objective function, of the MOTP, denoted by , quantifies the l-th decision maker’s desire to attain the optimal functional value, , over the range of values between this optimal value and the worst value, is expressed as a value between 0 and 100. The higher the value, the higher the preference of the l-th decision maker to achieve the optimal value of the k-th objective function. Definition 5 The percentage of achievement of the k-th objective function, of the MOTP with respect to the solution vector x, denoted by or is given by max Solving a Multi-objective Transpor tation Problem 8 ∈ ( ) ∈ Definition 6 The nonnegative underachievement size that the l-th decision maker is willing to accept for the k-th objective function of the MOTP is denoted by . Definition 7 For each objective function, , the selection criteria, , which the l-th decision maker, is going to use in searching for the best compromise solution should satisfy the following requirement: The best compromise solution should satisfy the requirement that the K selection criteria are satisf ied simultaneously for all the L decision makers. These selection criteria can be regarded as expressions of each of the L decision makers’ aspiration level for the k-th objective function. We want to search for a best compromise solution, x, in which the percentage of achievement, , of the k-th objective function is better or at least equal to the l-th decision maker’s aspiration level expressed in terms of the preference criterion, , and the underachievement tolerance value, . FUZZY PROGRAMMING TO SOLVE MOTP WITH MULTIPLE DECISION MAKERS Preliminary to fuzzy programming, the l-th decision maker, among a group of L decision makers, has to generate a f inite number of nondominated solutions to the MOTP satisfying his/her implicit preference structure (See Tapia and Murtagh 1989, 1991). We denote a nondominated solution as and let U l be the index set of alternative solutions, , favored by the l-th decision maker. We can let such nondominated solutions favored by the l-th decision maker constitute the following set: We also form the set = 1, … , = 1, … , (6) ( ) ( ) = ( ), ∈ ℱ = =1 which is the union of all the sets of favored nondominated solutions to the MOTP of the L decision makers. From this set, the L decision makers have a task of choosing the best compromise solution. ( ): 0 ≤ −∈ ≤ ≤ 100 for = 1, … , and = 1, … , ( ) C.O. Talaue and C.G. Tapia 9 ( ) ( ) Using the selection criteria in (6), we now def ine the membership function, , for ; and , of a favored nondominated solution in F as follows: = 1, … , ; = 1, … , = 1, … , ( ) = ( ) − +∈100 − + ∈ 0 ≤ −∈ ≤ ( ) ≤ 1000 ( ) < − ∈ Each solution can be considered to be a member of a fuzzy set whose degree of membership can be calculated using (7), with values ranging from 0 to 1. A solution with a membership value near 1 is taken to be a strongly desirable solution, while a membership value near 0 means a weakly desirable solution. We can def ine the following fuzzy sets: = ( ( ), ( )): ( ) ∈ ℱ = 1, … , ; = 1, … , where is the set of nondominated solutions of the MOTP and is the membership function given in (7). These fuzzy sets are also called fuzzy objectives. One of the ways of obtaining the intersection of these fuzzy objectives is by taking the minimum membership value among all the fuzzy objectives that can make up a non-empty fuzzy set . The fuzzy set can be expressed as follows: = ( ( ), min, ( )) ∶ ( ) ∈ ℱ The fuzzy set contains the solutions common to all the fuzzy objectives, and their membership values are determined by the membership function that gives the smallest membership value. The best compromise solution is then the nondominated solution in having the largest membership value, which means that it corresponds to the optimal solution of the following maximin program: max min, ( ) (8) (8) The above discussion considers a discrete set of alternatives among the number of selected nondominated solutions. The maximin program (8) can be extended to one of determining the best compromise solution among all nondominated solutions of the MOTP by considering the following mathematical program based on the model in Tapia and Murtagh ℱ ( ) (7) Solving a Multi-objective Transpor tation Problem 10 ( ∗ ) ∈ (1992), which incorporates this fuzzy algorithm into a single-objective mathematical model. We propose the fuzzy model that allows the search for a nondominated solution vector, x, which is found not only in the union of sets of favored solutions but also from among the feasible space of the nondominated solutions. (FP-MOTP): max Z subject to: satisfies (1) and (2) of MOTP ( ) − + ∈100 − + ∈ ≥ ∀ , 0 ≤ −∈ ≤ ( ) ≤ 100 ∀ , ( ) ( ) = 1 − ( ) − ( ∗ )− ( ∗ ) ∗ 100 (9) (10) (11) where is as given in (3) and is as given in (4). According to a proposition in Tapia (1992), FP-MOTP can be used to generate solutions that correspond to nondominated solutions of MOTP. In cases where the solution is unsatisfactory (e.g. , the value of Z is very close to zero), or in the event of infeasibility, or in case the resulting feasible solution is not acceptable to the decision makers, FP- MOTP can be used interactively and iteratively as needed in such a way that the values of the input parameters, including the decision makers' preference criteria, , and the underachievement tolerance values, , can be modif ied by the decision makers according to their individual preference structures. Infeasibility is also expected to occur should the L decision makers have highly conflicting preferences. This situation arises when one of the decision makers holds a very high aspiration for a particular objective function while the rest of the decision makers, on the contrary, hold a very low aspiration level for it. C.O. Talaue and C.G. Tapia 11 ∈ We apply the interactive procedure proposed in Tapia and Murtagh (1992), which makes use of a binary search technique to determine a combination of input parameters, and , that can give a feasible solution to the FP-MOTP. It is necessary to modify FP-MOTP in order to f ind a compromise nondominated solution that will be acceptable to all the decision makers. It is possible to reduce constraints of type (9) and of type (10) from in FP-MOTP by considering the most stringent constraint falling under each type. The revised fuzzy program has the following form: (RFP1) subject to: satisfies (1) and (2) of MOTP ( ) − (1)100 − (1) ≥ ∀ (12) 0 ≤ (1) ≤ ( ) ≤ 100 ∀ (13) (12) (13) (1) = max −∈ (14) Constraints (12) and (13) represent the most stringent constraints among those of types (9) and (10), respectively, as we consider here the maximum among the aspiration levels of all decision makers for each of the objective function. If RFP1 has a feasible solution, then this must be the best compromise solution as it satisf ies all the decision makers' preferences. However, RFP1 has constraints that require the most rigorous degree of satisfaction. Infeasibility therefore is likely to occur. If RFP1 does not provide a feasible solution, then the decision makers should make a compromise by way of ignoring some constraints that require a certain amount of rigor. In this case, it is necessary to solve RFP2. RFP2 is exactly the same as RFP1 except that (1) in (12) and (13) is changed to (2) where (2) = min −∈ (15) This means that RFP2 is the least rigorous model to solve for the given decision problem. Hence, if RFP2 does not provide a feasible solution, then a compromise solution acceptable to all the decision makers is impossible to achieve. The proposed where Pk (x) is given in (11) and l l Solving a Multi-objective Transpor tation Problem 12 ( ) ( ) algorithm is therefore not carried out for the initial set of preference criteria, , and underachievement tolerance values . The decision makers can then be required to input another set of parameters associated with aspiration levels of lower priority ranking. In case RFP2 has a feasible solution, then it should be possible to determine some revised models RFPn, n = 3, 4, . . . , N having the following formulation: (RFPn) ∈ subject to: x satisfies (1) and (2) of MOTP − ( )100 − ( ) ≥ ∀ (16) 0 ≤ ( ) ≤ 100 ∀ (16) (17) where is as given in (11) and for (where N is a pre- determined number of iterations) can be determined by using a binary search technique applied to the set of L expressed preference criteria and underachievement tolerance values. BINARY SEARCH ALGORITHM Constraints (16) and (17) can be characterized as having an intermediate degree of rigor to satisfy between the most rigorous requirements, which have most recently led to an infeasible solution, and the least rigorous requirements, which have most recently led to a feasible solution. To accomplish this, a binary search technique proves to be useful in determining the next value of needed in the revised models RFPn as follows: For n = 3, 4, . . . , N ( ) = 3, 4, . . . , ( ) = 12 ( + ) (18) where INF i is the most recent value of for which RFPninf has an infeasible solution, and FES i is the most recent value of for which a feasible solution exists for RFPnfes. ( ) ( ) C.O. Talaue and C.G. Tapia 13 max| ( ) − ( − 1)| ≤ This interactive solution procedure for RFPn may be terminated under any one of the following circumstances: • The prescribed maximum number of iterations N is reached, in which case the most recent feasible solution may be acceptable to all the decision makers as their best compromise solution. • The decision makers have accepted the feasible solution of the n-th iteration, where n < N. • The binary search algorithm has reached an iteration stage at which a prescribed degree of convergence, say , has been reached, i.e. , If, however, the binary search algorithm has already reached an iteration stage at which a prescribed degree of convergence has been reached but the decision makers are still not satisf ied with the solution, then we ask them to input a new set of preference criteria and underachievement tolerance values, and repeat the binary search until a compromise solution will have been reached. We are expecting all of the decision makers to be consistently in a compromising posture in any decision- making activity. NUMERICAL EXAMPLE To illustrate our fuzzy MOTP technique for multiple decision makers, we have developed computer codes using the Advanced Integrated Multidimensional Modeling Software (AIMMS 2012). The free AIMMS academic software can solve up to 5000 variables and constraints. For models with almost unlimited number of variables and constraints for commercial or industrial use, the AIMMS PRO is recommended. The use of parameter inputs necessary for the interactive solution of our proposed multi-objective transportation methodology in a group decision- making setting is very convenient. Complexity analysis is not our real concern and the problems of dominated MOMP or non-Pareto-eff icient solutions is non-existent here inasmuch as we are dealing with a purely linear mathematical model, which in a known real-world setting may not hopefully become excessively so large that existing software such AIMMS PRO would not be able to handle it. We use published data in Amir teimoori (2010), as follows: An automobile manufacturer has assembly plants located in eight towns: A, B, C, D, E, F, G and H. The cars are assembled and sent to major markets in three towns: I, J, and K. The Solving a Multi-objective Transpor tation Problem 14 1 , 2 , 3 , ( ) 1 1 2 3 2 manufacturer considers one input (shipping cost) and two outputs (the value of shipment and prof it). Hence, the objective functions to be optimized are the total shipping cost, total value of shipment and total cost, which we denote as and respectively. The appropriate input-output, , availabilities (a i ), and demands (b j ) are listed in Table 1. These are the parameter values that we input in the computer codes that we have written in AIMMS. A (531, 3500, 500) (431, 380, 600) (395, 3950, 400) 10 B (394, 2850, 600) (418, 2395, 700) (512, 2590, 485) 13 C (405, 310, 800) (512, 409, 1000) (412, 390, 1100) 11 D (355, 290, 705) (493, 385, 617) (570, 419, 518) 7 E (299, 415, 585) (398, 512, 490) (315, 255, 380) 9 F (319, 512, 488) (464, 215, 305) (435, 355, 512) 9 G (619, 612, 619) (490, 510, 505) (354, 550, 490) 4 H (456, 299, 601) (394, 512, 432) (439, 499, 519) 6 Dj 30 25 14 i/j I J K Si Table 1. The data for example. Each ordered triple represents the Shipping Cost (k = 1), Value of Shipment (k = 2), Profit (k = 3) of each unit of shipment from source i to destination j (i.e. ) = (531, 3500, 500), , To guide the decision makers in their input preferences (i.e. , preference criteria and underachievement tolerance values), we perform single optimization computations using our computer codes written in AIMMS, one for each function of the MOTP subject to the same constraints of the said model. The nondominated solution obtained by solely minimizing gives 25924 as the best value of while the worst value of is 29243 obtained from solely minimizing . The nondominated solution from solely maximizing gives 98234 as its best value. The worst value of is 53093 obtained from solely minimizing . Lastly, the nondominated solution as a result of solely maximizing gives 47794 as the best value. The worst value of is 40952 obtained from solely maximizing . The nondominated solutions obtained are given as row-vectors in Table 2. 1 2 3 3 min f 1 25924 68750 44044 max f 2 29243 98234 40952 max f 3 29343 53093 47794 f 1 f 2 f 3 Table 2. The nondominated solutions from the single objective optimizations 2 C.O. Talaue and C.G. Tapia 15 , , = , = , = ) Table 3. Solution vectors, obtained from the single objective optimizations and the correspond ing percentages of achievement, of each objective function (i.e., for min = , … , = , , , i\j I J K min f 1 PA k A 4 1 5 PA 1 100.00% B 13 PA 2 34.69% C 1 3 7 PA 3 45.19% D 7 E 9 F 9 G 2 2 H 6 max f 2 PA k A 4 4 2 PA 1 0.00% B 13 PA 2 100.00% C 11 PA 3 0.00% D 7 E 9 F 9 G 2 2 H 1 5 max f 3 PA k A 3 4 3 PA 1 27.96% B 3 10 PA 2 0.00% C 1 10 PA 3 100.00% D 6 1 E 7 2 F 9 G 3 1 H 2 1 The decision vectors, x ij i = A, ..., H, j = I, J, K, and the corresponding percentages of achievement (computed using (5) of Def inition (5)), are given in Table 3. Each l-th decision maker can use these values as a guide to determine his/her preference criterion, which is his/her aspiration level to achieve the optimal value of an objective function (see Def inition 4) and his/her underachievement tolerance value which he/she is willing to accept for the k-th objective function (see Def inition 6). The percentage of achievement, , of the k-th objective function corresponding to a nondominated solution serves as a guide to a decision maker as to the Solving a Multi-objective Transpor tation Problem 16 1 1 , = , . . . , H, = I, J, K , acceptability to him/her of a solution as this signifies the closeness of the objective's value at a decision vector to the true optimum over the range of values of an objective function. Hence, also serves as a guide for each decision maker in assigning the inputs and for fuzzy programming. Should it happen that all the decision makers are willing to accept any of the nondominated solutions out of the three single-objective optimization results, then the problem is already solved. For example, if all decision makers would choose a nondominated solution which has the highest average of percentages of achievement of the three objective functions, then all of them have the same choice, which is the nondominated solution optimizing the function, (see Table 3). However, in real life, this scenario is rather unlikely to happen as each decision maker does not normally place full preference on a particular objective but rather holds partial preferences on all the objective functions. Suppose there are three decision makers (L = 3). For discussion purposes, let us suppose that the decision makers have individually engaged in interactive and iterative solution processes to solve the MOTP (see Tapia and Murtagh 1989, 1991). Each decision maker is assumed to have tried solving the MOTP a number of times and used this as a learning process to come up with his/her own preference criteria and underachievement tolerance values, which are given in Table 4. These are also used as input parameters in our AIMMS computer codes. For example, decision maker 1 chooses a preference criterion for to be 70, because he wants to obtain a nondominated solution vector, x, for which the value of evaluated at x is 70% close to its best value of 25924 measured from its worst value of 29243. Additionally, he/she chooses an underachievement tolerance value of 5 for the f irst objective function. The same explanation holds for all the other input values in Table 4. Using these preference structures and applying the interactive and iterative solution approach for a single decision maker proposed in Tapia and Murtagh (1991), we perform three multi-objective optimizations using our AIMMS computer codes and obtain three decision vectors, , which are given in Table 4. Each nondominated solution's percentage of achievement, also computed using (5), is likewise given in Table 4. Realistically, not all the decision makers will favor the same nondominated solution out of the three multi-objective optimization results because different decision makers are more likely to have different or inconsistent preference structures relative to the multiple objective functions (see, for example, Table 4). A compromise has then to be reached and hence we now propose to apply the binary search technique. ∈ 1, 11 C.O. Talaue and C.G. Tapia 17 Table 4. Different preference structures, i.e., preference criteria and underachievement tolerance values chosen by decision makers l = 1, 2, 3; solution vectors obtained after using these preference structures in the method proposed in Tapia and Murtagh (1991); and the correspond ing percentages of achievement, of each objective function, k = 1, 2, 3 = , … , = , , , , 1 1 70 5 A 6 4 PA 1 70.96% 2 70 5 B 13 PA 2 70.90% 3 50 5 C 5 6 PA 3 50.01% D 7 E 9 F 9 G 4 H 6 2 1 70 5 A 10 PA 1 70.56% 2 45 5 B 13 PA 2 46.66% 3 70 10 C 11 PA 3 70.24% D 3 4 E 1 8 F 9 G 4 H 6 3 1 60 3 A 10 PA 1 60.44% 2 50 4 B 13 PA 2 50.02% 3 60 5 C 2 9 PA 3 60.06% D 7 E 9 F 4 G 4 H 6 l (Decision Maker) k i/j I J K Pak∈ The binary search starts with the preference structures of the three decision makers g i ve n i n Ta b l e 4 f r o m w h e r e t h e v a l u e s of t h e i r p r e f e r e n ce c r i te r i a a n d underachievement tolerance values are used as input parameters into our fuzzy model for group decision-making. The proposed algorithm, as implemented in the AIMMS environment applied to these input parameters, gives the results (presented in Table 5) after eight (i.e. , n = 1, 2, . . . ,8) iterations assuming the decision makers have agreed to do this maximum number of iterations. Each nondominated solution's Solving a Multi-objective Transpor tation Problem 18 ( ) 1(1) = max 70 − 5, 70 − 5, 60 − 3 = 65; 70 − 10, 60 − 5 = 60 percentage of achievement, , is likewise given in Table 5. The detailed description of the inputs in each iteration step is given below. = , , … , A 5 2 3 PA 1 = 68.44% A 4 2 4 PA 1 = 67.68% B 13 PA 2 = 62.00% B 13 PA 2 = 62.56% C 1 10 PA 3 = 61.30% C 2 9 PA 3 = 61.47% D 7 D 7 E 9 E 9 F 9 F 9 G 3 1 G 3 1 H 6 H 1 5 p2(1)=65p1(1)=65 p3(1)=60 n = 3 PA k p2(2)=40p1(2)=57 p3(2)=45 n = 4 PAk p 2 (3) =52.5 p 1 (3)=61 p 3 (3) =52.5n = 5 p2(4) =58.7 p1(4)=63 p3(4) =56.3n = 6 PA k p2(5) =61.9 p1(5)=64 p3(5) =58.1n = 7 p 2 (6) = 63.4 p1(6) =64.5 p3(6) =59.1n = 8 p 1 (7) =64.7 p 3 (7) =59.5 p 2 (7) =64.2 p 1 (8) =64.6 p 3 (8) =59.3 p 2 (8) =63.8 PA k n = 1 n = 2 i / j I J K i / j I J K A A B B C C D D E inf. E inf. F F G G H H A 3 2 5 PA 1 = 66.92% A 2 2 6 PA 1 = 66.16% B 13 PA 2 = 63.13% B 13 PA 2 = 63.70% C 3 8 PA 3 = 61.02% C 4 7 PA 3 = 60.57% D 7 D 7 E 9 E 9 F 9 F 9 G 3 1 G 3 1 H 2 4 H 1 5 PA k A A 2 3 5 PA 1 = 70.55% B B 1 12 PA 2 = 57.23% C C 3 8 PA 3 = 61.02% D D 7 E inf. E 9 F F 9 G G 3 1 H H 2 4 Table 5. Solution vectors, obtained after iterations of the binary search model RFPn and the correspond ing percentages of achievement, PAk , of each objective function. = , … , = , , , C.O. Talaue and C.G. Tapia 19 1(1) = max 70 − 5, 70 − 5, 60 − 3 = 65; 2(1) = max 70 − 5, 45 − 5, 50 − 4 = 6570 − 10, 60 − 5 = 60 2(1) = max 70 − 5, 45 − 5, 50 − 4 = 65; and 3(1) = max 50 − 5, (1) (2) (1) (2) 3(1) 3(3) (4) 1(4) 2(4) (7) 1(7) 2(7) For the f irst iteration, the fuzzy model RFP1 needs as input parameters, , for k = 1,2,3. These input parameters are computed using (14) as follows: using the input values in Table 4, . T h i s m e a n s that all the decision makers' maximum preferences for all the objectives are utilized. RFP1 gives an infeasible solution. Table 5 capsulizes the result of this iteration together with the results of succeeding iterations. For the next iteration, we use (15) to compute for the values of for k = 1, 2, 3 (i.e. , . These are the least s t r i n g e n t preferences of the decision makers. Since RFP2 turns out to be feasible, we can proceed to further iterations in order to search for a more stringent set of preferences that could result possibly in another feasible solution. In the third iteration, for k = 1, 2, 3 is taken to be the average of and (see (18), i.e. , average {65, 57} = 61, = average {65, 40}= 52.5, and = average {60; 45} = 52.5). By taking the average here, there is an intermediate degree of rigor that satisf ies both the most stringent preferences and the least stringent preferences of the decision makers. RFP3 turns out to be feasible. The solution obtained from RPF3 can still be improved by proceeding to the fourth iteration. Noting that iteration 3 is the last iteration that gives a feasible solution while iteration 1 is the last iteration that gives an infeasible solution, we then use in RFP4: for k = 1, 2, 3 the average of and (i.e. , = average {65, 61} = 63; = average {65, 52.5} = 58.7; and = average {60, 52.5} = 56.3). RFP4 gives us a feasible solution. We can fur ther improve the solution given in RFP4 by proceeding to the next two iterations by solving RFP5 and RFP6, which both give feasible solutions. In an attempt to further improve the solution given in RFP6, we proceed to the seventh iteration and solve RFP7. In RFP7, for k = 1, 2, 3 is the average of and (i.e. , = average {65, 64.5} = 64.7; = average {65, 63.4} = 64.2; and = average {60, 59.1} =59.5). for k = 1, 2, 3 are computed in this manner since iteration 6 is the last iteration that gives a feasible solution, while iteration 1 is the last iteration that gives an infeasible solution. RFP7, however, turns out to be infeasible. 50 − 5, 70 − 10, 60 − 5 = 60 , 1(2) = min 70 − 5, 70 − 5, 60 − 3 = 57; 2(2) = min 70 − 5, 45 − 5, 50 − 4 = 40 = 40; and 3(2) = min 50 − 5, 70 − 10, 60 − 5 = 45) (3) 3(2) (1) (3) 3(4) (1) (6) 3(7) (7) Solving a Multi-objective Transpor tation Problem 20 (8) (7) 1(8) 3(8) 2(8) = 13, = 4, = 7, Noting that RFP6 is the last iteration that gives a feasible solution while RFP7 is the last iteration that gives an infeasible solution, we perform the last (i.e. , predetermined) maximum number of iterations (that is n=8, i.e. solve RFP8) where for i = 1,2,3 is the average of and (i.e. , = average {64.5, 64.7} = 64.6; = average {63.4, 64.2} = 63.8; and = average {59.1, 59.5} = 59.3). RFP8 likewise turns out to be infeasible. Hence, the best compromise solution is given by RFP6: . In this group decision exercise, the last feasible result can be considered as the best compromise solution because it corresponds to the most stringent combination of preferences that the binary search methodology attempts to identify. CONCLUSION Many real applications of the transportation problem consider arcs with various attributes (input/output). As a result, a number of researches have been done to solve the MOTP. However, literature lacks methodologies on solving the MOTP that involves a group of decision makers who may have varying and conflicting preferences relative to the attributes of the arcs. This paper presents a model that makes it possible to solve the MOTP in a group decision-making setting. The proposed MOTP model (FP-MOTP) requires the decision makers to input their fuzzy aspiration levels in the form of preference criteria and underachievement tolerance values, which signify the relative importance of each attribute of the arcs to each decision maker. To illustrate our model and methodology, we use published data in Amirteimoori (2010) wherein each arc in the transportation problem involves one input and two output attributes. We demonstrate a scenario with three (3) hypothetical decision makers wherein they are required to input their fuzzy preferences signifying differently the importance of every attribute to them individually. In summary, we describe the methodology being proposed in this paper for solving a multi-objective transportation problem (MOTP) in a group decision-making setting as follows: Step 1. Each function (arc attribute) in the multiple objective transportation problem is separately optimized subject to the same set of transportation constraints. The results yield a decision support matrix that describes to the multiple decision makers the worst and the best values that could possibly be expected for each objective function (see Def initions (3) and (4)). (6) = 2, = 2, = 6, = 13, = 4,= 7, = 9, = 9, = 3, = 1, = 1, = 5 C.O. Talaue and C.G. Tapia 21 Step 2. Each decision maker is allowed individually to engage in several interactive and iterative fuzzy programming attempts (see FP-MOTP) wherein, as in a learning process, he/she can find a preference structure consisting of preference criteria and underachievement tolerance values (see Definitions (5) and (6), respectively) that he/she actually favors most, depending on the corresponding percentages of achievement of the objective functions (see Def inition (5)). Inevitably, it is possible that not all decision makers will have one and the same preference structure. Therefore, there is a need for the decision makers to come together and look for a compromise. Step 3. The binary search methodology (see Section (5)) is performed. It is an impartial tool that can provide a compromise nondominated solution to the MOTP. Ultimately, a best compromise nondominated solution is assured because it corresponds to the combination of preference criteria for all the objectives that are as high as possible relative to the initial various preference structures chosen by all the decision makers. We f inally note that in any decision-making activity involving multiple decision makers, it is to be expected that to arrive at the ultimate solution, every decision maker should be ready to compromise. ACKNOWLEDGMENT This study received funding from the UP Diliman Off ice of the Vice-Chancellor for Research and Development through the Outright Research Grants. REFERENCES Abd El-Wahed WF. 2001. A multi-objective transportation problem under fuzziness. Fuzzy Sets and Systems 117: 27-33. Abd El-Wahed WF, Abo-Sinna MA. 2001. A hybrid fuzzy-goal programming approach to multiple objective decision-making problems. Fuzzy Sets and Systems 119: 71-85. Abd El-Wahed WF, Lee S. 2006. Interactive fuzzy goal programming for multi-objective transportation problems.The International Journal of Management Science 34: 158- 166. Aenaida RS, Kwak NW. 1994. A linear goal programming for transshipment problems with flexible supply and demand constraints. Journal of Operational Research Society 45(2): 21-24. = 7, Solving a Multi-objective Transpor tation Problem 22 Amirteimoori A. 2010. An extended transportation problem: a DEA-based approach. CEJOR (2011) 19: 513-521. DOI: 10.1007/s10100-010-0140-0. Aneja YP, Nair KPK. 1979. Bicriteria transpor tation problems. Management Science 25: 73-80. B i t A K , B i s w a l M P, A l a m S S . 1 9 9 2 . F u z zy p r o g r a m m i n g a p p r o a c h to m u l t i - c r i te r i a decision-making transportation problem. Fuzzy Sets and Systems 50: 35-41. Bit AK, Biswal MP, Alam SS. 1993a. Fuzzy programming approach to multi-objective solid transportation problem. Fuzzy Sets and Systems 57: 183-194. Bit AK, Biswal MP, Alam SS. 1993b. An additive fuzzy programming model for multi- objective transportation problem. Fuzzy Sets and Systems 57: 13-19. C h a l l a m G A . 1 9 9 4 . F u z z y g o a l p r o g r a m m i n g ( F G P ) a p p r o a c h t o a s t o c h a s t i c transportation problem under budgetary constraints. Fuzzy Sets and Systems 66(3): 29-39. Chanas S, Kolodziejckzy W, Machaj AA . 1984. A fuzzy approach to the transportation problem. Fuzzy Sets and Systems 13: 211-221. Chanas S, Kuchta D. 1998. Fuzzy integer transportation problem. Fuzzy Sets and Systems 98: 18-29. Climaco JN, Antunes CH, Alves MJ. 1993. Interactive decision support for multi-objective transpor tation problems. European Journal of Operational Research 65: 58-67. Diaz A. 1976. Solving multi-objective problems. Ekonomicko-matematicky Obzor 14: 267-274. Diaz A . 1979. Finding a complete description of all eff icient solutions to a multi- objective transportation problem. Ekonomicko-matematicky Obzor 15: 62-73. Ehrgott M, Verma RA . 2001. Note on solving multi-criteria transpor tation-location problems by fuzzy programming. Asia-Pacif ic Operational Research 18: 149-164. Herrera F, Herrera-V iedma E, Verdegay J. 1995. Direct approach processes in group decision making using linguistic OWA operators. Fuzzy Sets and Systems 79: 175-190. Hong-Wei Z, Hong-ping S, JIan-qiang, L. 2009. Multi-objective transportation optimization based on Lam-GA. In: Proceedings of the IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS 2009); 2009 November 20-22; Shanghai, China. IEEE. p 214-217. Isermann H. 1979. The enumeration of all eff icient solutions for a linear multi-objective transpor tation problem. Naval Research Logistics Quar terly 26: 123-139. Kasana HS, Kumar KD. 2000. An eff icient algorithm for multi-objective transpor tation problems. Asia-Pacif ic Operational Research 17: 27-40. C.O. Talaue and C.G. Tapia 23 L a i Y, H w a n g C . 1 9 9 6 . F u z z y m u l t i p l e o b j ec t i v e d ec i s i o n s m a k i n g : M e t h o d s a n d applications. Berlin: Springer. Le e S a n g M , M o o r e L J . 1 9 9 3 . O p t i m i z i n g t r a n s p o r t a t i o n p r o b l e m s w i t h m u l t i p l e objectives. AIEE Transactions 5: 33-38. Li L, Lai KK. 2000. A fuzzy approach to the multi-objective transportation problem. Computers & Operational Research 27: 43-57. Mistuo G, Yinzhen L, Kenichi I. 1999. Solving multi-objective transportation problem by spanning tree-based genetic algorithm. IEICE Transactions on Fundamentals 12: 2802- 2810. Paragon Decision Technology. 2013. Advanced Integrated Multidimensional Modeling Software (AIMMS). Ri n g u e s t J L , Ri n k s D B . 1 9 8 7. I n t e r a c t i ve s o l u t i o n s f o r t h e l i n e a r m u l t i - o b j e c t i ve transpor tation problems. European Journal of Operational Research 32: 96-106. Romero C. 1991. Handbook of critical issues in goal programming. Oxford, New York: Pergamon Press. Tamiz M, Jones DF, Romero C. 1998. Goal programming for decision-making: An overview of the current state-of-the-ar t . European Journal of Operational Research 111: 569- 581. Tapia C, Mur tagh B. 1989. The use of preference criteria in interactive multi-objective mathematical programming. Asia-Pacif ic Journal of Operations Research 6: 131-147. Tapia C, Mur tagh B. 1991. Interactive fuzzy programming with preference criteria in multi-objective decision-making. Computers and Operations Research 3: 307-316. Tapia C, Murtagh B. 1992. Interactive group decision-making using fuzzy programming with preference criteria. Fuzzy Sets and Systems 45: 13-23. Wang J, Han Z, Zhang H. 2012. Multi-criteria group decision-making method based on intuitionistic interval fuzzy information. Group Decis Negot (September 2012) DOI 10.1007/s10726-012-9316-4. Wu F, Lu J, Zhang G, Ruan D. 2007. The development of a fuzzy multi-objective group decision-making support system. In: Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2007); 2007 July 23-26; Imperial College, London, UK. IEEE. p 670-675. Xiong J, Tan X, Yang K, Chen Y. 2013. Fuzzy group decision-making for multi-objective problems: Tradeoff between consensus and robustness. Journal of Applied Mathematics (2013), Article ID 657978, http://dx.doi.org/10.1155/2013/657978. Xu Z, Chen J. 2007. An interactive method for fuzzy multiple attribute group decision making. Information Sciences 1: 248-263. Solving a Multi-objective Transpor tation Problem 24 Zhang G, Lu J. 2004. A group decision- making method with fuzzy weights for decision makers, fuzzy preferences for alternatives and fuzzy judgments for selection criteria, I n : P r o c e e d i n g s o f t h e I n t e r n a t i o n a l C o n f e r e n c e o n F u z z y I n f o r m a t i o n P r o c e s s i n g Theories and Applications, Beijing, China, March 2003, volume 2, Tsinghua University Press, China, p 655-661. _______________ Cherryl O. Talaue, PhD is an Assistant Professor at the Institute of Mathematics, University of the Philippines Diliman. Cesar G. Tapia, PhD is a retired Professor of the Institute of Mathematics, University of the Philippines Diliman.