模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Solving the knapsack problem with imprecise weight coefficients using genetic algorithms

This paper investigates solving the knapsack problem with imprecise weight coefficients using genetic algorithms. This work is based on the assumption that each weight coefficient is imprecise due to decimal truncation or coefficient rough estimation by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. We investigate the possibility of using genetic algorithms in solving the fuzzy knapsack problem without defining membership functions for each imprecise weight coefficient. The proposed approach simulates a fuzzy number by distributing it into some partition points. We use genetic algorithms to evolve the values in each partition point so that the final values represent the membership grade of a fuzzy number. The empirical results show that the proposed approach can obtain very good solutions within the given bound of each imprecise weight coefficient than the fuzzy knapsack approach. The fuzzy genetic algorithm concept approach is different, but gives better results than the traditional fuzzy approach.     

具有风险偏好的模糊网络最短路算法

运用结构元理论来求解具有风险偏好的、带有模糊权值的网络最短路问题.首先,简要介绍模糊结构元及相关定理.之后,提出了组合序,证明组合序是全序.组合序含有参数θ,随着θ的取值范围不同,序反映风险偏好的类型不同.在组合序和相关定理的基础上,证明了模糊网络最短路的判定定理,定理表明:求模糊网络最短路等价求一经典网络最短路,且风险偏好大小由θ的取值来确定.最后,通过一个例子来说明求解过程.     

Ranking generalized fuzzy numbers in fuzzy decision making based on the left and right transfer coefficients and areas

Although a number of recent studies have proposed ranking fuzzy numbers based on the deviation degree, most of them have exhibited several shortcomings associated with non-discriminative and counter-intuitive problems. In fact, none of the existing deviation degree methods has guaranteed consistencies between the ranking of fuzzy numbers and that of their images under all situations. They have also ignored decision maker’s attitude toward risk, which significantly influences final ranking result. To overcome the above-mentioned drawbacks, this study proposes a new approach for ranking fuzzy numbers that ensures full consideration for all information of fuzzy numbers. Accordingly, an overall ranking index is obtained by the integration of the information from the left and the right (LR) areas between fuzzy numbers, the centroid points of fuzzy numbers and the decision maker’s attitude toward risk. This new method is efficient for evaluating generalized fuzzy numbers and distinguishing symmetric fuzzy numbers. It also overcomes the shortcomings of the existing approaches based on deviation degree. Several numerical examples are provided to illustrate the superiority of the proposed approach. Lastly, a new fuzzy MCDM approach for generalized fuzzy numbers is proposed based on the proposed ranking approach and the concept of generalized fuzzy numbers. The proposed fuzzy MCDM approach does not require the normalization process and thus avoids the loss of information results from transforming generalized fuzzy numbers to normal form.     

具有模糊支付的Moran过程演化博弈动态

以往对演化博弈的研究都假设个体从博弈中获得的支付是确定的并以精确的数来表示。然而由于受环境中各种不确定因素的影响,个体博弈时所获得的支付并不是一个精确的数值,而需要用一个模糊数来表示。本文研究模糊支付下2×2的对称博弈, 利用模糊数的运算, 分析具有模糊支付的有限种群Moran过程演化动态。在弱选择下以梯形模糊数和三角模糊数表示博弈支付,计算策略的模糊扎根概率,分析自然选择有利于策略扎根及策略成为模糊演化稳定策略的条件。将经典博弈推广到模糊环境中丰富了演化博弈理论,更具有现实意义。     

A simple approach to fuzzy critical path analysis in project networks

This paper develops a simple approach to critical path analysis in a project network with activity times being fuzzy numbers. The idea is based on the linear programming (LP) formulation and fuzzy number ranking method. The fuzzy critical path problem is formulated as an LP model with fuzzy coefficients of the objective function, and then on the basis of properties of linearity and additivity, the Yager’s ranking method is adopted to transform the fuzzy LP formulation to the crisp one which can be solved by using the conventional streamlined solution methods. Consequently, the critical path and total duration time can be obtained from the derived optimal solution. Moreover, in this paper we also define the most critical path and the relative path degree of criticality, which are theoretically sound and easy to use in practice. An example discussed in some previous studies illustrates that the proposed approach is able to find the most critical path, which is proved to be the same as that derived from an exhausted comparison of all possible paths. The proposed approach is very simple to apply, and it is not require knowing the explicit form of the membership functions of the fuzzy activity times.     

