- Title
- Dynamic programming-based column generation on time-expanded networks: application to the dial-a-flight problem
- Creator
- Engineer, Faramroze G.; Nemhauser, George L.; Savelsbergh, Martin W. P.
- Relation
- INFORMS Journal on Computing Vol. 23, Issue 1, p. 105-119
- Publisher Link
- http://dx.doi.org/10.1287/ijoc.1100.0384
- Publisher
- Institute for Operations Research and the Management Sciences (INFORMS)
- Resource Type
- journal article
- Date
- 2011
- Description
- We present a relaxation-based dynamic programming algorithm for solving resource-constrained shortest-path problems (RCSPPs) in the context of column generation for the dial-a-flight problem. The resulting network formulation and pricing problem require solving RCSPPs on extremely large time-expanded networks having a huge number of local resource constraints, i.e., constraints that apply to small subnetworks. The relaxation-based dynamic programming algorithm alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search space. Between consecutive searches, the relaxation is tightened using a set of critical resources and a set of critical arcs over which these resources are consumed. As a result, a relatively small state space is maintained, and many paths can be pruned while guaranteeing that an optimal path is ultimately found.
- Subject
- dynamic programming; column generation; time-expanded networks; dial-a-flight
- Identifier
- http://hdl.handle.net/1959.13/939576
- Identifier
- uon:12840
- Identifier
- ISSN:1091-9856
- Language
- eng
- Reviewed
- Hits: 638
- Visitors: 586
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|