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]

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]

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]

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]

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]

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]

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]

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric. [ABSTRACT FROM AUTHOR]

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time. [ABSTRACT FROM AUTHOR]

Dynamic routing is desirable because of its substantial improvement in communication bandwidth and intelligent adaptation to faulty links and congested traffic. However, implementation of adaptive routing in a network-on-chip system is not trivial and is further complicated by the requirements of deadlock-free and real-time optimal decision making. In this paper, we present a deadlock-free routing architecture which employs a dynamic programming (DP) network to provide on-the-fly optimal path planning and network monitoring for packet switching. Also, a new routing strategy called k-step look ahead is introduced. This new strategy can substantially reduce the size of routing table and maintain a high quality of adaptation which leads to a scalable dynamic-routing solution with minimal hardware overhead. Our results, based on a cycle-accurate simulator, demonstrate the effectiveness of the DP network, which outperforms both the deterministic and adaptive-routing algorithms in average delay on various traffic scenarios by 22.3%. Moreover, the hardware overhead for DP network is insignificant, based on the results obtained from the hardware implementations. [ABSTRACT FROM PUBLISHER]

Satellites are currently being used to track the positions of trains. Positioning systems using satellites can help reduce the cost of installing and maintaining trackside equipment. This paper develops a nonlinear combinatorial data reduction model for a large amount of railway Global Positioning System (GPS) data to decrease the memory space and, thus, speed up train positioning. Three algorithms are proposed by employing the concept of looking ahead, using the dichotomy idea, or adopting the breadth-first strategy after changing the problem into a shortest path problem to obtain an optimal solution. Two techniques are developed to substantially cut down the computing time for the optimal algorithm. The surveyed GPS data of the Qinghai–Tibet railway (QTR) are used to compare the performance of the algorithms. Results show that the algorithms can extract a few data points from the large amount of GPS data points, thus enabling a simpler representation of the train tracks. Furthermore, these proposed algorithms show a tradeoff between the solution quality and computation time of the algorithms. [ABSTRACT FROM PUBLISHER]