The shortest path problem with forbidden paths

DOI10.1016/j.ejor.2004.01.032zbMath1112.90379MaRDI QIDQ146692

Daniel Villeneuve, Guy Desaulniers, Guy Desaulniers, Daniel Villeneuve

Publication date: August 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.01.032

zbMATH Keywords

shortest paths; network flows; forbidden paths

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B10: Deterministic network models in operations research

Related Items

Dynamic programming approaches to solve the shortest path problem with forbidden paths, Shortest paths avoiding forbidden subpaths, The shortest path problem with forbidden paths, rsppfp, Comparing branch-and-price algorithms for the multi-commodity \(k\)-splittable maximum flow problem, Multi-objective and multi-constrained non-additive shortest path problems, On compact formulations for integer programs solved by column generation, Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks, Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-logit formulas, Developing work schedules for an inter-city transit system with multiple driver types and fleet types, An efficient algorithm to find next-to-shortest path on permutation graphs, Two- and three-index formulations of the minimum cost multicommodity \(k\)-splittable flow problem, Limitations of learning in automata-based systems, Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly, Finding \(K\) shortest looping paths with waiting time in a time--window network, A survey of resource constrained shortest path problems: Exact solution approaches, Finding Paths in Grids with Forbidden Transitions, Efficiently Generating k-Best Solutions to Procurement Auctions

Cites Work

• The shortest path problem with forbidden paths
• An algorithm for ranking paths that may contain cycles
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• The pickup and delivery problem with time windows
• An exact algorithm for IP column generation
• On a routing problem
• A Linear Programming Approach to the Cutting-Stock Problem
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Efficient string matching
• Finding the k Shortest Paths
• Algorithms on Strings, Trees and Sequences
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Fibonacci heaps and their uses in improved network optimization algorithms
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item