Search

In the multimodal transport network, due to various uncertain factors such as weather and traffic conditions, the transport time will become uncertain accordingly, besides, railway transport and water transport are usually limited by timetable. These factors will inevitably affect the path selection. The purpose of this study is to seek an optimal transport scheme that considers both the uncertainty of the multimodal transport network and the timetable limit. In view of the uncertainties of the multimodal transport network, interval data are used to represent the uncertainty of network weights, and robust optimization method is then adopted to process the interval data. An optimal model of robust shortest path considering timetable limit is established and genetic algorithm (GA) is designed to solve the problem. The GA designed provides an encoding method for variable-length chromosomes applicable to shortest path problem solving in the multimodal transport. And the handling methods for loops and inaccessible paths due to chromosome crossover and mutation are also suggested. And finally, numerical examples are provided to verify the validity of the model and algorithm.

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.

As a novel computational paradigm, Physarum solver has received increasing attention from the researchers in tackling a plethora of network optimization problems. However, the convergence of Physarum solver is grounded by solving a system of linear equations iteratively, which often leads to low computational performance. Two factors have been highlighted along the process: 1) high time complexity in solving the system of linear equations and 2) extensive iterations required for convergence. Thus, Physarum solver has been largely restricted by its unsatisfactory computational performance. In this paper, we aim to address these two issues by developing two enhancement strategies: 1) pruning inactive nodes and 2) terminating Physarum solver in advance. First, extensive nodes and edges become and stay inactive after a few iterations in identifying the shortest path. Removing these inactive nodes and edges significantly decreases the graph size, thereby reducing computational complexity. Second, we define a transition phase for edges. All of the paths experiencing such a transition phase are dynamically aggregated to form a set of near-optimal paths among which the optimal path is included. Depth-first search is then leveraged to identify the optimal path from the near-optimal paths set. Earlier termination of Physarum solver saves considerable iterations while guaranteeing the optimality of the found solution. Empirically, 20 randomly generated sparse and complete graphs with network sizes ranging from 50 to 2000 as well as two real-world traffic networks are used to compare the performance of accelerated Physarum solver to the other two state-of-the-art algorithms. [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]

Current inflating high cost of living may affect mobility of students to commute between their university and any other destination. In an attempt to help solve or minimise the problem, several proposed travel alternative modes from this research may help students to identify the shortest path and minimum cost path in a journey. In finding the minimum total travel cost and shortest total completion time for a journey between two destinations, the step-by-step Dijkstra algorithm was applied in the time-dependent shortest path problem (TDSPP) and cost-dependent shortest path problem (CDSPP) in this research. Interestingly, both problems treated separately mapped out two different paths with two different costs. The former mapped out a route from UiTM Perlis Branch to Arau by taxi, train from Arau to Alor Setar, and Malaysia Airlines flights from Alor Setar to Kuala Lumpur and on to Johor Bahru. The other route was best described by taxi from Arau to Alor Setar, Air Asia flight from Alor Setar to Kuala Lumpur and train from Kuala Lumpur to Johor Bahru.

The article deals with the problem of analysis of effectiveness of the heuristic methods with limited depth-first search techniques of decision obtaining in the test problem of getting the shortest path in graph. The article briefly describes the group of methods based on the limit of branches number of the combinatorial search tree and limit of analyzed subtree depth used to solve the problem. The methodology of comparing experimental data for the estimation of the quality of solutions based on the performing of computational experiments with samples of graphs with pseudo-random structure and selected vertices and arcs number using the BOINC platform is considered. It also shows description of obtained experimental results which allow to identify the areas of the preferable usage of selected subset of heuristic methods depending on the size of the problem and power of constraints. It is shown that the considered pair of methods is ineffective in the selected problem and significantly inferior to the quality of solutions that are provided by ant colony optimization method and its modification with combinatorial returns.

In the last decade, concealed by uncertain atmosphere, many algorithms have been studied deeply to workout the shortest path problem. In this paper, we compared the shortest path problem with various existing algorithms. Finally, we concluded the best algorithm for certain environment. [ABSTRACT FROM AUTHOR]

An elongation of the single-valued neutrosophic set is an interval-valued neutrosophic set. It has been demonstrated to deal indeterminacy in a decision-making problem. Real-world problems have some kind of uncertainty in nature and among them; one of the influential problems is solving the shortest path problem (SPP) in interconnections. In this contribution, we consider SPP through Bellman's algorithm for a network using interval-valued neutrosophic numbers (IVNNs). We proposed a novel algorithm to obtain the neutrosophic shortest path between each pair of nodes. Length of all the edges is accredited an IVNN. Moreover, for the validation of the proposed algorithm, a numerical example has been offered. Also, a comparative analysis has been done with the existing methods which exhibit the advantages of the new algorithm. [ABSTRACT FROM AUTHOR]

