Search

This paper proposes a methodology for the optimal design of series of sewer pipes including pumping stations. It employs a Shortest Path Algorithm to select the optimal combination of pipe diameters and invert elevations, as well as the optimal pumping features such as the number of pumps, location, and pumping head. The methodology is intended to be applied to the design of any sewer series. Although these are uncommon in real infrastructure, the study allows an analysis of the effect of pipe roughness, inflows, and pipe length on the total cost of the system and pumping features. The methodology was tested in theoretical series of 10 and 20 pipes as well as in a real series that is part of the sewer system of Bogotá, Colombia. The resulting designs suggested that using smooth pipes and reducing the pumping flow rate would decrease the cost of sewer systems in flat terrain. [ABSTRACT FROM AUTHOR]

The Shortest path problem is highly relevant in our daily lives, addressing uncertainties like traffic conditions and weather variations. To handle such uncertainties, we utilize Fuzzy Numbers. This paper focuses on Bipolar Neutrosophic Fuzzy Numbers, which have dual positive and negative aspects. They provide a robust framework for representing arc (node/edge) weights, signifying uncertain travel times between nodes. Importantly, these weights can change over time in bipolar neutrosophic fuzzy graphs. Our study introduces an extended Bellman-Ford Algorithm for identifying optimal paths and minimum times with time-dependent Bipolar Neutrosophic Fuzzy arc weights. We demonstrate its effectiveness through a step-by-step numerical example and conduct a comparative analysis to evaluate its efficiency. [ABSTRACT FROM AUTHOR]

The shortest path problem is a classic optimization problem in graph theory and computer technology. It involves identifying the shortest path between two nodes in a graph, where each edge has a numerical weight. In this paper, we put our effort into examining the use of the dynamic programming method to evaluate the shortest path (SP) between the two specified nodes in a multistage network where the parameter is a multi-value neutrosophic number (MVNN). Firstly, we propose an algorithm based on the forward and backward approach in an uncertain environment and also implement our approach in the Python-3 programming language. Furthermore, a numerical illustration has been provided to showcase the effectiveness and robustness of the novel model. [ABSTRACT FROM AUTHOR]

We present a theoretical framework that links Fermat's principle of least time to optimal transport theory via a cost function that enforces local transport. The proposed cost function captures the physical constraints inherent in wave propagation; when paired with specific mass distributions, it yields shortest paths in the considered media through the optimal transport plans. In the discrete setting, our formulation results in physically significant optimal couplings, whose off-diagonal entries identify shortest paths in both directed and undirected graphs. For undirected graphs with positive edge weights, commonly used to parameterize seismic media, our method provides solutions to the Eikonal equation consistent with those from the Dijkstra algorithm. For directed negative-weight graphs, corresponding to transportation cost matrices with negative entries, our approach aligns with the Bellman–Ford algorithm but offers considerable computational advantages. We also highlight potential research directions. These include the use of sparse cost matrices to reduce the number of unknowns and constraints in the considered transportation problem, and solving specific classes of optimal transport problems through the Dijkstra algorithm to enhance computational efficiency. [ABSTRACT FROM AUTHOR]

We develop a projection recurrent neural network (RNN) to obtain the solution of the shortest path problem (SPP). Our focus on the paper is to give a compact single-layer structure RNN model to solve the SPP. To present the RNN model, we utilise a mixed linear complementarity problem (MLCP). Moreover, the developed RNN is proved to be globally stable. Finally, some numerical simulations are stated to show the performance of the presented approach. We compare the results with some other methods. [ABSTRACT FROM AUTHOR]

The most well-known subject in graph theory is the shortest path problem (SPP), which has real-world applications in several different fields of study, including transportation, emergency services, network communications, fire station services, etc. The arc weights of the applicable SP problems are typically represented by fuzzy numbers in real-world applications. In this paper, we discussed the process of finding the shortest distance in a connected graph network in which the arc weights are multi-valued neutrosophic numbers (MNNs). Moreover, here we compare our method with some of the existing results and illustrate one implementation of our method with the help of one numerical example. [ABSTRACT FROM AUTHOR]

The shortest path (SP) problem (SPP) has several applications in graph theory. It can be used to calculate the distance between the provided initial and final vertex in a network. In this paper, we employed the Fermatean neutrosophic number as the appropriate edge weight of the network to estimate the SP connecting the start and end vertex. This technique is highly useful in establishing the shortest path for the decision-maker under uncertainty. We also investigated its effectiveness in comparison to several existing methods. Finally, a few numerical tests were performed to demonstrate the validity and stability of this new technique, as well as to compare different types of shortest paths with different networks. [ABSTRACT FROM AUTHOR]

