The Experts below are selected from a list of 29244 Experts worldwide ranked by ideXlab platform
Jun Wang - One of the best experts on this subject based on the ideXlab platform.
-
A recurrent neural network for solving the Shortest Path Problem
IEEE Transactions on Circuits and Systems I-regular Papers, 1996Co-Authors: Jun WangAbstract:The Shortest Path Problem is the classical combinatorial optimization Problem arising in numerous planning and designing contexts. In this paper, a recurrent neural network for solving the Shortest Path Problem is presented. The recurrent neural network is able to generate optimal solutions to the Shortest Path Problem. The performance of the recurrent neural network is demonstrated by means of three illustrative examples. The recurrent neural network is shown to be capable of generating the Shortest Path and suitable for electronic implementation.
-
ISCAS - A recurrent neural network for solving the Shortest Path Problem
Proceedings of IEEE International Symposium on Circuits and Systems - ISCAS '94, 1994Co-Authors: Jun WangAbstract:The Shortest Path Problem is the classical combinatorial optimization Problem arising in numerous planning and designing contexts. In this paper, a recurrent neural network for solving the Shortest Path Problem is presented. The proposed recurrent neural network is able to generate optimal solutions to the Shortest Path Problem. The performance and operating characteristics of the recurrent neural network are demonstrated by use of illustrative examples. >
Stephen D Boyles - One of the best experts on this subject based on the ideXlab platform.
-
Multicriteria Stochastic Shortest Path Problem for Electric Vehicles
Networks and Spatial Economics, 2017Co-Authors: Ehsan Jafari, Stephen D BoylesAbstract:This paper formulates the reliable routing of electric vehicles in stochas-tic networks as a multicriteria Shortest Path Problem with travel time and charging cost components. The reliability term is defined as the probability of finishing the trip without running out of charge. The arc travel times are represented as stochastic variables, and arc energy consumption is modeled as a linear function of arc length and arc travel time. The traveler aims to minimize the generalized cost, formulated as a linear function of travel time and charging cost, subject to a minimum reliability threshold, representing the level of risk a traveler is willing to take in favor of routes with lower cost. We propose a solution algorithm based on generalized dynamic programming and show that the optimal solution may include cycles that visit at least one charging station. The properties of the proposed multicriteria Shortest Path Problem are mathematically proved. The simulation results on randomly-generated networks show that cyclic Paths are very rare, and that the generalized cost of travel is a monotone increasing function of minimum reliability threshold.
-
robust optimization strategy for the Shortest Path Problem under uncertain link travel cost distribution
Computer-aided Civil and Infrastructure Engineering, 2015Co-Authors: Mehrdad Shahabi, Avinash Unnikrishnan, Stephen D BoylesAbstract:This article showed how numerical experiments conducted on small to large networks compare the robust optimization-based strategy to the classical deterministic Shortest Path in terms of the uncertainty. A robust optimization approach for the Shortest Path Problem where travel cost is uncertain and exact information on the distribution function is unavailable is developed. The article showed that under such conditions the robust Shortest Path Problem can be formulated as a binary nonlinear integer program, which can then be reformulated as a mixed integer conic quadratic program. This article presented an outer approximation algorithm as a solution algorithm, which is shown to be highly efficient for this class of programs.
Ocan Sankur - One of the best experts on this subject based on the ideXlab platform.
-
variations on the stochastic Shortest Path Problem
Verification Model Checking and Abstract Interpretation, 2015Co-Authors: Mickael Randour, Jeanfrancois Raskin, Ocan SankurAbstract:In this invited contribution, we revisit the stochastic Shortest Path Problem, and show how recent results allow one to improve over the classical solutions: we present algorithms to synthesize strategies with multiple guarantees on the distribution of the length of Paths reaching a given target, rather than simply minimizing its expected value. The concepts and algorithms that we propose here are applications of more general results that have been obtained recently for Markov decision processes and that are described in a series of recent papers.
Ming Liu - One of the best experts on this subject based on the ideXlab platform.
-
ICRA - Using DP Towards A Shortest Path Problem-Related Application
2019 International Conference on Robotics and Automation (ICRA), 2019Co-Authors: Jianhao Jiao, Han Ma, Rui Fan, Ming LiuAbstract:The detection of curved lanes is still challenging for autonomous driving systems. Although current cutting-edge approaches have performed well in real applications, most of them are based on strict model assumptions. Similar to other visual recognition tasks, lane detection can be formulated as a two-dimensional graph searching Problem, which can be solved by finding several optimal Paths along with line segments and boundaries. In this paper, we present a directed graph model, in which dynamic programming is used to deal with a specific Shortest Path Problem. This model is particularly suitable to represent objects with long continuous shape structure, e.g., lanes and roads. We apply the designed model and proposed an algorithm for detecting lanes by formulating it as the Shortest Path Problem. To evaluate the performance of our proposed algorithm, we tested five sequences (including 1573 frames) from the KITTI database. The results showed that our method achieves an average successful detection precision of 97.5%.
-
Using DP Towards A Shortest Path Problem-Related Application
arXiv: Computer Vision and Pattern Recognition, 2019Co-Authors: Jianhao Jiao, Han Ma, Rui Fan, Ming LiuAbstract:The detection of curved lanes is still challenging for autonomous driving systems. Although current cutting-edge approaches have performed well in real applications, most of them are based on strict model assumptions. Similar to other visual recognition tasks, lane detection can be formulated as a two-dimensional graph searching Problem, which can be solved by finding several optimal Paths along with line segments and boundaries. In this paper, we present a directed graph model, in which dynamic programming is used to deal with a specific Shortest Path Problem. This model is particularly suitable to represent objects with long continuous shape structure, e.g., lanes and roads. We apply the designed model and proposed an algorithm for detecting lanes by formulating it as the Shortest Path Problem. To evaluate the performance of our proposed algorithm, we tested five sequences (including 1573 frames) from the KITTI database. The results showed that our method achieves an average successful detection precision of 97.5%.
Abdel Lisser - One of the best experts on this subject based on the ideXlab platform.
-
New reformulations of distributionally robust Shortest Path Problem.
Computers and Operations Research, 2016Co-Authors: Jianqiang Cheng, Janny Leung, Abdel LisserAbstract:This paper considers a stochastic version of the Shortest Path Problem, namely Distributionally Robust Stochastic Shortest Path Problem(DRSSPP) on directed graphs. In this model, each arc has a deterministic cost and a random delay. The mean vector and the second-moment matrix of the uncertain data are assumed to be known, but the exact information of the distribution is unknown. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the Path cost and the expected Path delay penalty. As this Problem is NP-hard, we propose new reformulations and approximations using a sequence of semidefinite programming Problems which provide tight lower bounds. Finally, numerical tests are conducted to illustrate the tightness of the bounds and the value of the proposed distributionally robust approach.
-
Maximum probability Shortest Path Problem
Discrete Applied Mathematics, 2015Co-Authors: Jianqiang Cheng, Abdel LisserAbstract:The maximum probability Shortest Path Problem involves the constrained Shortest Path Problem in a given graph where the arcs resources are independent normally distributed random variables. We maximize the probability that all resource constraints are jointly satisfied while the Path cost does not exceed a given threshold. We use a second-order cone programming approximation for solving the continuous relaxation Problem. In order to solve this stochastic combinatorial Problem, a branch-and-bound algorithm is proposed, and numerical examples on randomly generated instances are given.
-
Distributionally robust stochastic Shortest Path Problem
Electronic Notes in Discrete Mathematics, 2013Co-Authors: Jianqiang Cheng, Abdel Lisser, Marc LetournelAbstract:This paper considers a stochastic version of the Shortest Path Problem, the Distributionally Robust Stochastic Shortest Path Problem(DRSSPP) on directed graphs. In this model, the arc costs are deterministic, while each arc has a random delay. The mean vector and the second-moment matrix of the uncertain data are assumed known, but the exact information of the distribution is unknown. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the Path cost and the expected Path delay penalty. As it is NP-hard, we approximate the DRSSPP with a semidefinite programming (SDP for short) Problem, which is solvable in polynomial time and provides tight lower bounds.
-
ICORES - STOCHASTIC Shortest Path Problem WITH UNCERTAIN DELAYS
2012Co-Authors: Jianqiang Cheng, Stefanie Kosuch, Abdel LisserAbstract:This paper considers a stochastic version of the Shortest Path Problem, the Stochastic Shortest Path Problem with Delay Excess Penalty on directed, acyclic graphs. In this model, the arc costs are deterministic, while each arc has a random delay, assumed normally distributed. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the Path cost and the expected Path delay penalty. In order to solve the model, a Stochastic Projected Gradient method within a branch-and-bound framework is proposed and numerical examples are given to illustrate its effectiveness. We also show that, within given assumptions, the Stochastic Shortest Path Problem with Delay Excess Penalty can be reduced to the classic Shortest Path Problem.
-
Stochastic Shortest Path Problem with Delay Excess Penalty
Electronic Notes in Discrete Mathematics, 2010Co-Authors: Stefanie Kosuch, Abdel LisserAbstract:Abstract We study and solve a particular stochastic version of the Restricted Shortest Path Problem, the Stochastic Shortest Path Problem with Delay Excess Penalty. While arc costs are kept deterministic, arc delays are assumed to be normally distributed and a penalty per time unit occurs whenever the given delay constraint is not satisfied. The objective is to minimize the sum of Path cost and total delay penalty.