New models for shortest path problem with fuzzy arc lengths

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.     

模糊值函数分析学的结构元方法简介(Ⅰ)——结构元与模糊数运算

简述了模糊值函数分析学在具体工程实践应用中存在的困难和障碍,系统地介绍了模糊结构元方法在模糊值函数分析学中的应用,包括模糊结构元的概念、模糊数的模糊结构元表示形式、基于结构元表达形式的模糊数运算与隶属函数确定.模糊结构元方法将复杂的模糊数运算转化为一类单调有界函数的运算,不仅仅为模糊分析计算的简化提供了工具,同时也为模糊值函数分析学应用的研究开创了一条新的途径.     

Evaluation of fuzzy linear regression models by comparing membership functions

Fuzzy linear regression models can provide an estimated fuzzy number that has a fuzzy membership function. If a point that has the highest membership value from the estimated fuzzy number is not within the support of the observed fuzzy membership function, a decision-maker can have high risk from the estimate. In this study a modification of fuzzy linear regression analysis based on a criterion of minimizing the difference of the fuzzy membership values between the observed and estimated fuzzy numbers is proposed. Two numerical examples are used to evaluate the fuzzy regression models.     

Linear programming with fuzzy parameters: An interactive method resolution

This paper proposes a method for solving linear programming problems where all the coefficients are, in general, fuzzy numbers. We use a fuzzy ranking method to rank the fuzzy objective values and to deal with the inequality relation on constraints. It allows us to work with the concept of feasibility degree. The bigger the feasibility degree is, the worst the objective value will be. We offer the decision-maker (DM) the optimal solution for several different degrees of feasibility. With this information the DM is able to establish a fuzzy goal. We build a fuzzy subset in the decision space whose membership function represents the balance between feasibility degree of constraints and satisfaction degree of the goal. A reasonable solution is the one that has the biggest membership degree to this fuzzy subset. Finally, to illustrate our method, we solve a numerical example.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

Using fuzzy numbers in knapsack problems

This paper investigates knapsack problems in which all of the weight coefficients are fuzzy numbers. This work is based on the assumption that each weight coefficient is imprecise due to the use of decimal truncation or rough estimation of the coefficients by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. Our work intends to extend the original knapsack problem into a more generalized problem that would be useful in practical situations. As a result, our study shows that the fuzzy knapsack problem is an extension of the crisp knapsack problem, and that the crisp knapsack problem is a special case of the fuzzy knapsack problem.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

Solving the Shortest Path Problem with Interval Arcs

This paper presents an algorithm for the shortest path problem when the connected arcs in a transportation network are represented as interval numbers. The methodology proposed in this paper considers fuzzy preference ordering of intervals (Sengupta and Pal (2000), European Journal of Operational Research 127, 28–43) from pessimistic and optimistic decision maker’s point of view.     

A Biologically Inspired Optimization Algorithm for Solving Fuzzy Shortest Path Problems with Mixed Fuzzy Arc Lengths

The shortest path problem is among fundamental problems of network optimization. Majority of the optimization algorithms assume that weights of data graph’s edges are pre-determined real numbers. However, in real-world situations, the parameters (costs, capacities, demands, time) are not well defined. The fuzzy set has been widely used as it is very flexible and cost less time when compared with the stochastic approaches. We design a bio-inspired algorithm for computing a shortest path in a network with various types of fuzzy arc lengths by defining a distance function for fuzzy edge weights using \(\alpha \) cuts. We illustrate effectiveness and adaptability of the proposed method with numerical examples, and compare our algorithm with existing approaches.     

On a multicriteria shortest path problem

Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.     

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

基于效用函数的模糊数的比较与排序

对相同的模糊数进行比较,不同风险偏好的决策者,会得到不同的结论.效用函数是对风险偏好的度量,因此,模糊数的比较与排序的方法,一定要结合决策者的效用函数来构造.为此,根据效用函数定义了模糊效用函数,在此基础上定义了效用序.之后,证明效用序为全序,进一步利用结构元理论对效用序进行表述.根据效用函数反映风险偏好的程度,对效用序进行分类.这样,决策者对模糊数进行比较时,依据自身对风险偏好程度来选择效用序.