A heuristic approach to hard constrained shortest path problems
type: Item
instance of: scholarly article
title: A heuristic approach to hard constrained shortest path problems
zbMATH Open document ID: 0574.90085
DOI: 10.1016/0166-218X(85)90007-1
author: Michel Minoux
author: Celso C. Ribeiro
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general. We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied. From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3918120
zbMATH Keywords: heuristic approach
zbMATH Keywords: feasible solutions
zbMATH Keywords: doubly constrained) shortest path problems
zbMATH Keywords: parametric shortest path calculations
zbMATH Keywords: pseudopolynomial algorithm
zbMATH Keywords: efficient solutions
MaRDI profile type: Publication
cites work: Q4065051
cites work: Vehicle routing and scheduling with time windows
cites work: Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
cites work: Q4198056
cites work: Shortest path with time constraints on movement and parking
cites work: The shortest route problem with constraints
cites work: Parametric shortest path algorithms with an application to cyclic staffing
cites work: Q5585020
cites work: Q4117605
cites work: Q3337942
cites work: A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems
description: scientific article; zbMATH DE number 3918120