Many spatial applications benefit from the fast answering to a seemingly simple spatial query: "Is a point of interest (POI) 'in-path' to the shortest path between a source and a destination?" In this context, an in-path POI is one that is either on the shortest path or can be reached within a bounded yet small detour from the shortest path. The fast answering of the in-path queries is contingent on being able to determine without having to actually compute the shortest paths during runtime. Thus, this requires a precomputation solution. The key contribution of the paper is the development of an in-path oracle that is based on precomputation of which pairs of sources and destinations are in-path with respect to the given POI. For a given road network with n nodes and m POIs, an O (m × n) -sized oracle is envisioned based on the reduction of the well-separated pairs (WSP) decomposition of the road network. Furthermore, an oracle can be indexed in a database using a B-tree that can answer queries at very high throughput. Experimental results on the real road network POI dataset illustrate the superiority of this technique compared to a baseline algorithm. The proposed approach can answer ≈ 1.5 million in-path queries per second compared to a few hundred per second using a suitable baseline approach. [ABSTRACT FROM AUTHOR]

In this paper, we consider an ambiguity-averse multistage network game between a user and an attacker. The arc costs are assumed to be random variables that satisfy prescribed first-order moment constraints for some subsets of arcs and individual probability constraints for some particular arcs. The user aims at minimizing its cumulative expected loss by traversing between two fixed nodes in the network, while the attacker's objective is to maximize the user's expected loss by selecting a distribution of arc costs from the family of admissible distributions. In contrast to most of the related studies, both the user and the attacker can dynamically adjust their decisions at particular nodes of the user's path. By observing the user's decisions, the attacker may reveal some additional distributional information associated with the arcs emanated from the current user's position. It is shown that the resulting multistage distributionally robust shortest path problem (DRSPP) admits a linear mixed-integer programming reformulation (MIP). In particular, we distinguish between acyclic and general graphs by introducing different forms of non-anticipativity constraints. Finally, we perform a numerical study, where the quality of adaptive decisions and computational tractability of the proposed MIP reformulation are explored with respect to several classes of synthetic network instances. [ABSTRACT FROM AUTHOR]

Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants put down a volatile pheromone on the edges as they traverse them. At each vertex, the next edge to traverse is chosen using a decision rule based on the current pheromone level. There is a bidirectional flow of ants around the network. In a previous field study, it was observed that the trail networks approximately minimize the number of vertices, thus solving a variant of the popular shortest path problem without any central control and with minimal computational resources. We propose a biologically plausible model, based on a variant of the reinforced random walk on a graph, which explains this observation and suggests surprising algorithms for the shortest path problem and its variants. Through simulations and analysis, we show that when the rate of flow of ants does not change, the dynamics converges to the path with the minimum number of vertices, as observed in the field. The dynamics converges to the shortest path when the rate of flow increases with time, so the colony can solve the shortest path problem merely by increasing the flow rate. We also show that to guarantee convergence to the shortest path, bidirectional flow and a decision rule dividing the flow in proportion to the pheromone level are necessary, but convergence to approximately short paths is possible with other decision rules. [ABSTRACT FROM AUTHOR]

Associated path detection is considered as the major concern of the traditional shortest path issue. The associated path is generally represented by the shortest distance among the source and destination. In the transportation network, distance or cost detection may identify this associated path. Specifically, it is very important to discover the shortest distance that has a minimum number of nodes, and it will give the most optimized result. In this paper, the Fuzzy based Pareto Optimal (FPO) approach is used to discover the shortest paths in a network graph. Initially, the FPO technique finds the shortest paths in a network by using set of rules. Then, the Lexicographical model uses a set of rules to rank the shortest distance based on minimum distance value. From the ranking results, the optimal shortest path is selected based on the proposed Ant Lion Optimization (ALO) algorithm. So, this paper achieves multi objectives like shortest path ranking and selection of the optimal shortest path. Time, distance or cost, convergence time, fitness function, and mean square error are the parameters used to relate the performance of the proposed technique with state-of-the-art techniques. Comparative results display the robustness and proficiency of the proposed system with several works. [ABSTRACT FROM AUTHOR]

This article studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks. [ABSTRACT FROM AUTHOR]

This paper presents a new heuristic algorithm tailored to solve large instances of an NP-hard variant of the shortest path problem, denoted the cost-balanced path problem, recently proposed in the literature. The problem consists in finding the origin–destination path in a direct graph, having both negative and positive weights associated with the arcs, such that the total sum of the weights of the selected arcs is as close to zero as possible. At least to the authors' knowledge, there are no solution algorithms for facing this problem. The proposed algorithm integrates a constructive procedure and an improvement procedure, and it is validated thanks to the implementation of an iterated neighborhood search procedure. The reported numerical experimentation shows that the proposed algorithm is computationally very efficient. In particular, the proposed algorithm is most suitable in the case of large instances where it is possible to prove the existence of a perfectly balanced path and thus the optimality of the solution by finding a good percentage of optimal solutions in negligible computational time. [ABSTRACT FROM AUTHOR]

