215 results on '"Shortest path problem"'
Search Results
2. Evaluation of Shortest path on multi stage graph problem using Dynamic approach under neutrosophic environment
- Author
-
Prasanta Kumar Raut, Siva Prasad Behera, Said Broumi, and Amarendra Baral
- Subjects
dynamic programming approach ,multistage graph ,neutrosophic multi-value number ,shortest path problem ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF
3. Intelligent path planning for cognitive mobile robot based on Dhouib-Matrix-SPP method
- Author
-
Souhail Dhouib
- Subjects
Path planning ,Mobile robot ,Shortest path problem ,Artificial intelligence ,Operations research ,Dhouib-Matrix-SPP ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF
4. Evaluation of Shortest path on multi stage graph problem using Dynamic approach under neutrosophic environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Baral, Amarendra
- Subjects
- *
DYNAMIC programming , *COMPUTER engineering , *PROGRAMMING languages , *GRAPH theory , *ALGORITHMS - Abstract
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]
- Published
- 2024
5. Extended TANYAKUMU Labelling Method to Compute Shortest Paths in Directed Networks
- Author
-
Trust Tawanda, Elias Munapo, Santosh Kumar, and Philimon Nyamugure
- Subjects
tanyakumu labelling method ,miwl algorithm ,shortest path problem ,transportation network ,Technology ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
6. Calculation of shortest path on Fermatean Neutrosophic Networks
- Author
-
Prasanta Kumar Raut, Siva Prasad Behera, Said Broumi, and Debdas Mishra
- Subjects
fermatean neutrosophic graph ,fermatean neutrosophic number ,shortest path problem ,uncertainty ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
7. Calculation of Fuzzy shortest path problem using Multi-valued Neutrosophic number under fuzzy environment
- Author
-
Prasanta Kumar Raut, Siva Prasad Behera, Said Broumi, and Debdas Mishra
- Subjects
directed graph network ,multi-valued neutrosophic numbers ,selection sort technique ,shortest path problem ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
8. Optimal Transport and Seismic Rays.
- Author
-
Magrini, Fabrizio and Sambridge, Malcolm
- Subjects
- *
COST functions , *UNDIRECTED graphs , *EIKONAL equation , *SPARSE matrices , *TRANSPORT theory , *DIRECTED graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
9. Employing the Bellman-Ford Algorithm with Score Functions to Address the Linear Diophantine Fuzzy Shortest Path Problem in Network Analysis.
- Author
-
Kannan, Vidhya and Appasamy, Saraswathi
- Subjects
FUZZY numbers ,FUZZY graphs ,ALGORITHMS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
10. Extended TANYAKUMU Labelling Method to Compute Shortest Paths in Directed Networks.
- Author
-
Tawanda, Trust, Munapo, Elias, Kumar, Santosh, and Nyamugure, Philimon
- Subjects
TRAVELING salesman problem ,POSTAL service ,EMERGENCY medical services ,PROBLEM solving - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
11. Calculation of Fuzzy shortest path problem using Multi-valued Neutrosophic number under fuzzy environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory , *GRAPH connectivity , *DIRECTED graphs , *FIRE stations , *TELECOMMUNICATION systems , *SERVICE stations , *FUZZY numbers - Abstract
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]
- Published
- 2023
12. Calculation of shortest path on Fermatean Neutrosophic Networks.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory - Abstract
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]
- Published
- 2023
13. In-Path Oracles for Road Networks.
- Author
-
Ghosh, Debajyoti, Sankaranarayanan, Jagan, Khatter, Kiran, and Samet, Hanan
- Subjects
- *
SPATIAL data structures , *DATABASES , *GEOGRAPHIC information systems - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
14. Grid Graph Reduction for Efficient Shortest Pathfinding
- Author
-
Chan-Young Kim and Sanghoon Sull
- Subjects
Blocking ,convolution ,dead-end/avoidable vertices ,nonblockable vertices ,pattern matching ,shortest path problem ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
15. Lifecycle Value Sustainment and Planning Mission Upgrades for Complex Systems: The Case of Warships.
- Author
-
Dwyer, Dylan and Efatmaneshnik, Mahmoud
- Subjects
WARSHIPS ,ASSET management ,FRIGATES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
16. Distributed algorithms from arboreal ants for the shortest path problem.
- Author
-
Garg, Shivam, Shiragur, Kirankumar, Gordon, Deborah M., and Charikar, Moses
- Subjects
- *
DISTRIBUTED algorithms , *ANTS , *TROPICAL forests , *RANDOM walks , *RANDOM graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
17. Ant Lion Optimized Lexicographic Model for Shortest Path Identification.
- Author
-
Kumawat, Sunita, Dudeja, Chanchal, and Kumar, Pawan
- Subjects
- *
ANT lions , *PARETO optimum - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
18. Optimal Transport and Seismic Rays
- Author
-
Fabrizio Magrini and Malcolm Sambridge
- Subjects
transportation theory ,ray theory ,shortest path problem ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
19. Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem.
- Author
-
Guo, Hongliang, Shi, Rui, Rus, Daniela, and Yau, Wei-Yun
- Subjects
- *
DYNAMIC programming , *TRAVEL time (Traffic engineering) , *TRAVELERS , *HEURISTIC algorithms , *APPROXIMATION algorithms , *STANDARD deviations - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
20. A Constructive Heuristics and an Iterated Neighborhood Search Procedure to Solve the Cost-Balanced Path Problem.
- Author
-
Ambrosino, Daniela, Cerrone, Carmine, and Sciomachen, Anna
- Subjects
- *
HEURISTIC algorithms , *HEURISTIC , *COMBINATORIAL optimization - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
21. Loopwise Route Representation-Based Topology Optimization for the Shortest Path Problems
- Author
-
Geunu Kim, Sungyong Kim, and In Gwun Jang
- Subjects
Loop-wise route representation ,shortest path problem ,sensitivity analysis ,topology optimization ,vehicle route problem ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2022
- Full Text
- View/download PDF
22. Optimization of Autonomous Agent Routes in Logistics Warehouse
- Author
-
Tomasz Markowski and Piotr Bilski
- Subjects
shortest path problem ,hive of robots ,logistics ,microcontrollers ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 ,Telecommunication ,TK5101-6720 - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
23. A Hybrid Routing Approach Using Two Searching Layers
- Author
-
Koca Gonca Ozmen and Yetkin Seda
- Subjects
motion control ,optimization ,path planning ,shortest path problem ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
24. Lifecycle Value Sustainment and Planning Mission Upgrades for Complex Systems: The Case of Warships
- Author
-
Dylan Dwyer and Mahmoud Efatmaneshnik
- Subjects
changeability ,complex systems ,capability systems ,lifecycle planning ,shortest path problem ,systems modelling ,Systems engineering ,TA168 ,Technology (General) ,T1-995 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
25. NMR assignment through linear programming.
- Author
-
Bravo-Ferreira, José F. S., Cowburn, David, Khoo, Yuehaw, and Singer, Amit
- Subjects
LINEAR programming ,NUCLEAR magnetic resonance ,X-ray crystallography ,CYTOSKELETAL proteins ,NUCLEAR magnetic resonance spectroscopy - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
26. An Optimization Framework for Power Infrastructure Planning.
- Author
-
Wiedemann, Nina and Adjiashvili, David
- Subjects
- *
INFRASTRUCTURE (Economics) , *MATHEMATICAL optimization , *POWER resources , *CONSTRUCTION projects - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
27. Deeper Weight Pruning Without Accuracy Loss in Deep Neural Networks: Signed-Digit Representation-Based Approach.
- Author
-
Ahn, Byungmin and Kim, Taewhan
- Subjects
- *
APPROXIMATION algorithms , *MULTIPLICATION , *PARALLEL processing , *PHYSIOLOGICAL effects of acceleration - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
28. Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph.
- Author
-
Jiang, Zetian, Wang, Tianzhe, and Yan, Junchi
- Subjects
- *
MULTIGRAPH , *ALGORITHMS , *SOURCE code , *DYNAMIC programming , *HEURISTIC algorithms , *ONLINE algorithms - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
29. Optimization of Autonomous Agent Routes in Logistics Warehouse.
- Author
-
Markowski, Tomasz and Bilski, Piotr
- Subjects
- *
INTELLIGENT agents , *WAREHOUSES , *LOGISTICS , *ROBOTS , *ALGORITHMS - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
30. Bellman–Ford algorithm for solving shortest path problem of a network under picture fuzzy environment.
- Author
-
Parimala, Mani, Broumi, Said, Prakash, Karthikeyan, and Topal, Selçuk
- Subjects
FUZZY numbers ,SET theory ,PICTURES ,FUZZY graphs ,RESEARCH methodology - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
31. Research on the Shortest Path Solution Method of Interval Valued Neutrosophic Graphs Based on the Ant Colony Algorithm
- Author
-
Lehua Yang, Dongmei Li, and Ruipu Tan
- Subjects
Ant colony algorithm ,interval valued neutrosophic numbers ,neutrosophic graph ,shortest path problem ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2020
- Full Text
- View/download PDF
32. A Dedicated Greedy Short Path Padding Solution Method for Error Resilient Circuit Designs
- Author
-
Yan He, Zhijian Chen, Xiaoyan Xiang, and Taotao Zhu
- Subjects
Greedy algorithms ,resilience ,shortest path problem ,ultra-low voltage ,minimum period ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2020
- Full Text
- View/download PDF
33. Solving the Network Shortest Path Problem on a Quantum Annealer
- Author
-
Thomas Krauss and Joey McCollum
- Subjects
Quantum annealing ,quantum computing ,shortest path problem ,simulated annealing ,Atomic physics. Constitution and properties of matter ,QC170-197 ,Materials of engineering and construction. Mechanics of materials ,TA401-492 - Abstract
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.
- Published
- 2020
- Full Text
- View/download PDF
34. A Constructive Heuristics and an Iterated Neighborhood Search Procedure to Solve the Cost-Balanced Path Problem
- Author
-
Daniela Ambrosino, Carmine Cerrone, and Anna Sciomachen
- Subjects
shortest path problem ,NP hard combinatorial optimization problem ,cost balanced optimization problem ,constructive heuristic ,neighborhood search procedure ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2022
- Full Text
- View/download PDF
35. Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem.
- Author
-
Ebrahimnejad, Ali, Enayattabr, Mohammad, Motameni, Homayun, and Garg, Harish
- Subjects
BEES algorithm ,WIRELESS sensor networks ,PARTICLE swarm optimization ,FUZZY numbers ,MEMBERSHIP functions (Fuzzy logic) - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
36. Fuzzy Constrained Shortest Path Problem for Location-Based Online Services.
- Author
-
Sori, Ali Abbaszadeh, Ebrahimnejad, Ali, Motameni, Homayun, and Verdegay, Jose Luis
- Subjects
- *
LOCATION-based services , *ENVIRONMENTAL economics , *WEATHER , *FUZZY numbers , *DYNAMIC programming - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
37. Solving fuzzy multi-objective shortest path problem based on data envelopment analysis approach.
- Author
-
Bagheri, M., Ebrahimnejad, Ali, Razavyan, S., Lotfi, F. Hosseinzadeh, and Malekmohammadi, N.
- Subjects
DATA envelopment analysis ,LINEAR programming ,FUZZY graphs ,QUALITY of service - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
38. An online graph-based anomalous change detection strategy for unsupervised video surveillance
- Author
-
Jongwon KIM and Jeongho CHO
- Subjects
Video surveillance ,Self-organizing maps ,Shortest path problem ,Anomalous event ,Change detection ,Electronics ,TK7800-8360 - Abstract
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.
- Published
- 2019
- Full Text
- View/download PDF
39. Optimal placement of freight electric vehicles charging stations and their impact on the power distribution network
- Author
-
Andrés Arias Londoño and Mauricio Granada-Echeverri
- Subjects
Electric vehicle ,Capacitated vehicle routing problem ,Shortest path problem ,Transportation network ,Power distribution system ,Electric vehicle charging station ,Industrial engineering. Management engineering ,T55.4-60.8 ,Production management. Operations management ,TS155-194 - Abstract
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.
- Published
- 2019
- Full Text
- View/download PDF
40. Computing Shortest Path in a Single Valued Neutrosophic Hesitant Fuzzy Network
- Author
-
M. Saad, T. Mahmood, Kifayat Ullah, and N. Jan
- Subjects
shortest path problem ,networking ,single-valued neutrosophic graphs ,single-valued neutrosophic hesitant fuzzy graphs ,Technology ,Science - Abstract
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.
- Published
- 2019
41. A Multi Objective Programming Approach to Solve Integer Valued Neutrosophic Shortest Path Problems
- Author
-
Ranjan Kumar, S A Edalatpanah, Sripati Jha, S. Broumi, Ramayan Singh, and Arindam Dey
- Subjects
optimization technique ,shortest path problem ,network distribution ,Triangular neutrosophic fuzzy numbers ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2019
- Full Text
- View/download PDF
42. The Shortest Path Problem and Its Critical Edge in Uncertain Environment
- Author
-
Ke Wei Jie, Gao Chang Zhao, and Xiao Jun Sun
- Subjects
Uncertain environment ,shortest path problem ,critical edge model ,algorithm ,benchmark test functions ,numerical examples ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
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.
- Published
- 2019
- Full Text
- View/download PDF
43. The Cost-Balanced Path Problem: A Mathematical Formulation and Complexity Analysis
- Author
-
Daniela Ambrosino and Carmine Cerrone
- Subjects
shortest path problem ,mixed-integer linear programming ,cost-balanced paths ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2022
- Full Text
- View/download PDF
44. Neutrosophic Shortest Path Problem
- Author
-
Ranjan Kumar, S A Edaltpanah, Sripati Jha, Said Broumi, and Arindam Dey
- Subjects
Trapezoidal neutrosophic fuzzy numbers ,scoring ,accuracy and certainty index ,shortest path problem ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2018
- Full Text
- View/download PDF
45. A genetic algorithm for the fuzzy shortest path problem in a fuzzy network.
- Author
-
Lin, Lihua, Wu, Chuzheng, and Ma, Li
- Subjects
FUZZY graphs ,FUZZY algorithms ,GENETIC algorithms ,REAL numbers ,ADDITION (Mathematics) ,ARC length ,AD hoc computer networks - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
46. Real-Time Path Planning for Strategic Missions.
- Author
-
Vasconcelos, João Vítor R., Brandão, Alexandre S., and Sarcinelli-Filho, Mário
- Subjects
MOBILE robots ,SEARCH algorithms ,NATURAL disasters ,ALGORITHMS ,ROBOTS - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
47. Short and long term optimization for micro-object conveying with air-jet modular distributed system.
- Author
-
Mabed, Hakim and Dedu, Eugen
- Subjects
- *
MINIATURE objects , *MICROELECTROMECHANICAL systems , *COMPUTATIONAL complexity , *MAINTAINABILITY (Engineering) , *TECHNOLOGICAL innovations , *TECHNOLOGY convergence - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
48. A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
- Author
-
Kunihiko Hiraishi
- Subjects
shortest path problem ,planning problem ,online algorithm ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
In a previous paper by the author, a pathfinding problem for directed trees is studied under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be found by a procedure whose computational cost becomes exponentially larger as the length increases. In this paper, the same problem is studied for a more general class of graphs called fork-join directed acyclic graphs. The problem for the new class of graphs contains the previous one. In addition, the optimality criterion used in this paper is stronger than that in the previous paper and is more appropriate for real applications.
- Published
- 2021
- Full Text
- View/download PDF
49. The robust shortest path problem for multimodal transportation considering timetable with interval data
- Author
-
Song Liu, Yong Peng, Qiankun Song, and Yiying Zhong
- Subjects
Multimodal transport network ,robust optimization ,shortest path problem ,genetic algorithm ,uncertain environments ,Control engineering systems. Automatic machinery (General) ,TJ212-225 ,Systems engineering ,TA168 - Abstract
In the multimodal transport network, due to various uncertain factors such as weather and traffic conditions, the transport time will become uncertain accordingly, besides, railway transport and water transport are usually limited by timetable. These factors will inevitably affect the path selection. The purpose of this study is to seek an optimal transport scheme that considers both the uncertainty of the multimodal transport network and the timetable limit. In view of the uncertainties of the multimodal transport network, interval data are used to represent the uncertainty of network weights, and robust optimization method is then adopted to process the interval data. An optimal model of robust shortest path considering timetable limit is established and genetic algorithm (GA) is designed to solve the problem. The GA designed provides an encoding method for variable-length chromosomes applicable to shortest path problem solving in the multimodal transport. And the handling methods for loops and inaccessible paths due to chromosome crossover and mutation are also suggested. And finally, numerical examples are provided to verify the validity of the model and algorithm.
- Published
- 2018
- Full Text
- View/download PDF
50. Applying the Dijkstra Algorithm to Solve a Linear Diophantine Fuzzy Environment
- Author
-
Mani Parimala, Saeid Jafari, Muhamad Riaz, and Muhammad Aslam
- Subjects
linear Diophantine fuzzy graphs ,Dijkstra’s algorithm ,linear Diophantine fuzzy numbers ,score function ,shortest path problem ,Mathematics ,QA1-939 - Abstract
Linear Diophantine fuzzy set (LDFS) theory expands Intuitionistic fuzzy set (IFS) and Pythagorean fuzzy set (PyFS) theories, widening the space of vague and uncertain information via reference parameters owing to its magnificent feature of a broad depiction area for permissible doublets. We codify the shortest path (SP) problem for linear Diophantine fuzzy graphs. Linear Diophantine fuzzy numbers (LDFNs) are used to represent the weights associated with arcs. The main goal of the presented work is to create a solution technique for directed network graphs by introducing linear Diophantine fuzzy (LDF) optimality constraints. The weights of distinct routes are calculated using an improved score function (SF) with the arc values represented by LDFNs. The conventional Dijkstra method is further modified to find the arc weights of the linear Diophantine fuzzy shortest path (LDFSP) and coterminal LDFSP based on these enhanced score functions and optimality requirements. A comparative analysis was carried out with the current approaches demonstrating the benefits of the new algorithm. Finally, to validate the possible use of the proposed technique, a small-sized telecommunication network is presented.
- Published
- 2021
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.