Network design formulations for scheduling U.S. Air Force channel route missions

Each month, the United States Air Forceʹs Air Mobility Command is responsible for designing a large-scale air mobility network—called the channel route network—that is used to transport military personnel and cargo throughout the world. Traditionally, planning the channel route network has been a manual process, requiring numerous hours to generate a monthly channel route schedule. We formulate the monthly channel route scheduling problem using a traditional network design formulation, and we use price-directive decomposition to overcome tractability issues. The resulting linear programming bounds on the optimal integer solution are weak. To overcome these challenges, we apply a variable redefinition technique known as composite variable modelling. Using this technique, we alleviate the need to explicitly include cargo flow decisions by implicitly capturing them in the design variables. The resulting formulation is computationally superior to the traditional network design formulation because it achieves tighter bounds, allowing excellent integer solutions to be found quickly.