In the field of graph theory, the shortest path problem is one of the most significant problems. However, since varieties of indeterminated factors appear in complex networks, determining of the shortest path from one vertex to another in complex networks may be a lot more complicated than the cases in deterministic networks. To illustrate this problem, the model of uncertain random digraph will be proposed via chance theory, in which some arcs exist with degrees in probability measure and others exist with degrees in uncertain measure. The main focus of this paper is to investigate the main properties of the shortest path in uncertain random digraph. Methods and algorithms are designed to calculate the distribution of shortest path more efficiently. Besides, some numerical examples are presented to show the efficiency of these methods and algorithms. [ABSTRACT FROM AUTHOR]

Most of the time, people experience difficulty in identifying the best shortest paths to reach their destination while travelling. This becomes the main motive to research the shortest path identification problem. In this work, an undirected network is considered for the research evaluation of the proposed method. Previously, various types of techniques have been developed by many researchers for this shortest path issue in a networking environment. However, most of them exhibit computational complexity issues when updating their weights for every iteration. Based on this observation, the proposed work plans to solve SPP (Shortest Path Problem) in an undirected network using Fuzzy Dijkstra's approach based on improved WSM (Weighted Sum Method) with heuristic optimization. Here, the weight updating process of WSM is optimized by Sea Lion Optimization approach in order to improve the working performance of WSM while combining with Fuzzy Dijkstra method. The proposed concept is evaluated in MATLAB, and the performance evaluation is done using time consumption, energy utilization, network lifetime and prediction accuracy by comparing it with Dijkstra, Fuzzy-MPSO and WSDA methods. [ABSTRACT FROM AUTHOR]

The ubiquitous expansion and transformation of the energy supply system involves large-scale power infrastructure construction projects. In view of investments of more than a million dollars per kilometre, planning authorities aim to minimize the resistances posed by multiple stakeholders. Mathematical optimization research offers efficient algorithms to compute globally optimal routes based on geographic input data. We propose a framework that utilizes a graph model where vertices represent possible locations of transmission towers, and edges are placed according to the feasible distance between neighbouring towers. In order to cope with the specific challenges arising in linear infrastructure layout, we first introduce a variant of the Bellman-Ford algorithm that efficiently computes the minimal-angle shortest path. Secondly, an iterative procedure is proposed that yields a locally optimal path at considerably lower memory requirements and runtime. Third, we discuss and analyse methods to output $k$ diverse path alternatives. Experiments on real data show that compared to previous work, our approach reduces the resistances by more than 10% in feasible time, while at the same time offering much more flexibility and functionality. Our methods are demonstrated in a simple and intuitive graphical user interface, and an open-source package (LION), available at https://pypi.org/project/lion-sp/ [ABSTRACT FROM AUTHOR]

In addition to the word-level weight pruning, which excludes the 0-value weights from the neural network inference computation, it is recently demonstrated that the bit-level weight pruning, which excludes the 0-bits in the weight value representation regardless of whether the weight values are zero or not, is very effective to further accelerate the neural network computation without accuracy loss. This work overcomes the inherent limitation of the bit-level weight pruning, that is, the maximal computation speedup is bounded by the total number of nonzero bits of the weights and the bound is invariably considered “uncontrollable” (i.e., constant) for the neural network to be pruned. Precisely, this work, based on the signed-digit encoding 1) proposes a transformation technique which converts the two’s complement representation of every weight into a set of signed-digit representations of the minimal number of essential (i.e., nonzero) bits; 2) formulates the problem of selecting signed-digit representations of weights that maximize the parallelism of bit-level multiplication on the weights into a objective shortest path problem to achieve a maximal digit-index by digit-index (i.e., columnwise) compression for the weights and solves it efficiently using an approximation algorithm; 3) proposes a supporting novel acceleration architecture (DWP) with no additional inclusion of nontrivial hardware; and 4) proposes a variant of DWP to support bit-level parallel multiplication with the capability of predicting a tight worst-case latency of the parallel processing. Through experiments on several representative models using the ImageNet dataset, it is shown that our proposed approach is able to reduce the number of essential bits by 69% on AlexNet, 74% on VGG-16, and 68% on ResNet-152, by which our accelerator is able to reduce the inference computation time by up to $3.57\times $ over the conventional bit-level weight pruning. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of multiple graph matching (MGM) by considering both offline batch mode and online setting. We explore the concept of cycle-consistency over pairwise matchings and formulate the problem as finding optimal composition path on the supergraph, whose vertices refer to graphs and edge weights denote score function regarding consistency and affinity. By our theoretical study we show that the offline and online MGM on supergraph can be converted to finding all pairwise shortest paths and single-source shortest paths respectively. We adopt the Floyd algorithm and shortest path faster algorithm (SPFA) , to effectively find the optimal path. Extensive experimental results show our methods surpass state-of-the-art MGM methods, including CAO , MISM , IMGM , and many other recent methods in offline and online settings. Source code will be made publicly available. [ABSTRACT FROM AUTHOR]

