Search

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]

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]

Abstract Shortest Distance Path problem has been studied extensively in the literature. This is an important problem with a wide range of applications in the world particularly, transportation, trip planning, etc. Various mathematical models have been proposed in the literature to solve the basic problem and its variations. In this study, we incorporate weather forecast into trip planning. Due to adverse weather conditions, shortest distance path to follow may vary. Furthermore, travel times also become less predictable. Various weather forecast scenarios are generated following a given distribution. Furthermore, stochastic travel times are also considered as part of the analysis. In this study, GA will produce multiple acceptable solutions where fitness function values for each acceptable solution can vary. The average value of arriving time will be considered as the fitness function for a chromosome after simulating the chromosome under different conditions randomly 100 times. [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]

Abstract We study a pathfinding problem of directed trees under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be searched by a procedure whose computational cost becomes very large as the length increases. We present a method that gives a shortest path. Under some assumptions, the proposed method is optimal in the number of procedure calls for the longest edge length. This graph problem is motivated by procedure synthesis for system configuration in cloud systems. [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]

We introduce Shortest Connection Game , a two-player game played on a directed graph with edge costs. Given two designated vertices in which the players start, the players take turns in choosing edges emanating from the vertex they are currently located at. This way, each of the players forms a path that origins from its respective starting vertex. The game ends as soon as the two paths meet, i.e., a connection between the players is established. Each player has to carry the cost of its chosen edges and thus aims at minimizing its own total cost. In this work we analyse the computational complexity of Shortest Connection Game . On the negative side, Shortest Connection Game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths. [ABSTRACT FROM AUTHOR]

The sewer network optimal hydraulic design, for a specific layout consisting of a series of pipes, is the combination of diameters and slopes along the series that satisfy all the hydraulic, commercial, and construction constraints, while minimizing the construction costs. This work explains an exact, exhaustive, and flexible framework to find the cost-optimal design of a series of sewer pipes using a DP-based optimization engine [1] . The hydraulic design problem is modeled as a Shortest Path Problem [2] , where the underlying graph considers every feasible combination of diameter and slope for each pipe in the series. As a result, a shortest path on the graph encodes the optimal hydraulic design decision for the series of pipes. The proposed methodology ensures the global optimal solution from an economic point of view because the graph considers all possible alternatives and the Bellman-Ford [3] algorithm implicitly explores all of them. Without having to simplify hydraulic constraints, this methodology still obtains the optimal solution in a very short computational time using a standard desktop computer. To evaluate the performance of the methodology, several numerical examples are presented varying the pipe material, the topography, and the number of pipes in the series. [ABSTRACT FROM AUTHOR]

In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography . On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]

The shortest path (SP) problem is a network optimization problem with a wide range of applications in business and engineering. Conventional network problems assume precise values for the weights of the edges. However, these weights are often vague and ambiguous in practical applications. Several heuristics have been proposed to find the shortest path (SP) weight and the corresponding SP on a network with fuzzy arc weights. These heuristics largely use α -cuts and the least squares method. We propose an artificial bee colony (ABC) algorithm to solve the fuzzy SP (FSP) problems with fuzzy arc weights. The performance of the proposed ABC algorithm is compared with the performance of other competing algorithms with two SP problems taken from the literature. We present a wireless sensor network (WSN) problem and demonstrate the applicability of the proposed method and exhibit the efficiency of the procedures and algorithms. [ABSTRACT FROM AUTHOR]

