# A tabu search approach to the strategic mobility mode selection problem.

Introduction

The efficient and effective solution to the Strategic Mobility Mode Selection Problem (SMMSP) is essential to the effective and efficient force projection of the US Military. The SM Mode Selection (SMMS) process assigns a transportation mode to personnel and materiel for shipment from CONUS to OCONUS. A foundation of the National Military Strategy (1) is to maintain most forces in CONUS while being prepared for OCONUS missions. (2) On demand, a previously constructed plan, the mission's time-phased force deployment data (TPFDD) (3) is executed to move specified personnel and cargo to designated locations. A TPFDD stipulates the timely deployment of personnel and cargo to the best mission locations.

The next section describes the basic SMMSP, presents a small example, and outlines the objectives of the research documented in this article.

The SMMSP

The TPFDD's sequence and timing is critical not only to mission accomplishment, but also to the safety of personnel and cargo in an OCONUS operational area or port of debarkation (POD). The multitrip reuse of aircraft and ships traveling from ports of embarkation (POE) in CONUS to OCONUS PODs and the presence of time window constraints, as described below, causes the SMMSP to be a variant of the vehicle routing problem with time windows. (4)

Other TPFDD restrictions such as the CONUS origin ready to load date (RLD), POE available load date (ALD), POD earliest arrival date (EAD), POD latest arrival date (LAD) and final destination required delivery date (RDD) are also present. These dates are time sequenced and are often mutually dependent. The RLD, ALD and EAD are hard constraints. The LAD and RDD are soft constraints.

In SM modeling, early completion is only one part of a multicriteria objective. A primary goal of an SM model is to meet the LADs. As presented in Figure 1, any arrival between the EADLAD time window is sufficient. It is also desirable to minimize vehicle usage, especially aircraft use. If the LADs cannot be met, a secondary objective, minimizing lateness (violations of LADs) and required resources, is invoked.

[FIGURE 1 OMITTED]

A TPFDD is presented at six different levels of detail. (5) The tabu search (TS) method documented here provides asset level visibility and operates at TPFDD Level 3. The generic reference to a TPFDD item is a requirement line number (RLN). All passengers (PAX) must be transported by air. Cargo not transportable by air is restricted to ships. Most items may be assigned either mode and the most appropriate should be selected. After RLN mode selection is completed, RLNs must be scheduled for transport at specific POEs on specific aircraft or ships, at specific times and dates. The aircraft or ship assignment implies a specific POD.

Motivation

Current SM models do not efficiently assign the transportation modes for RLNs, employing either prestipulated modes or myopic methods. A complete and detailed review of such models is presented by McKinzie and Barnes. (6) Three of these are the Deployment Network Tool Extended (DANTE) (7), Strategic Transportation Quick Look (STQL) (8) and Joint Flow and Analysis System for Transportation (JFAST) Link. (9) As shown in this article, the results from these models can be significantly improved upon by the application of modem direct search.

Problem Statement

We assume the following information is specified.

* Aircraft and ship quantities, availability dates, and types at each starting location.

* Open ports (POE and POD) for transportation.

We assume the following information is given in TPFDD (Level 3) format: For each

* RLN: Origin, destination, RLD, ALD, EAD, LAD, RDD, size, priority, and whether contents are hazardous.

* Aircraft or ship: capacity, speed, range, type.

* Port: ship and aircraft capacities, fuel and refuel capacities, maximum aircraft on ground and berths, number of takeoffs and landings per day, and on- off- load capabilities.

Conversations with subject matter experts (10) reveal that, from a command viewpoint, a RLN's priority is, de facto, its LAD. However, one RLN of 350 lbs arriving one day late is not equivalent to an RLN of 13 Stons arriving one day late. A simple yet representative method of calculating lateness is to multiply Stons by days late. In addition, the relatively low number of aircraft and their significantly higher cost per trip compared to ships must be considered. Hence, the consensus was that the objective function value for the SMMSP should be computed by adding: (1) the total number of ship trip legs, (2) ten times the number of aircraft legs, and (3) for each RLN, the LAD violation time in days multiplied by its Stons.

For example, ten aircraft trips, ten ship trips, and three RLNs of 50 Stons each arriving 3 days late would yield an objective function value of 560 units.

A Small SMMSP

Tables 1 through 6 present a schedule generated by JFAST for 17 RLNs that were extracted from a contingency deployment to Tunisia. All columns are self explanatory except for column M which indicates the item transport mode (X--item not moved, P --optional mode, S--sea mode, A--air mode).

Table 1's first RLN, 05AAL, is designated for air transport and weighs 882 Stons. (PAX are allocated one-fifth Ston per individual). Since strategic aircraft carry no more than 92 Stons, 05AAL requires at least ten aircraft. Strategic ships can haul at least 18,000 Stons, but require 2 or more weeks to travel from CONUS to Jerba-Zarzis, Tunisia (JEAH). 05AAL's LAD is day 100 and it can depart on day 0.

