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

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.