Algorithms for the weight constrained shortest path problem

Algorithms for the weight constrained shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor20021965
Country: United Kingdom
Volume: 8
Issue: 1
Start Page Number: 15
End Page Number: 29
Publication Date: Jan 2001
Journal: International Transactions in Operational Research
Authors: ,
Keywords: vehicle routing & scheduling, combinatorial analysis
Abstract:

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 Langrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights.

Reviews

Required fields are marked *. Your email address will not be published.