Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem
Faramroze G. Engineer, George L. Nemhauser, Martin W. P. Savelsbergh
INFORMS Journal on Computing · 2011 · Volume 23 · Issue 1
Abstract
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.
Keywords
dynamic programming, column generation, time-expanded networks, dial-a-flight
Enable JavaScript for citation tools and additional paper interactions.