There is a growing market for electric vehicles (EVs) in recent years. Due to this, many studies on electric vehicles are in progress and research on charging operations for EVs are especially active. Recent research trends on electric vehicle routes rely on the stochastic modelling of various factors such as convenience of a user's point of view, charging station (CS), location, destination, and so on. In this paper, a charging control scheme for electric vehicles is proposed from the point of view of the system operators rather than the user. From a user's point of view, the EV route can be set up directly, but it is difficult for the system operator to directly participate in the route of the EV. In this paper, a method is proposed to indirectly change the route of the EV by changing the charging cost through real-time dynamic pricing, in order to prevent risks in the system operation due to voltage fluctuations in the system. With dynamic pricing, the voltage of the system is kept within a stable range, and the EV user sets the route with an economic benefit. The proposed scheme is verified through Dijkstra's algorithm and a control strategy via a simulation model using MATLAB. [ABSTRACT FROM AUTHOR]

Given a network G(V,A,c) and a collection of origin-destination pairs with prescribed values, the reverse shortest path problem is to modify the arc length vector c as little as possible under some bound constraints such that the shortest distance between each origin-destination pair is upper bounded by the corresponding prescribed value. It is known that the reverse shortest path problem is NP-hard even on trees when the arc length modifications are measured by the weighted sum-type Hamming distance. In this paper, we consider two special cases of this problem which are polynomially solvable. The first is the case with uniform lengths. It is shown that this case transforms to a minimum cost flow problem on an auxiliary network. An efficient algorithm is also proposed for solving this case under the unit sum-type Hamming distance. The second case considered is the problem without bound constraints. It is shown that this case is reduced to a minimum cut problem on a tree-like network. Therefore, both cases studied can be solved in strongly polynomial time.

The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are widely desired. This holds in particular for the traveling salesman problem, which is a corner stone of logistic planning. In this paper, we devise column-generation-based IP methods to solve the TDTSP in full generality, both for arc- and path-based formulations. The algorithmic key is a time-dependent shortest path problem, which arises from the pricing problem of the column generation and is of independent interest—namely, to find paths in a time-expanded graph that are acyclic in the underlying (non-expanded) graph. As this problem is computationally too costly, we price over the set of paths that contain no cycles of length k. In addition, we devise—tailored for the TDTSP—several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide—to our knowledge—the first elaborate method to solve the TDTSP in general and with fully general time-dependence. We also provide for results on complexity and approximability of the TDTSP. In computational experiments on randomly generated instances, we are able to solve the large majority of small instances (20 nodes) to optimality, while closing about two thirds of the remaining gap of the large instances (40 nodes) after one hour of computation.

Pythagorean fuzzy set as an extension of fuzzy set has been presented to handle the uncertainty in real-world decision-making problems. In this work, we formulate a shortest path (SP) problem in an interval-valued Pythagorean fuzzy environment. Here, the costs related to arcs are taken in the form of interval-valued Pythagorean fuzzy numbers (IVPFNs). The main contributions of this paper are fourfold: (1) the interval-valued Pythagorean fuzzy optimality conditions in directed networks are described to design of solution algorithm. (2) To do this, an improved score function is used to compare the costs between different paths with their arc costs represented by IVPFNs. (3) Based on these optimality conditions and the improved score function, the traditional Dijkstra algorithm is extended to find the cost of interval-valued Pythagorean fuzzy SP (IVPFSP) and corresponding IVPFSP. (4) Finally, a small sized telecommunication network is provided to illustrate the potential application of the proposed method. [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]

In the multimodal transport network, due to various uncertain factors such as weather and traffic conditions, the transport time will become uncertain accordingly, besides, railway transport and water transport are usually limited by timetable. These factors will inevitably affect the path selection. The purpose of this study is to seek an optimal transport scheme that considers both the uncertainty of the multimodal transport network and the timetable limit. In view of the uncertainties of the multimodal transport network, interval data are used to represent the uncertainty of network weights, and robust optimization method is then adopted to process the interval data. An optimal model of robust shortest path considering timetable limit is established and genetic algorithm (GA) is designed to solve the problem. The GA designed provides an encoding method for variable-length chromosomes applicable to shortest path problem solving in the multimodal transport. And the handling methods for loops and inaccessible paths due to chromosome crossover and mutation are also suggested. And finally, numerical examples are provided to verify the validity of the model and algorithm. [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]