The paper introduces the distributed framework for determining the shortest path of robots in the logistic applications, i.e. the warehouse with a swarm of robots cooperating in the Real-Time mode. The proposed solution uses the optimization routine to avoid the downtime and collisions between robots. The presented approach uses the reference model based on Dijkstra, Floyd-Warshall and Bellman-Ford algorithms, which search the path in the weighted undirected graph. Their application in the onboard robot's computer requires the analysis of the time efficiency. Results of comparative simulations for the implemented algorithms are presented. For their evaluation the data sets reflecting actual processes were used. Outcomes of experiments have shown that the tested algorithms are applicable for the logistic purposes, however their ability to operate in the Real-Time requires the detailed analysis. [ABSTRACT FROM AUTHOR]

This paper considers SUB_GOALs by using basic A* algorithm and Subgoal Graphs in a hybrid approach to execute optimal route. SUB_GOALs identified with pre-searching from basic A* at break points and Subgoal Graphs at corners of obstacles are added to SUB_TABLE to expedite the final searching in the hybrid approach. Map to work on is divided to subregions with decision-making process by using line-of-sight to avoid redundant searching. In the final searching layer, all feasible SUB_GOALs gained from decision-making process in the same subregion are connected to find final solutions of routes. Solutions achieved in the divided subregions are evaluated and combined to discover the final optimal route. The proposed hybrid approach is applied to three different scenarios in various dimensions of maps. In these three scenarios, the shortest route without hitting obstacles is calculated as 46.67, 57.76 and 124.7 units, respectively, and compared with other search algorithms. Simulation results of route planning are demonstrated to exhibit the effectiveness of the proposed hybrid approach. [ABSTRACT FROM AUTHOR]

Selection of optimal paths or sequences of cells from a grid of cells is one of the most basic functions of raster-based geographic information systems. For this function to work, it is often assumed that the optimality of a path can be evaluated by the sum of the weighted lengths of all its segments – weighted, i.e. by the underlying cell values. The validity of this assumption must be questioned, however, if those values are measured on a scale that does not permit arithmetic operations. Through computational experiments with randomly generated artificial landscapes, this paper compares two models, minisum and minimax path models, which aggregate the values of the cells associated with a path using the sum function and the maximum function, respectively. Results suggest that the minisum path model is effective if the path search can be translated into the conventional least-cost path problem, which aims to find a path with the minimum cost-weighted length between two terminuses on a ratio-scaled raster cost surface. On the other hand, the minimax path model is found mathematically sounder if the cost values are measured on an ordinal scale and practically useful if the problem is concerned not with the minimization of cost but with the maximization of some desirable condition such as suitability. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple, connected graph. One is often interested in a short path between two vertices u , v ∈ V. We propose a spectral algorithm: construct the function ϕ : V → R ≥ 0 ϕ = arg ⁡ min f : V → R f (u) = 0 , f ≢ 0 ⁡ ∑ (w 1 , w 2) ∈ E (f (w 1) − f (w 2)) 2 ∑ w ∈ V f (w) 2 . ϕ can also be understood as the smallest eigenvector of the Laplacian Matrix L = D − A after the u -th row and column have been removed. We start in the point v and construct a path from v to u : at each step, we move to the neighbor for which ϕ is the smallest. This algorithm provably terminates and results in a short path from v to u , often the shortest. The efficiency of this method is due to a discrete analogue of a phenomenon in Partial Differential Equations that is not well understood. We prove optimality for trees and discuss a number of open questions. [ABSTRACT FROM AUTHOR]

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]

One of the important issues under discussion connected with traffic on the roads is improving transportation. In this regard, spatial information, including the shortest path, is of particular importance due to the reduction of economic and environmental costs. Here, the constrained shortest path (CSP) problem which has an important application in location-based online services is considered. The aim of this problem is to find a path with the lowest cost where the traversal time of the path does not exceed from a predetermined time bound. Since precise prediction of cost and time of the paths is not possible due to traffic and weather conditions, this paper discusses the CSP problems with fuzzy cost and fuzzy time. After formulating the CSP problem an efficient algorithm for finding the constrained optimal path is designed. The application of the proposed model is presented on a location-based online service called Snap. [ABSTRACT FROM AUTHOR]

Path finding models attempt to provide efficient approaches for finding shortest paths in networks. A well-known shortest path algorithm is the Dijkstra algorithm. This paper redesigns it in order to tackle situations in which the parameters of the networks may be uncertain. To be precise, we allow that the parameters take the form of special picture fuzzy numbers. We use this concept so that it can flexibly fit the vague character of subjective decisions. The main contributions of this article are fourfold: (i) The trapezoidal picture fuzzy number along with its graphical representation and operational laws is defined. (ii) The comparison of trapezoidal picture fuzzy numbers on the basis of their expected values is proposed in terms of their score and accuracy functions. (iii) Based on these elements, we put forward an adapted form of the Dijkstra algorithm that works out a picture fuzzy shortest path problem, where the costs associated with the arcs are captured by trapezoidal picture fuzzy numbers. Also, a pseudocode for the application of our solution is provided. (iv) The proposed algorithm is numerically evaluated on a transmission network to prove its practicality and efficiency. Finally, a comparative analysis of our proposed method with the fuzzy Dijkstra algorithm is presented to support its cogency. [ABSTRACT FROM AUTHOR]

