Search

In The traveling salesman problem (TSP) is an essential and the most popular conventional combinatorial optimization network problem in operations research, in which the TSP evaluates the shortest route or path in a network. In TSP, every node has been visited only once, excluding the starting node. In TSP, edge lengths are usually expressed to indicate journey time and expenses instead of distance from a location. The exact arc length can't be predicted because journey times and expenses vary depending on the amount of payload, climate, highway conditions, and so on. As a result, the Neutrosophic numbers introduce a new tool for dealing with unpredictability in TSP. The present article addresses TSP on a neutrosophic network where the edge weight is a neutrosophic number rather than a real number. For solving the Neutrosophic TSP, an algorithmic technique based on the genetic algorithm (GA) is proposed. We created a new mutation and crossover for our suggested GA. We used mathematical examples to show the usefulness of the algorithm that we suggested. The results of experiments suggest that the proposed GA can find the shortest path in a TSP within a neutrosophic framework. This provides valuable insights for decision-makers dealing with real-world situations characterized by imprecise and incomplete data. [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.

The Mobile Robot Path Problem looks to find the optimal shortest path from the starting point to the target point with collision-free for a mobile robot. This is a popular issue in robotics and in this paper the environment is considered as static and represented as a bidirectional grid map. Besides, the novel optimal method Dhouib-Matrix-SPP (DM-SPP) is applied to create the optimal shortest path for a mobile robot in a static environment. DM-SPP is a greedy method based on a column row navigation in the distance matrix and characterized by its rapidity to solve sparse graphs. The comparative analysis is conducted by applying DM-SPP on thirteen test cases and comparing its results to the results given by four metaheuristics the Max-Min Ant System, the Ant System with punitive measures, the A* and the Improved Hybrid A*. The outcomes acquired from different scenarios indicate that the proposed DM-SPP method can rapidly outperform the four predefined artificial intelligence methods.

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]

Shortest path problem (SPP) has various applications in areas such as telecommunications, transportation and emergency services, and postal services among others. As a result, several algorithms have been developed to solve the SPP and related problems. The current paper extends the TANYAKUMU labelling method for solving the Travelling salesman problem (TSP) to solve SPP in directed transportation networks. Numerical illustrations are used to prove the validity of the proposed method. The main contributions of this paper are as follows: (i) modification of TSP algorithm to solve single source SPP, (ii) the developed method numerically evaluated on four increasingly complex problems of sizes 11×11, 21×21, 23×23 and 26×26 and lastly (iii) the solutions obtained from solving these four problems are compared with those obtained by Minimum incoming weight label (MIWL) algorithm. The proposed algorithm computed the same shortest paths as the MIWL algorithm on all four problems.

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.

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.

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]

The realms of Intuitionistic Fuzzy Sets (IFSs), Pythagorean Fuzzy Sets (PFS), and qrung Orthopair Fuzzy Sets (q-ROFSs) have found extensive applications across various disciplines, notably in resolving real-world problems. However, limitations concerning membership and non-membership grades pose challenges to these theories. Efforts to mitigate these constraints have led to the introduction of a new concept, the Linear Diophantine Fuzzy Set (LDFS), with reference parameters. This study advances the shortest path (SP) problem for Linear Diophantine Fuzzy graphs. An innovative method for constructing direct network graphs within a Linear Diophantine Fuzzy (LDF) context is proposed. Distances or costs between nodes are encapsulated by Linear Diophantine Fuzzy numbers. The principal contribution of this investigation lies in proposing a novel approach to solving the Linear Fuzzy Diophantine Fuzzy shortest path problem using the Bellman-Ford algorithm for optimal solution attainment. Usage of the score function enables the comparison and identification of the minimum arc value between nodes. The proposed algorithm's validity is demonstrated through a numerical example, and a comparison with existing methodologies underscores the benefits of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Shortest path problem (SPP) has various applications in areas such as telecommunications, transportation and emergency services, and postal services among others. As a result, several algorithms have been developed to solve the SPP and related problems. The current paper extends the TANYAKUMU labelling method for solving the Travelling salesman problem (TSP) to solve SPP in directed transportation networks. Numerical illustrations are used to prove the validity of the proposed method. The main contributions of this paper are as follows: (i) modification of TSP algorithm to solve single source SPP, (ii) the developed method numerically evaluated on four increasingly complex problems of sizes 11×11, 21×21, 23×23 and 26×26 and lastly (iii) the solutions obtained from solving these four problems are compared with those obtained by Minimum incoming weight label (MIWL) algorithm. The proposed algorithm computed the same shortest paths as the MIWL algorithm on all four problems. [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]