• An auxiliary algorithm is proposed to construct initial stage of the MCDM methods. • A multi-objective fuzzy optimization model is formulated. • An extensive comparative analysis is conducted in terms of the addressed methods. • The stability and validity of the results are tested and discussed. • Key findings and managerial insights are provided. This paper examines the performances of the multi-criteria decision-making (MCDM) methods and optimization model in solving multi-attribute shortest path problems such as the safest shortest path under a fuzzy environment. To the best of the knowledge of the authors, this is the first study performing comparative analysis on finding the multi-attribute shortest path by employing well-known techniques in terms of computational effort and results in a fuzzy environment. To this end, the safest shortest path problem, where the risk and distance values concerning arcs on a directed network are defined as triangular fuzzy numbers, is handled. The solution process is carried out under two main headings: (i) To start the solution with MCDM methods, an auxiliary algorithm that constructs a fuzzy decision matrix is proposed. Then, Fuzzy-Technique for Order Preference by Similarity to Ideal Solution (F-TOPSIS), Fuzzy Simple Additive Weighting (F-SAW), and Fuzzy Evaluation Based on Distance from Average Solution (F-EDAS), that are fuzzy-based MCDM methods, are employed to rank the alternative paths. (ii) A multi-objective fuzzy optimization model is formulated, and the most reasonable paths are obtained considering different α-cut levels. Following that, comparative analysis is performed through a set of scenarios considering the different weights of the criteria to see the variability in the rankings. Besides, the addressed fuzzy-based MCDM methods are compared in terms of computational complexity. Overall, the main findings and managerial insights regarding the effectiveness and performance of the methods discussed in the solution process are provided. [ABSTRACT FROM AUTHOR]

This paper develops for the first time an analytical approach inspired from the basic differential multiplier method (BDMM) in a framework concept involving coupled nonlinear ordinary differential equations (ODEs) for finding shortest path (SP) in dynamically reconfigurable graphs. The application of BDMM to the shortest-path problem (SPP) results into a set of coupled ODEs which do essentially describe/constitute a Recurrent Neural Network (RNN) model. This model is characterized by three fundamental parameters describing (or expressing) the following: (a) the graph topology (through the ‘incidence matrix’), (b) the edge weights (dynamic external weights setting capability), and (c) the dynamic re-configurability through external input(s) of the source–destination nodes pair. The coupled ODEs constitute a universal modeling framework for SP detection. The three fundamental parameters of this framework are valid for all types of graphs (directed, undirected, connected, non-connected, complete- and non-complete) regardless of their topology, magnitude, size, etc. An overall thorough methodology and an illustrative extensive evaluation are provided. It is noticed and demonstrated that the main advantage of the concept suggested is that arc costs, the origin–destination ( s–t ) pair setting, and the graph topology are external commands representing the inputs (and also the coefficients/parameters) of the ODE-processor model (RNN). This enables a high flexibility and a full re-configurability of the developed shortest path problem solver concept and thereby without any re-training need. Further, this RNN based SP solver concept can handle even graphs with negative arc weights as well as graphs with nonlinear path cost models. To stress test this new RNN shortest path problem solver concept, a benchmarking is performed, whereby a detailed comparison of its performance with one of the currently best amongst the related traditional neural network based concepts (i.e. the Dynamic Neural Network (DNN) based SP solver) is performed. The superiority of the novel RNN SPP solver is convincingly demonstrated in an extensive benchmark while considering computational efficiency, robustness, convergence, flexibility, and re-configurability as performance metrics. Finally, it is demonstrated that the concept developed is applicable to solving shortest path tree (SPT) problems. A case study (SPT) is considered and various results obtained using the concept developed are compared with the results provided by several algorithms namely the semi-dynamic Dijkstra algorithms, the semi-dynamic MBallString algorithms, and the fully-dynamic MFP algorithm. The efficiency of the concept developed for solving SPT problems in both static and dynamically reconfigurable graphs networks is clearly demonstrated through multiple application examples. [ABSTRACT FROM AUTHOR]

Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair. [ABSTRACT FROM AUTHOR]

The Knödel graph W Δ , n is a graph of even order n and degree Δ where 2 ≤ Δ ≤ ⌊ log 2 ⁡ n ⌋ . Most properties of the Knödel graph are known only for W Δ , 2 Δ and W Δ − 1 , 2 Δ − 2 . In this paper we study the shortest path problem in W Δ , n for all Δ and n . We give a tight bound on the distance between any two vertices in W Δ , n . We show that for almost all Δ , the presented bound differs from actual distance by at most 2. The proofs are constructive and allow us to present an O ( log ⁡ n ) time algorithm to construct a short path between any pair of vertices in W Δ , n . The diameter of W Δ , n is known only for n = 2 Δ . Using our results on the shortest path problem, we present tight upper and lower bounds on the diameter of the Knödel graph for all Δ and n . [ABSTRACT FROM AUTHOR]