One of the major concerns in Evolutionary Algorithms is the premature convergence caused by what is known as the Exploration and Exploitation Balance problem. To maintain this balance, population diversity should be maintained during the initialization/optimization process. Maintaining diversity can be done through different strategies, but they commonly answer one question: when to introduce more diversity to the population? To answer this question there should be diversity metrics upon which a decision can be made to add diversity; consequently, add/reduce exploration/exploitation. There are as many diversity metrics as many problems and representations. That is, diversity metrics are very problem-specific. This work provides diversity metrics for the variable-length chromosome Genetic Algorithm for Shortest Path. The suggested metrics consider the varying lengths of the chromosomes, problem representation, and the search space. To measure chromosome-length diversity, a novel chromosome-length-based metric has been proposed. By exploiting the fact that the possible genes that can form any chromosome are well known in this specific direct-encoded population, a new simple metric that measures the representation of genes in the initial population is proposed and experimentally investigated. The presented metrics put through an extensive simulation and comparatively studied. Relationship between the proposed metrics has been quantified using Principal Component Analysis under varying network/population sizes. [ABSTRACT FROM AUTHOR]

Smart surface is a new conveying technology composed of a 2D planar surface presenting a matrix of distributed autonomous blocks. Every block contains a micro-electro-mechanical system (MEMS) actuator that controls the transfer of a possible object located above the block to the neighboring blocks, using air-jet forces. The spatial characteristics of the blocks impose some limits on the memory, energy and computation capabilities of the MEMS blocks. On the other hand, the system can reach several thousands of blocks making necessary to propose scalable algorithmic solutions. This paper studies different distributed algorithms to convey an object from an initial to a target position in the smart surface. The conveying policy emphasizes the long term use of the smart surface and the objects conveying efficiency measured by the time of the transfer. The problem stands as an original case of multi-objective Shortest Path problem (MOSP). Original because the quality of a given path is not evaluated by the sum of the weights of its segments, and because the segment weights change according to the used paths as provided by the algorithm itself. Therefore, the efficiency of a given algorithm is assessed on the basis of its performance during a long period of time. We describe here the best way to combine these two objectives and we propose a scalable incremental distributed protocol for objects conveying. The path optimality is adjusted according to the required calculation complexity. The performances of the different algorithmic and modeling variations are analyzed in terms of memory, time, computation and exchanged messages complexity. The obtained results prove the scalability of the algorithm, with linear computational, memory and convergence time complexity, and confirm the improvement of smart surface usage compared to a naive approach. The system lifespan increases of up to 130% on 40 × 40 smart surface, while the transfer cost (time and energy) is reduced. We show also that the computation time of the path with the incremental algorithm can be significantly reduced without significant degradation of the conveying system performance. For example, in a 40 × 40 smart surface, the number of messages is divided by 4 while the number of conveyed objects is only reduced by a ratio of 4%. • The smartsurface is new distributed conveying plateform • The smarsurface allows the manipulation and the transportation of fragile and tiny objects. • The distributed architecture ensures the modularity and maintainability of the system. • The smartsurface conveying problem is an original problem. • The conveying algorithm manages the tradeoff between the transfer time and the surface lifespan. • The computational complexity of the algorithm is less than O (m) • The algorithm convergence is reached with a time complexity of O (m). [ABSTRACT FROM AUTHOR]

In this paper, we consider general scalar robust optimization problems and study the characterizations for optimality conditions in the general vector spaces where we do not require any topology on the considered space. By using the image space analysis and nonlinear separation function, we derive some necessary and sufficient optimality conditions, especially saddle point sufficient optimality conditions for scalar robust optimization problems. Moreover, we discuss the validity and effectiveness of our results for the shortest path problem. [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]

We study two variants of the shortest path problem. Given an integer k , the k -color-constrained and the k -interchange-constrained shortest path problems, respectively, seek a shortest path that uses no more than k colors and one that makes no more than k − 1 alternations of colors. We show that the former problem is NP-hard, when the latter is tractable. The study of these problems is motivated by some limitations in the use of diameter-based metrics to evaluate the topological structure of transit networks. We notably show that indicators such as the diameter or directness of a transit network fail to adequately account for travel convenience in measuring the connectivity of a network and propose a new network indicator, based on solving the k -interchange-constrained shortest path problem, that aims at alleviating these limitations. [ABSTRACT FROM AUTHOR]

The shortest path problem is the problem of finding a path with minimum total weight from a source node to each destination node in a network. The existing solution to this fundamental problem searches the shortest paths to all network nodes until it meets the given multiple-destination nodes. By granting preference to routes to each destination node, the proposed algorithm meets the destination nodes faster. The results of the experimental analysis on a real-world dataset and simulated random networks show the superiority of the proposed algorithm to the existing solution. This remarkable improvement makes the proposed algorithm applicable in all related applications. [ABSTRACT FROM AUTHOR]

