Search

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]

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]

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

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

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

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

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

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

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

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

This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in a variety of contexts, including ship, helicopter, or unmanned aerial vehicle routing. The tool provides recommended schedules, consisting of waypoints, associated arrival and departure times, asset speed and bearing, that are optimized with respect to several objectives. The ship navigation is exacerbated by the need to address multiple conflicting objectives, spatial and temporal uncertainty associated with the weather, multiple constraints on asset operation, and the added capability of waiting at a waypoint with the intent to avoid bad weather, conduct opportunistic training drills, or both. The key algorithmic contribution is a multiobjective shortest path algorithm for networks with stochastic nonconvex edge costs and the following problem features: 1) time windows on nodes; 2) ability to choose vessel speed to next node subject to (minimum and/or maximum) speed constraints; 3) ability to select the power plant configuration at each node; and 4) ability to wait at a node. The algorithm is demonstrated on six real world routing scenarios by comparing its performance against an existing operational routing algorithm. [ABSTRACT FROM AUTHOR]

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

The shortest path problems (SPPs) with learning effects (SPLEs) have many potential and interesting applications. However, at the same time they are very complex and have not been studied much in the literature. In this paper, we show that learning effects make SPLEs completely different from SPPs. An adapted A* (AA*) is proposed for the SPLE problem under study. Though global optimality implies local optimality in SPPs, it is not the case for SPLEs. As all subpaths of potential shortest solution paths need to be stored during the search process, a search graph is adopted by AA* rather than a search tree used by A*. Admissibility of AA* is proven. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated. [ABSTRACT FROM AUTHOR]

Objective: We propose an effective automatic method for identification of four retinal layer boundaries from the spectral domain optical coherence tomography images in the presence and absence of pathologies and morphological changes due to disease. Methods: The approach first finds an approximate location of three reference layers and then uses these to bound the search space for the actual layers, which is achieved by modeling the problem as a graph and applying Dijkstra's shortest path algorithm. The edge weight between nodes is determined using pixel distance, slope similarity to a reference, and nonassociativity of the layers, which is designed to overcome the distorting effects that pathology can play in the boundary determination. Results: The accuracy of our method was evaluated on three different datasets. It outperforms the current five state-of-the-art methods. On average, the mean and standard deviation of the root-mean-square error in the form of mean $\pm$ standard deviation in pixels for our method is 1.57 $\pm$ 0.69, which is lower than compared to the existing top five methods of 16.17 $\pm$ 22.64, 6.66 $\pm$ 9.11, 5.70 $\pm$ 10.54, 3.69 $\pm$ 2.04, and 2.29 $\pm$ 1.54. Conclusion: Our method is highly accurate, robust, reliable, and consistent. This identification can enable to quantify the biomarkers of the retina in large-scale study for assessing, monitoring disease progression, as well as early detection of retinal diseases. Significance: Identification of these boundaries can help to determine the loss of neuroretinal cells or layers and the presence of retinal pathology, which can be used as features for the automatic determination of the stages of retinal diseases. [ABSTRACT FROM AUTHOR]

Network routing problems are often modeled with the assumption that the network structure is deterministic, though they are often subject to uncertainty in many real-life scenarios. In this paper, we study the traveling salesman and the shortest path problems with uncertain topologies modeled by arc failures. We present the formulations that incorporate chance constraints to ensure reliability of the selected route considering all arc failure scenarios. Due to the computational complexity and large scales of these stochastic network optimization problems, we consider two cutting plane methods and a Benders decomposition algorithm to respectively solve them. We also consider to solve the reformulations of the problems obtained by taking the logarithm transformation of the chance constraints. Numerical experiments are performed to obtain results for comparisons among these proposed methods. [ABSTRACT FROM AUTHOR]

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