An improved ant colony optimization (ACO) algorithm called pheromone mark ACO abbreviated PM-ACO is proposed for the non-ergodic optimal problems. PM-ACO associates the pheromone to nodes, and has a pheromone trace of scatter points which are referred to as pheromone marks. PM-ACO has a node-based pheromone update strategy, which includes two other rules except a best-so-far tour rule. One is called r -best-node update rule which updates the pheromones of the best-ranked nodes, which are selected by counting the nodes’ passed ants in each iteration. The other one is called relevant-node depositing rule which updates the pheromones of the k -nearest-neighbor (KNN) nodes of a best-ranked node. Experimental results show that PM-ACO has a pheromone integration effect of some neighbor arcs on their central node, and it can result in instability. The improved PM-ACO has a good performance when applied in the shortest path problem. [ABSTRACT FROM AUTHOR]

Recently the Hopfield Neural Network (HNN) is employed as an optimization tool to solve shortest path problem in communication networks. The hardware implementation of digital Hopfield neural network is an important issue that is considered in this paper. An efficient systolic architecture is proposed for efficient implementing of digital Hopfield neural networks for solving shortest path problem on Field-Programmable-Gate-Array (FPGA) chips. The VHDL hardware description language is employed for hardware modeling of proposed systolic architecture. The results achieved from simulation and hardware synthesizing demonstrates that the proposed systolic architecture has superior performance than relevant architectures in literature for chip area utilization, convergence and maximum operating frequency. [ABSTRACT FROM AUTHOR]

Infrastructure for fuel-cell and other alternative-fuel vehicles is lacking not only in the paucity of fuel stations, but also in inadequate web-based support to help drivers complete their trips via the few stations that do exist. In this paper, we present an online mapping tool for finding the shortest feasible path in a road network given the vehicle's driving range and station locations. Users input their origin, destination, type of fuel, and driving range, and the algorithm generates a new reduced feasible network in which the vertices are the origin and destination nodes and reachable fuel stations and the edges represent feasible paths between them. Dijkstra's shortest path algorithm is applied to this reduced network to find the shortest feasible path. Efficiency is substantially improved by preprocessing and storing the shortest-path distances between stations. We present a web-mapping prototype ( www.afvrouting.com ) for hydrogen and compressed natural gas stations in the United States. Sample results illustrate the need for this kind of globally optimal solution method by showing that the optimal feasible path and refueling stops can vary tremendously as a result of user inputs for driving range, initial tank level, and one-way or round-trip. [ABSTRACT FROM AUTHOR]

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time. [ABSTRACT FROM AUTHOR]

Abstract: A supply chain network design needs to consider the future probability of reconfiguration due to some problems of disaster or price changes. The objective of this article is to design a reconfigurable supply chain network by optimizing inventory allocation and transportation routing. A two-stage programming is composed according to Benders decomposition by allocating inventory in advance and anticipating the changes of transportation routings; thus the transportation routing is stochastic in nature. In addition, the fuzzy shortest path is developed to solve the problem complexity in terms of the multi-criteria of lead time and capacity with an efficient computational method. The results and analysis indicate that the proposed two-stage programming with fuzzy shortest path surpasses the performance of shortest path problem with time windows and capacity constraint (SPPTWCC) in terms of less computational time and CPU memory consumption. Finally, management decision-making is discussed among other concluding remarks. [Copyright &y& Elsevier]

Highlights: [•] We attribute the road network with time-dependent energy consumption data. [•] The data are based on vehicle speeds derived from floating car data. [•] We verify that the time-dependent optimal path problem is computationally feasible. [•] Time- and energy-optimal paths differ in more than 89 [•] Energy-optimal paths have approx. 12 [ABSTRACT FROM AUTHOR]

Abstract: The 0-1 knapsack problem is an open issue in discrete optimization problems, which plays an important role in real applications. In this paper, a new bio-inspired model is proposed to solve this problem. The proposed method has three main steps. First, the 0-1 knapsack problem is converted into a directed graph by the network converting algorithm. Then, for the purpose of using the amoeboid organism model, the longest path problem is transformed into the shortest path problem. Finally, the shortest path problem can be well handled by the amoeboid organism algorithm. Numerical examples are given to illustrate the efficiency of the proposed model. [Copyright &y& Elsevier]

