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.     

模糊最短路的一种算法

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

Fuzzy facility location-allocation problem under the Hurwicz criterion

Facility location-allocation (FLA) problem has been widely studied by operational researchers due to its many practical applications. Many researchers have studied the FLA problem in a deterministic environment. However, the models they proposed cannot accommodate satisfactorily various customer demands in the real world. Thus, we consider the FLA problem with uncertainties. In this paper, a new model named α-cost model under the Hurwicz criterion is presented with fuzzy demands. In order to solve this model, the simplex algorithm, fuzzy simulations and a genetic algorithm are integrated to produce a hybrid intelligent algorithm. Finally, some numerical examples are presented to illustrate the effectiveness of the proposed algorithm.     

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.     

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.     

Shortest Path Problem on a Network with Imprecise Edge Weight

A network with its arc lengths as imprecise number, instead of a real number, namely, interval number and triangular fuzzy number is considered here. Existing ideas on addition and comparison between two imprecise numbers of same type are introduced. To obtain a fuzzy shortest path from a source vertex to all other vertices, a common algorithm is developed which works well on both types of imprecise numbers under consideration. In the proposed algorithm, a decision-maker is to negotiate with the obtained fuzzy shortest paths according to his/her view only when the means are same but the widths are different of the obtained paths. Otherwise, a fuzzy optimal path is obtained to which the decision-maker always satisfies with different grades of satisfaction. All pairs fuzzy shortest paths can be found by repeated use of the proposed algorithm.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Fuzzy minimum weight edge covering problem

Minimum weight edge covering problem, known as a classic problem in graph theory, is employed in many scientific and engineering applications. In the applications, the weight may denote cost, time, or opponent’s payoff, which can be vague in practice. This paper considers the edge covering problem under fuzzy environment, and formulates three models which are expected minimum weight edge cover model, α-minimum weight edge cover model, and the most minimum weight edge cover model. As an extension for the models, we respectively introduce the crisp equivalent of each model in the case that the weights are independent trapezoidal fuzzy variables. Due to the complexity of the problem, a hybrid intelligent algorithm is employed to solve the models, which can deal with the problem with any type of fuzzy weights. At last, some numerical experiments are given to show the application of the models and the robustness of the algorithm.     

Analysis of critical paths in a project network with fuzzy activity times

This paper proposes an approach to critical path analysis for a project network with activity times being fuzzy numbers, in that the membership function of the fuzzy total duration time is constructed. The basic idea is based on the extension principle and linear programming formulation. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy total duration time at α. By enumerating different values of α, the membership function of the fuzzy total duration time is constructed, and the fuzzy critical paths are identified at the same time. Moreover, by applying the Yager ranking method, definitions of the most critical path and the relative degree of criticality of paths are developed; and these definitions are theoretically sound and easy to use in practice. Two examples with activity times being fuzzy numbers of L-R and L-L types discussed in previous studies are solved successfully to demonstrate the validity of the proposed approach. Since the total duration time is completely expressed by a membership function rather than by a crisp value, the fuzziness of activity times is conserved completely, and more information is provided for critical path analysis.     

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.     

On standard models of fuzzy region connection calculus

The Region Connection Calculus (RCC) is perhaps the most influential topological relation calculus. Based on the first-order logic, the RCC, however, does not fully meet the needs of applications where the vagueness of entities or relations is important and not ignorable. This paper introduces standard models for the fuzzy region connection calculus (RCC) proposed by Schockaert et al. (2008) [18]. Each of such a standard fuzzy RCC model is induced by a standard RCC model in a natural way. We prove that each standard fuzzy RCC model is canonical in the sense that any satisfiable set of fuzzy RCC8 constraints have a solution in it. A polynomial realization algorithm is also provided. As a side product, we show similar sets of fuzzy constraints have similar solutions if both are satisfiable. This allows us to approximate fuzzy RCC constraints that have arbitrary bounds by those have bounds with finite precision.     

Dynamic fuzzy reliability models of degraded hold-down structures for folded solar array

The hold-down structures are of considerable importance to the launch of solar array. Due to the difficulties in obtaining sufficient load specimen, it is imprecise to construct the stress as random variables. Therefore, dynamic fuzzy reliability models are developed in this paper, which resolve the problems in dealing with the interaction between the fuzzy stress process and the stochastic strength process. Even for a deterministic fuzzy stress process, the influences of material statistical properties on reliability can be affected by the level α of fuzzy stress. Meanwhile, the level α relates to investment in the collection of information about the fuzzy stress on hold-down bar. Hence, the models can be used for the economic analysis and optimal design of hold-down bar. Finally, key fuzzy parameters of stress, which have significant influences on both the reliability behavior and the effects of material statistical properties on reliability, are identified and some suggestions for the reliability enhancement of hold-down bar are provided in this paper.     

Fuzzy real algebra: Some results

In this paper, the possibility to perform easily most of the extended n-ary operations on fuzzy subsets of the real line is shown. A general algorithm is given. These results are particularized for usual operations such as addition, subtraction, multiplication, division, ‘max’ and ‘min’ operations for normalized convex fuzzy subsets of the real line, i.e. fuzzy numbers. A three parameters representation for fuzzy numbers is shown to be very convenient to perform usual operations. Lastly, interpretative comments about fuzzy real algebra are given and possible applications pointed out.     

Pendant-medians

The median of a network is any point in the network that minimizes the sum of the shortest distances from it to each vertex. Let's omit from this sum the distance to any vertex that is intermediate on the shortest path from the median to another vertex. In other words, include in the sum only the pendant vertices of the shortest distance spanning free. A pendant-median is any point in the network that minimizes this revised sum of the shortest distances. A pendant-median models facility locations in which customers can be served without penalty along the route to other, more distant customers.This paper presents a simple algorithm to locate a pendant-median of a tree network and presents several results for general networks.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

Fuzzy project scheduling problem and its hybrid intelligent algorithm

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers a type of project scheduling problem with fuzzy activity duration times. According to some management goals, three types of fuzzy models are built to solve the project scheduling problem. Moreover, the technique of fuzzy simulation and genetic algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy models. Finally, some numerical examples are given to illustrate the effectiveness of the algorithm.     

A hybrid intelligent algorithm for portfolio selection problem with fuzzy returns

Portfolio selection theory with fuzzy returns has been well developed and widely applied. Within the framework of credibility theory, several fuzzy portfolio selection models have been proposed such as mean–variance model, entropy optimization model, chance constrained programming model and so on. In order to solve these nonlinear optimization models, a hybrid intelligent algorithm is designed by integrating simulated annealing algorithm, neural network and fuzzy simulation techniques, where the neural network is used to approximate the expected value and variance for fuzzy returns and the fuzzy simulation is used to generate the training data for neural network. Since these models are used to be solved by genetic algorithm, some comparisons between the hybrid intelligent algorithm and genetic algorithm are given in terms of numerical examples, which imply that the hybrid intelligent algorithm is robust and more effective. In particular, it reduces the running time significantly for large size problems.     

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

L1 cheapest paths in “Fjord Scenery”

We show a simple proof of the existence of a path on the “border of water and rocks” based on combinatorial induction procedure and we present an algorithm for computing L₁ shortest path in “Fjord Scenery”. The proposed algorithm is a version of the Dijkstra technique adapted to a rectangle map with a square network. A few pre-processing modifications of the algorithm following from the combinatorial procedure are included. The validity of this approach is shown by numerical calculations for an example.