The goal of meta-heuristic algorithms such as genetic algorithm is to explore the search space of the combinatorial optimization problems efficiently to locate the optimal solutions, the feasible solutions with the best output values. However, typical meta-heuristic algorithms implicitly assume that the feasible solutions for the given problems can be generated easily, and they can fail to solve the problems with rare feasible solutions in effective manner. In this context, this paper aims to introduce the maze-type shortest path problem as an example of the combinatorial optimization problem with rare feasible solutions and to propose the fitness switching genetic algorithm for solving it. The maze-type shortest path problem is characterized by the maze-type network that contains many dead-ends, and the conventional genetic algorithms based on the population of feasible paths are not appropriate for finding the optimal path in such networks. On the contrary, this paper introduces the fitness switching and fitness leveling operations for maintaining the population of both feasible and infeasible paths during the search procedure. In addition, the infeasible paths are randomly modified by the simple local search of the proposed algorithm to find the feasible paths more quickly. The experiment results show that the proposed algorithm can address the issues in the combinatorial optimization problems with rare feasible solutions very effectively. [ABSTRACT FROM AUTHOR]

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

We present the first asymptotically optimal feedback planning algorithm for nonholonomic systems and additive cost functionals. Our algorithm is based on three well-established numerical practices: 1) positive coefficient numerical approximations of the Hamilton-Jacobi-Bellman equations; 2) the Fast Marching Method, which is a fast nonlinear solver that utilizes Bellman’s dynamic programming principle for efficient computations; and 3) an adaptive mesh-refinement algorithm designed to improve the resolution of an initial simplicial mesh and reduce the solution numerical error. By refining the discretization mesh globally, we compute a sequence of numerical solutions that converges to the true viscosity solution of the Hamilton-Jacobi-Bellman equations. In order to reduce the total computational cost of the proposed planning algorithm, we find that it is sufficient to refine the discretization within a small region in the vicinity of the optimal trajectory. Numerical experiments confirm our theoretical findings and establish that our algorithm outperforms previous asymptotically optimal planning algorithms, such as PRM* and RRT*. [ABSTRACT FROM AUTHOR]

This paper presents a column generation algorithm for solving combined vehicle and inventory problems. This problem is based on the idea of coordinating customer inventory levels through a minimum routing cost. This is a combinatory decision problem since vehicle routing and inventory problems, are combined. Using the column generation method, we can iteratively generate interesting routes to the system, based on their dual costs, this is routes that will improve the quality of the objective function because its reduced costs are negatives. The initial mixed integer problem has to be relaxed for getting its reduced costs. The sub problem is defined as the shortest path problem that returns a set of desirable routes. Finally, when the set of desirable routes is obtained, the mixed integer model should select a set of routes that fulfill both minimum shipping costs and the constraints of the system. [ABSTRACT FROM AUTHOR]

The elementary shortest path problem with resource constraints (ESPPRC) is an NP-hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state-of-the-art algorithms for the ESPPRC on the well-known Solomon's test bed for the VRPTW. [ABSTRACT FROM AUTHOR]

This paper describes a new method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our method uses line graphs to find the optimal path on a given discretization, often in the order of seconds on a single computer. The curves are then refined using local optimization making it possible to recover very smooth curves. We are able to place constraints on our curves such as maximum integrated curvature, or a maximum curvature at any point of the curve. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have over a hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of higher order regularization. [ABSTRACT FROM PUBLISHER]

Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph D and an undirected graph G on the same vertex set, and the sought pattern is a path P in D whose vertex set induces a connected subgraph of G. In this context, three concrete problems arise, depending on whether the existence of P is questioned or whether the length of P is to be optimized: in that case, one can search for a longest path or (maybe less intuitively) a shortest one. These problems have immediate applications in biological networks and predictable applications in social, information and communication networks. We study the classic and parameterized complexity of the problem, thus identifying polynomial and NP-complete cases, as well as fixed-parameter tractable and W[1]-hard cases. We also propose two enumeration algorithms that we evaluate on synthetic and biological data. [ABSTRACT FROM AUTHOR]