Abstract: The shortest path problem is the classical combinatorial optimization problem arising in numerous planning and designing contexts. This paper presents a neural network model for solving the shortest path problems. The main idea is to replace the shortest path problem with a linear programming (LP) problem. According to the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the shortest path problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper. [Copyright &y& Elsevier]

Abstract: metric spaces constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a metric space are connected by a unique shortest path . In this paper, we present an efficient algorithm for answering two-point distance queries in rectangular complexes and two of theirs subclasses, ramified rectilinear polygons ( rectangular complexes in which the links of all vertices are bipartite graphs) and squaregraphs ( rectangular complexes arising from plane quadrangulations in which all inner vertices have degrees ⩾4). Namely, we show that for a rectangular complex with n vertices, one can construct a data structure of size so that, given any two points , the shortest path between x and y can be computed in time, where p and q are vertices of two faces of containing the points x and y, respectively, such that and is the distance between p and q in the underlying graph of . If is a ramified rectilinear polygon, then one can construct a data structure of optimal size and answer two-point shortest path queries in time, where Δ is the maximal degree of a vertex of . Finally, if is a squaregraph, then one can construct a data structure of size and answer two-point shortest path queries in time. [Copyright &y& Elsevier]

Abstract: A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined. [Copyright &y& Elsevier]

Abstract: A common algorithm to solve the shortest path problem (SPP) is the Dijkstra algorithm. In this paper, a generalized Dijkstra algorithm is proposed to handle SPP in an uncertain environment. Two key issues need to be addressed in SPP with fuzzy parameters. One is how to determine the addition of two edges. The other is how to compare the distance between two different paths with their edge lengths represented by fuzzy numbers. To solve these problems, the graded mean integration representation of fuzzy numbers is adopted to improve the classical Dijkstra algorithm. A numerical example of a transportation network is used to illustrate the efficiency of the proposed method. [Copyright &y& Elsevier]

Abstract: This paper investigates an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP). By encoding a path as an OST, in contrast with the existing evolutionary algorithms (EA) for shortest path problem (SPP), the designed GA provides a “search from a paths set to another paths set” mutation mechanism such that both of its local search and global search capabilities are greatly improved. Because the possibility to find a feasible path in a paths set is usually larger than that of only one path is feasible, the designed GA has more predominance for solving MCSPPs. Some computational tests are presented and the test results are compared with those obtained by a recent EA of which the encoding approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for shortest path problems. The test results indicate that the new algorithm is available for both of MSPP and MCSPP. [Copyright &y& Elsevier]

Abstract: Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the -shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the -shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the -shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm. [Copyright &y& Elsevier]

Abstract: Multi-objective shortest path problem (MOSP) is an extension of a traditional single objective shortest path problem that seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. MOSP is one of the most important problems in network optimization with wide applications in telecommunication industries, transportation and project management. This research presents an algorithm based on multi-objective ant colony optimization (ACO) to solve the bi-objective shortest path problem. To analyze the efficiency of the algorithm and check for the quality of solutions, experimental analyses are conducted. Two sets of small and large sized problems that generated randomly are solved. Results on the set problems are compared with those of label correcting solutions that is the most known efficient algorithm for solving MOSP. To compare the Pareto optimal frontiers produced by the suggested ACO algorithm and the label correcting algorithm, some performance measures are employed that consider and compare the distance, uniformity distribution and extension of the Pareto frontiers. The results on the set of instance problems show that the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose an efficient method for implementing Dijkstra''s algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in time if , and time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. [Copyright &y& Elsevier]