Table 2 lists the 11 PAX RLNs that must travel by air. (05BC needs no transport because it is at its destination. This type of superfluous content is not unusual in a typical TPFFD.) The remaining ten RLNs depart from six different POEs and arrive at three PODs. Given sufficient pressurized aircraft, Table 3 shows one possible valid on time schedule. Table 4 details the remaining 5 RLNs to be scheduled. (02CB's current OCONUS location (CWFA) is in Italy and need not be considered for strategic transport.)

Of the remaining five items, one is scheduled for air, three for sea, and 01AAC's mode is optional. However, since 01AAC's POE (ZBES) and POD (FTZH) are both sea ports, its mode is changed to S. If the designated POE and POD could be modified, it is possible that 01AAC's mode could be changed to air. Tables 5 and 6 detail the remaining air and sea transport. The RLNs in Table 6 depart from ZBES (Wilmington, NC) and LCMT (Houston, TX) and all planned departures embody trivial loads that will arrive after their LAD.

This example uses only 17 RLNs. A typical TPFDD has over 4,000 RLNs. Since JFAST was used, no heuristic was employed to improve the solution either by (1) rearranging RLNs within their assigned POEs or PODs, (2) by moving RLNs to another POE or POD or (3) by exercising possible transport mode changes. As described below, utilizing such options can greatly improve the solution associated with any set of cargo.

Research Goals

The primary goals of the research documented here were to:

* Develop methods for producing a suite of excellent solutions to any instance of the SMMSP.

* Produce a model for the SMMSP that allows reusability of the model within the various SMMS models used by the Department of Defense (DoD).

* Conduct a comparison of our TS methods to an existing SM method.

Goal 1 was accomplished with an Adaptive Tabu Search (ATS) approach, ATS-SMMSP, where an adaptive neighborhood schema reallocated one or more RLNs from one transportation asset to another. Goal 2 was addressed implementing the model in JAVA. Finally, goal 3 was achieved by comparing the results of ATS-SMMSP to those of JFAST.

The remainder of this article consists of four sections. The second section recounts several relevant SM models, overviews pertinent associated TS topics and reviews associated military applications of TS. The third section presents a small example of a SMMSP and describes the ATS-SMMSP. The fourth section presents a comparison of results of the ATS-SMMSP and JFAST

The final section presents conclusions and proposes additional areas of investigation.

A Review of SM Literature and Associated TS Approaches

This section reviews available SM literature and the three aspects of TS most relevant to this research.

SM Models Overview

SMMSP literature is principally found in military publications and in unpublished information residing in the community of users and programmers of specific mobility models. SM models differ in sponsoring organizations, operating systems, ease of use, interoperability with other models, input and output interfaces, mode selection capability, level of detail, mission profile versatility, and computational efficiency. Where appropriate, these criteria will be addressed in the following sections. A detailed review of current and legacy models may be found in McKinzie and Barnes. (11)

High Level SM Models with No Mode Selection

This class of quick look models is employed in early planning, uses only regional origin and destination designations, uses approximate travel distances, combines unit equipment and resupplies, allows only macroscopic decisions, and provides a broad understanding of required time frames for timely delivery of all items. These models provide an early assessment of planning feasibility and the need for a redesign of the plan.

Examples of such tools are the Deployment Network Tool Extended (DANTE), (12, 13) JFAST-Link (14) and the Strategic Transportation Quick Look (STQL). (15)

Level IV SM Models (With Mode Selection)

This class of models includes:

* The Global Deployment Analysis System (GDAS), which provides extensive capabilities for analysis but can require a significant amount of time and effort to tailor it to a specific model. GDAS performs a deterministic simulation to determine the actual arrival, departure, loading, unloading, and queuing events at each facility.

* JFAST, the model of choice for the detailed planning community. JFAST is High Level Architecture-compliant and includes a TPFDD editor.

* The Model for Intertheater Deployment By Air and Sea (MIDAS), where all input and output files must be viewed and edited as flat files. The intense complexity of the MIDAS model presents a significant roadblock for many planners who have little experience and education in modeling. MIDAS's mode selection first assigns all cargo (except nonair transportable materiel) to aircraft. If available aircraft cannot feasibly transport all RLNs, all RLNs that can meet their RDD when moved by ship (Ship-RDD RLNs) are identified and MIDAS begins to assign such Ship-RDD RLNs to ships. MIDAS can produce schedules with individual aircraft tail numbers and can track RLN Level 6 detail.

* The private proprietary, expensive Mobility Simulation Model (MobSim), is portable and easy to use, consisting of a simulation tool that models multiple modes of transportation. MobSim reports the first feasible solution found unless instructed to report a global optimal solution. If a global optimum is required, MobSim attempts to secure it through exhaustive search. (16) Although a feasible solution can be reported in minutes, an excellent solution will usually not be found in an acceptable amount of time.

Tabu Search

In this section, aspects of TS particularly relevant to the SMMSP are discussed and an overview of historical TS applied to military combinatorial optimization problems is presented.

Classical applications of TS have focused primarily on the solution of combinatorial optimization problems. (17) The numerous TS successes are attributable to several characteristics including TS's abilities to traverse infeasible solution space regions and to escape local optima.

TS guides the search by recording attributes of visited solutions and forbidding return to such solutions before tabu tenure iterations have occurred. TS repeatedly chooses the best non-tabu solution from a predefined neighborhood of solutions until a termination condition is met. While early TS implementations used a static constant tabu tenure, advanced tabu memory structures can dynamically determine the tabu tenure for a solution or class of solutions. (18,19) TS can also be enhanced through the use of intensification and diversification strategies. (20, 21)

ATS-SMMSP uses a simple dynamic memory structure that defines a minimal, maximal, and initial tabu tenure. While enforcing the tenure extremes, an improving move yields a tabu tenure increment and a nonimproving move yields a decrement to the tabu tenure. (22) This simple enhancement to the TS memory structure can result in marked improvements in efficiency and effectiveness of a TS approach.

Battitti and Tecchiolli (23) introduced a more powerful dynamic TS memory structure, reactive TS (RTS). The number of repeated solution visitations is recorded. When solutions are repeated frequently, the tabu tenure is increased rapidly. The tabu tenure is quickly decreased when solutions are not frequently repeated. They also implemented a diversification escape technique that is used when "there is evidence that the system is in a complex attractor of the search space." (24) and Nanry and Barnes (25) developed advanced applications of RTS.

Related TS Applications

The TS implementations briefly discussed in this section were developed to solve complex military problems. These and the application presented in this article were built under the aegis of an ongoing consortium consisting of representatives from The University of Texas, the Air Force Institute of Technology, the Air Mobility Command and the Air Force Office of Scientific Research. These models greatly improve upon previous approaches by providing near optimal solutions in remarkably small amounts of time.

The Aerial Fleet Refueling Problem (AFRP) (26) is concerned with inflight refueling of a fleet of Air Force aircraft. The associated TS approach addressed a multicriteria set of goals and dramatically reduced the time and resources required for solution. In a typical large scale deployment scenario, the TS AFRP methodology yielded an ensemble of excellent solutions in about 4 hours. Previous methods required a team of analysts months to obtain a workable solution.

The Aerial Fleet Crew Scheduling Problem (AFCSP) (27,28) complements the TS AFRP model. The TS AFCSP model addresses the scheduling of the crews that operate associated AFRP aircraft and significantly improves the solutions found from current methods in remarkably short periods of time.

The Theater Distribution Vehicle Routing and Scheduling Problem (TDVRSP) model (29) uses an abstract algebraic view. Once the cargo or passenger arrives at the POD, each must be moved to the final destination. The TS TDVRSP model maintains total asset visibility and intransit visibility of vehicle assets and is a much more efficient and effective solution methodology than previous approaches. Although the US Air Force once deemed the TDVRSP too difficult for optimization, this new TS technique has shown that statement to be incorrect.

The ATS approach to the Strategic Airlift Problem (SAP) (30) produces detailed routing and scheduling of strategic airlift resources which are dramatically superior to the current approach embodied in Air Mobility Operations Simulator. This approach extends the dynamic neighborhood selection methodology first developed by Harwig. (31)

The SAP is a component of the SMMSP. ATS-SMMSP stipulates the mode of transport for each RLN and assigns RLNs to vehicles at a more macroscopic level than the SAP. The TS SAP model requires the prior stipulation of what items will be transported by air and focuses, in a more detailed manner, on solving the routing and scheduling of air movement. In addition to the SAP, the SMMSP solves the Strategic Sealift Problem at a macroscopic level.

TS and SM

The SMMSP is a large combinatorial optimization problem with partitioning, scheduling, and routing aspects. Partitioning occurs in the assignment of RLNs to a particular mode of transportation. Scheduling is inherent in the assignment of RLNs to particular POEs, PODs, and departure days. In addition to the RLNs being routed from their origin, POE, POD, and finally to their destination, the vehicles moving these RLNs are also scheduled and routed over multiple trips during the deployment operations. Each time the RLN reassignment causes a change in departure day or number of vehicles required for movement on a given day, the vehicles are rerouted.

Current models use greedy procedures to obtain feasible solutions to the problem. Classical optimization methods are incapable of providing timely solutions; thus, this problem is ideally suited for a TS approach. The next section details the ATS-SMMSP algorithm developed in this research.

The ATS-SMMSP Algorithm--Modeling and Methodology

A TPFDD stipulates all needed information for the transport of cargo for a given contingency and the solution of the SMMSP yields a redefinition of a TPFDD.

Two Representations of the SMMSP

There are two SMMSP solution representations using either vehicle routing or RLN routing. The vehicle routing representation groups the time stamps, paths, and RLNs by vehicle. The RLN routing representation groups the RLNs by POE, departure day, and POD. The small SMMSP example of Table 1 illustrated the RLN routing representation. Table 7 presents a vehicle routing solution representation of another small example which uses two wide-body planes (WBPs) and one B-747P to route the RLNs. Table 8 presents an equivalent RLN routing representation for the example of Table 7.

Both WBPs' maximum load is 59 Stons and the B-747P's maximum load is 93 Stons. All aircraft are available on day 0 at POE WW-YK (Tinker Air Force Base, OK). WBP-1 performs five trips. After flying to NRCH (Loring Air Fore Base, Maine), WBP-1 's first trip is on day 7 with one RLN of 2 Stons. After delivering cargo to AEQT (Algeciras [Gibraltar], Spain), it returns to PTFL (McGuire Air Force Base, NJ) and picks up 35 Stons on day 20 and unloads at AEQT on day 22. It then returns to PTFL, picks up 48 Stons on day 30 and delivers it to VRJT (Sigonella, Italy). Returning to NRCH, it picks up 6 Stons on day 34 and delivers it to AEQT. Finally WBP-1 returns to NRCH picking up 3 Stons on day 46 and delivering to AEQT. WBP-1's total routing was {Port (day, Ston)}: WWYK(0,0)--NRCH(7,2)--AEQT(9,0)--PTFL(20,35) --AEQT(22,0)--PTFL(28,48)--VRJT(30,0)--NRCH(34,6) --AEQT(36,0)--NRCH(46,3)--AEQT(48,0).

The second WBP performs a single trip with routing WWYK(0,0)--PTFL(35,14)--AEQT(37,0). The last aircraft, B-747P-1 performs three trips with a routing of WWYK(0,0)--PTFL(35,93) --AEQT(37,0)--NRCH(46,10)--UMXB(48,0)--NRCH(53,3) --AEQT(55,0).

This small example addresses only nine RLNs. Typical problems address thousands of RLNs and the inherent complexity of the SMMSP precludes the use of classical optimization methods. A heuristic approach that obtains an excellent solution in a relatively short amount of time is superior to either a poor solution achieved more quickly or to a provably optimal solution that requires insupportable time and effort. A direct search approach, like ATS, can successfully manage the presence of the many time window constraints and still track each RLN and vehicle as a unique entity.

An ATS Approach to the SMMSP

The highly successful applications of ATS to complex military logistics problems reviewed in Section 2 led to the use of ATS for this research. While TS does not guarantee an optimal solution, a well constructed TS methodology uses aspects of the problem structure to achieve excellent solutions with supportable computational effort. The ATS approach described in this section monitors such things as late arriving RLNs, time window flexibility and the number and type of transport vehicles available to enhance the search process.

The DoD hierarchically delegates authority to several levels of command. Within SM planning, associated commands coordinate priorities and interests and reach agreements regarding RLNs and transportation assets. Commanders specify RLN ports and modes and are very resistant to change. For this reason, the ATS-SMMSP performs three stages of analysis. Stage 1 solves the SMMSP preserving the commanders' port and mode assignments. Stage 2 preserves specified transport modes but allows RLN POE and POD changes. Stage 3 allows RLN port and transport mode changes. Stage 2 and 3 solutions may be used to demonstrate the improved solutions available for commanders willing to relax some of their preferences.

The ATS-SMMSP solution representation lists each RLN with its (POE/departure-day/POD) triplet. Since each POE (POD) is either an air or sea port, any RLN port assignment defines the mode of transport. Known transit times imply that any departure day stipulates the arrival day and directly allows accounting for any LAD violations. All ATS-SMMSP search neighborhoods allow and penalize delivery after the LAD, but strictly prohibit violations of RLD and EAD. RLN transport priority is dictated by the earliest LAD.

The software implementation of the ATS-SMMSP methodology is divided into three parts: (1) Input focuses on data validity, (2) ATS performs scheduling and assignment and (3) Output presents the new TPFDD generated by the ATS-SMMSP.

ATS-SMMSP Input

ATS-SMMSP requires six data files. The first three contain information associated with airplanes, ships and geographic locations. The airplane information includes the airplane type, maximum and minimum loads, speed, and size limitations. Due to the numerous ship configurations, only averages for ship types are available. For each ship type, the ship information also includes the speed, maximum and minimum draft, loading time and maximum load. The geographic location information is used for location verification and for time and distance calculations.

The remaining three contingency-specific files are the TPFDD, Vehicles Available, and Open Ports. The initial location, type, and available date of all vehicles are provided in the Vehicles Available file. TPFDD and Open Port files must be checked for validity and completeness. Some TPFDD errors and omissions can be easily corrected. For example, if a port indicated by a TPFDD is not an open port for a scenario, it is replaced with the closest open port in the port file. Another example would be when a POE-POD pair are incompatible mode types and require correction.

Scheduling and Assignment

As detailed by McKinzie, (32) prior to search commencement, the validated TPFDD file is used to create an initial ATS-SMMSP solution. This is performed by having RLNs move precisely as stated in the TPFDD, departing their TPFDD-designated POEs on the designated available load dates. Vehicles are greedily assigned to the triplets in order of earliest departure day, by first available vehicle. The initial solution is usually not good with many RLNs arriving late and many vehicles transporting trivial loads. This and other types of solution deficiencies are corrected by the ATS-SMMSP.

This greedy assignment is illustrated by the small example in Table 8 which, without loss of generality, considers only PAX. Two POEs are used--NRCH (Loring AFB, Maine) and PTFL (McGuire AFB, NJ). First, consider the RLNs at NRCH. On day 7, aircraft 5 departs with 5HJAV carrying a trivial load of two Stons. On day 34, aircraft 0 departs with 5HCAS (six Stons). On day 46, aircraft 8 transports three Stons to AEQT and aircraft 9 transports ten Stons to UMXB. Finally on day 53, aircraft 7 transports three Stons. Now, focusing on PTFL, aircraft 23 departs on day 20 with 35 Stons and aircraft 29 departs on day 28 with 48 Stons. On day 35, aircraft 24 and 10 transport 0EDB with a total of 107 Stons. Aircraft 24 is maximally loaded with 92 Stons and aircraft 10 transports the remaining 15 Stons. Each mission except PTFL mission 2 is far below their 50 percent trivial load weight.

This greedy assignment used nine aircraft trips for eight missions. The only temporally overlapping trips depart on day 46 and on days 34 and 35. The nine trips could have been accomplished using three unique aircraft. The cost of moving the RLNs would be the same and six aircraft would remain free for other uses such as providing earlier transport for RLNs that would arrive later than their LADs. Additional significant gains in efficiency could also be possible if the LADs would allow RLN aggregation onto fewer aircraft without increasing lateness.

ATS-SMMSP Search Stages

Stage 1 uses two phases to seek improvements without changing predefined ports or modes by considering moves in defined search neighborhoods. The best qualifying (non-tabu or aspiration satisfying) neighbor becomes the new incumbent solution. Phase I considers only late RLNs ordered by descending lateness penalty (days late times RLN Stons). Table 9 expands Table 8 providing ALD, EAD, and LAD detail. The three late RLNs are considered in the order 5WYH4 C, 5HCAJ, and 5HEBA.

Phase I examines late RLN using a port-pair neighborhood. Since 5WYH4 C has the unique port-pair NRCH-UMXB, it has no moves available. 5HCAJ and 5HEBA have port pair NRCH-AEQT. Hence, 5HCAJ has three possible moves. Moving to NRCH-7-AEQT is rejected for ALD violation. Moving 5HCAJ to NRCH-34-AEQT yields an arrival 12 days earlier (a lateness decrease of 36 Ston-days) and is the best current move. Moving to NRCH-53-AEQT adds seven more days delay and is discarded.

5HEBA is nine days late. Moving to NRCH-7-AEQT is discarded for ALD violation but moving to NRCH-34-AEQT yields a total lateness reduction of 37 Ston-days, the new best move. Moving to NRCH-46-AEQT yields a lesser reduction of 31 units and is discarded.

Following the complete neighborhood evaluation, the best move is executed. Phase I is applied until no moves exist. For our example, this yields the results of Table 10 with a lateness of 145 with seven aircraft used.

Phase II differs from Phase I only in the search neighborhood which does not require lateness and consists of the smaller of 10 percent of all RLNs or 100 RLNs. The RLNs are considered in ascending order by RLN Stons and alphabetically within equal Stons. For the current example, the list for Phase II is 5HJAV, 5HCAJ, 5HEBA, 5WYH4 B, 5WYH4 C, 5HCAS, 6ACBP, 0FBB, and 0EDB.

Phase II completes Stage 1 and yields the results in Table 11 with a lateness of 135 using six aircraft. Stage 1 reduced lateness by 93 units and three fewer aircraft are required. The best solution from Stage 1 is the initial solution for Stage 2 where pre-selected ports are not enforced. This is the first algorithm to allow improving port selections in an automated approach.

In Stage 2, logistical restrictions limit the distance to new replacement ports. Better security and transportation allow 700 miles in CONUS as opposed to 200 miles in OCONUS. As presented in the psuedocode of Figure 2, at each iteration, all RLNs are considered and the best allowable move is executed. The Stage 2 neighborhood is much larger than its Stage 1 counterpart because it considers all RLNs and relaxes the constraint that preserves port-pairs. The Stage 2 maximum time limit encompasses both Stage 2 and Stage 1.

Continuing with the example of Tables 9 through 12, POE NRCH is close enough to PTFL and to several other POEs for RLNs to move to a different triplet using any of these POEs. Similarly, because they are within 200 miles of one another, POD UMXB (Rota, Spain) and POD AEQT can be used interchangeably. All RLNs except 0FBB at PTFL-28-VRJT are current candidates for port change.

Table 12 presents the results for Stage 2. NRCH-7-AEQT, NRCH-46-AEQT, NRCH-53-AEQT and PTFL-28-VRJT are unchanged. 5HCAJ moved to PTFL-20-AEQT (changing its POE) and arrived on time at a cost savings of 15. 5WYH4 C moved to NRCH-34-AEQT (changing its POD) for a cost savings of 60 and 5WYH4 B moved to PTFL-35-AEQT reducing aircraft usage by one. At this point, no RLN is late and the total penalty of 50 units is due to the five required aircraft

In Stage 3, transportation modes may be altered. Our small PAX example restricted all RLNs to air transport. Only cargo RLNs may change modes, which implies a port change for our mode-specific ports. Figure 3 presents a high-level pseudo code for Stage 3. The maximum time-stopping criteria includes the time consumed by all three stages.

Other ATS-SMMSP Considerations

The ATS-SMMSP tabu memory structure is straightforward. An RLN may not be moved if it has been moved within the last tabu tenure iterations. The aspiration criterion allows tabu RLNs to move only if that would produce the best solution found so far in the search. Each RLN in the current search neighborhood is evaluated and the best allowable move yields the new incumbent solution. The tabu tenure varies in each stage. The initial tabu tenure is one-tenth the size of the candidate list of RLNs. The tabu tenure adaptively changes by decrementing with an improving move and incrementing with a nonimproving move. This adaptive procedure aids in intensifying and diversifying the search relative to a myopic measure of search history. (33)

McKinzie (34) presents a detailed discussion of the stopping criteria used in the ATS-SMMSP algorithm. These stopping criteria were based on total iterations, iterations since the best solution, iterations since an improved solution, and the total computation time.

ATS-SMMSP Outputs

Two of the three outputs from the ATS-SMMSP algorithm, the vehicle routing solution representation and the RLN triplet solution representation, have been presented above. The final type of output is a Joint Planning and Execution System (35) B-8 TPFDD which contains the information required by JFAST, the model used for discussing comparative results in the next section.

ATS-SMMSP Comparative Computational Results

This section reports the ATS-SMMSP results for the widely used, typical large single foreign theater deployment described by the unclassified Tunisia TPFDD provided by US Transportation Command (USTRANSCOM) J5. USTRANSCOM also supplied the air and sea files. The Center for Army Analysis provided the geographic location information used for location verification and for time and distance calculations.

These results are then compared to the results obtained by JFAST using the identical inputs used for ATS-SMMSP.

ATS-SMMSP Results

The Tunisia TPFDD contains 21,356 usable lines of data (6,666 RLNs) and has 144 cargo aircraft and 55 passenger aircraft allocated. The cargo aircraft originate at POE WWYK and the passenger aircraft originate at Logan International Airport, Boston, Massachusetts. Transit time from any CONUS to any OCONUS port was modeled as 3 days (load, flight, unload). There were 344 ships available within 15 different ship types initially located at different OCONUS locations around the world. Their average capacity was 25,000 Stons and transit time from CONUS to OCONUS was modeled as 14 days.

The ATS-SMMSP TPFDD validation module found 3,040 RLNs with errors and required 4 minutes to repair 2,585 RLN errors and discard 455 unrepairable RLNs. This resulted in 6,211 available RLNs. This unprecedented automated repair procedure increased the available RLNs by a remarkable 40 percent! All current DoD models simply discard RLNs in need of repair.

The initial greedy solution and the dramatically improved ATS-SMMSP Stage 1 solution are summarized in Table 13. Proceeding to Stage 2, each Stage 2 execution, terminated by an iteration count condition, was followed by a Stage 1 execution. Once the maximum time stopping criteria was reached, Stage 2 terminated. Stages 2 and 1 were executed ten times prior to termination. Table 13 shows that all metrics were improved, with a 10 percent decrease in late RLNs and a more than 20 percent decrease in total days late. The reductions achieved are not possible in current DoD SM models.

After each execution of Stage 3, Stage 2 is executed. (Stage 1 is executed within Stage 2). Stage 3 was executed six times before the maximum allowed time was reached. The best solution was found after a total computation time of 15 hours and 44 minutes. As shown in Table 13, improvements were made to all metrics except passenger aircraft usage. The increase in available cargo aircraft used brought about significant additional reductions in four other metrics. This procedure is the first demonstration of a mode replacement heuristic within SM Modeling. The improvements in reduction of lateness demonstrate the important capabilities of this method.

Figure 4 plots the objective function values against time for the Stage 3 search. The six executions of Stage 3 in this figure are evident by the groupings of starting values. The large point indicated by the oval on the graph indicates when the best objective function value was first found at Stage 3 execution 4. This value was saved as the best solution. Two more unique solutions with the same objective function value were found during Stage 3 execution 4.

[FIGURE 4 OMITTED]

JFAST Tunisia

To obtain comparable results, the identical TPFDDs from each ATS-SMMSP stage were input to JFAST. All scenario parameters were as stipulated in the ATS-SMMSP implementation. The input setup for JFAST is discussed in detail in McKinzie. (36) JFAST executes relatively quickly with the longest run taking less than 12 minutes. Since the time differences in all runs were small, additional analysis will not include run time comparisons.

Table 14 shows the total late arrivals (in 1,000 Stons) for the JFAST and ATS-SMMSP runs. The dramatic improvements in all three stages, reductions of at least 99.5 percent, emphasize the significant superiority of the ATS-SMMSP methodology. The number of late passenger Stons are higher in ATS-SMMSP. However with each passenger equating to 400 lbs, the maximal number of late passengers was no more than 70, a very acceptable value.

CONCLUSIONS AND RECOMMENDATIONS FOR FUTURE RESEARCH

Section 4 presented the ATS-SMMSP results for a TPFDD widely used in DoD. It then compared those results to the results from JFAST. This section discusses the unique contributions of this research and suggests directions for future research.

The contributions documented here include unprecedented developments and implementations in four arenas: (1) automated repair of TPFDDs, (2) application of advanced TS techniques to the SMMSP, (3) strategic modifications of command prespecified TPFDD port allocations, and (4) strategic modifications of command prespecified TPFDD transport mode specifications.

There are several additional areas that could be investigated. Here are three that deserve immediate attention.

* The research reported here was performed under the auspices of The University of Texas at Austin which required that no classified materials be used. For this reason, the ATS-SMMSP applied to only one instance of a TPFDD, the only unclassified TPFDD available. To establish the general applicability of the ATS-SMMSP, it should be applied to a wide range of TPFDDs. McKinzie (37) provides an initial look at that research direction where several parametric variants of the Tunisia TPFFD are considered.

* The current ATS-SMMSP does not begin with a good starting solution. An improved starting solution methodology would enhance the overall performance of the ATS-SMMSP.

* This current ATS-SMMSP used rudimentary techniques for vehicle assignment and route scheduling. Improved methods should be developed.

This research was sponsored by a grant from the Air Force Office of Scientific Research, and the article has been nominated for the Military Operations Research Society Barchi Prize.

Article Acronyms

AFRP--Aerial Fleet Refueling Problem

AFCSP--Aerial Fleet Crew Scheduling Problem

ALD--Available Load Date

ATS--Adaptive Tabu Search

CONUS--Continental United States

DANTE--Deployment Network Tool Extended

DoD--Department of Defense

EAD--Earliest Arrival Date

GDAS--Global Deployment Analysis System

JFAST--Joint Flow and Analysis System for Transportation

LAD--Latest Arrival Date

MIDAS--Model for Intertheater Deployment by Air and Sea

MobSim--Mobility Simulation Model

OCONUS--Outside the Continental United States

PAX- Passengers

POD--Port of Debarkation

POE--Port of Embarkation

RDD--Required Delivery Date

RLD--Ready to Load Date

RLN--Requirement Line Number

RTS--Reactive Tabu Search

SAP--Strategic Airlift Problem

SMMS--Strategic Mobility Mode Selection

SMMSP--Strategic Mobility Mode Selection Problem

STQL--Strategic Transportation Quick Look

TDVRSP--Theater Distribution Vehicle Routing and Scheduling Problem

TPFDD--Time Phased Force Deployment Data

TS--Tabu Search

USTRANSCOM--United States Transportation Command

WBP--Wide Body Plane

J. Wesley Barnes, PhD

Kaye McKinzie, PhD, USA

Notes

(1.) Chairman of the Joint Chiefs of Staff, "National Military Strategy," [Online] Available: http://www.defenselink.mil/news/Mar2005/d20050318nms.pdf, 05.

(2.) "Military Fundamentals for DA Civilians," [Online] Available: http://www.osc.army.mil/ig/milfun3.ppt, (accessed 27 Jul 02).

(3.) "TPFDD," [Online] Available: http://www.jfast.org/jfast/html/ Terms/TPFDD.htm, (accessed 1 Aug 02).

(4.) VRP Web site, [Online] Available: http://neo.lcc.uma.es/radi-aeb/ WebVRP/Problem_Descriptions/NP.html, (accessed 12 Dec 04).

(5.) Department of the Army, Field Manual (FM) 100-17, Mobilization, Deployment, Redeployment, Demobilization. Headquarters, Department of the Army, 92.

(6.) K. McKinzie and J.W. Barnes, "A Review of SM Models Supporting the Defense Transportation System," Mathematical Computer Modeling, Vol 39, No 6-8, 04, 839-868.

(7.) Military Traffic Management Command Transportation Engineering Agency, "DANTE," [Online] Available http://www.tea.army.mil/tools/dante.htm, (accessed 31 Jul 02).

(8.) William Key, "Strategic Transportation Quick Look (STQL), "Excel based spreadsheet model, USTRANSCOM, J-5, Oct 03.

(9.) JFAST Training using JFAST 8.0 Handbook, Improving the Deployment Process, Course taught at Scott Air Force Base, Illinois, Oct 03.

(10.) Author's interview with subject matter experts Lieutenant Colonel Seise, William Key, Carroll Keyfauver, and Lieutenant Colonel Sees, 2 Mar to 2 Jun 04.

(11.) K. McKinzie and J.W. Barnes, "A Review of SM Models Supporting the Defense Transportation System," Mathematical Computer Modeling, Vol 39, No 6-8, 04, 839-868.

(12.) Military Traffic Management Command Transportation Engineering Agency, "DANTE."

(13.) Barbara Sue Melendez, "On Scheduling Delivery in a Military Deployment Scenario," Ph.D. dissertation, North Carolina State University, Raleigh, North Carolina, 02.

(14.) Author's interview with Dennis Konkel, Oct 03.

(15.) Strategic Transportation Quick Look (STQL).

(16.) MobSim, Executive Summary, O'Fallon, Illinois: IIT Research, Inc., Oct 02.

(17.) F. Glover and M. Laguna, Tabu Search in: C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems, Blackwell: Oxford, 93, 70-150.

(18.) J. Harwig, "An Adaptive Tabu Search Approach to Cutting and Packing Problems," doctoral dissertation, The University of Texas, Austin, Texas, 03.

(19.) G.R. Lambert, "A Tabu Search Approach to the Strategic Airlift Problem," doctoral dissertation. The University of Texas, Austin, Texas, 04.

(20.) Glover and Laguna, 93.

(21.) W. Carlton and J. Barnes, "A Note on Hashing Functions and Tabu Search Algorithms," European Journal of Operational Research 95, 96, 237-239.

(22.) J.W. Barnes, V. Wiley, J. Moore, and D. Ryer, "Solving the Aerial Fleet Refueling Problem using Group Theoretic Tabu Search," Mathematical and Computer Modeling, 04, 6-8.

(23.) R. Battiti and G. Tecchiolli. "The Reactive Tabu Search," ORSA Journal on Computing, Vol 6, No 2, 94.

(24.) Carlton and Barnes, 96.

(25.) W.P. Nanry and J.W. Barnes, "Solving the Pickup and Delivery Problem with Time Windows using Reactive Tabu Search," Transportation Research, part B 34, pgs. 107-121. [Online] Available: http://www.tcaimsii.belvoir.army.mil/interfaces.htm, (accessed 27 Jul 02).

(26.) Barnes, et al, 6-8.

(27.) T.E. Combs and J.T. Moore, "A Hybrid Tabu Search/Set Partitioning Approach to Tanker Crew Scheduling," Military Operations Research, 9(1), 04, 43-56.

(28.) Todd A. Combs, "A Combined Adaptive Tabu Search and Set Partitioning Approach for the Crew Scheduling Problem with an Air Tanker Crew Application," doctoral dissertation, Air Force Institute of Technology, Wright-Patterson Air Force Base, Ohio, 02.

(29.) Crino, et al, 04.

(30.) G.R. Lambert.

(31.) J. Harwig.

(32.) Kaye McKinzie, "A Tabu Search Approach to Strategic Mobility Mode Selection," doctoral dissertation, The University of Texas, Austin, Texas 05.

(33.) R. Battiti and G. Tecchiolli, "The Reactive Tabu Search," ORSA Journal on Computing, Vol 6, No 2, 94.

(34.) McKinzie.

(35.) Chairman of the Joint Chiefs of Staff, "JOPES Volume I, Joint Operation Planning and Execution System (JOPES)," Planning Policies and Procedures, 3122.01, 01.

(36.) McKinzie.

(37.) Ibid.

J. Wesley Barnes, Cullen Trust for Higher Education Endowed Professor in Engineering, is the Graduate Advisor and Chair of the Graduate Studies Committee for the Graduate Program in Operations Research and Industrial Engineering at the University of Texas at Austin. This year marks his 33d year at the University of Texas at Austin.

Lieutenant Colonel Kaye McKinzie is currently a division chief in the joint operations directorate at the Training and Doctrine Command Analysis Center, Fort Leavenworth, Kansas. At the time of the writing of the article she was a senior military analyst in the requirements and experimentation division, TRADOC Analysis Center.

The efficient and effective solution to the Strategic Mobility Mode Selection Problem (SMMSP) is essential to the effective and efficient force projection of the US Military. The SM Mode Selection (SMMS) process assigns a transportation mode to personnel and materiel for shipment from CONUS to OCONUS. A foundation of the National Military Strategy (1) is to maintain most forces in CONUS while being prepared for OCONUS missions. (2) On demand, a previously constructed plan, the mission's time-phased force deployment data (TPFDD) (3) is executed to move specified personnel and cargo to designated locations. A TPFDD stipulates the timely deployment of personnel and cargo to the best mission locations.

The next section describes the basic SMMSP, presents a small example, and outlines the objectives of the research documented in this article.

The SMMSP

The TPFDD's sequence and timing is critical not only to mission accomplishment, but also to the safety of personnel and cargo in an OCONUS operational area or port of debarkation (POD). The multitrip reuse of aircraft and ships traveling from ports of embarkation (POE) in CONUS to OCONUS PODs and the presence of time window constraints, as described below, causes the SMMSP to be a variant of the vehicle routing problem with time windows. (4)

Other TPFDD restrictions such as the CONUS origin ready to load date (RLD), POE available load date (ALD), POD earliest arrival date (EAD), POD latest arrival date (LAD) and final destination required delivery date (RDD) are also present. These dates are time sequenced and are often mutually dependent. The RLD, ALD and EAD are hard constraints. The LAD and RDD are soft constraints.

In SM modeling, early completion is only one part of a multicriteria objective. A primary goal of an SM model is to meet the LADs. As presented in Figure 1, any arrival between the EADLAD time window is sufficient. It is also desirable to minimize vehicle usage, especially aircraft use. If the LADs cannot be met, a secondary objective, minimizing lateness (violations of LADs) and required resources, is invoked.

[FIGURE 1 OMITTED]

A TPFDD is presented at six different levels of detail. (5) The tabu search (TS) method documented here provides asset level visibility and operates at TPFDD Level 3. The generic reference to a TPFDD item is a requirement line number (RLN). All passengers (PAX) must be transported by air. Cargo not transportable by air is restricted to ships. Most items may be assigned either mode and the most appropriate should be selected. After RLN mode selection is completed, RLNs must be scheduled for transport at specific POEs on specific aircraft or ships, at specific times and dates. The aircraft or ship assignment implies a specific POD.

Motivation

Current SM models do not efficiently assign the transportation modes for RLNs, employing either prestipulated modes or myopic methods. A complete and detailed review of such models is presented by McKinzie and Barnes. (6) Three of these are the Deployment Network Tool Extended (DANTE) (7), Strategic Transportation Quick Look (STQL) (8) and Joint Flow and Analysis System for Transportation (JFAST) Link. (9) As shown in this article, the results from these models can be significantly improved upon by the application of modem direct search.

Problem Statement

We assume the following information is specified.

* Aircraft and ship quantities, availability dates, and types at each starting location.

* Open ports (POE and POD) for transportation.

We assume the following information is given in TPFDD (Level 3) format: For each

* RLN: Origin, destination, RLD, ALD, EAD, LAD, RDD, size, priority, and whether contents are hazardous.

* Aircraft or ship: capacity, speed, range, type.

* Port: ship and aircraft capacities, fuel and refuel capacities, maximum aircraft on ground and berths, number of takeoffs and landings per day, and on- off- load capabilities.

Conversations with subject matter experts (10) reveal that, from a command viewpoint, a RLN's priority is, de facto, its LAD. However, one RLN of 350 lbs arriving one day late is not equivalent to an RLN of 13 Stons arriving one day late. A simple yet representative method of calculating lateness is to multiply Stons by days late. In addition, the relatively low number of aircraft and their significantly higher cost per trip compared to ships must be considered. Hence, the consensus was that the objective function value for the SMMSP should be computed by adding: (1) the total number of ship trip legs, (2) ten times the number of aircraft legs, and (3) for each RLN, the LAD violation time in days multiplied by its Stons.

For example, ten aircraft trips, ten ship trips, and three RLNs of 50 Stons each arriving 3 days late would yield an objective function value of 560 units.

A Small SMMSP

Tables 1 through 6 present a schedule generated by JFAST for 17 RLNs that were extracted from a contingency deployment to Tunisia. All columns are self explanatory except for column M which indicates the item transport mode (X--item not moved, P --optional mode, S--sea mode, A--air mode).

Table 1's first RLN, 05AAL, is designated for air transport and weighs 882 Stons. (PAX are allocated one-fifth Ston per individual). Since strategic aircraft carry no more than 92 Stons, 05AAL requires at least ten aircraft. Strategic ships can haul at least 18,000 Stons, but require 2 or more weeks to travel from CONUS to Jerba-Zarzis, Tunisia (JEAH). 05AAL's LAD is day 100 and it can depart on day 0.

Table 2 lists the 11 PAX RLNs that must travel by air. (05BC needs no transport because it is at its destination. This type of superfluous content is not unusual in a typical TPFFD.) The remaining ten RLNs depart from six different POEs and arrive at three PODs. Given sufficient pressurized aircraft, Table 3 shows one possible valid on time schedule. Table 4 details the remaining 5 RLNs to be scheduled. (02CB's current OCONUS location (CWFA) is in Italy and need not be considered for strategic transport.)

Of the remaining five items, one is scheduled for air, three for sea, and 01AAC's mode is optional. However, since 01AAC's POE (ZBES) and POD (FTZH) are both sea ports, its mode is changed to S. If the designated POE and POD could be modified, it is possible that 01AAC's mode could be changed to air. Tables 5 and 6 detail the remaining air and sea transport. The RLNs in Table 6 depart from ZBES (Wilmington, NC) and LCMT (Houston, TX) and all planned departures embody trivial loads that will arrive after their LAD.

This example uses only 17 RLNs. A typical TPFDD has over 4,000 RLNs. Since JFAST was used, no heuristic was employed to improve the solution either by (1) rearranging RLNs within their assigned POEs or PODs, (2) by moving RLNs to another POE or POD or (3) by exercising possible transport mode changes. As described below, utilizing such options can greatly improve the solution associated with any set of cargo.

Research Goals

The primary goals of the research documented here were to:

* Develop methods for producing a suite of excellent solutions to any instance of the SMMSP.

* Produce a model for the SMMSP that allows reusability of the model within the various SMMS models used by the Department of Defense (DoD).

* Conduct a comparison of our TS methods to an existing SM method.

Goal 1 was accomplished with an Adaptive Tabu Search (ATS) approach, ATS-SMMSP, where an adaptive neighborhood schema reallocated one or more RLNs from one transportation asset to another. Goal 2 was addressed implementing the model in JAVA. Finally, goal 3 was achieved by comparing the results of ATS-SMMSP to those of JFAST.

The remainder of this article consists of four sections. The second section recounts several relevant SM models, overviews pertinent associated TS topics and reviews associated military applications of TS. The third section presents a small example of a SMMSP and describes the ATS-SMMSP. The fourth section presents a comparison of results of the ATS-SMMSP and JFAST

The final section presents conclusions and proposes additional areas of investigation.

A Review of SM Literature and Associated TS Approaches

This section reviews available SM literature and the three aspects of TS most relevant to this research.

SM Models Overview

SMMSP literature is principally found in military publications and in unpublished information residing in the community of users and programmers of specific mobility models. SM models differ in sponsoring organizations, operating systems, ease of use, interoperability with other models, input and output interfaces, mode selection capability, level of detail, mission profile versatility, and computational efficiency. Where appropriate, these criteria will be addressed in the following sections. A detailed review of current and legacy models may be found in McKinzie and Barnes. (11)

High Level SM Models with No Mode Selection

This class of quick look models is employed in early planning, uses only regional origin and destination designations, uses approximate travel distances, combines unit equipment and resupplies, allows only macroscopic decisions, and provides a broad understanding of required time frames for timely delivery of all items. These models provide an early assessment of planning feasibility and the need for a redesign of the plan.

Examples of such tools are the Deployment Network Tool Extended (DANTE), (12, 13) JFAST-Link (14) and the Strategic Transportation Quick Look (STQL). (15)

Level IV SM Models (With Mode Selection)

This class of models includes:

* The Global Deployment Analysis System (GDAS), which provides extensive capabilities for analysis but can require a significant amount of time and effort to tailor it to a specific model. GDAS performs a deterministic simulation to determine the actual arrival, departure, loading, unloading, and queuing events at each facility.

* JFAST, the model of choice for the detailed planning community. JFAST is High Level Architecture-compliant and includes a TPFDD editor.

* The Model for Intertheater Deployment By Air and Sea (MIDAS), where all input and output files must be viewed and edited as flat files. The intense complexity of the MIDAS model presents a significant roadblock for many planners who have little experience and education in modeling. MIDAS's mode selection first assigns all cargo (except nonair transportable materiel) to aircraft. If available aircraft cannot feasibly transport all RLNs, all RLNs that can meet their RDD when moved by ship (Ship-RDD RLNs) are identified and MIDAS begins to assign such Ship-RDD RLNs to ships. MIDAS can produce schedules with individual aircraft tail numbers and can track RLN Level 6 detail.

* The private proprietary, expensive Mobility Simulation Model (MobSim), is portable and easy to use, consisting of a simulation tool that models multiple modes of transportation. MobSim reports the first feasible solution found unless instructed to report a global optimal solution. If a global optimum is required, MobSim attempts to secure it through exhaustive search. (16) Although a feasible solution can be reported in minutes, an excellent solution will usually not be found in an acceptable amount of time.

Tabu Search

In this section, aspects of TS particularly relevant to the SMMSP are discussed and an overview of historical TS applied to military combinatorial optimization problems is presented.

Classical applications of TS have focused primarily on the solution of combinatorial optimization problems. (17) The numerous TS successes are attributable to several characteristics including TS's abilities to traverse infeasible solution space regions and to escape local optima.

TS guides the search by recording attributes of visited solutions and forbidding return to such solutions before tabu tenure iterations have occurred. TS repeatedly chooses the best non-tabu solution from a predefined neighborhood of solutions until a termination condition is met. While early TS implementations used a static constant tabu tenure, advanced tabu memory structures can dynamically determine the tabu tenure for a solution or class of solutions. (18,19) TS can also be enhanced through the use of intensification and diversification strategies. (20, 21)

ATS-SMMSP uses a simple dynamic memory structure that defines a minimal, maximal, and initial tabu tenure. While enforcing the tenure extremes, an improving move yields a tabu tenure increment and a nonimproving move yields a decrement to the tabu tenure. (22) This simple enhancement to the TS memory structure can result in marked improvements in efficiency and effectiveness of a TS approach.

Battitti and Tecchiolli (23) introduced a more powerful dynamic TS memory structure, reactive TS (RTS). The number of repeated solution visitations is recorded. When solutions are repeated frequently, the tabu tenure is increased rapidly. The tabu tenure is quickly decreased when solutions are not frequently repeated. They also implemented a diversification escape technique that is used when "there is evidence that the system is in a complex attractor of the search space." (24) and Nanry and Barnes (25) developed advanced applications of RTS.

Related TS Applications

The TS implementations briefly discussed in this section were developed to solve complex military problems. These and the application presented in this article were built under the aegis of an ongoing consortium consisting of representatives from The University of Texas, the Air Force Institute of Technology, the Air Mobility Command and the Air Force Office of Scientific Research. These models greatly improve upon previous approaches by providing near optimal solutions in remarkably small amounts of time.

The Aerial Fleet Refueling Problem (AFRP) (26) is concerned with inflight refueling of a fleet of Air Force aircraft. The associated TS approach addressed a multicriteria set of goals and dramatically reduced the time and resources required for solution. In a typical large scale deployment scenario, the TS AFRP methodology yielded an ensemble of excellent solutions in about 4 hours. Previous methods required a team of analysts months to obtain a workable solution.

The Aerial Fleet Crew Scheduling Problem (AFCSP) (27,28) complements the TS AFRP model. The TS AFCSP model addresses the scheduling of the crews that operate associated AFRP aircraft and significantly improves the solutions found from current methods in remarkably short periods of time.

The Theater Distribution Vehicle Routing and Scheduling Problem (TDVRSP) model (29) uses an abstract algebraic view. Once the cargo or passenger arrives at the POD, each must be moved to the final destination. The TS TDVRSP model maintains total asset visibility and intransit visibility of vehicle assets and is a much more efficient and effective solution methodology than previous approaches. Although the US Air Force once deemed the TDVRSP too difficult for optimization, this new TS technique has shown that statement to be incorrect.

The ATS approach to the Strategic Airlift Problem (SAP) (30) produces detailed routing and scheduling of strategic airlift resources which are dramatically superior to the current approach embodied in Air Mobility Operations Simulator. This approach extends the dynamic neighborhood selection methodology first developed by Harwig. (31)

The SAP is a component of the SMMSP. ATS-SMMSP stipulates the mode of transport for each RLN and assigns RLNs to vehicles at a more macroscopic level than the SAP. The TS SAP model requires the prior stipulation of what items will be transported by air and focuses, in a more detailed manner, on solving the routing and scheduling of air movement. In addition to the SAP, the SMMSP solves the Strategic Sealift Problem at a macroscopic level.

TS and SM

The SMMSP is a large combinatorial optimization problem with partitioning, scheduling, and routing aspects. Partitioning occurs in the assignment of RLNs to a particular mode of transportation. Scheduling is inherent in the assignment of RLNs to particular POEs, PODs, and departure days. In addition to the RLNs being routed from their origin, POE, POD, and finally to their destination, the vehicles moving these RLNs are also scheduled and routed over multiple trips during the deployment operations. Each time the RLN reassignment causes a change in departure day or number of vehicles required for movement on a given day, the vehicles are rerouted.

Current models use greedy procedures to obtain feasible solutions to the problem. Classical optimization methods are incapable of providing timely solutions; thus, this problem is ideally suited for a TS approach. The next section details the ATS-SMMSP algorithm developed in this research.

The ATS-SMMSP Algorithm--Modeling and Methodology

A TPFDD stipulates all needed information for the transport of cargo for a given contingency and the solution of the SMMSP yields a redefinition of a TPFDD.

Two Representations of the SMMSP

There are two SMMSP solution representations using either vehicle routing or RLN routing. The vehicle routing representation groups the time stamps, paths, and RLNs by vehicle. The RLN routing representation groups the RLNs by POE, departure day, and POD. The small SMMSP example of Table 1 illustrated the RLN routing representation. Table 7 presents a vehicle routing solution representation of another small example which uses two wide-body planes (WBPs) and one B-747P to route the RLNs. Table 8 presents an equivalent RLN routing representation for the example of Table 7.

Both WBPs' maximum load is 59 Stons and the B-747P's maximum load is 93 Stons. All aircraft are available on day 0 at POE WW-YK (Tinker Air Force Base, OK). WBP-1 performs five trips. After flying to NRCH (Loring Air Fore Base, Maine), WBP-1 's first trip is on day 7 with one RLN of 2 Stons. After delivering cargo to AEQT (Algeciras [Gibraltar], Spain), it returns to PTFL (McGuire Air Force Base, NJ) and picks up 35 Stons on day 20 and unloads at AEQT on day 22. It then returns to PTFL, picks up 48 Stons on day 30 and delivers it to VRJT (Sigonella, Italy). Returning to NRCH, it picks up 6 Stons on day 34 and delivers it to AEQT. Finally WBP-1 returns to NRCH picking up 3 Stons on day 46 and delivering to AEQT. WBP-1's total routing was {Port (day, Ston)}: WWYK(0,0)--NRCH(7,2)--AEQT(9,0)--PTFL(20,35) --AEQT(22,0)--PTFL(28,48)--VRJT(30,0)--NRCH(34,6) --AEQT(36,0)--NRCH(46,3)--AEQT(48,0).

The second WBP performs a single trip with routing WWYK(0,0)--PTFL(35,14)--AEQT(37,0). The last aircraft, B-747P-1 performs three trips with a routing of WWYK(0,0)--PTFL(35,93) --AEQT(37,0)--NRCH(46,10)--UMXB(48,0)--NRCH(53,3) --AEQT(55,0).

This small example addresses only nine RLNs. Typical problems address thousands of RLNs and the inherent complexity of the SMMSP precludes the use of classical optimization methods. A heuristic approach that obtains an excellent solution in a relatively short amount of time is superior to either a poor solution achieved more quickly or to a provably optimal solution that requires insupportable time and effort. A direct search approach, like ATS, can successfully manage the presence of the many time window constraints and still track each RLN and vehicle as a unique entity.

An ATS Approach to the SMMSP

The highly successful applications of ATS to complex military logistics problems reviewed in Section 2 led to the use of ATS for this research. While TS does not guarantee an optimal solution, a well constructed TS methodology uses aspects of the problem structure to achieve excellent solutions with supportable computational effort. The ATS approach described in this section monitors such things as late arriving RLNs, time window flexibility and the number and type of transport vehicles available to enhance the search process.

The DoD hierarchically delegates authority to several levels of command. Within SM planning, associated commands coordinate priorities and interests and reach agreements regarding RLNs and transportation assets. Commanders specify RLN ports and modes and are very resistant to change. For this reason, the ATS-SMMSP performs three stages of analysis. Stage 1 solves the SMMSP preserving the commanders' port and mode assignments. Stage 2 preserves specified transport modes but allows RLN POE and POD changes. Stage 3 allows RLN port and transport mode changes. Stage 2 and 3 solutions may be used to demonstrate the improved solutions available for commanders willing to relax some of their preferences.

The ATS-SMMSP solution representation lists each RLN with its (POE/departure-day/POD) triplet. Since each POE (POD) is either an air or sea port, any RLN port assignment defines the mode of transport. Known transit times imply that any departure day stipulates the arrival day and directly allows accounting for any LAD violations. All ATS-SMMSP search neighborhoods allow and penalize delivery after the LAD, but strictly prohibit violations of RLD and EAD. RLN transport priority is dictated by the earliest LAD.

The software implementation of the ATS-SMMSP methodology is divided into three parts: (1) Input focuses on data validity, (2) ATS performs scheduling and assignment and (3) Output presents the new TPFDD generated by the ATS-SMMSP.

ATS-SMMSP Input

ATS-SMMSP requires six data files. The first three contain information associated with airplanes, ships and geographic locations. The airplane information includes the airplane type, maximum and minimum loads, speed, and size limitations. Due to the numerous ship configurations, only averages for ship types are available. For each ship type, the ship information also includes the speed, maximum and minimum draft, loading time and maximum load. The geographic location information is used for location verification and for time and distance calculations.

The remaining three contingency-specific files are the TPFDD, Vehicles Available, and Open Ports. The initial location, type, and available date of all vehicles are provided in the Vehicles Available file. TPFDD and Open Port files must be checked for validity and completeness. Some TPFDD errors and omissions can be easily corrected. For example, if a port indicated by a TPFDD is not an open port for a scenario, it is replaced with the closest open port in the port file. Another example would be when a POE-POD pair are incompatible mode types and require correction.

Scheduling and Assignment

As detailed by McKinzie, (32) prior to search commencement, the validated TPFDD file is used to create an initial ATS-SMMSP solution. This is performed by having RLNs move precisely as stated in the TPFDD, departing their TPFDD-designated POEs on the designated available load dates. Vehicles are greedily assigned to the triplets in order of earliest departure day, by first available vehicle. The initial solution is usually not good with many RLNs arriving late and many vehicles transporting trivial loads. This and other types of solution deficiencies are corrected by the ATS-SMMSP.

This greedy assignment is illustrated by the small example in Table 8 which, without loss of generality, considers only PAX. Two POEs are used--NRCH (Loring AFB, Maine) and PTFL (McGuire AFB, NJ). First, consider the RLNs at NRCH. On day 7, aircraft 5 departs with 5HJAV carrying a trivial load of two Stons. On day 34, aircraft 0 departs with 5HCAS (six Stons). On day 46, aircraft 8 transports three Stons to AEQT and aircraft 9 transports ten Stons to UMXB. Finally on day 53, aircraft 7 transports three Stons. Now, focusing on PTFL, aircraft 23 departs on day 20 with 35 Stons and aircraft 29 departs on day 28 with 48 Stons. On day 35, aircraft 24 and 10 transport 0EDB with a total of 107 Stons. Aircraft 24 is maximally loaded with 92 Stons and aircraft 10 transports the remaining 15 Stons. Each mission except PTFL mission 2 is far below their 50 percent trivial load weight.

This greedy assignment used nine aircraft trips for eight missions. The only temporally overlapping trips depart on day 46 and on days 34 and 35. The nine trips could have been accomplished using three unique aircraft. The cost of moving the RLNs would be the same and six aircraft would remain free for other uses such as providing earlier transport for RLNs that would arrive later than their LADs. Additional significant gains in efficiency could also be possible if the LADs would allow RLN aggregation onto fewer aircraft without increasing lateness.

ATS-SMMSP Search Stages

Stage 1 uses two phases to seek improvements without changing predefined ports or modes by considering moves in defined search neighborhoods. The best qualifying (non-tabu or aspiration satisfying) neighbor becomes the new incumbent solution. Phase I considers only late RLNs ordered by descending lateness penalty (days late times RLN Stons). Table 9 expands Table 8 providing ALD, EAD, and LAD detail. The three late RLNs are considered in the order 5WYH4 C, 5HCAJ, and 5HEBA.

Phase I examines late RLN using a port-pair neighborhood. Since 5WYH4 C has the unique port-pair NRCH-UMXB, it has no moves available. 5HCAJ and 5HEBA have port pair NRCH-AEQT. Hence, 5HCAJ has three possible moves. Moving to NRCH-7-AEQT is rejected for ALD violation. Moving 5HCAJ to NRCH-34-AEQT yields an arrival 12 days earlier (a lateness decrease of 36 Ston-days) and is the best current move. Moving to NRCH-53-AEQT adds seven more days delay and is discarded.

5HEBA is nine days late. Moving to NRCH-7-AEQT is discarded for ALD violation but moving to NRCH-34-AEQT yields a total lateness reduction of 37 Ston-days, the new best move. Moving to NRCH-46-AEQT yields a lesser reduction of 31 units and is discarded.

Following the complete neighborhood evaluation, the best move is executed. Phase I is applied until no moves exist. For our example, this yields the results of Table 10 with a lateness of 145 with seven aircraft used.

Phase II differs from Phase I only in the search neighborhood which does not require lateness and consists of the smaller of 10 percent of all RLNs or 100 RLNs. The RLNs are considered in ascending order by RLN Stons and alphabetically within equal Stons. For the current example, the list for Phase II is 5HJAV, 5HCAJ, 5HEBA, 5WYH4 B, 5WYH4 C, 5HCAS, 6ACBP, 0FBB, and 0EDB.

Phase II completes Stage 1 and yields the results in Table 11 with a lateness of 135 using six aircraft. Stage 1 reduced lateness by 93 units and three fewer aircraft are required. The best solution from Stage 1 is the initial solution for Stage 2 where pre-selected ports are not enforced. This is the first algorithm to allow improving port selections in an automated approach.

In Stage 2, logistical restrictions limit the distance to new replacement ports. Better security and transportation allow 700 miles in CONUS as opposed to 200 miles in OCONUS. As presented in the psuedocode of Figure 2, at each iteration, all RLNs are considered and the best allowable move is executed. The Stage 2 neighborhood is much larger than its Stage 1 counterpart because it considers all RLNs and relaxes the constraint that preserves port-pairs. The Stage 2 maximum time limit encompasses both Stage 2 and Stage 1.

Figure 2. Within Mode Search Pseudo Code While Stage 2 time limit not exceeded { Until a Stage 2 iteration count termination criterion is satisfied { For each transport mode- air or sea {For each RLNs of this mode { For each neighborhood solution { evaluate objective function and determine tabu and aspiration status store best Stage 2 neighbor found } } } Move to best allowable Stage 2 solution found } Perform Stage I search Save best solution found }

Continuing with the example of Tables 9 through 12, POE NRCH is close enough to PTFL and to several other POEs for RLNs to move to a different triplet using any of these POEs. Similarly, because they are within 200 miles of one another, POD UMXB (Rota, Spain) and POD AEQT can be used interchangeably. All RLNs except 0FBB at PTFL-28-VRJT are current candidates for port change.

Table 12 presents the results for Stage 2. NRCH-7-AEQT, NRCH-46-AEQT, NRCH-53-AEQT and PTFL-28-VRJT are unchanged. 5HCAJ moved to PTFL-20-AEQT (changing its POE) and arrived on time at a cost savings of 15. 5WYH4 C moved to NRCH-34-AEQT (changing its POD) for a cost savings of 60 and 5WYH4 B moved to PTFL-35-AEQT reducing aircraft usage by one. At this point, no RLN is late and the total penalty of 50 units is due to the five required aircraft

In Stage 3, transportation modes may be altered. Our small PAX example restricted all RLNs to air transport. Only cargo RLNs may change modes, which implies a port change for our mode-specific ports. Figure 3 presents a high-level pseudo code for Stage 3. The maximum time-stopping criteria includes the time consumed by all three stages.

Figure 3. Pseudo Code for Stage 3 While Stage 3 time limit not reached { Until a Stage 3 iteration count termination criterion is satisfied { For each neighbor cargo RLN triplet within distance limitations { evaluate objective function and determine tabu and aspiration status save best found Stage 3 solution } Move to best Stage 3 solution found } Execute Stage 2 (and Stage 1) }

Other ATS-SMMSP Considerations

The ATS-SMMSP tabu memory structure is straightforward. An RLN may not be moved if it has been moved within the last tabu tenure iterations. The aspiration criterion allows tabu RLNs to move only if that would produce the best solution found so far in the search. Each RLN in the current search neighborhood is evaluated and the best allowable move yields the new incumbent solution. The tabu tenure varies in each stage. The initial tabu tenure is one-tenth the size of the candidate list of RLNs. The tabu tenure adaptively changes by decrementing with an improving move and incrementing with a nonimproving move. This adaptive procedure aids in intensifying and diversifying the search relative to a myopic measure of search history. (33)

McKinzie (34) presents a detailed discussion of the stopping criteria used in the ATS-SMMSP algorithm. These stopping criteria were based on total iterations, iterations since the best solution, iterations since an improved solution, and the total computation time.

ATS-SMMSP Outputs

Two of the three outputs from the ATS-SMMSP algorithm, the vehicle routing solution representation and the RLN triplet solution representation, have been presented above. The final type of output is a Joint Planning and Execution System (35) B-8 TPFDD which contains the information required by JFAST, the model used for discussing comparative results in the next section.

ATS-SMMSP Comparative Computational Results

This section reports the ATS-SMMSP results for the widely used, typical large single foreign theater deployment described by the unclassified Tunisia TPFDD provided by US Transportation Command (USTRANSCOM) J5. USTRANSCOM also supplied the air and sea files. The Center for Army Analysis provided the geographic location information used for location verification and for time and distance calculations.

These results are then compared to the results obtained by JFAST using the identical inputs used for ATS-SMMSP.

ATS-SMMSP Results

The Tunisia TPFDD contains 21,356 usable lines of data (6,666 RLNs) and has 144 cargo aircraft and 55 passenger aircraft allocated. The cargo aircraft originate at POE WWYK and the passenger aircraft originate at Logan International Airport, Boston, Massachusetts. Transit time from any CONUS to any OCONUS port was modeled as 3 days (load, flight, unload). There were 344 ships available within 15 different ship types initially located at different OCONUS locations around the world. Their average capacity was 25,000 Stons and transit time from CONUS to OCONUS was modeled as 14 days.

The ATS-SMMSP TPFDD validation module found 3,040 RLNs with errors and required 4 minutes to repair 2,585 RLN errors and discard 455 unrepairable RLNs. This resulted in 6,211 available RLNs. This unprecedented automated repair procedure increased the available RLNs by a remarkable 40 percent! All current DoD models simply discard RLNs in need of repair.

The initial greedy solution and the dramatically improved ATS-SMMSP Stage 1 solution are summarized in Table 13. Proceeding to Stage 2, each Stage 2 execution, terminated by an iteration count condition, was followed by a Stage 1 execution. Once the maximum time stopping criteria was reached, Stage 2 terminated. Stages 2 and 1 were executed ten times prior to termination. Table 13 shows that all metrics were improved, with a 10 percent decrease in late RLNs and a more than 20 percent decrease in total days late. The reductions achieved are not possible in current DoD SM models.

After each execution of Stage 3, Stage 2 is executed. (Stage 1 is executed within Stage 2). Stage 3 was executed six times before the maximum allowed time was reached. The best solution was found after a total computation time of 15 hours and 44 minutes. As shown in Table 13, improvements were made to all metrics except passenger aircraft usage. The increase in available cargo aircraft used brought about significant additional reductions in four other metrics. This procedure is the first demonstration of a mode replacement heuristic within SM Modeling. The improvements in reduction of lateness demonstrate the important capabilities of this method.

Figure 4 plots the objective function values against time for the Stage 3 search. The six executions of Stage 3 in this figure are evident by the groupings of starting values. The large point indicated by the oval on the graph indicates when the best objective function value was first found at Stage 3 execution 4. This value was saved as the best solution. Two more unique solutions with the same objective function value were found during Stage 3 execution 4.

[FIGURE 4 OMITTED]

JFAST Tunisia

To obtain comparable results, the identical TPFDDs from each ATS-SMMSP stage were input to JFAST. All scenario parameters were as stipulated in the ATS-SMMSP implementation. The input setup for JFAST is discussed in detail in McKinzie. (36) JFAST executes relatively quickly with the longest run taking less than 12 minutes. Since the time differences in all runs were small, additional analysis will not include run time comparisons.

Table 14 shows the total late arrivals (in 1,000 Stons) for the JFAST and ATS-SMMSP runs. The dramatic improvements in all three stages, reductions of at least 99.5 percent, emphasize the significant superiority of the ATS-SMMSP methodology. The number of late passenger Stons are higher in ATS-SMMSP. However with each passenger equating to 400 lbs, the maximal number of late passengers was no more than 70, a very acceptable value.

CONCLUSIONS AND RECOMMENDATIONS FOR FUTURE RESEARCH

Section 4 presented the ATS-SMMSP results for a TPFDD widely used in DoD. It then compared those results to the results from JFAST. This section discusses the unique contributions of this research and suggests directions for future research.

The contributions documented here include unprecedented developments and implementations in four arenas: (1) automated repair of TPFDDs, (2) application of advanced TS techniques to the SMMSP, (3) strategic modifications of command prespecified TPFDD port allocations, and (4) strategic modifications of command prespecified TPFDD transport mode specifications.

There are several additional areas that could be investigated. Here are three that deserve immediate attention.

* The research reported here was performed under the auspices of The University of Texas at Austin which required that no classified materials be used. For this reason, the ATS-SMMSP applied to only one instance of a TPFDD, the only unclassified TPFDD available. To establish the general applicability of the ATS-SMMSP, it should be applied to a wide range of TPFDDs. McKinzie (37) provides an initial look at that research direction where several parametric variants of the Tunisia TPFFD are considered.

* The current ATS-SMMSP does not begin with a good starting solution. An improved starting solution methodology would enhance the overall performance of the ATS-SMMSP.

* This current ATS-SMMSP used rudimentary techniques for vehicle assignment and route scheduling. Improved methods should be developed.

This research was sponsored by a grant from the Air Force Office of Scientific Research, and the article has been nominated for the Military Operations Research Society Barchi Prize.

Article Acronyms

AFRP--Aerial Fleet Refueling Problem

AFCSP--Aerial Fleet Crew Scheduling Problem

ALD--Available Load Date

ATS--Adaptive Tabu Search

CONUS--Continental United States

DANTE--Deployment Network Tool Extended

DoD--Department of Defense

EAD--Earliest Arrival Date

GDAS--Global Deployment Analysis System

JFAST--Joint Flow and Analysis System for Transportation

LAD--Latest Arrival Date

MIDAS--Model for Intertheater Deployment by Air and Sea

MobSim--Mobility Simulation Model

OCONUS--Outside the Continental United States

PAX- Passengers

POD--Port of Debarkation

POE--Port of Embarkation

RDD--Required Delivery Date

RLD--Ready to Load Date

RLN--Requirement Line Number

RTS--Reactive Tabu Search

SAP--Strategic Airlift Problem

SMMS--Strategic Mobility Mode Selection

SMMSP--Strategic Mobility Mode Selection Problem

STQL--Strategic Transportation Quick Look

TDVRSP--Theater Distribution Vehicle Routing and Scheduling Problem

TPFDD--Time Phased Force Deployment Data

TS--Tabu Search

USTRANSCOM--United States Transportation Command

WBP--Wide Body Plane

J. Wesley Barnes, PhD

Kaye McKinzie, PhD, USA

Notes

(1.) Chairman of the Joint Chiefs of Staff, "National Military Strategy," [Online] Available: http://www.defenselink.mil/news/Mar2005/d20050318nms.pdf, 05.

(2.) "Military Fundamentals for DA Civilians," [Online] Available: http://www.osc.army.mil/ig/milfun3.ppt, (accessed 27 Jul 02).

(3.) "TPFDD," [Online] Available: http://www.jfast.org/jfast/html/ Terms/TPFDD.htm, (accessed 1 Aug 02).

(4.) VRP Web site, [Online] Available: http://neo.lcc.uma.es/radi-aeb/ WebVRP/Problem_Descriptions/NP.html, (accessed 12 Dec 04).

(5.) Department of the Army, Field Manual (FM) 100-17, Mobilization, Deployment, Redeployment, Demobilization. Headquarters, Department of the Army, 92.

(6.) K. McKinzie and J.W. Barnes, "A Review of SM Models Supporting the Defense Transportation System," Mathematical Computer Modeling, Vol 39, No 6-8, 04, 839-868.

(7.) Military Traffic Management Command Transportation Engineering Agency, "DANTE," [Online] Available http://www.tea.army.mil/tools/dante.htm, (accessed 31 Jul 02).

(8.) William Key, "Strategic Transportation Quick Look (STQL), "Excel based spreadsheet model, USTRANSCOM, J-5, Oct 03.

(9.) JFAST Training using JFAST 8.0 Handbook, Improving the Deployment Process, Course taught at Scott Air Force Base, Illinois, Oct 03.

(10.) Author's interview with subject matter experts Lieutenant Colonel Seise, William Key, Carroll Keyfauver, and Lieutenant Colonel Sees, 2 Mar to 2 Jun 04.

(11.) K. McKinzie and J.W. Barnes, "A Review of SM Models Supporting the Defense Transportation System," Mathematical Computer Modeling, Vol 39, No 6-8, 04, 839-868.

(12.) Military Traffic Management Command Transportation Engineering Agency, "DANTE."

(13.) Barbara Sue Melendez, "On Scheduling Delivery in a Military Deployment Scenario," Ph.D. dissertation, North Carolina State University, Raleigh, North Carolina, 02.

(14.) Author's interview with Dennis Konkel, Oct 03.

(15.) Strategic Transportation Quick Look (STQL).

(16.) MobSim, Executive Summary, O'Fallon, Illinois: IIT Research, Inc., Oct 02.

(17.) F. Glover and M. Laguna, Tabu Search in: C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems, Blackwell: Oxford, 93, 70-150.

(18.) J. Harwig, "An Adaptive Tabu Search Approach to Cutting and Packing Problems," doctoral dissertation, The University of Texas, Austin, Texas, 03.

(19.) G.R. Lambert, "A Tabu Search Approach to the Strategic Airlift Problem," doctoral dissertation. The University of Texas, Austin, Texas, 04.

(20.) Glover and Laguna, 93.

(21.) W. Carlton and J. Barnes, "A Note on Hashing Functions and Tabu Search Algorithms," European Journal of Operational Research 95, 96, 237-239.

(22.) J.W. Barnes, V. Wiley, J. Moore, and D. Ryer, "Solving the Aerial Fleet Refueling Problem using Group Theoretic Tabu Search," Mathematical and Computer Modeling, 04, 6-8.

(23.) R. Battiti and G. Tecchiolli. "The Reactive Tabu Search," ORSA Journal on Computing, Vol 6, No 2, 94.

(24.) Carlton and Barnes, 96.

(25.) W.P. Nanry and J.W. Barnes, "Solving the Pickup and Delivery Problem with Time Windows using Reactive Tabu Search," Transportation Research, part B 34, pgs. 107-121. [Online] Available: http://www.tcaimsii.belvoir.army.mil/interfaces.htm, (accessed 27 Jul 02).

(26.) Barnes, et al, 6-8.

(27.) T.E. Combs and J.T. Moore, "A Hybrid Tabu Search/Set Partitioning Approach to Tanker Crew Scheduling," Military Operations Research, 9(1), 04, 43-56.

(28.) Todd A. Combs, "A Combined Adaptive Tabu Search and Set Partitioning Approach for the Crew Scheduling Problem with an Air Tanker Crew Application," doctoral dissertation, Air Force Institute of Technology, Wright-Patterson Air Force Base, Ohio, 02.

(29.) Crino, et al, 04.

(30.) G.R. Lambert.

(31.) J. Harwig.

(32.) Kaye McKinzie, "A Tabu Search Approach to Strategic Mobility Mode Selection," doctoral dissertation, The University of Texas, Austin, Texas 05.

(33.) R. Battiti and G. Tecchiolli, "The Reactive Tabu Search," ORSA Journal on Computing, Vol 6, No 2, 94.

(34.) McKinzie.

(35.) Chairman of the Joint Chiefs of Staff, "JOPES Volume I, Joint Operation Planning and Execution System (JOPES)," Planning Policies and Procedures, 3122.01, 01.

(36.) McKinzie.

(37.) Ibid.

J. Wesley Barnes, Cullen Trust for Higher Education Endowed Professor in Engineering, is the Graduate Advisor and Chair of the Graduate Studies Committee for the Graduate Program in Operations Research and Industrial Engineering at the University of Texas at Austin. This year marks his 33d year at the University of Texas at Austin.

Lieutenant Colonel Kaye McKinzie is currently a division chief in the joint operations directorate at the Training and Doctrine Command Analysis Center, Fort Leavenworth, Kansas. At the time of the writing of the article she was a senior military analyst in the requirements and experimentation division, TRADOC Analysis Center.

Table 1. SMMSP Example RLN Description PAX Bulk Over Out Orig 05AAL 2/160TH SOAR ABN 2 MH47 40 273 395 206 CYWF 05AAF HHC ABN SF GROUP (HQ ADVON) 132 712 274 274 HDBL 05BB SOF CMDR USAF COMAFSOF HQ ELE 44 20 0 0 FTEV 05BD SOF 04 MC130E 8 SOS 83 206 159 0 FTEV 05BKB MIB CEWI ABN CORPS GRV 6 181 0 0 LEXG 5BKD MIB CEWI ABN CORPS GRV 415 302 0 0 LEXG 00AJ STINGER MISSILES 0 168 0 0 HCTL 00DDA HQS HQS CO SPT BN ABN 95 0 0 191 HCTL 00JCC AR CO AR BN ABN DIV/SEPBD 20 0 0 191 HCTL 00KB HHC MED HEL BN CH 47 68 80 1490 160 HFTZ 02CB MICOM RESUPPLY 0 0 1728 0 CWFA 00BE AVN MAINT CO AASLT 150 210 3282 0 HDBL 01AAC CORPS FINANCE GROUP 0 80 160 0 HCTL 00KCC HHD AIR TRAFFIC CONTROL B 0 100 829 1480 HFTZ 00GDC AR CO AR BN ABN DIV/SEPBD 0 0 0 191 HCTL 00FTC FWD COMM CO ABN 0 341 108 0 HCTL 05BC SOF 04 HC130 48 460 0 0 FUQN RLN Description RLD POE ALD POD EAD 05AAL 2/160TH SOAR ABN 2 MH47 0 CYWF 0 JEAH 100 05AAF HHC ABN SF GROUP (HQ ADVON) 13 CYWF 13 JEAH 13 05BB SOF CMDR USAF COMAFSOF HQ ELE 0 FTEV 0 FUQN 1 05BD SOF 04 MC130E 8 SOS 0 FTEV 0 FUQN 1 05BKB MIB CEWI ABN CORPS GRV 6 LEXG 15 JEAH 28 5BKD MIB CEWI ABN CORPS GRV 6 LEXG 15 MQNA 27 00AJ STINGER MISSILES 0 QKJA 12 JEAH 12 00DDA HQS HQS CO SPT BN ABN 8 TMKH 18 JEAH 24 00JCC AR CO AR BN ABN DIV/SEPBD 0 TMKH 12 JEAH 12 00KB HHC MED HEL BN CH 47 0 UHGN 0 JEAH 0 02CB MICOM RESUPPLY 15 XQDT 16 JEAH 16 00BE AVN MAINT CO AASLT 0 CYWF 13 JEAH 13 01AAC CORPS FINANCE GROUP 6 ZBES 18 FTZH 24 00KCC HHD AIR TRAFFIC CONTROL B 0 LCMT 0 FTZH 0 00GDC AR CO AR BN ABN DIV/SEPBD 0 ZBES 12 FTZH 12 00FTC FWD COMM CO ABN 0 ZBES 18 FTZH 24 05BC SOF 04 HC130 0 FUQN 0 FUQN 1 RLN Description LAD M Dest RDD 05AAL 2/160TH SOAR ABN 2 MH47 100 A JEAH 100 05AAF HHC ABN SF GROUP (HQ ADVON) 14 A JEAH 14 05BB SOF CMDR USAF COMAFSOF HQ ELE 1 A FUQN 1 05BD SOF 04 MC130E 8 SOS 1 A FUQN 1 05BKB MIB CEWI ABN CORPS GRV 32 A JEAH 32 5BKD MIB CEWI ABN CORPS GRV 31 A MQNA 31 00AJ STINGER MISSILES 25 A JEAH 25 00DDA HQS HQS CO SPT BN ABN 26 A JEAH 26 00JCC AR CO AR BN ABN DIV/SEPBD 22 A JEAH 22 00KB HHC MED HEL BN CH 47 9999 A JEAH 9999 02CB MICOM RESUPPLY 20 S JEAH 20 00BE AVN MAINT CO AASLT 18 P JEAH 18 01AAC CORPS FINANCE GROUP 26 P FTZH 26 00KCC HHD AIR TRAFFIC CONTROL B 9999 S FTZH 9999 00GDC AR CO AR BN ABN DIV/SEPBD 22 S FTZH 22 00FTC FWD COMM CO ABN 28 S FTZH 28 05BC SOF 04 HC130 1 X FUQN 1 Table 2. Pressurized Air Transport RLN Description PAX Bulk Over Out Orig 05AAL 2/160TH SOAR ABN 2 MH47 40 273 395 206 CYWF 05AAF HHC ABN SF GROUP (HQ ADVON) 132 712 274 274 HDBL 05BB SOF CMDR USAF COMAFSOF HQ ELE 44 20 0 0 FTEV 05BD SOF 04 MC130E 8 SOS 83 206 159 0 FTEV 05BKB MIB CEWI ABN CORPS GRV 6 181 0 0 LEXG 05BKD MIB CEWI ABN CORPS GRV 415 302 0 0 LEXG OODDA HQS HQS CO SPT BN ABN 95 0 0 191 HCTL 00JCC AR CO AR BN ABN DIV/SEPBD 20 0 0 191 HCTL 00KB HHC MED HEL BN CH 47 68 80 1490 160 HFTZ 00BE AVN MAINT CO AASLT 150 210 3282 0 HDBL 05BC SOF 04 HC130 48 460 0 0 FUQN RLN Description RLD POE ALD POD EAD 05AAL 2/160TH SOAR ABN 2 MH47 0 CYWF 0 JEAH 100 05AAF HHC ABN SF GROUP (HQ ADVON) 13 CYWF 13 JEAH 13 05BB SOF CMDR USAF COMAFSOF HQ ELE 0 FTEV 0 FUQN 1 05BD SOF 04 MC130E 8 SOS 0 FTEV 0 FUQN 1 05BKB MIB CEWI ABN CORPS GRV 6 LEXG 15 JEAH 28 05BKD MIB CEWI ABN CORPS GRV 6 LEXG 15 MQNA 27 OODDA HQS HQS CO SPT BN ABN 8 TMKH 18 JEAH 24 00JCC AR CO AR BN ABN DIV/SEPBD 0 TMKH 12 JEAH 12 00KB HHC MED HEL BN CH 47 0 UHGN 0 JEAH 0 00BE AVN MAINT CO AASLT 0 CYWF 13 JEAH 13 05BC SOF 04 HC130 0 FUQN 0 FUQN 1 RLN Description LAD M Dest RDD 05AAL 2/160TH SOAR ABN 2 MH47 100 A JEAH 100 05AAF HHC ABN SF GROUP (HQ ADVON) 14 A JEAH 14 05BB SOF CMDR USAF COMAFSOF HQ ELE 1 A FUQN 1 05BD SOF 04 MC130E 8 SOS 1 A FUQN 1 05BKB MIB CEWI ABN CORPS GRV 32 A JEAH 32 05BKD MIB CEWI ABN CORPS GRV 31 A MQNA 31 OODDA HQS HQS CO SPT BN ABN 26 A JEAH 26 00JCC AR CO AR BN ABN DIV/SEPBD 22 A JJEAH 22 00KB HHC MED HEL BN CH 47 9999 A JEAH 9999 00BE AVN MAINT CO AASLT 18 P JEAH 18 05BC SOF 04 HC130 1 X FUQN 1 Table 3. Passenger Schedule POE : UHGN departure day: 0 POD: JEAH arrival day: 1 STon: 1744 Veh Reqd: 19 RLN: 0 is : 00KB Unit Stons: 1744 POE : FTEV departure day: 0 POD: FUQN arrival day: 1 STon: 410 Veh Reqd: 5 RLN: 0 is : 05BB Unit Stons: 29 RLN: 1 is : 05BD Unit Stons: 382 POE:CYWF departure day: 13 POD: JEAH arrival day: 14 STon: 5690 Veh Reqd: 62 RLN: 0 is : 00BE Unit Stons: 3522 RLN: 1 is : 05AAF Unit Stons: 1286 RLN: 2 is : 05AAL Unit Stons: 882 POE : LEXG departure day: 15 POD: JEAH arrival day: 16 STon: 182 Veh Reqd: 2 RLN: 0 is : 05BKB Unit Stons: 182 departure day: 15 POD: MQNA arrival day: 16 STon: 385 Veh Reqd: 5 RLN: 0 is : 05BKD Unit Stons: 385 POE : TMKH departure day: 18 POD: JEAH arrival day: 19 STon: 405 Veh Reqd: 5 RLN: 0 is : 00DDA Unit Stons: 210 RLN: 1 is : 00JCC Unit Stons: 195 Table 4. RLNs Currently Unscheduled RLN Description PAX Bulk Over Out Orig 00AJ STINGER MISSILES 0 168 0 0 HCTL 01AAC CORPS FINANCE GROUP 0 80 160 0 HCTL 00KCC HHD AIR TRAFFIC CONTROL B 0 100 829 1480 HFTZ 00GDC AR CO AR BN ABN DIV/SEPBD 0 0 0 191 HCTL 00FTC FWD COMM CO ABN 0 341 108 0 HCTL RLN Description RLD POE ALD POD EAD 00AJ STINGER MISSILES 0 QKJA 12 JEAN 12 01AAC CORPS FINANCE GROUP 6 ZBES 18 FTZH 24 00KCC HHD AIR TRAFFIC CONTROL B 0 LCMT 0 FTZH 0 00GDC AR CO AR BN ABN DIV/SEPBD 0 ZEES 12 FTZH 12 00FTC FWD COMM CO ABN 0 ZBES 18 FTZH 24 RLN Description LAD M Dest RDD 00AJ STINGER MISSILES 25 A JEAH 25 01AAC CORPS FINANCE GROUP 26 P FTZH 26 00KCC HHD AIR TRAFFIC CONTROL B 9999 S FTZH 9999 00GDC AR CO AR BN ABN DIV/SEPBD 22 S FTZH 22 00FTC FWD COMM CO ABN 28 S FTZH 28 Table 5. Air Cargo Schedule POE : QKJA departure day: 12 POD: JEAH arrival day: 13 STon: 168 Veh Reqd: 3 RLN: 0 is : 00AJ Unit Stons: 168 Table 6. Sea Schedule POE : ZBES departure day: 13 POD: FTZH arrival day: 27 STon: 191 Veh Reqd: 1 RLN: 0 is : 00GDC Unit Stons: 191 departure day: 25 POD: FTZH arrival day: 39 STon: 689 Veh Reqd: 1 RLN: 0 is : 00FTC Unit Stons: 449 RLN: 0 is : 01AAC Unit Stons: 240 POE : LCMT departure day: 1 POD: FTZH arrival day: 15 STon: 2409 Veh: 1 RLN: 0 is : 00KCC Unit Stons: 2409 Table 7. Example Vehicle Routing Solution Representation Air Cargo: WBP-1 day: 0 Port: WWYK Load: 0 Unused: 59 day: 7 Port: NRCH Load: 2 Unused: 57 RLN: 0 is : 5HJAV Unit Stons: 2 day: 9 Port: AEQT Load: 0 Unused: 59 day: 20 Port: PTFL Load: 35 Unused: 24 RLN: 0 is : 6ACBP Unit Stons: 35 day: 22 Port: AEQT Load: 0 Unused: 59 day: 28 Port: PTFL Load: 48 Unused: 11 RLN: 0 is : 0FBB Unit Stons: 48 day: 30 Port: VRJT Load: 0 Unused: 59 day: 34 Port: NRCH Load: 6 Unused: 53 RLN: 0 is : 5HCAS Unit Stons: 6 day: 36 Port: AEQT Load: 0 Unused: 59 day: 46 Port: NRCH Load: 3 Unused: 56 RLN: 0 is : 5HCAJ Unit Stons: 3 day: 48 Port: AEQT Load: 0 Unused: 59 Air Cargo: WBP-2 day: 0 Port: WWYK Load: 0 Unused: 59 day: 35 Port: PTFL Load: 14 Unused: 45 RLN: 0 is : 0EDB Unit Stons: 107 day: 37 Port: AEQT Load: 0 Unused: 59 Air Cargo: B-747P-I day: 0 Port: WWYK Load: 0 Unused: 93 day: 35 Port: PTFL Load: 93 Unused: 0 RLN: 0 is : 0EDB Unit Stons: 107 day: 37 Port: AEQT Load: 0 Unused: 93 day: 46 Port: NRCH Load: 10 Unused: 83 RLN: 0 is : 5WYH4 B Unit Stons: 5 RLN: 1 is : 5WYH4 C Unit Stons: 5 day: 48 Port: UMXB Load: 0 Unused: 93 day: 53 Port: NRCH Load: 3 Unused: 90 RLN: 0 is : 5HEBA Unit Stons: 3 day: 55 Port: AEQT Load: 0 Unused: 93 Table 8. Initial Solution for the Passenger Example POE : NRCH departure day: 7 POD: AEQT arrival day: 8 STon: 2 1 Veh: #5 RLN: 0 is : 5HJAV Unit Stons: 2 departure day: 34 POD: AEQT arrival day: 35 STon: 6 1 Veh: #0 RLN: 0 is : 5HCAS Unit Stons: 6 departure day: 46 POD: AEQT arrival day: 47 STon: 3 1 Veh: #8 RLN: 0 is : 5HCAJ Unit Stons: 3 departure day: 46 POD: UMXB arrival day: 47 STon: 10 1 Veh: #9 RLN: 0 is : 5WYH4 Unit B 0 Stons: 5 RLN: 1 is : 5WYH4 Unit C 0 Stons: 5 departure day: 53 POD: AEQT arrival day: 54 STon: 3 1 Veh: #7 RLN: 0 is : 5HEBA Unit Stons: 3 POE : PTFL departure day: 20 POD: AEQT arrival day: 21 STon: 35 1 Veh: #23 RLN: 0 is : 6ACBP Unit Stons: 35 departure day: 28 POD: VRJT arrival day: 29 STon: 48 1 Veh: #29 RLN: 0 is : 0FBB Unit Stons: 48 departure day: 35 POD: AEQT arrival day: 36 STon: 107 2 Veh: #24,10 RLN: 0 is : 0EDB Unit Stons: 107 Table 9. Phase I Search Example (Reducing Lateness) POE : NRCH departure day: 7 POD: AEQT arrival day: 8 STon: 2 1 Veh: #5 RLN: 0 is : 5HJAV Unit Stons: 2 ALD: 4 EAD: 6 LAD:40 departure day: 34 POD: AEQT arrival day: 35 STon: 6 1 Veh: #0 RLN: 0 is : 5HCAS Unit Stons: 6 ALD: 26 EAD: 32 LAD:50 departure day: 46 POD: AEQT arrival day: 47 STon: 3 1 Veh: #8 RLN: 0 is : 5HCAJ Unit Stons: 3 ALD: 10 EAD: 11 LAD:30 departure day: 46 POD: UMXB arrival day: 47 STon: 10 1 Veh: #9 RLN: 0 is : 5WYH4 Unit B 0 Stons: 5 ALD: 34 EAD: 36 LAD:50 RLN: 1 is : 5WYH4 Unit C 0 Stons: 5 ALD: 20 EAD: 24 LAD:35 departure day: 53 POD: AEQT arrival day: 54 STon: 3 1 Veh: #7 RLN: 0 is : 5HEBA Unit Stons: 3 ALD: 30 EAD: 32 LAD:45 POE : PTFL departure day: 20 POD: AEQT arrival day: 21 STon: 35 1 Veh: #23 RLN: 0 is : 6ACBP Unit Stons: 35 ALD: 20 EAD: 24 LAD:29 departure day: 28 POD: VRJT arrival day: 29 STon: 48 1 Veh: #29 RLN: 0 is : 0FBB Unit Stons: 48 ALD: 23 EAD: 26 LAD:34 departure day: 35 POD: AEQT arrival day: 36 STon: 107 2 Veh: #24,10 RLN: 0 is : 0EDB Unit Stons: 107 ALD: 29 EAD: 36 LAD:44 Table 10. Example Phase I Results POE : NRCH departure day: 7 POD: AEQT arrival day: 8 STon: 2 1 Veh: #5 RLN: 0 is : 5HJAV Unit Stons: 2 ALD: 4 EAD: 6 LAD:40 departure day: 34 POD: AEQT arrival day: 35 STon: 12 1 Veh: #0 RLN: 0 is : 5HCAS Unit Stons: 6 ALD: 26 EAD: 32 LAD:50 RLN: 1 is : 5HCAJ Unit Stons: 3 ALD: 10 EAD: 11 LAD:30 RLN: 2 is : 5HEBA Unit Stons: 3 ALD: 30 EAD: 32 LAD:45 departure day: 46 POD: UMXB arrival day: 47 STon: 10 1 Veh: #9 RLN: 0 is : 5WYH4 Unit B 0 Stons: 5 ALD: 34 EAD: 36 LAD:50 RLN: 1 is : 5WYH4 Unit C 0 Stons: 5 ALD: 20 EAD: 24 LAD:35 POE : PTFL departure day: 20 POD: AEQT arrival day: 21 STon: 35 1 Veh: #23 RLN: 0 is : 6ACBP Unit Stons: 35 ALD: 20 EAD: 24 LAD:29 departure day: 28 POD: VRJT arrival day: 29 STon: 48 1 Veh: #29 RLN: 0 is : 0FBB Unit Stons: 48 ALD: 23 EAD: 26 LAD:34 departure day: 35 POD: AEQT arrival day: 36 STon: 107 2 Veh: #24,10 RLN: 0 is : 0EDB Unit Stons: 107 ALD: 29 EAD: 36 LAD:44 Table 11. Results of the Phase II Search Process POE : NRCH departure day: 34 POD: AEQT arrival day: 35 STon: 14 1 Veh: #0 RLN: 0 is : 5HCAS Unit Stons: 6 ALD: 26 EAD: 32 LAD:50 RLN: 1 is : 5HCAJ Unit Stons: 3 ALD: i0 EAD: 11 LAD:30 RLN: 2 is : 5HEBA Unit Stons: 3 ALD: 30 EAD: 32 LAD:45 RLN: 3 is : 5HJAV Unit Stons: 2 ALD: 4 EAD: 6 LAD:40 departure day: 46 POD: UMXB arrival day: 47 STon: 10 1 Veh: #9 RLN: 1 is : 5WYH4 Unit B 0 Stons: 5 ALD: 34 EAD: 36 LAD:50 RLN: 2 is : 5WYH4 Unit C 0 Stons: 5 ALD: 20 EAD: 24 LAD:35 POE : PTFL departure day: 20 POD: AEQT arrival day: 21 STon: 35 1 Veh: #23 RLN: 0 is : 6ACBP Unit Stons: 35 ALD: 20 EAD: 24 LAD:29 departure day: 28 POD: VRJT arrival day: 29 STon: 48 1 Veh: #29 RLN: 0 is : 0FBB Unit Stons: 48 ALD: 23 EAD: 26 LAD:34 departure day: 35 POD: AEQT arrival day: 36 STon: 107 2 Veh: #24,10 RLN: 0 is : 0EDB Unit Stons: 107 ALD: 29 EAD: 36 LAD:44 Table 12. Results of Stage 2 Search Process POE : NRCH departure day: 34 POD: AEQT arrival day: 35 STon: 16 1 Veh: #0 RLN: 0 is : 5HCAS Unit Stons: 6 ALD: 26 EAD: 32 LAD:50 RLN: 1 is : 5HEBA Unit Stons: 3 ALD: 30 EAD: 32 LAD:45 RLN: 2 is : 5HJAV Unit Stons: 2 ALD: 4 EAD: 6 LAD:40 RLN: 3 is : 5WYH4 Unit C 0 Stons: 5 ALD: 20 EAD: 24 LAD:35 POE : PTFL departure day: 20 POD: AEQT arrival day: 21 STon: 38 1 Veh: #23 RLN: 0 is : 6ACBP Unit Stons: 35 ALD: 20 EAD: 24 LAD:29 RLN: 1 is : 5HCAJ Unit Stons: 3 ALD: 10 EAD: 11 LAD:30 departure day: 28 POD: VRJT arrival day: 29 STon: 53 1 Veh: #29 RLN: 0 is : 0FBB Unit Stons: 48 ALD: 23 EAD: 26 LAD:34 departure day: 35 POD: AEQT arrival day: 36 STon: 112 2 Veh: #24,10 RLN: 0 is : 0EDB Unit Stons: 107 ALD: 29 EAD: 36 LAD:44 RLN: 1 is : 5WYH4 Unit B 0 Stons: 5 ALD: 34 EAD: 36 LAD:50 Table 13. Vehicle Usage and Lateness Stage 1 Initial Results % Reduced Obj Fn Value 3,402,252 618,289 81.83 Cargo Aircraft 1,070 804 24.86 Passenger Aircraft 1,338 985 26.38 Ships 306 224 26.80 Number Late RLN 2,158 1,354 37.26 Total Days Late 157,408 11,414 80.12 Stage 2 Stage 3 Results % Reduced Results % Reduced Obj Fn Value 400,879 35.16 324,234 19.12 Cargo Aircraft 794 1.24 1,020 (28.46) Passenger Aircraft 969 1.62 969 0.00 Ships 223 0.45 209 6.28 Number Late RLN 1,218 10.04 1,143 6.16 Total Days Late 8,944 21.64 8,625 3.57 Table 14. Passenger and Cargo Ston (in 1,000 Stons) Arrival Violations Passenger Cargo Stons Stons Total Stons JFAST SMMSP JFAST SMMSP JFAST SMMSP Stage 1 11,894 47 6 14 11,900 61 Stage 2 11,894 35 6 13 11,900 48 Stage 3 11,827 17 6 13 11,833 30

Printer friendly Cite/link Email Feedback | |

Title Annotation: | INSIDE LOGISTICS: EXPLORING THE HEART OF LOGISTICS |
---|---|

Author: | Barnes, J. Wesley; McKinzie, Kaye |

Publication: | Air Force Journal of Logistics |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Sep 22, 2006 |

Words: | 9558 |

Previous Article: | F-16 Risk Analysis: Block 60 FLIR-Assisted Landing Instruction. |

Next Article: | Logistics history: Baffled by DAFL: Directive Authority History for Logistics. |

Topics: |

## Reader Opinion