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

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

0.00 Avg rating0 Votes
Article ID: iaor20125441
Volume: 40
Issue: 1
Start Page Number: 385
End Page Number: 394
Publication Date: Jan 2013
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

The resource‐constrained shortest‐path problem (RCSP) is often used as a sub‐problem in branch‐and‐price because it can model the complex logic by which many actual systems operate. This paper addresses two special issues that arise in such an application. First, RCSP in this context is dynamic in the sense that arc costs are updated at each column‐generation iteration, but constraints are not changed. Often, only a few arc costs are updated at an iteration. Second, RCSP must be solved subject to arcs that are forbidden or prescribed as corresponding binary variables are fixed to 0 or 1 by the branching rule. A reoptimizing algorithm for dealing with a few arc‐cost changes and a method for dealing with fixed arcs are proposed and incorporated into a three‐stage approach, specializing it for repeatedly solving the dynamic RCSP as a sub‐problem in branch‐and‐price. Computational tests evaluate the effectiveness of the proposed algorithms.

Reviews

Required fields are marked *. Your email address will not be published.