The shortest path is an important problem in network optimization theory. This paper considers the shortest path problem under the situation where weights of edges in a network include both uncertainty and randomness and focuses on the case that the weights of edges are expressed by uncertain random variables. Some optimization models based on chance theory are proposed in order to find the shortest path which fully reflects uncertain and random information. This paper proposes also an intelligent algorithm to calculate the shortest path for an uncertain random network. A numerical example is given to illustrate its effectiveness. [ABSTRACT FROM AUTHOR]

In this paper, the traditional shortest path planning problem for vehicle is advanced to length-targeted path planning problem, i.e., to plan path with its length being as close to a specified value as possible. Lengthening and shortening of given initial paths are used to solve this problem. Based on an operation set consisting of three basic path homotopies, we build a comprehensive and systematic framework to plan paths with target length, which is a generalization of the existing related studies. Thereby, the expected paths can be independently searched through such deformation processes within topological classes. The proposed framework can produce the largest length coverage in different scenarios and under different conditions, and it can also generate expected paths with arbitrary topological classification in terms of the curvature constraint and the obstacle constraint. Examples show that our lengthening and shortening method can effectively solve the length-targeted path planning problem in environment without or with obstacles. Note to Practitioners—This paper presents a curvature-bounded lengthening and shortening approach for path planning of vehicles. The curvature and obstacle constraints in the path planning problem are handled using the topological technique. In addition, a rigorous classification system is presented to systematically categorize the potential paths. Within a path class, any path can be deformed to other paths while keeping the curvature bounded. Then, the path deformation process is conducted via a series of basic homotopy operations to approach the target length. The length coverage range of this process is reduced when some endpoint conditions are meet or the vehicle is trapped into a closed region. [ABSTRACT FROM AUTHOR]

This paper considers a shortest path problem in an imprecise and random environment. The edges in the network represent the approximate time required to cover the distance from one vertex to another vertex while the traffic conditions change randomly for each edge. The approximate time has been defined by using trapezoidal fuzzy number whereas the traffic conditions has been defined in linguistic term. Such type of network problem can be called as Fuzzy Stochastic Shortest Path Problem (FSSPP) in imprecise and random environment. In order to solve the model, a method has been proposed based on the Dijkstra’s algorithm and some numerous example have been solved to present its effectiveness. [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]

Plenty of problems are related to the calculation of edges and nodes in the realistic networks. It also influences the realization of shortest path problem (SPP) because of its essential fuzziness. This paper presents a fuzzy-based modified particle swarm optimization (fuzzy-based MPSO) algorithm for resolving the shortest path issue. The proposed work also evaluates the uncertainties of this shortest path problem through the utilization of offered algorithm. Actually, the normal PSO algorithm is altered and estimated to tackle the fuzzy-based SPP (FSPP) with uncertain edges. The performance of the planned algorithm will be improved; also the results are compared with the existing methodologies. The early convergence of the PSO technique can be alleviated and travelled via the dynamic operation of fuzzy method. And the proposed method is compared with other metaheuristic algorithms such as evolutionary random weight networks (GA-RWNs), grasshopper optimization algorithm with evolutionary population dynamics (GOA-EPD), levy weight grey wolf optimization (LGWO) and PSO in terms of cost and time consumption. The related results and discussion is performed in the working platform of MATLAB tool for the demonstration of the proposed work to manage the FSPP in indeterminate networks. [ABSTRACT FROM AUTHOR]

The traditional shortest path problem is mainly concerned with identifying the associated paths in the transportation network that represent the shortest distance between the source and the destination in the transportation network by finding either cost or distance. As for the problem of research under study it is to find the shortest optimal path of multi-objective (cost, distance and time) at the same time has been clarified through the application of a proposed practical model of the problem of multi-objective shortest path to solve the problem of the most important 25 commercial US cities by travel in the car or plane. The proposed model was also solved using the lexicographic method through package program Win-QSB 2.0 for operational research applications. [ABSTRACT FROM AUTHOR]

We study a bi-criteria path problem on a directed multigraph with cycles, where each arc is associated with two parameters. The first is the survival probability of moving along the arc, and the second is the length of the arc. We evaluate the quality of a path by two independent criteria. The first is to maximize the survival probability along the entire path, which is the product of the arc probabilities, and the second is to minimize the total path length, which is the sum of the arc lengths. We prove that the problem of finding a path which satisfies two bounds, one for each criterion, is NP-complete, even in the acyclic case. We further develop approximation algorithms for the optimization versions of the studied problem. One algorithm is based on approximate computing of logarithms of arc probabilities, and the other two are fully polynomial time approximation schemes (FPTASes). One FPTAS is based on scaling and rounding of the input, while the other FPTAS is derived via the method of K-approximation sets and functions, introduced by Halman et al. (Math Oper Res 34:674–685, 2009). [ABSTRACT FROM AUTHOR]

