			Home About us Contact

Shortest Path Problem (shortest + path_problem)

Distribution by Scientific Domains

Mathematics and Statistics	47%
Information Science and Computing	11%

Selected Abstracts

Algorithms for the Weight Constrained Shortest Path Problem

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2001
Irina Dumitrescu
Given a directed graph whose arcs have an associated cost, and associated weight, the weight constrained shortest path problem (WCSPP) consists of finding a least-cost path between two specified nodes, such that the total weight along the path is less than a specified value. We will consider the case of the WCSPP defined on a graph without cycles. Even in this case, the problem is NP-hard, unless all weights are equal or all costs are equal, however pseudopolynomial time algorithms are known. The WCSPP applies to a number of real-world problems. Traditionally, dynamic programming approaches were most commonly used, but in recent times other methods have been developed, including exact approaches based on Lagrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights. [source]

Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009
Ranga Muhandiramge
Abstract Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19 (1989), 379,394), calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and edges. However, for each node and edge, a Lagrangean dual problem exists whose solution may differ from the relaxation of the full problem. Thus, using one Lagrange multiplier does not offer the best possible network reduction. Furthermore, eliminating nodes and edges from the network may change the Lagrangean dual solutions in the remaining reduced network, warranting an iterative solution and reduction procedure. We develop a method for solving the related Lagrangean dual problems for each edge simultaneously which is iterated with eliminating nodes and edges. We demonstrate the effectiveness of our method computationally: we test it against several others and show that it both reduces solve time and the number of intractable problems encountered. We use a modified version of Carlyle and Wood's (38th Annual ORSNZ Conference, Hamilton, New Zealand, November, 2003) enumeration algorithm in the gap closing stage. We also make improvements to this algorithm and test them computationally. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Parallel Algorithms for Dynamic Shortest Path Problems

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2002
Ismail Chabini
The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster-than-real-time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst-case running-time complexity. This implies that no algorithm with a better worst-case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all-to-one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially-available high-performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared-memory and two message-passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message-passing environment based on the parallel virtual machine (PVM) library and a multi-threading environment based on the SUN Microsystems Multi-Threads (MT) library. We also develop a time-based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ,ideal' theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared-memory machine containing eight processors. Satisfactory speed-ups in the running time of sequential algorithms are achieved, in particular for shared-memory machines. Numerical results indicate that shared-memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real-time ITS applications. [source]

The Push Tree problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004
Frédéric Havet
Abstract In this article, we introduce the Push Tree problem, which exposes the tradeoffs between the use of push and pull mechanisms in information distribution systems. One of the interesting features of the Push Tree problem is that it provides a smooth transition between the minimum Steiner Tree and the Shortest Path problems. We present initial complexity results and analyze heuristics. Moreover, we discuss what lessons can be learned from the static and deterministic Push Tree problem for more realistic scenarios characterized by high uncertainty and changing information request and update patterns. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 281,291 2004 [source]

A dynamic multicast routing satisfying multiple QoS constraints

INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT, Issue 5 2003
Debasish Chakraborty
In this paper we propose a QoS-based routing algorithm for dynamic multicasting. The complexity of the problem can be reduced to a simple shortest path problem by applying a Weighted Fair Queuing (WFQ) service discipline. Using a modified Bellman,Ford algorithm, the proposed routing builds a multicast tree, where a node is added to the existing multicast tree without re-routing and satisfying QoS constraints.,With user defined life-time of connection this heuristic algorthm builds multicast tree which is near optimum over the whole duration of session. Simulation results show that tree costs are nearly as good as other dynamic multicast routings that does not consider QoS. Copyright © 2003 John Wiley & Sons, Ltd. [source]

Shortest paths on dynamic graphs

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 5 2008
Giacomo Nannicini
Abstract Among the variants of the well-known shortest path problem, those that refer to dynamically changing graphs are theoretically interesting, as well as computationally challenging. Application-wise, there is an industrial need for computing point-to-point shortest paths on large-scale road networks whose arcs are weighted with a travelling time that depends on traffic conditions. We survey recent techniques for dynamic graph weights as well as dynamic graph topology. [source]

Algorithms for the Weight Constrained Shortest Path Problem

A travelling salesman problem with allocation, time window and precedence constraints , an application to ship scheduling

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2000
K. Fagerholt
Abstract A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship's flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem. [source]

On the complexity of finding paths in a two-dimensional domain I: Shortest paths

MLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 6 2004
Arthur W. Chou
Abstract The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type (A) and type (B); and it has a polynomial-space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source]

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2002
S. Raghavan
Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph,a directed series-parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series-parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574,592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031 [source]

Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem

Minimum work paths in elevated networks

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2008
Takeshi Shirabe
Abstract A new variant of the shortest path problem involves a bicycle traveling from an origin to a destination through a network situated on a hilly geography. Determining a path that takes the least amount of pedaling work involves a conservative force, gravity, and a nonconservative force, friction, acting on the bicycle. The cyclist's pedaling work to overcome the friction of each arc varies with the bicycle's kinetic and gravitational potential energies, which transform to one another. Although geometric characteristics of the network are invariable, arc weights representing required pedaling work are variable. This problem is formulated as a quadratic integer program and an approximation procedure is presented. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008 [source]

Minimizing beam-on time in cancer radiation treatment using multileaf collimators

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004
Natashia Boland
Abstract In this article the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators (MLC) is investigated. It is shown that the problem is equivalent to decomposing a given integer matrix into a positive linear combination of (0, 1) matrices. These matrices, called shape matrices, must have the strict consecutive-1-property, together with another property derived from the technological restrictions of the MLC equipment. Various decompositions can be evaluated by their beam-on time (time during which radiation is applied to the patient) or the treatment time (beam-on time plus time for setups). We focus on the former, and develop a nonlinear mixed-integer programming formulation of the problem. This formulation can be decomposed to yield a column generation formulation: a linear program with a large number of variables that can be priced by solving a subproblem. We then develop a network model in which paths in the network correspond to feasible shape matrices. As a consequence, we deduce that the column generation subproblem can be solved as a shortest path problem. Furthermore, we are able to develop two alternative models of the problem as side-constrained network flow formulations, and so obtain our main theoretical result that the problem is solvable in polynomial time. Finally, a numerical comparison of our exact solutions with those of well-known heuristic methods shows that the beam-on time can be reduced by a considerable margin. © 2004 Wiley Periodicals, Inc. [source]

On the online shortest path problem with limited arc cost dependencies

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2002
S. Travis Waller
Abstract This paper is concerned with the stochastic shortest path problem with recourse when limited forms of spatial and temporal arc cost dependencies are accounted for. Recourse is defined as the opportunity for a decision maker to reevaluate his or her remaining path when en-route information is available. Formulations with recourse typically provide opportunities for corrective actions when information becomes available; information here is modeled as arc cost dependencies, defined as spatial and temporal. System properties are stated and proved and solution algorithms are developed for limited cases of spatial and temporal arc cost dependencies. The numerical results verify some of the theoretical insights and demonstrate the applicability of the introduced algorithms. © 2002 Wiley Periodicals, Inc. [source]