Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price

DOI10.1016/j.cor.2012.07.007zbMath1349.90829OpenAlexW2071216266MaRDI QIDQ339594

Xiaoyan Zhu, Wilbert E. Wilhelm

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.07.007

zbMATH Keywords

column generationbranch-and-pricefixed arcsre-optimizationresource-constrained shortest-path problemthree-stage approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Accelerating the branch-and-price algorithm using machine learning, Theory and application of reciprocal transformation of “path problem” and “time float problem”, Branch-and-price-and-cut for a service network design and hub location problem, An exact reduction technique for the k-colour shortest path problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Enabling flexibility on a dual head placement machine by optimizing platform-tray-feeder picking operations
• A reoptimization algorithm for the shortest path problem with time windows
• Crew pairing at Air France
• A generalized linear programming model for nurse scheduling
• A new algorithm for reoptimizing shortest paths when the arc costs change
• A technical review of column generation in integer programming
• A model to optimize placement operations on dual-head placement machines
• The shortest route problem with constraints
• A special case of transfer lines balancing by graph approach
• Algorithms for the Weight Constrained Shortest Path Problem
• A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
• An Optimization Model for the Simultaneous Operational Flight and Pilot Scheduling Problem
• Reoptimization procedures in shortest path problem
• Shortest chain subject to side constraints
• An algorithm for the resource constrained shortest path problem
• A dual algorithm for the constrained shortest path problem
• A note on the problem of updating shortest paths
• Approximation Schemes for the Restricted Shortest Path Problem
• A new shortest path updating algorithm
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• A Set Partitioning Approach to the Crew Scheduling Problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Constraint programming based column generation for crew assignment