Consider a situation in which individuals –the buyers –have different valuations for the products of a given set. An envy-free assignment of product items to buyers requires that the items obtained by every buyer be purchased at a price not larger than his/her valuation, and each buyer's welfare (difference between product value and price) be the largest possible. Under this condition, the problem of finding prices maximizing the seller's revenue is known to be APX -hard even for unit-demand bidders (with several other inapproximability results for different variants), that is, when each buyer wishes to buy at most one item. Here, we focus on Envy-free Complete Allocation , the special case where a fixed number of copies of each product is available, each of the n buyers must get exactly one product item, and all the products must be sold. This case is known to be solvable in O (n 4) time. We revisit a series of results on this problem and, answering a question found in Leonard (1983), show how to solve it in O (n 3) time by connections to perfect matchings and shortest paths. [ABSTRACT FROM AUTHOR]

Humans generally solve multi-destination routes with simple rules-of-thumb. Animals may do the same, but strong evidence is limited to a few species. We examined whether strepsirrhines, who diverged from haplorhines more than 58 mya, would demonstrate the use of three heuristics used by humans and supported in vervets, the nearest neighbor rule, the convex hull, and a cluster strategy, when solving a multi-destination route. We hypothesized that the evolution of these strategies may depend on a species' dietary specialization. Three nocturnal lemur species were tested on an experimental array at the Duke Lemur Center. Frugivorous fat-tailed dwarf lemurs (Cheirogaleus medius) were expected to follow paths most consistent with distance-saving navigational heuristics because fruit trees are stationary targets. Gray mouse lemurs (Microcebus murinus) and aye-ayes (Daubentonia madagascariensis), which rely on more mobile and ephemeral foods, were expected to use fewer paths consistent with these heuristics and be more exploratory. Our data supported all of these hypotheses. Dwarf lemurs used paths consistent with all three heuristics, took the shortest paths, and were the least exploratory. Mouse lemurs were quite exploratory but sometimes used paths consistent with heuristics. Aye-ayes showed no evidence of heuristic use and were the most exploratory. Distinguishable patterns of inter- and intra-individual variation in ability to solve the route, speed, and behavior occurred in each species. This research suggests that these simple navigational heuristics are not part of a readily available set of cognitive tools inherited by all primates but instead evolve due to need in each lineage. [ABSTRACT FROM AUTHOR]

In several multiobjective decision problems Pairwise Comparison Matrices (PCM) are applied to evaluate the decision variants. The problem that arises very often is the inconsistency of a given PCM. In such a situation it is important to approximate the PCM with a consistent one. One of the approaches is to minimize the distance between the matrices, most often the Euclidean distance. In the paper we consider the problem of minimizing the maximum distance. After applying the logarithmic transformation we are able to formulate the obtained subproblem as a Shortest Path Problem and solve it more efficiently. We analyze the structure of the set of optimal solutions and prove some of its properties. This allows us to provide an iterative algorithm that results in a unique, Pareto-efficient solution. [ABSTRACT FROM AUTHOR]

Neutrosophic (NS) set hypothesis gives another way to deal with the vulnerabilities of the shortest path problems (SPP). Several researchers have worked on fuzzy shortest path problem (FSPP) in a fuzzy graph with vulnerability data and completely different applications in real world eventualities. However, the uncertainty related to the inconsistent information and indeterminate information isn't properly expressed by fuzzy set. The neutrosophic set deals these forms of uncertainty. This paper presents a model for shortest path problem with various arrangements of integer-valued trapezoidal neutrosophic (INVTpNS) and integer-valued triangular neutrosophic (INVTrNS). We characterized this issue as Neutrosophic Shortest way problem (NSSPP). The established linear programming (LP) model solves the classical SPP that consists of crisp parameters. To the simplest of our data, there's no multi objective applied mathematics approach in literature for finding the Neutrosophic shortest path problem (NSSPP). During this paper, we tend to introduce a multi objective applied mathematics approach to unravel the NSPP. The subsequent integer valued neutrosophic shortest path (IVNSSP) issue is changed over into a multi objective linear programming (MOLP) issue. At that point, a lexicographic methodology is utilized to acquire the productive arrangement of the subsequent MOLP issue. The optimization process affirms that the optimum integer valued neutrosophic shortest path weight conserves the arrangement of an integer valued neutrosophic number. Finally, some numerical investigations are given to demonstrate the adequacy and strength of the new model. [ABSTRACT FROM AUTHOR]

