A stochastic program for optimizing military sealift subject attack

We describe a stochastic program for planning the wartime, sealift deployment of military cargo that is subject to attack. The cargo moves on ships from U.S. or allied seaports of embarkation, to seaports of debarkation (SPODs) near the theater of war where it is unloaded and sent on to final, in-theater destinations. The question we ask is: Can a deployment-planning model, with probabilistic information on the time and location of potential enemy attacks on SPODs, successfully hedge against those attacks? That is, can this information be used to reduce the expected disruption caused by such attacks? We develop a specialized, stochastic mixed-integer program whose solutions answer that question in the affirmative for realistic deployment data. Furthermore, compared to the optimal deterministic solution, the stochastic solution incurs only a minor "disruption penalty" when no attack occurs, and outcomes for worst-case scenarios are better. Insight gained from the stochastic-programming approach also points to possible improvements in current, rulebased, scheduling methods.