Understanding the criteria that bicyclists apply when they choose their routes is crucial for planning new bicycle paths or recommending routes to bicyclists. This is becoming more and more important as city councils are becoming increasingly aware of limitations of the transport infrastructure and problems related to automobile traffic. Since different groups of cyclists have different preferences, however, searching for a single set of criteria is prone to failure. Therefore, in this paper, we present a new approach to classify trajectories recorded and shared by bicyclists into different groups and, for each group, to identify favored and unfavored road types. Based on these results we show how to assign weights to the edges of a graph representing the road network such that minimumweight paths in the graph, which can be computed with standard shortest-path algorithms, correspond to adequate routes. Our method combines known algorithms for machine learning and the analysis of trajectories in an innovative way and, thereby, constitutes a new comprehensive solution for the problem of deriving routing preferences from initially unclassified trajectories. An important property of our method is that it yields reasonable results even if the given set of trajectories is sparse in the sense that it does not cover all segments of the cycle network. [ABSTRACT FROM AUTHOR]

Robot navigation is still an open research topic, mainly regarding applications that require online planning. In this context, this manuscript presents an implementation of the Lifelong Planning A* (LPA*) search algorithm to guide a mobile robot in an environment that changes along time, by detecting obstacles and updating the current mapping information. Firstly, simulations validate the strategy, and later experiments confirm these results considering a real application. The result is that the LPA* algorithm is able to guide the mobile robot to its target in a changing environment. Obstacles are interactively included in the scene to force the route redesign and the seeking for a new optimal solution connecting the current robot position and its target position.

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.

The shortest path problem is a topic of increasing interest in various scientific fields. The damage to roads and bridges caused by disasters makes traffic routes that can be accurately expressed become indeterminate. A neutrosophic set is a collection of the truth membership, indeterminacy membership, and falsity membership of the constituent elements. It has a symmetric form and indeterminacy membership is their axis of symmetry. In uncertain environments, the neutrosophic number can more effectively express the edge distance. The objectives in this study are to solve the shortest path problem of the neutrosophic graph with an edge distance expressed using trapezoidal fuzzy neutrosophic numbers (TrFNN) and resolve the edge distance according to the score and exact functions based on the TrFNN. Accordingly, the use of a circle-breaking algorithm is proposed to solve the shortest path problem and estimate the shortest distance. The feasibility of this method is verified based on two examples, and the rationality and effectiveness of the approach are evaluated by comparing it with the Dijkstra and Bellman algorithms.

In the first part of the review, we observed that there exists a significant gap between the predictive and prescriptive models pertaining to crash risk prediction and minimization, respectively. In this part, we review and categorize the optimization/ prescriptive analytic models that focus on minimizing crash risk. Although the majority of works in this segment of the literature are related to the hazardous materials (hazmat) trucking problems, we show that (with some exceptions) many can also be utilized in non-hazmat scenarios. In an effort to highlight the effect of crash risk prediction model on the accumulated risk obtained from the prescriptive model, we present a simulated example where we utilize four risk indicators (obtained from logistic regression, Poisson regression, XGBoost, and neural network) in the k-shortest path algorithm. From our example, we demonstrate two major designed takeaways: (a) the shortest path may not always result in the lowest crash risk, and (b) a similarity in overall predictive performance may not always translate to similar outcomes from the prescriptive models. Based on the review and example, we highlight several avenues for future research.

There is a growing market for electric vehicles (EVs) in recent years. Due to this, many studies on electric vehicles are in progress and research on charging operations for EVs are especially active. Recent research trends on electric vehicle routes rely on the stochastic modelling of various factors such as convenience of a user’s point of view, charging station (CS), location, destination, and so on. In this paper, a charging control scheme for electric vehicles is proposed from the point of view of the system operators rather than the user. From a user’s point of view, the EV route can be set up directly, but it is difficult for the system operator to directly participate in the route of the EV. In this paper, a method is proposed to indirectly change the route of the EV by changing the charging cost through real-time dynamic pricing, in order to prevent risks in the system operation due to voltage fluctuations in the system. With dynamic pricing, the voltage of the system is kept within a stable range, and the EV user sets the route with an economic benefit. The proposed scheme is verified through Dijkstra’s algorithm and a control strategy via a simulation model using MATLAB.

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

To find the shortest path between the nodes of a graph, different algorithms like Bellman-Ford, Dijkstra, Floyd-Warshall and Johnson exist. However, in this paper, the issue of shortest path problem with special reference to Dijkstra's algorithm is presented. An idea of shortlisting the appropriate nodes in a graph is proposed and presented, which is then used to find the shortest path with the help of Dijkstra's algorithm. This complete work - named Capton algorithm-provides a solution to single source shortest path problem with minimized time complexity as compared to Dijkstra's algorithm. [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]

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

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

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]