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 & 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 & Maniezzo, 2015), and vehicle routing problems (Coelho & Laporte, 2015). Combinatorial problems are normally easy to describe but difficult to solve (Korte & 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 an algorithm can be developed which solves the problem to optimality in a polynomial-time (Du & 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 & Ries (2015); Nishi 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 & 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 overviews a new idea, so-called fuzzy greedy evaluation concept for the integration of approaches for hard combinatorial optimization problems. The paper also provides a comprehensive discussion on mathematics of the proposed methodology. In this presentation, the proposed method can be seen as a generic heuristic for the integration of approaches to hard combinatorial optimization problems. Furthermore, the current work shows another application of the proposed method with different objectives in addition to the previously published literature on the same subject. For example, it shows that how different adaptations of the proposed method can be yielded to different results.
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. More detailed discussions of fuzzy sets and their properties can be found in (Klir & Yuan, 1995; Zimmermann, 2001; Wang & Klir, 2013).