Search

Seamline detection is one of the most important issues in mosaicking high-resolution remote sensing images (HRRSIs). However, it is difficult to make a balance between efficiency and accuracy. On that account, a shortest matrix path-based dynamic programming (SMP-DP) algorithm is proposed to find the optimal seamline for HRRSI mosaicking. First, a pixel cost matrix defined by intensity difference, gradient similarity, and geometric difference is constructed in the overlapping area. Second, the least average path cost from the starting pixel to each pixel is calculated and the SMP-DP algorithm is applied to find the optimal path. Experimental results on HRRSI prove that the proposed method detects high-quality seamline and crosses much fewer objects with the highest computational efficiency, compared with the state-of-the-art method and commercial software. [ABSTRACT FROM AUTHOR]

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

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]

From the more than two hundred partial orders for fuzzy numbers proposed in the literature, only a few are total. In this article, we introduce the notion of admissible order for fuzzy numbers equipped with a partial order, i.e., a total order which refines the partial order. In particular, it is given special attention to the partial order proposed by Klir and Yuan in 1995. Moreover, we propose a method to construct admissible orders on fuzzy numbers in terms of linear orders defined for intervals considering a strictly increasing upper dense sequence, proving that this order is admissible for a given partial order. Finally, we use admissible orders to ranking the path costs in fuzzy weighted graphs. [ABSTRACT FROM AUTHOR]

Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations. [ABSTRACT FROM AUTHOR]

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

The construction of low-cost nanogrids could help speed up the electrification rate in remote communities in sub-Saharan Africa. One of the challenges in nanogrid design for these communities is the uncertainty in future load demand profiles impacting the cabling topology. We propose two new wiring design approaches for radial direct current power distribution systems. The first one is a modified minimum spanning tree (MST) algorithm and the second one is an adaptive shuffled frog leaping algorithm (SFLA). Their objective is to identify the optimal cable path and the lowest cost wiring characteristics to electrify rural areas with poor infrastructural development. A comparative study of computation burdens has shown the applicability limits relative to the SFLA based approach and encouraged the implementation of the MST as it is faster and does not imply any limitation regarding the number of dwellings to electrify, while providing low-cost wiring design option. The latter is applied to a village located in Kenya and demonstrated more than 25% savings on the entire system cabling cost compared to a classical wiring design based on shortest-path calculation. [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]

The comparably low driving ranges of battery electric vehicles (BEV) cause time-consuming recharging stops if long distances have to be covered. Thus, navigation systems not only have to compute routes leading from the BEV’s current position to the destination, but also to plan recharging stops. This type of routing problem is often modeled as a constrained shortest path problem. The constraint ensures that the BEV does not run out of energy. In this paper, a de facto deterministic reformulation of this problem type is suggested, which allows handling uncertainty–particularly the risks resulting from imperfect energy consumption predictions. For this purpose, a certain part of the battery capacity is used as an energy buffer. Different approaches to dynamically optimize the size of this energy buffer in dependency of the expected level of uncertainty are proposed and a corresponding modification of a typical routing algorithm is described. Furthermore, a simulation study is conducted showing that the described framework allows keeping the probability to run out of energy close to zero (for the test settings: < 0.5%) as long as a suitable approach for defining the size of the energy buffer is applied. [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 shortest path problem (SPP) is considerably important in several fields. After typhoons, the resulting damage leads to uncertainty regarding the path weight that can be expressed accurately. A neutrosophic set is a collection of the truth membership, indeterminacy membership, and falsity membership degrees of the elements. In an uncertain environment, neutrosophic numbers can express the edge distance more effectively. Based on the theories of interval valued neutrosophy and neutrosophic graphs, this paper proposes a shortest path solution method of interval valued neutrosophic graphs using the ant colony algorithm. Further, an analysis comparing the proposed algorithm with the Dijkstra algorithm was used to probe the potential shortcomings and advantages of the proposed method. In addition, this approach confirmed the effectiveness of the proposed algorithm. Furthermore, we investigated the convergence processes of the ant colony algorithm with different parameter settings, analyzed their results, and used different score functions to solve the SPP and analyze the results.

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

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

In this paper, we study the feasibility of sending drones to deliver goods from a depot to a customer by solving what we call the Mission-Feasibility Problem (MFP). Due to payload constraints, the drone can serve only one customer at a time. To this end, we propose a novel framework based on time-dependent cost graphs to properly model the MFP and tackle the delivery dynamics. When the drone moves in the delivery area, the global wind may change thereby affecting the drone’s energy consumption, which in turn can increase or decrease. This issue is addressed by designing three algorithms, namely: (i) compute the route of minimum energy once, at the beginning of the mission, (ii) dynamically reconsider the most convenient trip towards the destination, and (iii) dynamically select only the best local choice. We evaluate the performance of our algorithms on both synthetic and real-world data. The changes in the drone’s energy consumption are reflected by changes in the cost of the edges of the graphs. The algorithms receive the new costs every time the drone flies over a new vertex, and they have no full knowledge in advance of the weights. We compare them in terms of the percentage of missions that are completed with success (the drone delivers the goods and comes back to the depot), with delivered (the drone delivers the goods but cannot come back to the depot), and with failure (the drone neither delivers the goods nor comes back to the depot). [ABSTRACT FROM AUTHOR]

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

This brief presents an inverse optimal control methodology and its application to training a predictive model of human motor control from a manipulation task. It introduces a convex formulation for learning both objective function and constraints of an infinite-horizon constrained optimal control problem with nonlinear system dynamics. The inverse approach utilizes Bellman’s principle of optimality to formulate the infinite-horizon optimal control problem as a shortest path problem and the Lagrange multipliers to identify constraints. We highlight the key benefit of using the shortest path formulation, i.e., the possibility of training the predictive model with short and selected trajectory segments. The method is applied to training a predictive model of movements of a human subject from a manipulation task. The study indicates that individual human movements can be predicted with low error using an infinite-horizon optimal control problem with constraints on the shoulder movement. [ABSTRACT FROM AUTHOR]

While battery electric vehicles (EVs) are on the advance, the broad customer basis is still concerned about battery electric range, a phenomenon commonly known as range anxiety. To tackle these concerns, the functionality of in-vehicle navigational systems must adapt to the new propulsion technology with a limited battery capacity. Central aim is to consider charging infrastructure in route planning. Furthermore, detailed powertrain models are required to accurately forecast an EV’s energy consumption. On the other hand, such detailed models are hardly applicable to large scale road networks that are usually handled by routing services for vehicle navigation. This study proposes a two-staged approach to compute time optimal routes for EVs. To this end, a reduced road network is obtained from a leading routing service. Subsequently, a detailed consumption model is applied and the resulting multiobjective shortest path problem is solved using an adapted Moore-Bellman-Ford algorithm. Within an experimental study, the consumption forecast is validated against measurement data and query times of the proposed methodology are assessed for generic routing problems. The former shows significant improvement of consumption forecast accuracy compared to state-of-the-art models while the latter indicates potential for application in car manufacturers vehicle backend services. [ABSTRACT FROM AUTHOR]

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]