• Definition of the Shared Resource-Constrained Multi-Shortest Path Problem, SRMSPP. • A parallelizable matheuristic to solve the SRMSPP. • Instances with thousands of networks and millions of arcs are solved. • The SRMSPP can be applied to some Scheduling Problems. We tackle the problem of finding, for each network within a collection, the shortest path between two given nodes, while not exceeding the limits of a set of shared resources. We present an integer programming (IP) formulation of this problem and propose a parallelizable matheuristic consisting of three phases: (1) generation of feasible solutions, (2) combination of solutions, and (3) solution improvement. We show that the shortest paths found with our procedure correspond to the solution of some type of scheduling problems such as the Air Traffic Flow Management (ATFM) problem. Our computational results include finding optimal solutions to small and medium-size ATFM instances by applying Gurobi to the IP formulation. We use those solutions to assess the quality of the output produced by our proposed matheuristic. For the largest instances, which correspond to actual flight plans in ATFM, exact methods fail and we assess the quality of our solutions by means of Lagrangian bounds. Computational results suggest that the proposed procedure is an effective approach to the family of shortest path problems that we discuss here. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem. [Copyright &y& Elsevier]

Abstract: We consider a stochastic shortest path problem with associative criteria in which for each node of a graph we choose a probability distribution over the set of successor nodes so as to reach a given target node optimally. We formulate such a problem as an associative Markov decision processes. We show that an optimal value function is a unique solution to an optimality equation and find an optimal stationary policy. Also we give a value iteration method and a policy improvement method. [Copyright &y& Elsevier]

Abstract: In this paper, a new nonlinear neural network for solving the shortest path problem is presented. The our nonlinear neural networks are able to generate optimal solutions to the shortest path problem. The performance of the our neural networks are demonstrated by means of illustrative example. The our neural networks are shown to be capable of generating the shortest path and suitable for electronic implementation. [Copyright &y& Elsevier]

Abstract: We discuss the shortest path problem from a specified node to every other nodes on a network in which a positive fuzzy quantity with finite support is assigned to each arc as its arc length. We define an order relation between fuzzy quantities with finite supports. Then by applying Hansen’s multiple labeling method and Dijkstra’s shortest path algorithm, we propose a new algorithm for finding the set of non-dominated paths with respect to the extension principle. Moreover, we show that the only existing approach for this problem, Klein’s algorithm, may lead to a dominated path in the sense of extension principle. [Copyright &y& Elsevier]

Abstract: In this paper, we study the shortest path problem with stochastic arc length. According to different decision criteria, we originally propose the concepts of expected shortest path, α-shortest path and the most shortest path, and present three new types of models: expected value model, chance-constrained programming and dependent-chance programming. In order to solve these models, a hybrid intelligent algorithm integrating stochastic simulation and genetic algorithm is developed and some numerical examples are given to illustrate its effectiveness. [Copyright &y& Elsevier]

Abstract: Shortest path finding has a variety of applications in transportation and communication.In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The previous works on this topic had two assumptions that can be relaxed in this paper. First, in the previous works, the systems were assumed to be integral-weighted, whereas in this paper, the systems are real-weighted. Second, and more importantly, the previous works have shown that the algorithm is self-stabilizing under the more restricted central demon model, whereas in this paper, we give a rigorous proof showing that the algorithm is actually self-stabilizing under the more general distributed demon model. The work in this paper is of significance because in the existing literature on self-stabilizing systems, most of the papers regarding the distributed demon are for the ring networks only; there are very few papers that discuss the self-stabilizing algorithms for the general distributed systems assuming the distributed demon model. [Copyright &y& Elsevier]

This paper deals with a shortest path problem on a network in which a fuzzy number, instead of a real number, is assigned to each arc length. Such a problem is “ill-posed” because each arc cannot be identified as being either on the shortest path or not. Therefore, based on the possibility theory, we introduce the concept of “degree of possibility” that an arc is on the shortest path. Every pair of distinct paths from the source node to any other node is implicitly assumed to be noninteractive in the conventional approaches. This assumption is unrealistic and involve inconsistencies. To overcome this drawback, we define a new comparison index between the sum of fuzzy numbers by considering interactivity among fuzzy numbers. An algorithm is presented to determine the degree of possibility for each arc on a network. Finally, this algorithm is evaluated by means of large-scale numerical examples. Consequently, we can find this approach is efficient even for real world practical networks. [Copyright &y& Elsevier]

