The shortest path problem with forbidden paths

DOI10.1016/j.ejor.2004.01.032zbMath1112.90379OpenAlexW2040572217MaRDI 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 pathsnetwork flowsforbidden paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items

Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly, A new heuristic branching scheme for the crew pairing problem with base constraints, On an exact method for the constrained shortest path problem, Shortest paths avoiding forbidden subpaths, Multi-objective and multi-constrained non-additive shortest path problems, Comparing branch-and-price algorithms for the multi-commodity \(k\)-splittable maximum flow problem, Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks, A two-stage solution approach for the directed rural postman problem with turn penalties, Dynamic programming approaches to solve the shortest path problem with forbidden paths, Finding \(K\) shortest looping paths with waiting time in a time--window network, A branch and price algorithm to solve the quickest multicommodity \(k\)-splittable flow problem, Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-logit formulas, The shortest path problem with forbidden paths, A survey of resource constrained shortest path problems: Exact solution approaches, Developing work schedules for an inter-city transit system with multiple driver types and fleet types, Efficiently Generating k-Best Solutions to Procurement Auctions, rsppfp, Finding Paths in Grids with Forbidden Transitions, 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, Shortest path with acceleration constraints: complexity and approximation algorithms, Limitations of learning in automata-based systems, On compact formulations for integer programs solved by column generation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• 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