In this paper, the traditional shortest path planning problem for vehicle is advanced to length-targeted path planning problem, i.e., to plan path with its length being as close to a specified value as possible. Lengthening and shortening of given initial paths are used to solve this problem. Based on an operation set consisting of three basic path homotopies, we build a comprehensive and systematic framework to plan paths with target length, which is a generalization of the existing related studies. Thereby, the expected paths can be independently searched through such deformation processes within topological classes. The proposed framework can produce the largest length coverage in different scenarios and under different conditions, and it can also generate expected paths with arbitrary topological classification in terms of the curvature constraint and the obstacle constraint. Examples show that our lengthening and shortening method can effectively solve the length-targeted path planning problem in environment without or with obstacles. Note to Practitioners—This paper presents a curvature-bounded lengthening and shortening approach for path planning of vehicles. The curvature and obstacle constraints in the path planning problem are handled using the topological technique. In addition, a rigorous classification system is presented to systematically categorize the potential paths. Within a path class, any path can be deformed to other paths while keeping the curvature bounded. Then, the path deformation process is conducted via a series of basic homotopy operations to approach the target length. The length coverage range of this process is reduced when some endpoint conditions are meet or the vehicle is trapped into a closed region. [ABSTRACT FROM AUTHOR]

Virtual network services that span multiple data centers are important to support emerging data-intensive applications in fields such as bioinformatics and retail analytics. Successful virtual network service composition and maintenance requires flexible and scalable “constrained shortest path management” both in the management plane for virtual network embedding (VNE) or network function virtualization service chaining (NFV-SC), as well as in the data plane for traffic engineering (TE). In this paper, we show analytically and empirically that leveraging constrained shortest paths within recent VNE, NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%) and higher energy efficiency. The management of complex VNE, NFV-SC and TE algorithms can be, however, intractable for large scale substrate networks due to the NP-hardness of the constrained shortest path problem. To address such scalability challenges, we propose a novel, exact constrained shortest path algorithm viz., neighborhoods method (NM). Our NM uses novel search space reduction techniques and has a theoretical quadratic speed-up making it practically faster (by an order of magnitude) than recent branch-and-bound exhaustive search solutions. Finally, we detail our NM-based SDN controller implementation in a real-world testbed to further validate practical NM benefits for virtual network services. [ABSTRACT FROM AUTHOR]

Complex and interconnected systems belonging to biological, social, economic, and technology application fields are generally described through scale-free topology models. In this context, it is essential to characterize the distribution of shortest paths in order to obtain precious insights on the network behavior. Unfortunately, the few contributions available in the current scientific literature require a case-by-case tuning of model parameters. To bridge this gap, novel Gaussian-based models are proposed hereby, whose parameters can be immediately tuned based on the number of nodes ($N$) composing the network, only. In this way, given $N$ , it becomes possible to predict the distribution of shortest paths without retuning the model for each scenario of interest. The outcomes of the proposed models have been successfully validated and compared with respect to state-of-the-art approaches in a wide set of network topologies. To provide a further insight, the conceived Gaussian-based models have been also evaluated for real Internet topologies, learned from reference data sets. Obtained results highlight that the proposed models are able to reach a good tradeoff between the level of accuracy and complexity, even for real network configurations. [ABSTRACT FROM AUTHOR]