Single-pair shortest pathfinding (SP) algorithms are used to identify the path with the minimum cost between two vertices in a given graph. However, their time complexity can rapidly increase as the graph size grows. In this paper, we propose a pattern-based blocking algorithm in a grid graph (PBGG) that iteratively blocks or reduces free space vertices that do not require exploration. The blocking process is based on the neighbors of each vertex and utilizes $3 \times 3$ binary pattern matching. The time complexity of blocking is $O(I\cdot \lceil \vert V\vert /C\rceil)$ , where $\vert V\vert $ is the number of vertices, $I$ is the maximum number of iterations, and $C$ is the number of parallelized cores. PBGG significantly reduces the total computation time when utilized to preprocess an input grid graph before applying existing SP algorithms. It also guarantees that if a minimum-cost path exists in the original graph, then the SP algorithms can find at least one path with the same minimum cost in the reduced graph. The proposed method is formulated by convolutions that can be easily implemented using machine learning platforms, such as PyTorch. Experimental results show that when PBGG can significantly reduce the total computation time when employed in conjunction with SP algorithms such as $\text{A}\ast $ and Jump Point Search. On average, PBGG reduces the total computation times by 71% for A and 41% for Jump Point Search, compared to the times taken by the SP algorithms alone.

Changeability analysis methods primarily assist with formulating a response to uncertain and new requirements from various system stakeholders and include asset management issues such as modelling lifecycle path dependency. Epoch-era networks proved to be an effective tool for managing the evolving requirements of a capability system, ensuring sustained value through life. Over the life of a system, stakeholders are faced with countless options to change their capability systems to sustain value, which is path dependent and can greatly impact the scope of decisions available later in life. This paper introduces and demonstrates the application of a revised epoch-era network approach to explore many potential lifecycle paths, along with utility vs. expense strategies, demonstrated through an example of a military frigate subject to evolving requirements. Results indicated the future limitations to sustaining value if the largest and most capable technology upgrades are selected too early in life. The two best lifecycle paths from different strategies were compared to understand the utility/expense trade-offs for the most optimal frigate upgrade trajectory. [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]

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.

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]

This study investigates the analogy between the electric circuit and roadway traffic analyses based on the loop-wise route representation (LRR). These two seemingly different fields share common aspects in terms of primitive components, system behavior, and underlying principles. Considering this analogy, a novel topology optimization is proposed to solve a shortest path problem by introducing artificial loop variables, which are conceptually analogous to loop current in the electric circuit. Then, the loop-wise route optimization is formulated to minimize the travel cost in both symmetric and asymmetric networks. By virtue of using the LRR, the proposed method can guarantee the flow conservation at each node without imposing any constraint functions. To verify the proposed method, numerical experiments in 10 $\times10$ grid-type networks are conducted under various settings. These results show that the shortest path problems can be solved in a simpler form of unconstrained topology optimization. With further work, the proposed method could be applied to solve general vehicle routing problems such as traveling salesman problems in a more effective way.

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.

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.