This paper introduces a new variant of the Shortest Path Problem ( S P P ) called the Cost-Balanced Path Problem ( C B P P ). Various real problems can either be modeled as B C P P or include B C P P as a sub-problem. We prove several properties related to the complexity of the C B P P 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 C B P P , 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. [ABSTRACT FROM AUTHOR]

This paper addresses a scheduling problem in a flexible supply chain, in which the jobs can be either processed in house, or outsourced to a third-party supplier. The goal is to minimize the sum of holding and delivery costs. This problem is proved to be strongly $\mathcal{NP}$-hard. Consider two special cases, in which the jobs have identical processing times. For the problem with limited outsourcing budgets, a $\mathcal{NP}$-hardness proof, a pseudo-polynomial algorithm and a fully polynomial time approximation scheme are presented. For the problem with unlimited outsourcing budgets, the problem is shown to be equivalent to the shortest path problem, and therefore it is in class $\mathcal{P}$. This shortest-path-problem solution approach is further shown to be applicable to a similar but more applicable problem, in which the number of deliveries is upper bounded. [ABSTRACT FROM AUTHOR]

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

The present paper focuses on the development of an algorithm for safely and optimally managing the routing of aircraft on an airport surface in future airport operations. This tool is intended to support air traffic controllers' decision-making in selecting the paths of all aircraft and the engine startup approval time for departing ones. Optimal routes are sought for minimizing the time both arriving and departing aircraft spend on an airport surface with engines on, with benefits in terms of safety, efficiency and costs. The proposed algorithm first computes a standalone, shortest path solution from runway to apron or vice versa, depending on the aircraft being inbound or outbound, respectively. For taking into account the constraints due to other traffic on an airport surface, this solution is amended by a conflict detection and resolution task that attempts to reduce and possibly nullify the number of conflicts generated in the first phase. An example application on a simple Italian airport exemplifies how the algorithm can be applied to true-world applications. Emphasis is given on how to model an airport surface as a weighted and directed graph with non-negative weights, as required for the input to the algorithm. [ABSTRACT FROM AUTHOR]

In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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

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

In this study, we introduce a Fuzzy Time-Dependent Network (FTDN) and analyze its shortest path problem. The FTDN is a network in which travel times are represented as fuzzy sets and are also time-dependent. Under these circumstances, the shortest path problem on the FTDN is far more complex in comparison with the shortest path problem on the existing networks. To highlight the complexity, we show that on the FTDN, "standard" shortest path algorithms (e.g., the well-known Dijkstra algorithm) are not able to come up with solutions. Subsequently, we construct a suitable method which is suitable to deal with the shortest problem. A fuzzy programming model is presented for finding the shortest path on the FTDN. The proposed model is handled through the techniques which combine mechanisms of fuzzy simulation and genetic optimization. In this particular setting, fuzzy simulation is exploited to estimate the value of uncertain functions, which do not exist in the general networks. The proposed model is evaluated with the use of numerical experimentation. A comparative analysis demonstrates that the proposed model leads to the shortest path while standard algorithms are not capable of finding the path when dealing with the shortest path problem on the FTDN. [ABSTRACT FROM AUTHOR]

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

Motion planning for mobile vehicles involves the solution of two disparate subproblems: the satisfaction of high-level logical task specifications and the design of low-level vehicle control laws. A hierarchical solution of these two subproblems is efficient, but it may not ensure compatibility between the high-level planner and the constraints that are imposed by the vehicle dynamics. To guarantee such compatibility, we propose a motion-planning framework that is based on a special interaction between these two levels of planning. In particular, we solve a special shortest path problem on a graph at a higher level of planning, and we use a lower level planner to determine the costs of the paths in that graph. The overall approach hinges on two novel ingredients: a graph-search algorithm that operates on sequences of vertices and a lower level planner that ensures consistency between the two levels of hierarchy by providing meaningful costs for the edge transitions of a higher level planner using dynamically feasible, collision-free trajectories. [ABSTRACT FROM PUBLISHER]

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