Neutrosophic set theory provides a new tool to handle the uncertainties in shortest path problem (SPP). This paper introduces the SPP from a source node to a destination node on a neutrosophic graph in which a positive neutrosophic number is assigned to each edge as its edge cost. We define this problem as neutrosophic shortest path problem (NSSPP). A simple algorithm is also introduced to solve the NSSPP. The proposed algorithm finds the neutrosophic shortest path (NSSP) and its corresponding neutrosophic shortest path length (NSSPL) between source node and destination node. Our proposed algorithm is also capable to find crisp shortest path length (CrSPL) of the corresponding neutrosophic shortest path length (NSSPL) which helps the decision maker to choose the shortest path easily. We also compare our proposed algorithm with some existing methods to show efficiency of our proposed algorithm. Finally, some numerical experiments are given to show the effectiveness and robustness of the new model. Numerical and graphical results demonstrate that the novel methods are superior to the existing method. [ABSTRACT FROM AUTHOR]

Shortest path problems play important roles in computer science, communication networks, and transportation networks. In a shortest path improvement problem under unit Hamming distance, an edge-weighted graph with a set of source-terminal pairs is given. The objective is to modify the weights of the edges at a minimum cost under unit Hamming distance such that the modified distances of the shortest paths between some given sources and terminals are upper bounded by the given values. As the shortest path improvement problem is NP-hard, it is meaningful to analyze the complexity of the shortest path improvement problem defined on rooted trees with one common source. We first present a preprocessing algorithm to normalize the problem. We then present the proofs of some properties of the optimal solutions to the problem. A dynamic programming algorithm is proposed for the problem, and its time complexity is analyzed. A comparison of the computational experiments of the dynamic programming algorithm and MATLAB functions shows that the algorithm is efficient although its worst-case complexity is exponential time. [ABSTRACT FROM AUTHOR]

The constantly increasing number of vehicles and the immense size and complexity of road maps set a tough scenario for real world routing. In spite of the tremendous efforts done up to date to tackle this problem, finding the shortest-path in practice is still a challenge due to memory and time constrains. Moreover, most of the efforts have been focused on algorithmics, setting aside the management of the data. However, memory and time constraints are very important to actually construct real world applications, advising a new global approach. In this study we propose a holistic strategy for finding the shortest-path based on efficiently managing the road map data. Our proposal is based on the tile map partitioning, a logic geographical partition strategy. We have developed a routing system highly scalable based on a micro steady state evolutionary algorithm to find the optimal tile map partitioning. We show the actual efficiency and scalability by using the road maps of Malaga, Spain, and Mexico City, making it clear the significant reductions in the time needed to compute the shortest-path (in a real application), what is a key issue that can be freely exploited in future open software for maps. [ABSTRACT FROM AUTHOR]

Finding the shortest path in road networks becomes one of important issues in location based services (LBS). The problem of finding the optimal meeting point for a group of users has also been well studied in existing works. In this paper, we investigate a new problem for two users. Each user has his/her own source and destination. However, whether to meet before going to their destinations is with some uncertainty. We model it as minimum path pair ( MPP) query, which consists of two pairs of source and destination and a user-specified weight $\alpha$ to balance the two different needs. The result is a pair of paths connecting the two sources and destinations respectively, with minimal overall cost of the two paths and the shortest route between them. To solve MPP queries, we devise algorithms by enumerating node pairs. We adopt a location-based pruning strategy to reduce the number of node pairs for enumeration. An efficient algorithm based on point-to-point shortest path calculation is proposed to further improve query efficiency. We also give two fast approximate algorithms with approximation bounds. Extensive experiments are conducted to show the effectiveness and efficiency of our methods. [ABSTRACT FROM AUTHOR]

The choroid is vascular tissue located underneath the retina and supplies oxygen to the outer retina; any damage to this tissue can be a precursor to retinal diseases. This paper presents an automated method of choroidal segmentation from Enhanced Depth Imaging Optical Coherence Tomography (EDI-OCT) images. The Dijkstra shortest path algorithm is used to segment the choroid–sclera interface (CSI), the outermost border of the choroid. A novel intensity-normalisation technique that is based on the depth of the choroid is used to equalise the intensity of all non-vessel pixels in the choroid region. The outer boundary of choroidal vessel and CSI are determined approximately and incorporated to the edge weight of the CSI segmentation to choose optimal edge weights. This method is tested on 190 B-scans of 10 subjects against choroid thickness (CTh) results produced manually by two graders. For comparison, results obtained by two state-of-the-art automated methods and our proposed method are compared against the manual grading, and our proposed method performed the best. The mean root-mean-square error (RMSE) for finding the CSI boundary by our method is 7.71 ± 6.29 pixels, which is significantly lower than the RMSE for the two other state-of-the-art methods ( 36.17 ± 11.97 pixels and 44.19 ± 19.51 pixels). The correlation coefficient for our method is 0.76 , and 0.51 and 0.66 for the other two state-of-the-art methods. The interclass correlation coefficients are 0.72, 0.43 and 0.56 respectively. Our method is highly accurate, robust, reliable and consistent. This identification can enable to quantify the biomarkers of the choroidin large scale study for assessing, monitoring disease progression as well as early detection of retinal diseases. Identification of the boundary can help to determine the loss or change of choroid, which can be used as features for the automatic determination of the stages of retinal diseases. [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]