106 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. Shortest Path Approximation and Optimal Transport with Flow-rate Constraints
- Author
-
Dong, Anqi
- Subjects
Mechanical engineering ,Computer science ,Mathematics ,Optimal Transport ,Optimization ,Shortest Path Problem ,Transportation - Abstract
In an increasingly interconnected world, the efficient and economical transportation of individuals and commodities has emerged as a cornerstone of modern society. Optimizing transportation plans has a huge potential for journey planning, congestion reduction, supply chain management, and data exchanges. These strategies hold immense relevance not onlyin the realm of engineering and transportation, but also in other fields, such as physics, computer science, economics, and several subject areas in mathematics. The present thesis aims to elucidate the optimization of transportation strategies, with a particular focus on two classical problems, finding short paths in large networks and solving optimal transport problems with flow-rate constraints.The so-called shortest path problem seeks an optimal path of transporting one unit of mass between pairs of vertices on graphs. We present a novel formulation of the problem as an l1-regularized regression, often referred to as lasso (Least Absolute Shrinkage and Selection Operator). Based on this formulation, we draw a connection specifically between trees that grow as active edge-sets in the least angle regression (LARS) algorithm of the lasso problem, and respective shortest-path trees that emerge using the bi-directional Dijkstra algorithm. Then, to overcome the dimensionality challenge in large graphs, we explore the alternating direction method of multipliers (ADMM) in the lasso formulation. The resulting derivativeproximal algorithm speeds up the search for the short paths, trading off optimality (i.e., finding shortest paths) that may not be absolutely essential in a variety applications.The basic transport problem is motivated by the need to transport resources/mass between end-point distributions (supply and demand). We consider the classical Monge-Kantorovich optimal transport problem with a quadratic cost functional to penalize distance of transport, with an added constraint that transported mass is required to pass through constriction points while abiding by specified allowable flow-rate; constriction points may be conceptualized as toll stations with limited throughput. Our contributions in this topic are as follows: (1) we provide a precise Monge formulation for the optimal transport problem with flux constraint at constriction sites along the path that is amenable to generalization in higher dimensions. We work out in detail the case of transport in one dimension by proving existence and uniqueness of solutions. Under suitable regularity assumptions we give an explicit construction of the transport plan; (2) we provide a Kantorovich-type reformulation of the problem by introducing a marginal probability density for the time that mass-elements cross toll stations –a probability density that is to be determined so as to meet given flow-rate constraints. Interestingly, the Kantorovich-type formalism leads to multi-marginal optimal transport problem that is readily solvable by using linear programming. Moreover, existence and uniqueness of solutions are also established in this setting. Then, (3) we propose an entropic penalty term to regularize and reduce the computational cost of resulting multi-marginal problems. Entropic regularization of standard optimal transport leads to an efficient algorithm, the Sinkhorn algorithm, which applies in the present case as well. Leveraging the splittable nature of the cost in our formulation, we proposed a Gluing Sinkhorn algorithm for the multi-marginal optimal transport problem, which reduces the computational cost to a level comparable to that in standard two-marginal problems.
- Published
- 2023
22. 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
23. 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
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. A Hybrid Routing Approach Using Two Searching Layers.
- Author
-
Koca, Gonca Ozmen and Yetkin, Seda
- Subjects
- *
GRAPH algorithms , *SEARCH algorithms , *DECISION making - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
32. 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
33. 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
34. Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems
- Author
-
Wei Wu, Takito Hayashi, Kato Haruyasu, and Liang Tang
- Subjects
Information Systems and Management ,General Computer Science ,Modeling and Simulation ,polynomial-time algorithm ,robust optimization ,scheduling ,batch scheduling ,Management Science and Operations Research ,Industrial and Manufacturing Engineering ,shortest path problem - Published
- 2023
35. 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
36. 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
37. ERA*: Enhanced Relaxed A* algorithm for solving the shortest path problem in regular grid maps.
- Author
-
Ammar, Adel
- Subjects
- *
GRIDS (Cartography) , *ALGORITHMS - Abstract
This paper introduces a novel algorithm for solving the point-to-point shortest path problem in a static regular 8-neighbor connectivity (G8) grid. This algorithm can be seen as a generalization of Hadlock algorithm to G8 grids, and is shown to be theoretically equivalent to the relaxed A ⁎ (R A ⁎) algorithm in terms of the provided solution's path length, but with substantial time and memory savings, due to a completely different computation strategy, based on defining a set of lookup matrices. Through an experimental study on grid maps of various types and sizes (1290 runs on 43 maps), it is proven to be 2.25 times faster than R A ⁎ and 17 times faster than the original A ⁎ , in average. Moreover, it is more memory-efficient, since it does not need to store a G score matrix. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
38. Towards Indoor Temporal-variation aware Shortest Path Query
- Author
-
Zijin Feng, Jianliang Xu, Huan Li, Hong Cheng, Hua Lu, Muhammad Aamir Cheema, and Tiantian Liu
- Subjects
Query processing ,Computer science ,Computation ,Real-time computing ,02 engineering and technology ,Topology ,Set (abstract data type) ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,indoor space indexing ,Buildings ,Routing ,Process (computing) ,Indexes ,shortest path query ,Navigation ,Computer Science Applications ,Semantics ,Temporal variation ,Tree (data structure) ,Computational Theory and Mathematics ,Shortest path problem ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Routing (electronic design automation) ,Cube ,Information Systems - Abstract
The recent years have witnessed the growing popularity of indoor location-based services (LBS) in practice and research. Among others, indoor shortest path query (ISPQ) is of fundamental importance for indoor LBS. However, existing works on ISPQ ignore indoor temporal variations, e.g., the open and close times associated with entities like doors and rooms. In this paper, we define a new type of query called Indoor Temporal-variation aware Shortest Path Query (ITSPQ). It returns the valid shortest path based on the up-to-date indoor topology at the query time. A set of techniques is designed to answer ITSPQ efficiently. We design a graph structure (IT-Graph) that captures indoor temporal variations. To process ITSPQ using IT-Graph, we design two algorithms that check a door's accessibility synchronously and asynchronously. Furthermore, we propose a novel index structure (IT-Index) that extends the state-of-the-art index significantly by storing dynamic door-to-door distances in a compact distance cube associated with tree nodes. When processing ITSPQ using IT-Index, we make use of the distance cube to avoid time-consuming indoor distance computation on-the-fly. We evaluate the proposed techniques using extensive experiments on synthetic and real data. The results show that our IT-Index based method is the most efficient for processing ITSPQ at a modest cost of index memory consumption.
- Published
- 2023
39. Path planning of a mobile robot among curved obstacles through tangent drawing and trapezoidal decomposition
- Author
-
Neeta A. Eapen
- Subjects
Computer Networks and Communications ,Computer science ,020209 energy ,Computation ,02 engineering and technology ,Biomaterials ,Mobile robot ,0202 electrical engineering, electronic engineering, information engineering ,Motion planning ,Time complexity ,Path planning ,Tangent ,Civil and Structural Engineering ,Fluid Flow and Transfer Processes ,Mechanical Engineering ,020208 electrical & electronic engineering ,Metals and Alloys ,Binary logarithm ,Engineering (General). Civil engineering (General) ,Electronic, Optical and Magnetic Materials ,Curved obstacle ,Hardware and Architecture ,Shortest path problem ,Path (graph theory) ,TA1-2040 ,Algorithm - Abstract
Most of the previous studies on mobile robot path planning consider the obstacles as polygons. However, the complex shaped obstacles should be considered as curves rather than polygons, since the latter may result in non-optimal paths. Three new algorithms are proposed for finding the shortest path of a mobile robot among curved obstacles: TAD which uses a tangent drawing method, TRAD which uses trapezoidal decomposition, and TAD-TRAD which uses a combination of the TAD and the TRAD algorithms. The time complexities of the TAD algorithm, the TRAD algorithm, and the TAD-TRAD algorithm are O ( n 3 log n ) , O ( n log n ) , and O ( n ( log n ) 2 ) respectively, where n is the total number of arcs in all the obstacles. The TAD and the TAD-TRAD algorithms compute an optimal shortest path, whereas the TRAD algorithm computes an approximate shortest path, among curved obstacles. The TAD algorithm has a lower time complexity than existing algorithms which are implemented for the computation of the optimal shortest path. The TRAD algorithm has a lower time complexity than existing algorithms which compute an approximate shortest path and the TAD-TRAD algorithm has a lower time complexity than existing algorithms which compute an optimal shortest path. The experimental comparison of the TAD, TRAD, and TAD-TRAD algorithms on 200 randomly generated problems shows that the TAD-TRAD algorithm has the least running time. Moreover, the TAD-TRAD algorithm computes an optimal path using a lesser number of tangents and with lesser time complexity when experimental comparisons are performed with existing algorithms in the literature.
- Published
- 2021
40. On the first general Zagreb eccentricity index
- Author
-
Aisha Javed, Muhammad Imran, Muhammad Jamil, and Roslan Hasni
- Subjects
Combinatorics ,eccentricity of vertices ,first general zagreb eccentricity index ,General Mathematics ,extremal graphs ,lcsh:Mathematics ,Shortest path problem ,Bipartite graph ,lcsh:QA1-939 ,Upper and lower bounds ,Graph ,Vertex (geometry) ,Mathematics - Abstract
In a graph G, the distance between two vertices is the length of the shortest path between them. The maximum distance between a vertex to any other vertex is considered as the eccentricity of the vertex. In this paper, we introduce the first general Zagreb eccentricity index and found upper and lower bounds on this index in terms of order, size and diameter. Moreover, we characterize the extremal graphs in the class of trees, trees with pendant vertices and bipartite graphs. Results on some famous topological indices can be presented as the corollaries of our main results.
- Published
- 2021
41. Research on routing and scheduling algorithms for the simultaneous transmission of diverse data streaming services on the industrial internet
- Author
-
Chenyang Guo, Lina Li, Rui Zhang, Yan Song, and Panfeng Xu
- Subjects
Schedule ,Multidisciplinary ,Computer science ,business.industry ,Reliability (computer networking) ,Ant colony optimization algorithms ,Science ,Information technology ,Network topology ,Article ,Scheduling (computing) ,Traffic classification ,Shortest path problem ,Medicine ,Routing (electronic design automation) ,business ,Computer network - Abstract
OPC UA PubSub Over TSN is the core of the Industrial Internet and guarantees flexible interaction features for multiple parties in real-time for industrial communication. To achieve the transmission of time-triggered traffic in PubSub NetworkMessage, routing and scheduling data need to be analyzed. Traditional routing and scheduling methods have disadvantages such as low calculation efficiency, slow convergence speed, and poor reliability. Therefore, a routing and scheduling method for OPC UA PubSub NetworkMessage time-triggered traffic based on an improved ant colony algorithm is proposed. First, we analyze the network topology model, traffic model, and traffic transmission constraints of TSN; then, we apply the K-means clustering algorithm, the KSP algorithm based on the shortest path idea, and an improved ant colony algorithm for traffic classification, routing, and scheduling calculation. Experimental results show that this method can effectively reduce the delay increase caused by link congestion, improve the ability to schedule time-triggered traffic, and accelerate the convergence rate of iteration.
- Published
- 2021
42. A Constructive Heuristics and an Iterated Neighborhood Search Procedure to Solve the Cost-Balanced Path Problem
- Author
-
Carmine Cerrone, Daniela Ambrosino, and ANNA FRANCA SCIOMACHEN
- Subjects
Computational Mathematics ,Numerical Analysis ,Computational Theory and Mathematics ,cost balanced optimization problem ,constructive heuristic ,neighborhood search procedure ,NP hard combinatorial optimization problem ,shortest path problem ,Theoretical Computer Science - 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
43. Fast Path Recovery for Single Link Failure in SDN-Enabled Wide Area Measurement System
- Author
-
Venkata Dinavahi and Tong Duan
- Subjects
General Computer Science ,Transmission delay ,industrial network ,Computer science ,020209 energy ,Real-time computing ,Phasor ,020206 networking & telecommunications ,02 engineering and technology ,Fast path ,Phasor measurement unit ,fault-tolerate ,Shortest path problem ,Path (graph theory) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,software-defined network ,Communication system ,smart grid ,wide area measurement system ,Dijkstra's algorithm - Abstract
In the wide area measurement system (WAMS), the end-to-end transmission delay between the phasor measurement unit (PMU) and phasor data concentrator (PDC) is strictly constrained for real-time monitoring and protection applications. When a communication link failure happens, fast path recovery is required to reduce the impact of measurement losses. In this work, the promising software-defined network (SDN) technique is leveraged to compute the re-routing path in a global view upon a single link failure. More specifically, a hybrid fast path recovery algorithm (HFPR-A) is proposed based on the principle of simplicity: in some cases, the shortest path or approximate shortest path between PMU and PDC can be recovered by adding only one edge to the original forwarding tree; while in the other cases, the shortest paths can be recovered with lower computational complexity than the traditional Dijkstra’s algorithm. The proposed HFPR-A is implemented on the Ryu + Mininet testbed, and the simulation results on different IEEE benchmark test power systems show that the proposed HFPR-A could find shorter re-routing paths than the existing methods with a low-enough response time.
- Published
- 2022
- Full Text
- View/download PDF
44. Filling in pattern designs for incomplete pairwise comparison matrices: (quasi-)regular graphs with minimal diameter
- Author
-
Zsombor Szádoczki, Sándor Bozóki, and Hailemariam Abebe Tekile
- Subjects
FOS: Computer and information sciences ,Information Systems and Management ,Discrete Mathematics (cs.DM) ,Degree (graph theory) ,Strategy and Management ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,Management Science and Operations Research ,Vertex (geometry) ,Combinatorics ,Set (abstract data type) ,Optimization and Control (math.OC) ,Path (graph theory) ,Shortest path problem ,FOS: Mathematics ,Graph (abstract data type) ,Pairwise comparison ,Adjacency matrix ,Mathematics - Optimization and Control ,Computer Science - Discrete Mathematics ,Mathematics - Abstract
Multicriteria Decision Making problems are important both for individuals and groups. Pairwise comparisons have become popular in the theory and practice of preference modelling and quantification. We focus on decision problems where the set of pairwise comparisons can be chosen, i.e., it is not given a priori. The objective of this paper is to provide recommendations for filling patterns of incomplete pairwise comparison matrices (PCMs) based on their graph representation. Regularity means that each item is compared to others for the same number of times, resulting in a kind of symmetry. A graph on an odd number of vertices is called quasi-regular, if the degree of every vertex is the same odd number, except for one vertex whose degree is larger by one. If there is a pair of items such that their shortest connecting path is very long, the comparison between these two items relies on many intermediate comparisons, and is possibly biased by all of their errors. Such an example was previously found, where the graph generated from the table tennis players' matches included a long shortest path between two vertices (players), and the calculated result appeared to be misleading. If the diameter of the graph of comparisons is low as possible (among the graphs of the same number of edges), we can avoid, or, at least decrease, such cumulated errors. The aim of our research is to find graphs, among regular and quasi-regular ones, with minimal diameter. Both theorists and practitioners can use the results, given in several formats in the appendix: graph, adjacency matrix, list of edges., Comment: 68 pages, 28 figures
- Published
- 2022
45. A column generation approach for the driver scheduling problem with staff cars
- Author
-
Shyam Sundar Govinda Raja Perumal, Jesper Larsen, Morten Riis, Tue R.L. Christensen, and Richard Martin Lusby
- Subjects
Schedule ,Operations research ,Job shop scheduling ,Computer science ,Heuristic ,Mechanical Engineering ,Column generation ,Transportation ,Management Science and Operations Research ,Dynamic programming ,Shortest path problem ,Driver scheduling problem ,Heuristics ,Integer programming ,Labor union ,Information Systems - Abstract
Given a set of timetabled bus trips, transport companies are faced with the challenge of finding a feasible driver schedule that covers all trips and abides by various labor union regulations. The regulations are primarily concerned with providing sufficient breaks for the drivers during the day. Practical limitations in the city network enforce drivers to travel by cars between bus stops to have breaks. Transport companies have a limited number of cars, known as staff cars,which have to be returned to their respective depots at the end of the day. The simultaneous scheduling of drivers and staff cars for the drivers is known as the driver scheduling problem with staff cars (DSPSC). It is estimated that the DSPSC accounts for 60% of a bus company’s operational expense, and this paper proposes a column generation approach that attempts to minimize operational expense. The column generation framework iterates between a master problem, a subproblem for generating driver variables and a subproblem for generating staff car variables. The subproblem related to the drivers is formulated as a resource constrained shortest path problem, which is solved by a dynamic programming approach. Several heuristic branching strategies are explored to find integer solutions. The proposed methodology is tested on eight real-life instances from seven Northern European bus companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver and an adaptive large neighborhood search (ALNS) heuristic indicate that the column generation approach provides improved solutions for six instances and the average improvement is 1.45%.
- Published
- 2022
46. Drawing Shortest Paths in Geodetic Graphs
- Author
-
Michael Hoffmann, Maximilian Pfister, Thomas Schneck, Stephen G. Kobourov, Henry Förster, Sabine Cornelsen, Martin Gronemann, Auber, David, and Valtr, Pavel
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,050101 languages & linguistics ,Class (set theory) ,General Computer Science ,Discrete Mathematics (cs.DM) ,Computer science ,05 social sciences ,Geodetic datum ,02 engineering and technology ,Space (mathematics) ,Graph ,Computer Science Applications ,Theoretical Computer Science ,Combinatorics ,Computational Theory and Mathematics ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science - Computational Geometry ,020201 artificial intelligence & image processing ,0501 psychology and cognitive sciences ,Geometry and Topology ,Edge crossings ,Unique shortest paths ,Geodetic graphs ,Computer Science - Discrete Mathematics - Abstract
Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low., Journal of Graph Algorithms and Applications, 26 (3), ISSN:1526-1719
- Published
- 2022
47. Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
- Author
-
Nikolaus Augsten, Michael H. Böhlen, Bezaye Tesfaye, Mateusz Pawlik, Christian S. Jensen, University of Zurich, and Tesfaye, Bezaye
- Subjects
Spatial network databases ,Temporal graphs ,Theoretical computer science ,Computer Networks and Communications ,Computer science ,10009 Department of Informatics ,Node (networking) ,Graph partition ,000 Computer science, knowledge & systems ,1710 Information Systems ,Theoretical Computer Science ,Ranking (information retrieval) ,1712 Software ,Tree traversal ,Reachability ,Path (graph theory) ,Shortest path problem ,1705 Computer Networks and Communications ,Reachability queries ,2614 Theoretical Computer Science ,Dijkstra's algorithm ,Software ,Public transport networks ,Information Systems - Abstract
Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra’s algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution.
- Published
- 2022
48. Suitability Analysis of Routing Algorithms for Web-based Transportation Planning
- Author
-
Arnis Lektauers and Davis Jaunzems
- Subjects
Transportation planning ,Operations research ,Process (engineering) ,Computer science ,business.industry ,Policy-based routing ,Shortest path problem ,Information system ,Suitability analysis ,Web application ,Routing (electronic design automation) ,business ,Routing algorithms ,transportation planning ,web-based geographical information systems - Abstract
The routing of vehicles in complex urban or regional systems is a task that needs to be solved in numerous transportation-oriented applications. This paper describes the process and approaches used for routing algorithm analysis emphasizing transportation planning in interactive web-based planning, analysis and simulation solutions. The objectives of the presented research are to examine existing routing algorithms used for finding the shortest path between the nodes in transport networks and to analyse the implementation possibilities and efficiency of routing algorithms in web-based geographical information systems.
- Published
- 2021
49. Shortest Path Algorithm in Dynamic Restricted Area Based on Unidirectional Road Network Model
- Author
-
Xiaohui He, Haitao Wei, and Shusheng Zhang
- Subjects
Mathematical optimization ,Computer science ,02 engineering and technology ,Fast path ,lcsh:Chemical technology ,Biochemistry ,Article ,Analytical Chemistry ,statistical parameter ,0202 electrical engineering, electronic engineering, information engineering ,lcsh:TP1-1185 ,Motion planning ,Electrical and Electronic Engineering ,navigation ,Instrumentation ,path planning ,Network model ,restrict search area ,020206 networking & telecommunications ,Dijkstra algorithm ,Flow network ,Atomic and Molecular Physics, and Optics ,Path (graph theory) ,Shortest path problem ,unidirectional road network ,020201 artificial intelligence & image processing ,Routing (electronic design automation) ,Dijkstra's algorithm - Abstract
Accurate and fast path calculation is essential for applications such as vehicle navigation systems and transportation network routing. Although many shortest path algorithms for restricted search areas have been developed in the past ten years to speed up the efficiency of path query, the performance including the practicability still needs to be improved. To settle this problem, this paper proposes a new method of calculating statistical parameters based on a unidirectional road network model that is more in line with the real world and a path planning algorithm for dynamically restricted search areas that constructs virtual boundaries at a lower confidence level. We conducted a detailed experiment on the proposed algorithm with the real road network in Zhengzhou. As the experiment shows, compared with the existing algorithms, the proposed algorithm improves the search performance significantly in the condition of optimal path under the premise of ensuring the optimal path solution.
- Published
- 2021
50. Investigation on biomedical waste management of hospitals using cohort intelligence algorithm
- Author
-
Snehal Sagar Kolekar, Gagandeep Kaur, and Poorva Agrawal
- Subjects
0209 industrial biotechnology ,Route optimization ,Road accident ,Computer science ,Cohort intelligence ,Biomedical waste management ,Total travel distance ,Cohort Intelligence algorithm ,Biomedical waste ,02 engineering and technology ,Information technology ,QA75.5-76.95 ,T58.5-58.64 ,Field (computer science) ,Shortest time period ,020901 industrial engineering & automation ,Hazardous waste ,Electronic computers. Computer science ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Algorithm - Abstract
With the innovative development of advanced technology in the field of medical, there is an enlargement in the generation of other problems such as management of biomedical waste. Hazardous waste generated from hospitals is required to be managed within time and it can be done effectively using some computer science technology. In the proposed methodology, Biomedical Waste (BMW) problem is solved with the consideration of route optimization. Route optimization is important in BMW management because while transporting the BMW from hospital to depot (disposal site) there are many types of risks associated with that route like traffic, vehicle failure, road accident etc. To avoid the dangerous effects of BMW on humans and environment, it is necessary to optimize the distance. It can help in promoting healthy and risk free life. This paper addresses the problem of finding the shortest path using Cohort Intelligence algorithm for BMW management with the consideration of human risk.
- Published
- 2021
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.