Search

The k-tree problem is to find a tree with k vertices in a given graph such that the total cost is minimum and is known to be NP-hard. In this paper, the k-tree problem with fuzzy weights is firstly formulated as the chance-constrained programming by using the possibility measure and the credibility measure. Then an oriented tree and knowledge-based hybrid genetic algorithm is designed for solving the proposed fuzzy programming models. Keywords: Fuzzy set, credibility measure, spanning tree, genetic algorithm, quadratic tree, k-tree. [ABSTRACT FROM AUTHOR]

The derivative problems from the classical shortest path problem (SPP) are becoming more and more important in real life[1]. The dissimilar shortest paths problem is a typical derivative problem. In Vehicles Navigation System(VNS),it is necessary to provide drivers alternative paths to select. Usually, the path selected is a dissimilar path to the jammed path. In fact, "dissimilar" is fuzzy. Considering traffic and transportation networks in this paper, we put forward to the definition of dissimilar paths measure that takes into account the decision maker's preference on both the road sections and the intersections. The minimum model is formulated in which not only the length of paths but also the paths dissimilar measure is considered. And a genetic algorithm also is designed. Finally, we calculate and analyze the dissimilar paths in the traffic network of the middle and east districts of Lanzhou city in P.R. of China by the method proposed in this paper. [ABSTRACT FROM AUTHOR]