Search

Solving the shortest path problem is very difficult in situations such as emergency rescue after a typhoon: road-damage caused by a typhoon causes the weight of the rescue path to be uncertain and impossible to represent using single, precise numbers. In such uncertain environments, neutrosophic numbers can express the edge distance more effectively: membership in a neutrosophic set has different degrees of truth, indeterminacy, and falsity. This paper proposes a shortest path solution method for interval-valued neutrosophic graphs using the particle swarm optimization algorithm. Furthermore, by comparing the proposed algorithm with the Dijkstra, Bellman, and ant colony algorithms, potential shortcomings and advantages of the proposed method are deeply explored, and its effectiveness is verified. Sensitivity analysis performed using a 2020 typhoon as a case study is presented, as well as an investigation on the efficiency of the algorithm under different parameter settings to determine the most reasonable settings. Particle swarm optimization is a promising method for dealing with neutrosophic graphs and thus with uncertain real-world situations. [ABSTRACT FROM AUTHOR]

Shortest path (SP) optimization problems arise in a wide range of applications such as telecommunications and transportation industries. The main purpose of these problems is to find a path between two predetermined nodes within a network as cheaply or quickly as possible. Conventional SP problems generally assume that the arc weights are defined by crisp variables, though imprecise data have been lately incorporated into the analysis. The present study formulates the SP problem in a directed interval-valued triangular fuzzy network. The resulting interval-valued fuzzy SP (IVFSP) problem is converted into a multi objective linear programming (MOLP) problem. Then, a lexicographic optimization structure is used to obtain the efficient solution of the resulting MOLP problem. The optimization process confirms that the optimum interval-valued fuzzy shortest path weight preserves the form of an interval-valued triangular fuzzy number. The applicability of the proposed approach is illustrated through an example dealing with wireless sensor networks. [ABSTRACT FROM AUTHOR]

Researchers have studied several different types of directed shortest path (SP) problems under fuzzy environment. However, few researchers have focused on solving this problem in an interval-valued fuzzy network. Thus, in order to light these, we investigate a generalized kind of the SP problem under interval-valued fuzzy environment namely all pairs shortest path (APSP) problem. The main contributions of the present study are fivefold: (1) In the interval-valued fuzzy network under consideration, each arc weight is represented in terms of interval-valued fuzzy number. (2) We seek the shortest weights between every pair of nodes in a given interval-valued fuzzy network based on a dynamic approach. (3) In contrast to most existing approaches, which provide the shortest path between two predetermined nodes, the proposed approach provides the interval-valued fuzzy shortest path between every pair of nodes. (4) Similarly to the competing methods in the literature, the proposed approach not only gives the interval-valued fuzzy weights of all pairs shortest path but also provides the corresponding interval-valued fuzzy APSP. (5) The efficiency of the proposed approach is illustrated through two applications of APSP problems in wireless sensor networks and robot path planning problems. [ABSTRACT FROM AUTHOR]

Many studies have shown that Physarum polycephalum slime mold is able to find the shortest path in a maze. In this paper we study this behavior in a network, using a hyperbolic model of chemotaxis. Suitable transmission and boundary conditions at each node are considered to mimic the behavior of such an organism in the feeding process. Several numerical tests are presented for special network geometries to show the qualitative agreement between our model and the observed behavior of the mold. [ABSTRACT FROM AUTHOR]

Intelligent Transportation Systems (ITS) are defined as those systems utilizing synergistic technologies and systems engineering concepts to develop and improve transportation systems. In this paper, a novel route selection problem based on the envisaged driving mode with dynamic signals in ITS is proposed. It belongs to a kind of the shortest path problem of dynamic weight-varying networks, and the arc-weights of the network vary with the arc-chosen, so it cannot be solved by the existing greedy algorithms. According to the characteristics of the proposed problem, firstly, a dynamic programming model for the driving mode on a single path is established. Secondly, two algorithms for solving the route selection problem based on the former mode are developed. One is a brute-force algorithm based on matrix expansion with the computational complexity ofO (Nt × n²). The other is an improved adaptive ant colony algorithm with the complexity ofO (Nc × m × n²). Finally, the computational experiments show the advantages and disadvantages of the two effective algorithms with numerical examples. [ABSTRACT FROM AUTHOR]

To compute optimal paths between locations in road networks is an important operation for e.g. transport business. Efficient algorithms for path planning usually assume a single start and a single target. In some scenarios, however, we want to compute all shortest paths from a set of starts to a set of targets. If we use the one-to-one planning in a loop, we consider each path as an independent computation. The drawback: we cannot take benefit of similarities between planning steps. In this paper, we present an approach that addresses this problem and provides a many-to-many path planning. An example that is heavily based on many-to-many path planning: given a home depot and a set of delivery points, what is the optimal round-trip that starts at the home depot, approaches each delivery point and turns back to the home depot. This problem is known as the Traveling Salesman Problem, but usually it is not applied to real road networks. In this paper we describe the efficient many-to-many path planning that is based on A *. It significantly reduces the number of visited crossings due to computation similarities. We adapt the approach to provide a solution for the Traveling Salesman Problem on road networks. [ABSTRACT FROM AUTHOR]