Return to Index
Operations Research Models and Methods
 
Problems Section
Problems for Network Flow Programming Models
 - Military Aircraft Routing

a. The nodes on the left represent the original assignment of planes to bases. We explain the arcs going from left to right. The arc from Bi to Tj is the transportation from base to target on the first day. The arc pair from Tj to Tj' holds the damage value and the losses at the target (gains less than 1). The arc from Tj' to base Bi is the transit from the target to the overnight base. The arc from Bi to Bi' holds the limit for overnight stays. The arc Bi' to Tj is the travel to the target on the second day. Again, the arc pair from Tj to Tj' holds the damage value and the loss percentage. The arcs from Tj' to Bi is the travel to the bases at the end of the second day.

At the node on the far right, there is an external flow of -T, where T is the original number of planes. The arc entering that node from below holds the cost of lost planes. The flow in that arc will be the number of planes lost through the two days

Network Model: Arc parameters are (upper bound, cost, gain)

 

 

b. Have node pairs such as T1, T1' for all twelve targets on both days. For day 1, Identify the flow on the target arcs be tj11 and tj21, where j is the target index, 1 refers to the arc with cost -dj and 2 refers to the arc with cost -0.75dj. Similarly define tj12 and tj22 for the second day.

Define the binary variables, wj = 1 if target is hit on the first day and 0 if it is hit on the second day, for j = 1 to 12.

Add side constraints: tj11 + tj21 ¾ 10wj and tj12 + tj22 ¾ 10(1 - wj), for each target j. This forces the flows on a target in day 1 to be 0 unless the target is selected. It forces the flows on a target in day 2 to be zero unless it is not selected for day 1.

This is a mixed integer programming model.


  
Return to Top

tree roots

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2001 - All rights reserved