ABSTRACT withintheirpowerstoreducethenumberof ground convoys and thus reduce exposure TheAirTaskingandEfficiencyModel ofpersonneltotheever-increasingnumber (ATEM)hasbeenusedsince2006.Its ofimprovisedexplosivedevices.Thedirec- Optimizing development was motivated by an torofCDDOCpressedhisstaff,‘‘Wecannot urgentneedtoplanandevaluateintratheater fly everything, but we need to fly every- Intratheater airlift of passengers and palletized freight thingwecan.’’ for Operation Iraqi Freedom in Iraq and The United States Transportation Com- Military Operation Enduring Freedom in Afghani- mand divides intratheater air routes into stan.ATEMplansroutesandaircraftconfig- two broad categories, frequency channel Airlift in urations (capacity of passenger seats and routes and requirements channel routes pallet positions)for aheterogeneous fleetof (United States Transportation Command, Iraq and aircraft flying between multiple airfields. 2005). Frequency channel routes are pub- ATEMrespectslimitsoncrewdutyperiods, lished in a schedule, much like an airline, timesandabilities ofeachairfield to handle based on anticipated demands for a given Afghanistan andfueleachaircrafttype,andaircraftspeed time period. Requirements channel routes and carrying capacity. Initially, ATEM ad- are decided each day, and move emergent vised improving daily and weekly route demand as necessary. Author Brau was Dr. Gerald G. Brown, ensembles,conveyingmorepassengersand stationed at Camp Arifjan in October 2005, pallets and using fewer aircraft than prior and at that time he found that air planners Dr. W. Matthew Carlyle, manually generated solutions. This early were manually scheduling CENTCOM and Dr. Robert F. Dell usereducedtherequirednumberofground intratheater airlift using basic tools such as convoys and thereby exposure to impro- whiteboards and simple Microsoft Excel NavalPostgraduateSchool visedexplosivedevices.Later,ATEMadvised spreadsheetstokeeptrackofassetsandma- [email protected], where to advantageously move aircraft to teriel. He immediately started working on [email protected], new home airfields, how to shift aircraft an optimization model to assist planners in [email protected] betweentheaters,andwhentobringaircraft creating the requirements channel routes homefromwar. and prescribing air and ground movement John W. Brau, Jr. of passengers (PAX) and air freight pallets ThatIhavehoistedsailtoallthewinds, (PALS), hereafter referred to collectively as which should transport me farthest cargo. He contacted the other authors soon USTRANSCOM/TCAC-D fromyoursight. afterhestartedthiseffort,andbyDecember [email protected] Shakespeare,Sonnet 2005 our team had begun development of adecisionsupporttoolcalledtheAirTrans- portation and Efficiency Model (ATEM) for INTRODUCTION quicklycreatingrequirementschannelroutes, tohelpclearbackloggedcargo,andtodesign The logistics of transporting, arming, high-qualityweeklyfrequencychannelroutes feeding,clothing,sheltering,andfuelinghun- for future demands. The solutions provided dreds of thousands of personnel involved by ATEM maximize the flow of PAX and with our military operations in Iraq and PALSonintratheaterairplanes:byanalyzing Afghanistan has been a daunting challenge daily operations data, we realized this pre- for US Central Command (CENTCOM), sented the greatest opportunity to make a theunifiedcombatantcommandwhosearea significantnear-termimprovement. of responsibility includes those countries. ATEMwouldbeoflittleutilitywithout The CENTCOM Deployment and Distribu- an interface making it easy for nonanalyst tion Operations Center (CDDOC) at Camp plannerstounderstandanduse.So,wede- Arifjan, Kuwait, receives specific demand veloped a portable, laptop-based graphical signalsandmanageswhatisessentiallythe user interface using Microsoft Excel and APPLICATIONAREAS: last echelon in a world-wide supply chain. Visual Basic (Microsoft, 2012a,b), and a Airlift,VehicleRouting, This echelon conducts intratheater move- mathematical modeling suite including ConvoyMitigation, ment of materiel, using convoys of trucks the General Algebraic Modeling System IEDMitigation, and,whenpossible,airlift,tomoveperson- (http://www.gams.com) and several com- DecisionSupport nelandtheirequipmenttowheretheyare mercial optimization packages. A trip to ORMETHODS: neededinsupportofmilitaryoperations. Kuwaitbytwoofourco-authorsconfirmed Optimization, In2005theCENTCOMcommanderdi- that such a decision support tool would be Spreadsheets,Heuristics rectedUSmilitaryleaderstodoeverything asignificantimprovementinbothfrequency MMiilliittaarryyOOppeerraattiioonnssRReesseeaarrcchh,,VV1188NN3322001133,,ddooii1100..55771111//11008822559988331188333355 PPaaggee3355 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN andrequirementschannelplanning,andhelped ofStaff2000).Strategicdistribution,themove- solidifythestructureofthemodelbasedonour ment of forces from Continental US (CONUS) direct experience with air logistics in Iraq and bases into a theater of operations, flows along onourdiscussionswithplannersintheatre. intertheaterdistributionchannels.Operational distribution, the movement of materiel within aCOCOMtheater,flowsalongintratheaterlogis- MILITARYAIRLIFTPLANNINGTOOLS tics channels. VRPs are inherent in both inter- theater and intratheater distribution, and the Our intratheater distribution problem is Department of Defense employs many tools to a variant of the vehicle routing problem (VRP) solveboththeseproblems. (Dantzig and Ramser, 1959). The objective of The major strategic distribution models in VRPistodesignasetofroutesforagivenfleet use when we started ATEM and still in use to- of vehicles that satisfies customer demands at day are the Global Deployment Analysis Sys- dispersed locations from one or more depots, tem (GDAS), Joint Flow and Analysis System atlowestcost.Sideconstraintsaddedtotheba- for Transportation (JFAST), Model for Inter- sic VRP create variants of the problem. Typical theater Deployment by Air and Sea (MIDAS), variantsincludethecapacitatedvehiclerouting the Mobility Simulation Model (MobSim), and problem, wherevehicles have limited capacity, theConsolidatedAirMobilityPlanningSystem the vehicle routing problem with pickups and (CAMPS). Barnes and McKinzie (2004) survey deliveries, where customers can both receive thesesystems.Inadditiontothese,othersimu- material from and return material to a depot, lation models in use today include the Air the vehicle routing problem with time win- Mobility Operations Simulation (AMOS) and dows,wherevisits tocustomers mustbemade theAnalysisofMobilityPlatform(AMP). withinaspecifiedtimeepoch,andtheshuttling GDAS uses alternating greedy cargo and problem,whereeachcustomerisbothanorigin greedy vehicle heuristics combined with route and a destination for shipments from and to insertiontoassignpassengerstomodesoftrans- other customers, and the dial-a-ride problem, portation (air, ground, and sea) for transport where customer pickups and drop-offs are between points of CONUS embarkation to merged into a set of vehicle routes. See Toth pointsofdebarkationinsomeareaofoperations. and Vigo (2002) for a survey of VRP problems JFAST employs local search to plan strategic andsolutiontechniques. lift from CONUS to some deployment area of We find intratheater airlift as required in operations(seeKoprowski[2005],andhisrefer- Operation Iraqi Freedom (OIF) and Operation ences for a summary). MIDAS is a simulation Enduring Freedom (OEF) to be a unique VRP. thatrepresentsstrategicdeploymentofunitper- Feillet, Dejax, and Gendreau (2005) present the sonnel and equipment by air and sealift into profitable arc tour problem that shares much theater ports of debarkation (Military Surface incommon,butinadditiontothefeaturesthey Deployment and Distribution Transportation describewealsomustplanformultipledepots, EngineeringAgencyCommand,2005).MobSim multiple (here, two) types of cargo capacity on is a network-based discrete event stochastic eachvehicle,andalimitedheterogeneousvehi- model.CAMPS,thereplacementforbothADANS clefleet. (Air Mobility Command Deployment Analysis JointPub3-0(JointChiefsofStaff2001)de- System) and CMARPS (Combined Mating and fines three levels of war: strategic, operational, Ranging Planning System), is a heuristic plan- andtactical.Militarylogisticsmustenableoper- ning tool (Becker et al., 2004). AMOS is a rule- ations at all three levels. The Joint Staff and based, discrete-event simulation of worldwide service staffs concentrate on strategic logistics airlift with the ability to model detailed air to matters. Combatant Commanders (COCOM) airrefuelingandairfieldcongestion(seeMason link strategic- and operational-level logistics. [2009]andWuandPowell[2009]).AMPisasim- Finally, subordinate commanders blend oper- ulation that includes MIDAS and other legacy ational and tactical logistics to accomplish simulation models (Raytheon, 2013). Noel and missionsassignedbytheCOCOM(JointChiefs Stratton (2012) catalog the portfolio of more Page36 MilitaryOperationsResearch,V18N32013 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN than 40 models (including those referenced be served by each route and what capacity, in above)thathavehadsomeuseatAirMobility termsofPAXandPALS,itcanliftoneachflight Command. in that route: any cargo from a demand line Intratheaterdistributiontoolsarelesscom- whose origin precedes its destination on that mon. Barnes et al. (2004) provide approximate routecouldconceivablybecarriedbyanaircraft solutions to an intratheater VRP with a tabu flyingthatroute,althoughitmightrequiresev- searchmetaheuristic,butweknowofnoinstal- eral flight legs to get there. ATEM allows such lation of their product. They claim that, at the loading of cargo and carrying it through one timeofpublicationoftheirpaper,allotherthe- ormoreintermediateairfieldsbeforeunloading ater distribution tools were simulation-based. it at its destination (planners call this through- These include ELIST (Enhanced Logistics Intra- put); the number of legs per load is controlled theater Support Tool), TRANS (Transportation by a single parameter, maxloadhops, (where the Resource Assessment Network Simulator), and numberofhopsaparticularpieceofcargomakes MASS (Mobility Analysis Support System). isjustthenumberofconsecutiveflightlegsbe- Transway(Pohl2006)usesatabusearchmeta- tween its origin and destination), and setting heuristic to help plan intertheater (and intra- thisparametertoonepreventsanythroughput theater) distribution. Burks et al. (2010) also (i.e., every passenger or pallet can travel on at tackleintratheaterdistributionwithtabusearch. mostoneleginaroute). We have no evidence that either of these Finally, for each airport ATEM needs to products were ever used by the Department knowthemaximumnumberoflandingsallowed of Defense. eachday,andthenumberofaircraftofeachtype thatarebasedatthatairport.Givenanenumera- tion of every admissible route for each aircraft ATEM INTEGER LINEAR PROGRAM type, configuration, and home airport, ATEM FORMULATION seeks an optimal assignment of a single route toeachaircraftandanallocationofcargotothose Wepresentanintegerlinearprogram(ILP) routes that maximizes (prioritized) PALS and formulationofATEM.ATEMtakesasinputalist PAX conveyed. It may not always be possible of airport pairs and the number of PAX and to fill each flight on a route with cargo. For in- PALS traveling between them; each of these stance,anemptyflight(adeadhead)maybeneces- pairs and associated demands is known as sarytorepositionanairplane,ortobringitback ademandline,becauseitisrepresentedbyasin- homeattheendofitsroute. gle line on a demand spreadsheet used by the planners. Indices [;cardinality] ATEM also takes as input a (typically very large) list of routes, each of which is specific to a 2A setofairfields(aliasa,a)½;20(cid:2) i j anairplanetypeandtoaparticularconfiguration c 2C set of cargo types (passengers of that airplane. A route for one airplane on andcargopallets)½;2(cid:2) one day consists of a sequence of flight legs, p 2P setofairplanetypes½;5(cid:2) where each leg is a single nonstop flight be- p 2P setofairplanesoftypepbased ai tween an origin and a destination airfield. The atairfielda i firstlegdepartsfromtheairplane’shomeairfield, g 2G set of configurations for air- p and the last leg returns to this same home air- planetypep½;5(cid:2) (cid:2) (cid:3) field. Each route consists of a feasible sequence a;a 2L set of possible flight legs or i j offlightlegs,inthattheassociatedaircraftcan, segments(airportofembarka- in one day, make all of the flights on the route tion(APOE),airportofdebar- inthesequencegivenwithoutviolatinganyop- kation(APOD)pairs)½;100(cid:2) erational restriction or resource requirement r 2R setofroutesforairplanetypep pai (suchasfuelandtotalflighttime). startingatairfielda½#100;000(cid:2) This route and configuration data allows s 2f1;2;.;Sg ordinalofstoponaroute(alias ATEM to determine which demand lines can s#,so)[;7] MMiilliittaarryyOOppeerraattiioonnssRReesseeaarrcchh,,VV1188NN3322001133 PPaaggee3377 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Data X LOADrss#c#caprcSELECTr len numberofstopsonrouter ðs;s#Þ2Hr: r s#so,s# aðr;sÞ airfieldatstopnumbersonroute r,where1#s#len "r;1#so,lenr;c (4) r carry amountofcargoconleg(cid:2)a;a(cid:3)that X aiajcr canbeairliftedbyrouter i j SELECTr#landingaj "aj 2A (5) (cid:2) (cid:3) r;s#: cdpemaiaajicajc dperimoraintydoufncaitrsgooncolengle(cid:2)gai;aaij;(cid:3)ajfor 1a,ðrs;#s##Þ5lenajr; cargoc caprc capacityonrouterofcargotypec The objective function (1) calculates the landing maximumnumberoflandings in priority-weighted value of all cargo conveyed a airfielda on all routes. For each airfield and each air- planespa numberofairplanetypepstarting plane type based there, constraint (2) limits fromairfielda the number of routes selected to the number maxloadhops the maximum number of consecu- of airplanes available. For each demand line tive legs the cargo from a single and cargo type, constraint (3) prevents air- demandlinecantravelononeroute planes from lifting more that the demand availableandaccountsforanyextraliftcapac- ityavailable.Foreachroute,andeachstopon Calculated Sets thatroutethatisnotthelaststop,andeachcargo ðs;s#Þ2H stop s’ comes after, and within type, constraint (4) limits loading on the flight r departing that stop by the airplane capacity for maxloadhops of, stop s on route r: 1#s,s##len ,s#2s#maxloadhops each cargo type, for the configuration used on r thatroute.Foreachairfield,constraint(5)limits totaldailylandingsbyallroutesselected;note Variables that each route may land at an airfield more thanonce,andmaycarryportionsofsomede- SELECTr integer number of times airplane mandlineontwoormorelegs. typep(r)isflownonrouter Inthespecialcasewheremaxloadhops¼1, LOADrss#c integer cargo units airlifted by air- thecapacityavailableoneachflightlegonaroute plane type p(r) flying route r from isjustthecapacityoftheaircraftassignedtothe APOE airfield s to APOD airfield route,becausetheaircraftiscompletelyemptied s#ofcargotypec at each stop on the route. We can simplify the model and eliminate many constraints and all oftheLOAD variablesby defining anewset of ATEM-ILP Formulation variables, called EXTRA, that measure the un- usedcapacityoneachlegofeachrouteselected. X Maximize cpaðr;sÞaðr;s#ÞcLOADrss#c (1) The ‘‘Solving ATEM’’ section of this paper r;ðs;s#Þ2Hr;c more fully discusses the benefits of this Subjectto: simplification. X SELECTr#planespai "ai 2A;p2Pai (2) New Variables r2Rpai X EXTRA unusedcapacityofselectedroutes LOADrss#c#demaiajc "ðai;ajÞ2L;c forcargoc,oaniajcleg(cid:2)a;a(cid:3) r;s;s#: i j ðs;s#Þ2Hr; With these variables accounting for the overall aðr;sÞ5ai; loadingofeachlegontheroutewecanremove aðr;s#Þ5aj theLOADvariablesandreplaceconstraints(3) (3) and(4)with: Page38 MilitaryOperationsResearch,V18N32013 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Figure1. MapofIraqindicatingasampleofairfieldlocationsbydots.AlUdeid(located350nauticalmilestothesouth- east)inQatar,andIncirlik(located325nauticalmilestothenorthwest)inTurkey,arenotshown.(AfterNationalIm- agingandMappingAgency,2003;http://www.lib.utexas.edu/maps/middle_east_and_asia/iraq_planning_2003.jpg) Xcarry SELECT # dem which calculates the total carrying capacity of aiajcr r aiajc eachroute,andthensubtractsanyunusedcapac- r 1EXTRAaiajc "ðai;ajÞ2L;c; (6) itytoarriveatthetotalamountofcargolifted. which explicitly accounts for unused space on ATEMalsoallows,foreachaircraft,theselec- each flight in a route, and replace the objective tionofadifferentrouteoneachdayofamultiday functionwith: planninghorizon(e.g.,oneweek).Forsimplicity X ofexposition,wehavenotincludedadayindex, Maximize cp carry SELECT aiajc aiajcr r althoughoneexistsinATEM.However,because Xðai;ajÞ2L;c;r airplanesreturntotheirhomeairbaseaftereach 2 cp EXTRA ; (7) aiajc aiajc day offlying, the days in a plan areonly linked ðai;ajÞ2L;c bythecargoremainingtobelifted. MMiilliittaarryyOOppeerraattiioonnssRReesseeaarrcchh,,VV1188NN3322001133 PPaaggee3399 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN CENTCOM INTRATHEATER AIRLIFT Table1. Exampleofdemandlines,eachwithanor- igin and destination airfield, a number of PAX and Weconsiderthefrequencyandrequirement PALStocarry,andapriority.Thereare126passengers channel route selection problems faced by the andonepallettoflyfromAlSalemtoAlasad,withpri- CENTCOM Combined Air Operations Center orityone.Bycontrast,the44passengersandonepallet (CAOC), located at Al Udeid Air Force Base, toflyfromAlSalemtoTallilhavepriority100,signi- fyingeachofthesePAXandPALSis100timesmore nearDoha,Qatarin2005and2006. importanttocarrythanapriority1demand.Priority isasimplewaytohighlightfrustratedcargo.Thisde- Airfield Locations and Demand Data mandmaybeforaday,aweek,orsomelongerplan- ningepoch. Weusedabout20airfieldstosupportintra- theaterairdistributioninIraq,includingseveral APOE AOPD PAX PALS PRIORITY outsidethecountry;Figure1showslocationsof AlSalem Alasad 126 1 1 someofthesefordistributioninIraq.Table1pro- AlSalem AlTaq 159 1 1 videsanexcerptfromalongersheetofdemand AlSalem Balad 108 5 1 lines. Each demand line expresses the number AlSalem Baghdad 273 3 1 of PALS and PAX that need to be transported AlSalem Mosul 47 4 1 between an APOE and an APOD. A standard AlSalem Kirkuk 33 2 1 ‘‘463L’’ pallet is 88 inches long by 108 inches AlSalem QWest 5 3 1 wide, and each carries a maximum of 10,000 AlSalem AlSahra 51 1 1 pounds(DepartmentoftheArmy,1993).Apas- AlSalem Tallafar 52 2 1 sengerrepresentsasinglepersonandpersonal AlSalem Tallil 44 1 100 gear. AlSalem AlUdeid 113 8 1 Alasad AlSalem 117 1 1 Ouroverallobjectiveistomaximizethepri- Alasad AlTaq 17 3 1 oritizednumberofPAXandPALSlifted,where Alasad Balad 7 2 1 some PAX and PALS have different priority Alasad AlUdeid 5 2 1 than others (e.g., delayed, or frustrated, cargo AlTaq AlSalem 135 6 1 might be given a higher priority to encourage AlTaq Kuwait 1 7 1 clearing out the backlog). Each cargo type and AlTaq Alasad 14 17 1 eachindividualdemandlineisassignedapri- AlTaq Balad 2 2 1 ority.ATEMmultiplieseachdemandbyitscargo AlTaq Baghdad 2 1 1 type priority and by its line priority, and maxi- AlTaq AlUdeid 3 1 1 mizes the total resulting prioritized demand Balad AlSalem 288 3 1 thatismoved.Table1isanexampleofsuchde- Balad Kuwait 4 8 1 Balad Alasad 6 2 1 mand data, including demand line priorities. Balad AlTaq 7 5 1 Datapresentedinthistableandtheremaining Balad Baghdad 13 7 1 tables are a sample of possible ATEM input Balad Mosul 10 6 1 valuesprovidedbyCENTCOMplannersforun- classifieduse.Plannerscanchangethevaluesof theseATEMinputparametersatwillasthesitu- C-130J1,C-130J2,C-17(see Figure 4), and IL-76. ation dictates. Figure 2 presents a summary of Each airplane type, with the exception of the oneweekofdemandforpalletsandpassengers IL-76, can beflowninany ofanumberof alter- inIraq. nateconfigurations,witheachconfigurationpro- viding the passenger seat and pallet position Airplanes and Load Configurations capacities.Table2listsconfigurationsbyairplane type (with the exception of C-130J2) along with Thenumberandtypesofairplanesavailable associatedpassengerandpalletcapacities. fordistributionalsovaries,butusuallyconsisted Airplane and aircrew endurance limit the whenATEMwasfirstusedofabout35airplanes lengthofaroute,asshowninTable3,whichalso of five different types for CENTCOM intra- shows a sample of possible fuel and crew con- theaterairlift,includingC-130E(seeFigure3), straints that limit routes. ‘‘Max #landings in Page40 MilitaryOperationsResearch,V18N32013 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Figure 2. PALS and PAX demand for a seven-day Iraq scenario. Pallet demands are depicted in the upper, darkerbarsegments.Thereareabout20x20¼400airfieldpairs,butonly85ofthesehavedemandlineshere.De- mandlinesvarywidelyinmagnitude,andincludesomepure-passengerandsomepure-palletdemands.Airfield pairsaresuppressedforbrevity. box before recrew’’ represents the number of airplanehomeairfieldsandthenumbersofair- landings into a combat area, where approach planesbasedateach.Flyingtimesbetweenair- anddepartureinvolveevasivetacticalmaneu- fields are given for each airplane type. Other vers, and may be conducted at night without inputincludesthenumberoflandingspermit- lighting.Inadditiontotheseconstraints,plan- tedateachairfieldperday,aswellastheability nersalsolimitthemaximumnumberofstops of each airfield to accommodate each airplane anairplanecanmakeduringaroute.Forexam- type. ple, a C-17, which is nominally based outside Iraq, can make no more than three landings in Iraq before it needs to return to its home base. ROUTE GENERATION However,itcanrecrew,andreturntolandinIraq atmost threemore times before returningtoits Givendemanddata,afleetofairplaneswith homeairfield. theirhomeairfields,and a timehorizon,ATEM prescribes a configuration and a route for each Airfield Capabilities airplaneoneachdayintheplanninghorizonthat movesasmuchcargoaspossible. Table 4 is a sample of ground times at air- Acompleteflightensemblespecifiesaroute fieldsbyairplanetype.Similarly,Table5samples for each airplane on each day in the planning airfieldrefueltimesbyairplanetype.Table6lists horizon. We have discovered, by hand, that Figure3. C-130EatAlUdeid.Thetailrampispositionedtotransfercargopalletsbyforkliftorroll-on,roll-off k-loadervehicle.TheC-130hasasingleroller-railtrackformanuallypushingcargopalletsforward,oraft,oroff. Forscale,authorDellisstandingundertheinboardstarboardengine.Intheimageontheright,anaircrewmem- berfoldsuphammockseatsinaconfigurationchangetomakeroomforanothercargopallet. MMiilliittaarryyOOppeerraattiioonnssRReesseeaarrcchh,,VV1188NN3322001133 PPaaggee4411 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Figure4. C-17atAlUdeid.Theaftk-loadervehiclesarereceivingrowsofpassengerseatspushedoff(andaban- doneduntilalaterevolutionhere)inaconfigurationchangetoaccommodatemorecargopallets.TheC-17has two,parallelroller-railtracksformanuallypushingcargopalletsforward,oraft.Forscale,ontheright,authors BrauandDellappearstandingonthetailramp,workingthroughthedetailsofloadconfigurationchangeswith theairplane’sloadmaster. conjuring these routes while synchronously Givenaflighttimet . 0foreacharc(i,j)in ij determiningtheirjointfeasibilityandeffective- A,andathresholdvalueT[MAXROUTEHRS, nessisthecruxofsolvingthisproblem.Manual the pseudocode in Figure 5 enumerates the fi- planning experience suggests thumb rules that nitenumberofs-tpathsoflengthboundedbyT. canbeagoodguidehere,butnomanualplanner Forsimplicityofexposition,wedonotclut- can be expected to solve this complex problem terthisalgorithmwiththeadmissibilitytestsfor everydaywithanythingapproachingoptimality. refuelingrequirementsalongtheroute,themin- Thereareanumberofwell-knownwaystoauto- imumandmaximumroutelengths,orthemax- mate route construction. In this case, there are imum number of flights (hops) per route (see few enough airfields, and few enough demand Table 3 for examples of these data). However, lines, and each route can include at most few thesetestsareeasilyincludedatthesamepoint enoughhops,thatwecanenumerateeveryfeasi- inthealgorithm asthetestfor totalroutetime. bleroute,andthusnotworryaboutmissingany Although in general the number of paths in a good one. For each airplane and its origin air- single graph can be exponential in the number field,ATEMsuccessivelyconstructseverypossi- ofnodesinthegraph,fortheOIFandOEFcases ble permutation of airfield-hops that can be wehaveexaminedwecanaccommodateexhaus- visitedinonedutyperiod,endingwithareturn tive enumeration. With data similarto thatpre- totheoriginairfield.Simplerules,suchasnever sented here, we generate on the order of a few flyingtwodeadheadlegsinarow,helplimitthe hundredthousandfeasibleroutes. number of routes. Additional rules eliminate Filteringroutestolimittheminimumnum- routeslackingarequiredrefuelorcrewreplace- berof hops,the maximum numberof landings mentevent. ‘‘in the box,’’ and so forth, is a simple matter WedefineadirectedgraphG¼(N,A)with ofkeepingtrackofthesenumbers,suppressing node set N defined by a start node s, an end thecompleteroutesthatdonotmeetthelower node t (here, s ¼ t), and an intermediate eche- thresholdsandfathomingenumerationofpar- lon of nodes for every stop on a route up to tial paths as soon as they exceed the upper maxroutehops-1.Forspecificity,eachofthesein- thresholds. termediatenodesisnamed(airfield,hopnum- Routes are generated separately for each ber).WespecifyadirectedarcinAconnecting airplanetypeandeachorigin homeairfield for eachnodewith‘‘hopnumber’’witheveryother that airplane type. Any route longer than the nodewith‘‘hopnumber11’’towhichwemight given maximum time before refueling for that flydirectly. airplanetyperequiresa(single)stopatarefueling Page42 MilitaryOperationsResearch,V18N32013 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Table2. Loadconfigurationsbyairplanetypewith ensemblecouldbeusedasaninitialincumbent passengerandpalletcapacities.AC-130Ehaspassen- for a local search heuristic. However, we seek gerhammockseatsthatcanbefoldedupormovedout a certificate of optimality for our solutions, so ofthewaytomakeroomforcargopalletstobepushed weusetheintegerlinearprograminthe‘‘ATEM aboardonarollerrailandcancarrybetweenzeroand integer linear program formulation’’ section to fivecargopalletswitheachadditionalpalletconfigura- chooseanoptimalsetofroutes(outofallfeasible tionreducingpassengercapacityindiscretestepsfrom routes)andtoestablishanupperboundonhow 72 down to nine. Configuration changes don’t take muchadditionalcargocouldhavebeenmoved. long,andsomecanbecompletedin-flightinanticipa- tionofthenextload.Bycontrast,theC-17hastwopar- allel cargo pallet roller rails, and some configuration changesrequirerowsofpassengerseatsmountedon SOLVING ATEM theserailstoberolledoffandleftonairfield,tobere- coveredlater.Theseconfigurationchangesare better The ATEM integer linear programming assisted by special ground vehicles called k-loaders. model has hundreds of thousands of variables The IL-76 is chartered to carry pallets only. (Not andconstraintsfortheoptimizationmodelwith listed:C-130J2.) throughput,andtensofthousandsofconstraints Airplane Passenger Pallet for the reformulation without. If throughput is Configuration type capacity capacity notallowedwecansolveallofourproblemin- stances using, e.g., GAMS/CPLEX [2012]. If we Acp2 C-130E 9 5 allow throughput (i.e., maxloadhops . 1), then Acp3 C-130E 25 4 theintegerprogramsbecomesignificantlylarger Acp4 C-130E 42 3 duetothequadraticdependenceonmaxloadhops Acp5 C-130E 56 2 of the number of LOAD variables. Some cases ap1 C-130E 72 0 canstillbesolvedwithCPLEX,butwefindthat jac2 C-130J1 0 8 Jacp2 C-130J1 18 7 theexecutiontimesaremuchlongerthaninthe Jacp3 C-130J1 34 6 case of no throughput. Schedulers do not have Jacp4 C-130J1 50 5 immediate access to commercial solvers, so we Jacp5 C-130J1 60 4 developed a companion heuristic algorithm to Jacp6 C-130J1 74 3 provide good solutions to ATEM in a very Jacp7 C-130J1 94 2 short runtime. Our basic heuristic consists of jap1 C-130J1 115 1 data preprocessing followed by greedy selec- C17c C-17 0 18 tion of routes. The preprocessing reduces de- C17cp C-17 54 11 mand lines that appear on routes that may C17p C-17 189 4 have been fixed by the planner. Aftergenerat- Ilc IL-76 0 9 ing all of the routes a greedy heuristic makes a single pass through the list of aircraft (and their home cities) and for each of those and airfieldbetweenminimumtimebeforerefueland foreachdayintheplanninghorizonitchooses maximumtimebeforerefuel.Similarly,foranair- theroutethatmaximizesliftofremainingcargo plane type with a crew replacement restriction (withoutthroughput)onthatroute,assignsthat (i.e.,maximumnumberoflandingsintheboxbe- route to that aircraft on that day, and then forecrewreplacementisasmallinteger,suchas removes that lifted cargo from those demand three)anyroutemustreturntoitsoriginairfield lines.IncontrastwiththeILP,theheuristicdoes beforethenumberoflandingsatairfields‘‘inthe not consider throughput. Bridges [2006] de- box’’followingthelastlandingattheoriginair- scribes two additional iterative improvement fieldexceedsthislimit.Routesviolatingeitherre- stepstoimproveagreedysolution.Healsocon- quirementaresuppressed. siders generalizing relaxations including air- Wefindthatselectingafeasibleensembleof plane configuration changes during a route, routes that moves a large amount of cargo is andthroughput. relatively straightforward once we have enu- The results worksheet (Figure 6) serves as merated all the feasible routes. This feasible bothanoutputdisplayandanimportantinput. MMiilliittaarryyOOppeerraattiioonnssRReesseeaarrcchh,,VV1188NN3322001133 PPaaggee4433 OPTIMIZINGINTRATHEATERMILITARYAIRLIFTINIRAQANDAFGHANISTAN Table3. Routelimitationsbyairplanetype.Limitationsincludethemaximumtimeanairplanecanoperate,time betweenrefueling,numberoflandingsinthebox,andnumberoftimesanairplanecanreplaceaircrews.Each routeforeachairplanetypeisalsolimitedbysomeMaxRouteHopsnumberoflandings. Airplanetype C-17 C-130E C-130J1 C-130J2 IL-76 Maxroutetime(hrs) 12.00 9.50 9.50 9.50 12.00 Maxtimebeforerefuel(hrs) 12.00 5.00 5.00 5.00 12.00 Mintimebeforerefuel(hrs) 12.00 3.00 3.00 3.00 12.00 Max#landingsinboxbeforerecrew 3 20 20 20 20 Maxnumberrecrews 1 0 0 0 0 TheplannercanuseATEMrepeatedlytorefine EXAMPLES a plan. The planner can designate the first col- umnofafavoredroutewith‘‘fix’’andthenum- Wepresentfourrepresentativescenariosof ber of days the route will be repeated by a intratheater airlift for Iraq and Afghanistan in specificairplane.SubsequentATEMrouterevi- 2005 and 2006. The first and smallest of these sions will honor this guidance. These distin- isasingle-dayrequirementforlogisticsdistri- guished routes have either been automatically butiontoandwithinAfghanistan.Oursecond generated by ATEM, or manually entered by scenario is for a seven-day planning horizon theplanner.BecauseATEMconsidersalladmis- thatsuggestsfrequencychannelsinIraq.Next, sibleroutes,theonlyreasonforaplannertokey wetestalarge,single-daydistributionrequire- inarouteistoviolatesomebusinessruleATEM ment within Iraq. Finally, we show how to wouldhonor. parametrically remove airplanes from a chan- The routes selected worksheet in Figure 7 nel design. The ATEM-ILP integer linear pro- will indicate a planned refueling by a prefix, gram is generated by GAMS (2012) and solved for example, ‘‘F_Al_Salem.’’ A planned crew- withGAMS/CPLEX12.3(2012)ona3-GHzlap- replacementeventwouldappear‘‘C_Al_Salem.’’ top,usingavalueof0.01fortherelativeoptimal- Ifanypassengerorcargoiscarriedformorethan itycriterion (CPLEXterminates afterfindinga onehop,thisexceptionwouldappearasaninter- solution that is guaranteed to be within 1% of mediate line tracing the throughput in addition optimal). tothecustomaryone-hopresultsshown. Table5. Sampleofairfieldrefuelingtimes.Refuel- ingisconcurrentwithgroundtime.Forexample,if Table 4. Sample of airfield ground times. Ground aC-17requiresrefuelinginBalad,itstotalground timevariesbyairfieldandairplanetype.Inthisexam- time is 90 minutes. All other airplanes require 75 ple,aC-17requires45minutesonthegroundatBalad, minutesonthegroundtorefuelatBalad.An‘‘n’’in- while all other airplane types require 30 dicates that the airplane type cannot refuel at minutesthere. thatairfield. Groundtime(mins) Refueltime(mins) Airfield C-17 C-130E C-130J1 C-130J2 IL-76 Airfield C-17 C-130E C-130J1 C-130J2 IL-76 Alasad 45 60 60 60 60 Alasad 90 60 60 60 60 AlTaq 45 30 30 30 30 AlTaq 90 60 60 60 60 Balad 45 30 30 30 30 Balad 90 75 75 75 75 Baghdad 45 60 60 60 60 Baghdad 90 90 90 90 90 Mosul 45 30 30 30 30 Mosul n n n n n Kirkuk 45 45 45 45 45 Kirkuk 90 75 76 77 77 Basrah 45 45 45 45 45 Basrah n n n n n QWest 45 45 45 45 45 QWest n n n n n AlSahra 45 30 30 30 30 AlSahra n n n n n Page44 MilitaryOperationsResearch,V18N32013