Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem

作者：Engineer Faramroze G^*; Nemhauser George L; Savel**ergh Martin W P

来源：INFORMS Journal on Computing, 2011, 23(1): 105-119.

DOI：10.1287/ijoc.1100.0384

• dynamic programming
• column generation
• time-expanded networks
• dial-a-flight

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.

• 出版日期2011