三角模糊数的一种排序方法

根据模糊数学原理,定义了一个三角模糊数的排序函数,并利用可能度研究三角模糊数的排序方法.对一组待排序的三角模糊数,根据不同情况,分别给出了相应的可能度计算公式,其结果反映的是一个三角模糊数大于另一个三角模糊数的可能程度,该公式具有计算方便等特点.最后,由两两比较的结果建立一个可能度矩阵,并给出了一种基于可能度矩阵的三角模糊数排序算法.应用实例表明,这种算法具有一定的合理性.     

具有模糊信息的多目标运输问题求解

提出一种求解具有模糊信息的多目标运输问题的方法。利用专家意见通过模糊算法集给从各产地到各目的地运送单位物资的模糊综合指标值,运用一种对模糊数排序的方法,将模糊多目标运输问题转化为单目标的运输问题进行求解,最后给出了一个数值例子。     

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

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

带有模糊约束的最优路

到目前为止,最短路问题已有很多好的算法,但这些算法都是假定所有弧的长度均为确定的数值;而在实际中,常会遇到一些网络,其所有弧的长度具有不确定性.本文将这种不确定性以模糊数的形式给定,然后提出了模糊最优路的概念,并针对L-R型模糊数给出了具体的算法.     

基于结构元方法的模糊数互补判断矩阵排序法

利用模糊结构元方法,研究了决策信息以模糊数互补判断矩阵形式给出的有限方案决策问题。给出了模糊数互补判断矩阵的定义,介绍了模糊数排序的一种简捷方法——组合序。在该序的基础上,对模糊有序加权平均(FOWA)算子的若干性质进行证明。利用该算子能够将模糊数互补判断矩阵转换为实数矩阵,进而,对模糊数互补矩阵的排序问题转换成实数矩阵的排序问题。只要矩阵中的元为有界闭模糊数,就可以利用FOWA算子进行排序。最后通过算例对比分析,算例表明利用本文的方法进行排序更为简捷。     

基于广义判断形式的模糊排序方法

广义判断下的ＡＨＰ（ＧＪＡＨＰ）是一种广义ＡＨＰ。它是在研究不完全信息下的决策排序问题时，通过构造广义判断矩阵的数学模型而建立的一种广义ＡＨＰ。本文应用集值统计的方法，在区间判断标度基础上确定模糊判断矩阵元素的正模糊数表示。给出了基于模糊区间数排序权值向量的特征根算法。讨论了Ｆｕｚｚｙ环境下求解各种判断形式的模糊排序权值向量的方法。     

证券组合的模糊规划模型

通过结构元方法定义了一种模糊数排序准则,利用模糊约束将Markowitz投资组舍模型转化为模糊线性规划模型,并利用模糊数来描述证券的期望收益率和风险损失率,建立模糊数模糊证券投资组合模型.最后,利用定义的模糊数排序准则把模糊数规划问题转化为经典的线性规划问题,然后再对该模型进行求解,并通过算例阐述了该方法的有效性.     

模糊数双指标排序的结构元方法

针对现有模糊数排序存在的一些问题,提出了双指标的模糊数排序方法。给出了模糊数隶属函数与其单调变换函数相互转化方法。定义波动数与特征数两个指标,利用这两个指标对模糊数进行排序,并给出了排序原则。该方法可以对各种模糊数进行排序,通过该排序原则常能够简化计算,同时,一定程度上能够弥补一些排序方法不能反映模糊数"波动"情况的问题。通过算例对比分析,本文的方法求解简单,并具有广泛适用性。     

模糊数排序的可能度方法

由两个模糊数的隶属函数确定三个面积,据此建立一个对模糊数进行大小比较的可能度计算公式.公式表达式非常简洁,同时还具有传递性、互补性等诸多良好的性质,因而具有很强的实用性和可操作性.对给定的一组模糊数,先利用两两比较的结果建立一个可能度矩阵,同时给出基于可能度矩阵的模糊数排序算法.最后给出一个排序算法的实例.     

基于模糊结构元表述的模糊数排序

讨论了如何利用结构元理论来解决模糊数的排序问题.首先,给出了四种经典的模糊数排序方法,并证明了这四种方法都可以利用结构元理记来表述;进而,提出了一种基于结构元理论的排序方法,给出了该方法的性质,并同传统方法进行了比较.     

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 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.     

网络最短的最优解集结构

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.     

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.     

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 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.     

Shortest path algorithms for knapsack type problems

The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm.     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.     

The first <Emphasis Type="Italic">K</Emphasis> minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。