Finding a shortest feasible path between two given locations is a common problem in many real-world applications. Previous studies have shown that mobile platforms would consume excessive energy when moving along shortest paths on uneven terrains, which often consist of rapid elevation changes. Mobile platforms powered by portable energy sources may fail to follow such paths due to the limited energy available. This paper proposes a new heuristic search algorithm called constraints satisfying A* (CSA*) to find solutions to such resource constrained shortest path problems. When CSA* is guided by admissible heuristics, it guarantees to find a globally optimal solution to a given constrained search problem if such a solution exists. When CSA* is guided by consistent heuristics, it is optimally efficient over a class of equally informed admissible constrained search algorithms with respect to the set of paths expanded. Test results obtained using real terrain data verify the applicability of the proposed algorithm in shortest path planning for energy-constrained mobile platforms on uneven terrains. [ABSTRACT FROM AUTHOR]

Tracking control of robot manipulators is a fundamental and significant problem in robotic industry. As a conventional solution, the Jacobian-matrix-pseudo-inverse (JMPI) method suffers from two major limitations: one is the requirement on known information of the robot model such as parameter and structure; the other is the position error accumulation phenomenon caused by the open-loop nature. To overcome such two limitations, this paper proposes a novel Jacobian-matrix-adaption (JMA) method for the tracking control of robot manipulators via the zeroing dynamics. Unlike existing works requiring the information of the known robot model, the proposed JMA method uses only the input-output information to control the robot with unknown model. The solution based on the JMA method transforms the internal, implicit, and unmeasurable model information to the external, explicit, and measurable input-output information. Moreover, simulation studies including comparisons and tests substantiate the efficacy and superiority of the proposed JMA method for the tracking control of robot manipulators subject to unknown models. [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]

Routing service considering uncertainty is at the core of intelligent transportation systems and has attracted increasing attention. Existing stochastic shortest path models require the exact probability distributions of travel times and usually assume that they are independent. However, the distributions are often unavailable or inaccurate due to insufficient data, and correlation of travel times over different links has been observed. This paper presents a robust shortest path (RSP) model that only requires partial distribution information of travel times, including the support set, mean, variance, and correlation matrix. We introduce a concept of robust mean-excess travel time to hedge against the risk from both the uncertainty of the random travel times and the uncertainty in their distributions. To solve the RSP problem, an equivalent dual formulation is derived and used to design tight lower and upper bound approximation methods, which adopt the scenario approach and semi-definite programming approach, respectively. To solve large problems, we further propose an efficient primal approximation method, which only needs to solve two deterministic shortest path problems and a mean-standard deviation shortest path problem, and analyze its approximation performance. Experiments validate the tightness of the proposed bounds and demonstrate the impact of uncertainty on the relative benefit and cost of robust paths. [ABSTRACT FROM PUBLISHER]

In some micro grids, the charging of electric vehicles (EVs) and the generation of wind power may partially cancel each other. This is an effective way to reduce the variation of the wind power to the state grid. Due to the forecasting error, it is of great practical interest to schedule the EV charging demand under the worst-case scenario of the wind power generation. We consider this important robust scheduling problem in this paper and make three major contributions. First, we formulate this robust scheduling problem as a robust stochastic shortest path problem whereby the objective function is a weighted sum of the wind power utilization and the total charging cost. Second, a robust simulation-based policy improvement method is developed to improve the performance of a base policy in the worst case. This improvement is mathematically shown under mild assumptions. Third, the performance of this method is numerically demonstrated based on real wind and EV data. [ABSTRACT FROM PUBLISHER]

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]

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]

The uncertainty of travel times on a time-dependent network is conventionally considered as randomness or fuzziness. However, sometimes, randomness or fuzziness cannot describe the uncertainty of the travel times on the time-dependent network. In this paper, we introduce a random fuzzy time-dependent network (RFTDN), in which travel times of a time-dependent network are represented as mixed uncertainty of randomness and fuzziness. With these conditions, the resulting RFTDN is far more complex when compared with the known networks. The complexity stems from estimating the length of a path, which is a basic and core issue when analyzing a network. To address this problem, we propose an optimized method that is suitable to cope with the shortest path problem of the RFTDN. The proposed method is realized by means of random fuzzy simulation and a new repair-based genetic optimization. Random fuzzy simulation is used to estimate the random fuzzy functions that describe the length of arcs, whereas the repair-based genetic algorithm is presented for finding the shortest path on the network. Furthermore, the proposed repair-based genetic operators are demonstrated their effectiveness by analyzing running time. A numerical example is also provided to show the robustness of the proposed approach. [ABSTRACT FROM PUBLISHER]