Article Preview
TopIntroduction
In recent decades, there has been a growth of interest in methods for finding optimal solutions to a class of problems called combinatorial optimization. The subject is very wide and many books and articles have been published on its various aspects. Typical examples of combinatorial optimization problems are the travelling salesman (Lawler, 1985; Gutin and Punnen, 2002; Gutin, 2013), variants of the assignment problem (Cela et al., 2014), scheduling problems (Pinedo et al., 2015), the set covering (Beasley, 1990; Boschetti and Maniezzo, 2015), and vehicle routing problems (Coelho and Laporte, 2015). Combinatorial problems are normally easy to describe but difficult to solve (Korte and Vygen, 2012). The foundations for the theory of computational complexity are to be found in Cook’s (1971) seminal paper. In his paper, Cook attempted to classify problems in practice as easy or hard. A problem is called easy if we can develop an algorithm which solves the problem to optimality in a polynomial-time (Du and Pardalos, 2005). A problem is called hard or intractable if such efficient algorithms do not exist or the solution cannot be found within a reasonable computational time bound.
Due to the practical importance of combinatorial optimization problems, many methods have been developed for solving them (Pulleyblank, 2014); Martello and Ries, 2015); Mohanty et al., 2017). These methods can be classified as either exact or approximate. Exact methods guarantee to find an optimal solution in a bounded amount of time. Of course, for those combinatorial optimization problems which belong to the class NP-hard (Garey and Johnson, 1979), exact methods need an exponential amount of time. Thus, approximation methods which usually called heuristics, are often considered to be the only practical tools available to solve hard combinatorial optimization problems.
This paper introduces a new idea for the integration of approaches for hard combinatorial optimization problems. The paper consists of two main parts. The first part focuses on description of the theory and mathematics of the so-called fuzzy greedy evaluation concept. The second part demonstrates computational examples of the proposed concept for hard combinatorial optimization problems. The concluding remarks contain some suggestions for further research.
Fuzzy Sets
In many real-world problems fuzzy sets allow us to represent vague concepts expressed in natural language. The membership function of a fuzzy set A can be denoted by µA: X → [0,1]. Each fuzzy set should be uniquely defined by one particular membership function. Consider a fuzzy set where membership function is defined in Equation (1). This is one of the general formulae of a parameterized family of membership functions described in Klir and Yuan (1995).
(1)This fuzzy set expresses, in a particular form, the general concept of a class of real numbers that are close to r. When the non-negative parameter ρ increases, the graph of µA(x) becomes narrower. The function has the following properties: µA(r) = 1 and µA(x) < 1 for all x ≠ r. For a complete discussion of fuzzy sets, we refer to (Klir and Yuan, 1995; Zimmermann, 2001; Wang and Klir, 2013).