A heuristic approach to hard constrained shortest path problems

DOI10.1016/0166-218X(85)90007-1zbMath0574.90085MaRDI QIDQ1063522

Michel Minoux, Celso Carneiro Ribeiro

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

efficient solutionsheuristic approachfeasible solutionspseudopolynomial algorithmdoubly constrained) shortest path problemsparametric shortest path calculations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)

Related Items (5)

Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic ⋮ Designing a minimal spanning tree network subject to a budget constraint ⋮ Maximum probability shortest path problem ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ A parametric critical path problem and an application for cyclic scheduling

Cites Work

• A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems
• Parametric shortest path algorithms with an application to cyclic staffing
• The shortest route problem with constraints
• Vehicle routing and scheduling with time windows
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• Shortest path with time constraints on movement and parking
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A heuristic approach to hard constrained shortest path problems