Changeability analysis methods primarily assist with formulating a response to uncertain and new requirements from various system stakeholders and include asset management issues such as modelling lifecycle path dependency. Epoch-era networks proved to be an effective tool for managing the evolving requirements of a capability system, ensuring sustained value through life. Over the life of a system, stakeholders are faced with countless options to change their capability systems to sustain value, which is path dependent and can greatly impact the scope of decisions available later in life. This paper introduces and demonstrates the application of a revised epoch-era network approach to explore many potential lifecycle paths, along with utility vs. expense strategies, demonstrated through an example of a military frigate subject to evolving requirements. Results indicated the future limitations to sustaining value if the largest and most capable technology upgrades are selected too early in life. The two best lifecycle paths from different strategies were compared to understand the utility/expense trade-offs for the most optimal frigate upgrade trajectory.

Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in this technique involves solving a discrete optimization problem that assigns the resonance frequency to each atom in the protein. This paper introduces LIAN (LInear programming Assignment for NMR), a novel linear programming formulation of the problem which yields state-of-the-art results in simulated and experimental datasets. [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]

An elongation of the novel intuitionistic fuzzy set is a picture fuzzy set theory. The demonstration of this has been used to deal with the abstinence criteria in a decision-making problem. The uncertainty in nature occurs sometimes in real-world problems and amidst them, the prominent one is the shortest path problem (SPP) solving. In the last few years, one of the best algorithms on the network for finding SPP is Bellman–Ford. Due to uncertainty in the decision-making process, it becomes difficult for decision-makers for communicating their point of view and judgment with certainty. We conceive of SPP in this contribution via Bellman's algorithm (BA) for a network with trapezoidal picture fuzzy numbers (TPFNs). We introduce a new algorithm to stand the shortest picture fuzzy path between each pair of nodes. A TPFN is considered for the length of all edges. A numerical example for the validation of the presented algorithm has also been proposed. There has also been relative research with existing techniques showing the benefits of the new algorithm. [ABSTRACT FROM AUTHOR]

The shortest path problem (SPP) is considerably important in several fields. After typhoons, the resulting damage leads to uncertainty regarding the path weight that can be expressed accurately. A neutrosophic set is a collection of the truth membership, indeterminacy membership, and falsity membership degrees of the elements. In an uncertain environment, neutrosophic numbers can express the edge distance more effectively. Based on the theories of interval valued neutrosophy and neutrosophic graphs, this paper proposes a shortest path solution method of interval valued neutrosophic graphs using the ant colony algorithm. Further, an analysis comparing the proposed algorithm with the Dijkstra algorithm was used to probe the potential shortcomings and advantages of the proposed method. In addition, this approach confirmed the effectiveness of the proposed algorithm. Furthermore, we investigated the convergence processes of the ant colony algorithm with different parameter settings, analyzed their results, and used different score functions to solve the SPP and analyze the results.

Resilient circuits represent promising approaches for improving both circuit performance and tolerance for dynamic variations. However, the short path padding problem becomes severe during the implementation, resulting in significant area overhead and even frequency degradation, which might nullify the benefits of resilience. The present work addresses this issue by proposing a progressive resilient design methodology, including a clock period prediction method that can accurately access the minimum clock period possible in an early stage and a short path padding method, based on the greedy heuristic algorithm to reduce both the total padding delay and the runtime. The runtime for the padding stage is further minimized by introducing an accelerated padding method that decreases the number of point visits required during the greedy padding process. The proposed methodology is applied to several benchmark circuits, decreasing averagely 26.1% in the total number of padding buffers and 38.1% in the runtime, compared to a present state of the art methodology. Thus, this proposal not only avoids iterations of padding assignments by early period prediction, but also is a feasible and effective short path padding methodology for resilient circuits.

This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path |P| to be provided as an input. For a graph with |V| vertices, |E| edges, and no self-loops, it encodes the problem instance using |V||P| qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using |E| qubits for directed graphs or 2|E| qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in |E| + |V| qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.

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.

