کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482304 | 1446187 | 2007 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context](/preview/png/482304.png)
This paper presents a unified three-stage approach (TSA), comprising preprocessing, setup, and iterative solution stages, for solving several variations of the resource constrained shortest-path problem (RCSP). TSA is designed specially for column-generation applications in which sub-problems must be solved repetitively. The first two stages are implemented one time and only the third stage need be applied repetitively. In a companion paper, the authors proposed a TSA for solving RCSP on an acyclic graph with upper bound resource-limitation constraints. This paper shows that a TSA can be designed to solve each of several related problems: shortest-path with equality resource-limitation constraints; shortest-path with resource windows; resource-constrained, k-shortest path; and multiple-resource, multiple-choice knapsack. A numerical example demonstrates application of a TSA to design an international assembly system and its supply chain using branch and price with multiple-choice knapsack sub-problems. Computational results show that our TSA can solve this sub-problem effectively in such a column-generation environment.
Journal: European Journal of Operational Research - Volume 183, Issue 2, 1 December 2007, Pages 564–577