بهینه سازی چندمعیاره ی تعاملی مبتنی بر جستجوی پراکنده از اهداف فازی برای برنامه ریزی تولید ذغال سنگ

We present an interactive multi-criteria procedure that uses user defined tradeoff-cutting planes to identify promising feasible solution search space. New solutions in the promising feasible solution search space are constructed using combination of scatter and random search. The procedure of identifying tradeoff-cutting planes and scatter search continues for either a predetermined fixed number of iterations or until no solutions in the promising feasible solution search space are found. We formulate a coal production planning problem with fuzzy profit and fuzzy coal quality decision-maker utilities, and apply our procedure for additive and multiplicative decision-maker utilities.

Fuzzy logic is recognized as an important decision support tool due to its capability to incorporate linguistic non-crisp variable values (Elamvazuthi et al., 2012). The availability of software platforms such as Matlab with fuzzy toolbox is making the use of fuzzy logic very easy in production planning (Vasant, 2003 and Vasant et al., 2004). As a result, a variety of fuzzy linear programming (FLP) and heuristic (Vasant and Barsoum, 2010) applications have emerged from variety of industries ranging from textiles (Elamvazuthi et al., 2009), crude oil refinery (Vasant et al., 2012) to coal mining (Pendharkar, 1997). Interactive FLP has been applied to production planning in textile firms, transportation planning and crude oil refinery industries (Vasant et al., 2011, Peidro and Vasant, 2011 and Vasant et al., 2010a). Among the popular membership functions in FLP are linear and S-shaped membership functions (Bhattacharya and Vasant, 2007 and Vasant et al., 2010b). Diaz-Madrronero et al. (2010) describe different membership functions used in FLP and their benefits. Generally, linear membership functions are easy to use and have higher computational efficiency. S-shaped membership functions provide flexibility in describing uncertain and ill-known fuzzy problems (Elamvazuthi et al., 2010). Interactive multi-criteria problems involve simultaneous optimization of two or more conflicting objectives (Bas, 2012 and Vasant et al., 2007). Assuming an n-dimensional decision variable vector x=[x1,…,xn]T, a feasible solution set X such that the feasible set of decisions satisfy x∈X, a set of h≥2 criteria functions fh (x), and a group/individual utility function u, the interactive multi-criteria optimization problem is described as follows ( Troutt, 1994 and Steuer, 1986): equation(1) max{u(f1(x),…,fh(x)):x∈X⊏nR}max{u(f1(x),…,fh(x)):x∈X⊏Rn} Turn MathJax on Assuming that u(f1(x),…,fh(x))u(f1(x),…,fh(x)) is concave, twice differentiable and satisfies strict non-satiety1 assumption, any solution that maximizes (1) is called the best compromise solution ( Troutt, 1994 and Steuer, 1986). Most popular methods to find a compromise solution require user interaction to identify the compromise solution. These methods use cutting planes (Shin and Ravindran, 1991), Marginal Rate of Substitution (MRS) (Geoffrion et al., 1972), or abstract mass concept (AMC) (Troutt, 1994) to obtain the compromise solution. While all of these methods are similar in their implementation of user interaction, they are different in their assumptions and the manner in which they process information. The MRS method seeks tradeoff rates between different criteria to narrow the location of compromise solution. The AMC method is an advanced method that seeks the cutting plane information from the user to solve a continuous piecewise polynomial system of equations that yields direction specific gradients for different criteria, which are then used to identify a compromise solution half-space. The AMC is useful when the decision maker’s utility function is not known or when the decision maker’s utility function is known but there are too many criteria to optimize which renders MRS method too difficult to use. When the decision maker’s utility function is known and the decision-making criteria are reasonably small then constructing cutting planes is very simple. Shin and Ravindran (1991) illustrate how these cutting planes can be constructed. Generally, the construction of these cutting planes requires interaction from the user on his/her satisfaction about a computer generated solution. Typically, a possible solution is shown to the user and if the user is not satisfied with the shown solution then a cutting plane is constructed by using the value of shown solution and partial derivatives of utility function with respect to different criterion. Once a half-space for compromise solution is identified, finding the next feasible solution in half-space becomes the next problem to solve in an interactive multi-criteria optimization. A popular method that is used to identify feasible solutions in the half-space is called parameter space investigation (PSI) method (Steuer and Sun, 1995). The PSI method uses Monte Carlo strategy to randomly search for solutions in the solution half-space and retains solutions that belong to the solution half-space and rejects any other solutions. While the PSI works well and is independent of the number of criteria and the number of constraints, its performance is highly sensitive to the dimension of variable vector x (Steuer and Sun, 1995). For example, assuming that p(xs) is the probability that a randomly generated sth element of vector x, for s∈{1,…,n}, from the PSI method’s Monte Carlo strategy belongs to the feasible solution space then the probability that all elements belonging to the feasible solution space is given by View the MathML source∏s=1np(xs). When cutting/cutoff planes are added due to user interaction, half-space for the compromise solution only shrinks leading to new probabilities pnew(xs)≤p(xs)pnew(xs)≤p(xs), ∀xs. For large dimension of x or for several user interactions with reasonable dimension, finding feasible solutions using the PSI method gets difficult because View the MathML source∏s=1npnew(xs)→0 with higher dimension of x and increasing user interactions. Steuer and Sun (1995), using a multi-criteria linear programming problem, report that for n=10, PSI method finds only 10 feasible solutions in 100,000 trials and for n=20 no feasible solution can be found in 100,000 trials. Since user interaction only decreases the feasible region resulting in lower pnew(xs)pnew(xs), using PSI method may be inefficient for even small problems with n=5 and five user interactions. An alternative to the use of PSI method is the scatter search approach (Glover et al., 2000). Scatter search is an alternative approach to random search approach where generalized path construction in Euclidean space is used to construct solutions. In a scatter search approach, initial sets of solutions are randomly generated. Of these random solutions, the set of solutions that belong to the feasible region are called the reference set (Laguna and Marti, 2003). The solutions from reference set are combined, using convex and non-convex combinations, to identify new reference set solutions. A typical reference set contains 5–20 solutions and two solutions are combined at a time to generate new reference set solutions. If the new reference set solutions are better quality solutions than the solutions in previous reference set then the previous reference set is updated to contain the best 5–20 solutions. Occasionally, intensification and diversification strategies are used to explore solution search space ( Glover et al., 2003 and Laguna, 2002). Intensification uses minor Euclidean space perturbations to the existing reference set solutions to identify improvements. In diversification, either a random search or a line search is used in an attempt to identify solutions that are far away from the current reference set solutions. In this paper, we propose a multi-criteria coal production planning problem with fuzzy profit and fuzzy coal quality criteria. Next, we propose a scatter-search based interactive multi-criteria optimization procedure to identify promising solutions, and test the procedure using an example with additive and multiplicative decision-maker utilities. The rest of the paper is organized as follows. In Section 2, we propose the fuzzy multi-criteria model for coal production planning. In Section 3, we describe the scatter search based interactive multi-criteria optimization procedure for solving interactive multi-criteria optimization problems. In Section 4, we describe a production planning example, apply scatter search procedure and provide the results of our experiments. In Section 5, we provide a discussion on the proposed procedure. In Section 6, we conclude our paper with a summary.

In this paper, we developed a scatter search procedure for interactive multi-criteria optimization problems. We also proposed a fuzzy bi-criteria production planning problem in the coal mining industry. Using a coal production planning problem, we illustrated an application of scatter search procedure for additive and multiplicative decision-maker utilities. The results of our experiments indicate that the scatter search procedure works very well for interactive multi-criteria optimization problems. For our problem, the reference set solutions in scatter search procedure converge very fast, and five solutions with a maximum of five interactions worked very well. We believe that a natural extension to our study is to extend the scatter search procedure for solving multi-criteria combinatorial optimization problems. The extension would require the proposed scatter search procedure to be combined with other heuristic search procedures such as tabu search, simulated annealing or genetic algorithms. When combined with a heuristic procedure, scatter search may be used to obtain values for variables that take real-number values, and a heuristic search procedure (tabu search, simulated annealing or genetic algorithm) may be used to obtain values for variables that take discrete/integer values.