In recent years, numerous researchers examined and analyzed several different types of uncertainty in shortest path (SP) problems. However, those SP problems in which the costs of arcs are expressed in terms of mixed interval-valued fuzzy numbers are less addressed. Here, for solving such uncertain SP problems, first a new procedure is extended to approximate the summation of mixed interval-valued fuzzy numbers using alpha cuts. Then, an extended distance function is introduced for comparing the path weights. Finally, we intend to use a modified artificial bee colony (MABC) algorithm to find the interval-valued membership function of SP in such mixed interval-valued fuzzy network. The proposed algorithm is illustrated via two applications of SP problems in wireless sensor networks and then the results are compared with those derived from genetic and particle swarm optimization (PSO) algorithms, based on three indexes convergence iteration, convergence time and run time. The obtained results confirm that the MABC algorithm has less convergence iteration, convergence time and implementation time compared to GA and PSO algorithm. [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]

The shortest path problem (SPP) is a special network structured linear programming problem that appears in a wide range of applications. Classical SPPs consider only one objective in the networks while some or all of the multiple, conflicting and incommensurate objectives such as optimization of cost, profit, time, distance, risk, and quality of service may arise together in real-world applications. These types of SPPs are known as the multi-objective shortest path problem (MOSPP) and can be solved with the existing various approaches. This paper develops a Data Envelopment Analysis (DEA)-based approach to solve the MOSPP with fuzzy parameters (FMOSPP) to account for real situations where input–output data include uncertainty of triangular membership form. This approach to make a connection between the MOSPP and DEA is more flexible to deal with real practical applications. To this end, each arc in a FMOSPP is considered as a decision-making unit with multiple fuzzy inputs and outputs. Then two fuzzy efficiency scores are obtained corresponding to each arc. These fuzzy efficiency scores are combined to define a unique fuzzy relative efficiency. Hence, the FMOSPP is converted into a single objective Fuzzy Shortest Path Problem (FSPP) that can be solved using existing FSPP algorithms. [ABSTRACT FROM AUTHOR]

Abstract Due to various accidents and crime threats to an unspecified number of people, many surveillance technologies have been studied as an interest in individual security continues to increase throughout society. In particular, intelligent video surveillance technology is one of the most active research areas in the field of surveillance; this popularity has been spurred by recent advances in computer vision/image processing and machine learning. The main goal is to automatically detect, recognize, and analyze objects of interest from collected sensor information and then efficiently extract/utilize this useful information, such as by detecting abnormal events or intruders and recognizing objects. Anomalous event detection is a key component of security, and many existing anomaly detection algorithms rely on a foreground subtraction process to detect changes in the foreground scene. By comparing input image frames with a reference image, changed areas of the image can be efficiently detected. However, this technique can be insensitive to static changes and has difficulties in noisy environments since it depends on a reference image. We propose a new strategy for improved dynamic/static change detection that complements the weak points of existing detection methods, which have low robustness in noisy environments. To achieve this goal, we employed a self-organizing map (SOM) for data clustering and regarded the cluster distribution of neurons, represented by the weight of the optimized SOM, as a directed graph problem. We then applied the shortest path algorithm to recognize anomalous events. The real-time monitoring capability of the proposed change detection system was verified by applying it to self-produced test data and the CDnet-2014 dataset. This system showed robustness against noise that was superior to other surveillance systems in various environments.

In this paper, an optimization model for the Charging Station Location Problem of Electric Vehicles for Freight Transportation CSLP-EVFT is presented. This model aims to determine an optimal location strategy of Electric Vehicle Charging Stations EVCSs and the routing plan of a fleet of electric vehicles under battery driving range limitation, in conjunction with the impact on the power distribution system. Freight transportation is modeled under the mobility patterns followed by the Capacitated Vehicle Routing Problem CVRP for contracted fleet, and Shortest Path SP problem for subcontracted fleet. A linear formulation of the power flow is used in order to consider the impact on the electric grid. Several costs are examined, i.e., EVs routing, installation and energy consumption of EVCSs, and energy losses. Although uncertainties related to temporal variation of some aspects (number of customers and their demands, fleet size, power network nodes and routes) are not addressed, the proposed model represents a useful approach to evaluate multiple scenarios or to be introduced within stochastic optimization. Instead, the mathematical model is studied under the variation of EVs travel range that accounts for the advance of battery technology and sensitivity analysis. Additionally, the problem is reduced to a mixed integer non-linear mathematical model, which is linearized by using multivariable Taylor’s series.

