首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 9 毫秒
1.
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.  相似文献   

2.
We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications. We present tree search algorithms for the exact solution of the VRP incorporating lower bounds computed from (i) shortest spanningk-degree centre tree (k-DCT), and (ii)q-routes. The final algorithms also include problem reduction and dominance tests. Computational results are presented for a number of problems derived from the literature. The results show that the bounds derived from theq-routes are superior to those fromk-DCT and that VRPs of up to about 25 customers can be solved exactly.  相似文献   

3.
We consider the stochastic shortest path problem, a classical finite-state Markovian decision problem with a termination state, and we propose new convergent Q-learning algorithms that combine elements of policy iteration and classical Q-learning/value iteration. These algorithms are related to the ones introduced by the authors for discounted problems in Bertsekas and Yu (Math. Oper. Res. 37(1):66-94, 2012). The main difference from the standard policy iteration approach is in the policy evaluation phase: instead of solving a linear system of equations, our algorithm solves an optimal stopping problem inexactly with a finite number of value iterations. The main advantage over the standard Q-learning approach is lower overhead: most iterations do not require a minimization over all controls, in the spirit of modified policy iteration. We prove the convergence of asynchronous deterministic and stochastic lookup table implementations of our method for undiscounted, total cost stochastic shortest path problems. These implementations overcome some of the traditional convergence difficulties of asynchronous modified policy iteration, and provide policy iteration-like alternative Q-learning schemes with as reliable convergence as classical Q-learning. We also discuss methods that use basis function approximations of Q-factors and we give an associated error bound.  相似文献   

4.
When vehicle routing problems with additional constraints (e.g. capacities or time windows) are solved via column generation and branch-and-price, it is common that the pricing problem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the nodes. The pricing problem is usually solved via dynamic programming in two possible ways: requiring elementary paths or allowing paths with cycles. We experimentally compare these two strategies and we evaluate the effectiveness of some algorithmic ideas to improve their performance.  相似文献   

5.
A label setting algorithm for solving the Elementary Resource Constrained Shortest Path Problem, using node resources to forbid repetition of nodes on the path, is implemented. A state-space augmenting approach for accelerating run times is considered. Several augmentation strategies are suggested and compared numerically.  相似文献   

6.
The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ε-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic (PFH) is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path.  相似文献   

7.
Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.  相似文献   

8.
For stochastic shortest path problems, error bounds for value iteration due to Bertsekas elegantly generalize the classic MacQueen–Porteus error bounds for discounted infinite-horizon Markov decision problems, but incur prohibitive computational overhead. We derive bounds on these error bounds that can be computed with little or no overhead, making them useful in practice—especially so, since easily-computed error bounds have not previously been available for this class of problems.  相似文献   

9.
《Applied Mathematical Modelling》2014,38(9-10):2613-2629
This paper investigates the solution algorithms for the multi-criteria multi-modal shortest path problem (M-SPP), which belongs to the set of problems known as NP-hard, in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on). To get their destination, the passengers can alternate between different modes. As a special demand, the time-window is usually associated with the M-SPP. Because of the service time-limit of modes, the available modes at a stop are varied with the time. So the optimal M-SPP with arriving time-window cannot be simply obtained by finding the optimal M-SPP firstly and then reversely deducing the leaving time-window of the origin according to the arriving time-window of destination. In this paper, the M-SPP with arriving time-window is firstly proposed. To solve the multi-criteria M-SPPs (MM-SPP) with transfer delaying, an improved exact label correcting algorithm (LCA) is designed and, to solve the proposed MM-SPPs with both of transfer delaying and arriving time-window, an exact reverse LCA is designed. Finally, some computing examples are given to test the effectiveness of the designed algorithms.  相似文献   

10.
In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.  相似文献   

11.
The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.  相似文献   

12.
Mobile communication technologies enable truck drivers to keep abreast of changing traffic conditions in real-time. We assume that such communication capability exists for a single vehicle traveling from a known origin to a known destination where certain arcs en route are congested, perhaps as the result of an accident. Further, we know the likelihood, as a function of congestion duration, that congested arcs will become uncongested and thus less costly to traverse. Using a Markov decision process, we then model and analyze the problem of constructing a minimum expected total cost route from an origin to a destination that anticipates and then responds to changes in congestion, if they occur, while the vehicle is en route. We provide structural results and illustrate the behavior of an optimal policy with several numerical examples and demonstrate the superiority of an optimal anticipatory policy, relative to a route design approach that reflects the reactive nature of current routing procedures.  相似文献   

13.
We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.  相似文献   

14.
15.
16.
We present methods to find the shortest path in a network where each path is associated with two objectives. We describe how to obtain the nondominated paths and the extreme nondominated paths, and compare the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, we describe how to find the optimal extreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case we suggest a branch and bound method to solve the problem.  相似文献   

17.
On the directed hop-constrained shortest path problem   总被引:1,自引:0,他引:1  
  相似文献   

18.
New models for shortest path problem with fuzzy arc lengths   总被引:1,自引:0,他引:1  
This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.  相似文献   

19.
20.
Let G=(V, E) be a digraph with n vertices including a special vertex s. Let E′ ? E be a designated subset of edges. For each e?E there is an associated real number ?1(e). Furthermore, let ?2(e)=1 if e?E′ and ?2(e)=0 if e?E ? E′. The length of edge e is ?1(e)? λ?2(e), where λ is a parameter that takes on real values. Thus the length varies additively in λ for each edge of E′.We shall present two algorithms for computing the shortest path from s to each vertex υ?V parametrically in the parameter λ, with respective running times O(n3) and O(n|E|log n). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known.This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E′=E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n2 log n) algorithm for the cyclic staffing problem.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号