The existing dynamic and stochastic shortest path problem (DSSPP) algorithms assume that the mean and variance of link travel time (or other specific random variable such as cost) are available. When they are used with observed data from previous time periods, this assumption is reasonable. However, when they are applied using forecast data for future time periods, which happens in the context of ATIS, the travel time uncertainty needs to be taken into account. There are two components of travel time uncertainty and these are the individual travel time variance and the mean travel time forecasting error.The objectives of this study are to examine the characteristics of two components of travel time uncertainty, to develop mathematical models for determining the mean and variance of the forecast individual travel time in future time periods in the context of ATIS, and to validate the proposed models. First, this study examines the characteristics of the two components of uncertainty of the individual travel time forecasts for future time periods and then develops mathematical models for estimating the mean and variance of individual route travel time forecasts for future time periods. The proposed models are then implemented and the results are evaluated using the travel time data from a test bed located in Houston, Texas. The results show that the proposed DSSPP algorithms can be applied for both travel time estimation and travel time forecasting. [Copyright &y& Elsevier]

• Use of magnetic skyrmions to find and display the final solution of the shortest path problem. • Skyrmions must exhibit a zero skyrmion Hall angle (use of synthetic antiferromagnets, antiferromagnets, compensated ferrimagnets). • Failure to use ferromagnets, where skyrmions exhibit a finite skyrmion Hall angle. • Perspective for the hardware realization of skyrmion devices for the solution of the shortest path problem based on a self-reinforced algorithm. Magnetic skyrmions are emerging as key elements of unconventional operations having unique properties such as small size and low current manipulation. In particular, it is possible to design skyrmion based neurons and synapses for neuromorphic computing in devices where skyrmions move along the current direction (zero skyrmion Hall angle). Here, we show that, for a given graph, skyrmions can be used in optimization problems facing the calculation of the shortest path. Our tests show a solution with the same path length as computed with the Dijkstra's Algorithm. In addition, we also discuss how skyrmions act as positive feedback on this type of problems giving rise to a self-reinforcement of the path which is a possible solution. [ABSTRACT FROM AUTHOR]

• Stratified sampling reduces genotype diversify thus reducing exploration time. • Opposition-Based guessing increases initial population fitness. • Path Length diversity is more important during the initialization phase. • The repair function can introduce diversity to population. Initialization is the first and a major step in the implementation of evolutionary algorithms (EAs). Although there are many common general methods to initialize EAs such as the pseudo-random number generator (PRNG), there is no single method that can fit every problem. This study provides a new, flexible, diversity-aware, and easy-to-implement initialization method for a genetic algorithm for the shortest path problem. The proposed algorithm, called stratified opposition-based sampling (SOBS), considers phenotype and genotype diversity while striving to achieve the best fitness for the initialization population. SOBS does not depend on a specific type of sampling, because the main goal is to stratify the sampling space. SOBS aims at an initial population with higher fitness and diversity in the phenotype and genotype. To investigate the performance of SOBS, four network models were used to simulate real-world networks. Compared with the most frequently used initialization method, that is, PRNG, SOBS provides more accurate solutions, better running time with less memory usage, and an initial population with higher fitness. Statistical analysis showed that SOBS yields solutions with higher accuracy in 68–100% of the time. Although this study was focused on the genetic algorithm, it can be applied to other population-based EAs that solve the shortest path problem and use the same direct population representation such as particle swarm optimization (PSO). [ABSTRACT FROM AUTHOR]

This paper studies an iterative stochastic algorithm for solving the stochastic shortest path problem. This algorithm, which uses a distributed learning automata, tries to find the shortest path by taking a sufficient number of samples from the edges of the graph. In this algorithm, which edges to be sampled are determined dynamically as the algorithm proceeds. At each iteration of this algorithm, a distributed learning automata used to determine which edges to be sampled. This sampling method, which uses distributed learning automata, reduces the number of samplings from those edges, which may not be along the shortest path, and resulting in a reduction in the number of the edges to be sampled. In this paper, we propose a new method for analysis of the algorithm. The method proposed in this paper, unlike the previous ones, which were based on the Martingale theory, is based on the sampling. The proof given in this paper, unlike the previous ones, which were for a specific input graph, is not restricted to the input graph and is general. We also show that as the number of samples taken from the edges increases, the probability of finding the shortest path also increases. Experimental results obtained from some benchmark stochastic graphs and some random graphs also confirm the theoretical results. [ABSTRACT FROM AUTHOR]