In engineering, computer sciences and many other applied sciences, finding shortest path in a network is one of the famous problems. The aim of this manuscript is to develop a novel algorithm for finding shortest path in a network where nodes and edges have some uncertainty. Firstly, the concept of single-valued neutrosophic hesitant fuzzy graph (SVNHFG) has been introduced with some related graph theoretical results such that complement, subgraph, degree and path etc. Some examples are provided to understand the defined concepts. Then, the new algorithm for solving shortest path problems (SPPs) has been introduced followed by a flowchart for a stepwise description. A numerical example is provided in the environment of SVNHFGs to demonstrate the proposed algorithm. The advantages of proposed method over the existing techniques are also discussed.

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.

In order to make strategic, tactical and operational decisions for the shortest path in an uncertain environment. Firstly, the information transmission time expectation-variance shortest path model in uncertain environment is proposed. Secondly, to avoid the interruption of information transmission caused by sudden situations, a fuzzy shortest path critical edge model is established. Then, an improved ant colony algorithm with traffic congestion factor and random variables is developed. Finally, to assess the performance of Improved ant colony algorithm, experiments on a set of 6 benchmark test functions are conducted, and numerical examples of these models are given to illustrate its effectiveness.

This paper introduces a new variant of the Shortest Path Problem (SPP) called the Cost-Balanced Path Problem (CBPP). Various real problems can either be modeled as BCPP or include BCPP as a sub-problem. We prove several properties related to the complexity of the CBPP problem. In particular, we demonstrate that the problem is NP-hard in its general version, but it becomes solvable in polynomial time in a specific family of instances. Moreover, a mathematical formulation of the CBPP, as a mixed-integer programming model, is proposed, and some additional constraints for modeling real requirements are given. This paper validates the proposed model and its extensions with experimental tests based on random instances. The analysis of the results of the computational experiments shows that the proposed model and its extension can be used to model many real applications. Obviously, due to the problem complexity, the main limitation of the proposed approach is related to the size of the instances. A heuristic solution approach should be required for larger-sized and more complex instances.

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.

The shortest path problem (SPP) is an optimization problem of determining a path between specified source vertex s and destination vertex t in a fuzzy network. Fuzzy logic can handle the uncertainties, associated with the information of any real life problem, where conventional mathematical models may fail to reveal proper result. In classical SPP, real numbers are used to represent the arc length of the network. However, the uncertainties related with the linguistic description of arc length in SPP are not properly represented by real number. We need to address two main matters in SPP with fuzzy arc lengths. The first matter is how to calculate the path length using fuzzy addition operation and the second matter is how to compare the two different path lengths denoted by fuzzy parameter. We use the graded mean integration technique of triangular fuzzy numbers to solve this two problems. A common heuristic algorithm to solve the SPP is the genetic algorithm. In this manuscript, we have introduced an algorithmic method based on genetic algorithm for determining the shortest path between a source vertex s and destination vertex t in a fuzzy graph with fuzzy arc lengths in SPP. A new crossover and mutation is introduced to solve this SPP. We also describe the QoS routing problem in a wireless ad hoc network. [ABSTRACT FROM AUTHOR]

Featured Application: Our proposal has application in a real problem, whose objective is to guide a mobile robot to a target point in an environment that changes along time. These changes are characterized by the addition of obstacles that prevent navigation or the inability to follow a previously computed route, for instance scenarios of recent hazards or natural disasters. Robot navigation is still an open research topic, mainly regarding applications that require online planning. In this context, this manuscript presents an implementation of the Lifelong Planning A* (LPA*) search algorithm to guide a mobile robot in an environment that changes along time, by detecting obstacles and updating the current mapping information. Firstly, simulations validate the strategy, and later experiments confirm these results considering a real application. The result is that the LPA* algorithm is able to guide the mobile robot to its target in a changing environment. Obstacles are interactively included in the scene to force the route redesign and the seeking for a new optimal solution connecting the current robot position and its target position. [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]