This paper describes the methodology and techniques used in solving the aircraft parking problem. The objective of this problem is to maximize the utilization of aprons which provide for parking areas for fixed- and rotary-wing aircraft. Based on aircraft parking arrangements, lateral clearance standards, grades, and other associated considerations specified for various aviation facilities, area must be reserved in the apron for necessary maneuvering through the apron, and access and exit to parking positions, and space must be included in the parking area for safe and controlled movement of aircraft under their own power. To achieve the objective while satisfying the standard requirements, we designed an efficient algorithm which first identifies a series of rectangles in parking aprons, and then finds an optimal parking pattern in these rectangles. Our algorithm considers the parking priority when there are different types of aircraft and can handle any irregularly shaped aprons. This algorithm is further enhanced by a ``what-if'' analysis to reflect the impact on the parking plan due to changed scenarios such as when a special type of aircraft is added or the parking space is reduced by hazardous cargo clearance areas. We used Esri products for data conversion, user interface and resulting parking layout display. The application was written in AML and C and was implemented on NT.
While the United States has entered into the relative calm of the post-Cold War era, conflicts continue to demand the vigilance of our armed forces in planning for worldwide force projection. Today, seething ethnic unrest, or economic upheaval are the likely causes of conflict. Such unrest is focused on the lesser developed nations of the world, with limited (and/or decaying) infrastructure to support the U.S. reliance on air mobility to deliver the bulk of traditional forces. Add to this calculus the need to rapidly deploy a local-theater force structure (including troops, and all supporting facilities) through a myriad of diplomatic agreements, such as those limiting overflight and landing access, with the same effectiveness as in a fixed-theater conflict. The need for new technologies to complement the skills of military planners in utilizing all available infrastructure is evident. Computerized decision support tools, such as ones based on geospatial information systems (GIS), provide a force multiplication factor needed by today's contingency planners.
This paper describes the development of a prototype Civil Engineer Contingency Aircraft Parking Model (CECAPP) for the Air Mobility Command Headquarters, Directorate of Civil Engineering at Scott Air Force Base, Illinois. Through the Naval Command, Control, and Ocean Surveillance Center, In-Service Engineering, East Coast Division (NISE East), a project team consisting of High Technology Solutions, Inc. (HTS), and Environmental Systems Research Institute (Esri) was formed to produce an operable prototype 30 days after the initial team meeting with the customer.
The project kick-off meeting was held on July 16, 1996 at Scott Air Force Base, where the Air Mobility Command presented the project team with an extensive, well organized collection of information on aircraft parking. In addition, the team interviewed a number of subject matter experts to generate an understanding of the manual approaches to contingency aircraft parking, and of the physical constraints faced by the contingency planner.
In the worst case scenario, the engineer is flown into the proposed airfield with little more than a suitcase of equipment with which to plan the operations of hundreds of millions of dollars of equipment, potentially affecting the lives of thousands of personnel. The engineer optimizes the available air field space through a complex manual design process to accept, park, service, and launch a variety of aircraft required by the mission. The constraints on the design process include requirements, and specifications for runways, parking aprons, and taxi lanes leading to runways and amongst parked aircraft. Data on the proposed airfield is frequently limited, and might include vector and raster products in a variety of military and commercial data formats. Without much exaggeration, the planner has little more than paper and pen with which to perform the planning function.
Based on the limited equipment space available for the deployed contingency planner, the team determined that the prototype should be designed to operate in a compact, portable computing environment - a laptop computer. The variety of data products utilized in the planning process dictated the use of a GIS software package with significant image and data integration capability. The newly released beta version of Esri's comprehensive ArcInfo GIS package for Windows NT was chosen. This decision was based on the desire to use the powerful spatial analysis and data integration tool set built into ArcInfo, combined with a programming language such as Arc Macro Language (AML), providing for remote calls to sophisticated optimization routines written in other programming languages, such as C-code.
Briefly described, the contingency aircraft parking plan development process requires the civil engineer to determine the physical and material characteristics of runways, taxiways, and aprons of the proposed facility either through direct observation, or through remotely sensed data. The planner then follows a process of eliminating aircraft from the force mix based on runway, taxiway, or apron criteria; bounding available parking areas based on aircraft access, safety clearance areas, and required storage; and then manually evaluating the remaining parking areas to optimize the number and desired type of aircraft parked. The force mix often changes during mission planning, and the planner must react quickly to such changes, reporting the impacts on aircraft parking to higher command levels.
The automated process can be described as a two-dimensional cutting problem. The parking area for each aircraft may be viewed as a rectangle, with known dimensions and other restrictions (such as required pavement strength) as attributes. However, the problem is more complicated than that of cutting the given parking area into the maximum number of equal sized rectangles, since the parking area rectangle varies in size with aircraft type. The complexity of the problem increases further by user-definition of odd shaped parking areas. Within the context of achieving a parking scenario within a reasonable computing time, there is no exact solution to the problem. Noting the complexity, the project team proceeded with a heuristic approach, attempting to reach a reasonable, vice optimal, solution. Other sections of this paper will describe the development of the optimization algorithm, and the process of integrating the various modules.
It should be noted that the challenge of the CECAPP development project extended beyond the complexity of the algorithm. Incorporating a beta release of the ArcInfo for Windows NT software, while leading to some valuable improvements in the package prior to production release, complicated the installation and testing process at Scott Air Force Base. In addition, the project team was geographically dispersed - with NISE East located in Charleston, SC; HTS located in Fairfax, VA; and Esri located in Redlands, CA. Despite these complexities, the project team performed well together in a "virtual teaming" environment, and the ArcInfo NT product provided a seamless transition for the GIS professionals familiar with the ArcInfo product for the UNIX environment.
After the initial meeting, and development of a detailed work schedule, the team returned to their home offices to begin development. During the final two weeks before the prototype demonstration, the HTS project engineer returned to Scott Air Force Base, reviewing Air Force requirements against the model, transferring and loading files, and confirming the operation of the software. Additionally, valuable test information on the beta ArcInfo NT product were relayed back to Esri in Redlands. The entire project team met again at Scott Air Force Base during the final week of the project.
The prototype CECAPP model was presented at Scott Air Force Base, Illinois by the NISE East Team to Brig Gen Philip Stowell, commander of the Directorate of Civil Engineering, Air Mobility Command Headquarters on August 23, 1996.
The aircraft parking problem can be regarded as a variation of the 2-dimensional cutting problem which arises in a wide range of industries such as glass, steel, wooden or paper industries. In the Operations Research literature, many researchers have developed models and methodologies for determining how a set of two-dimensional shapes will fit onto one or more stock sheets in a way that the waste is minimized.
One common feature of most of the cutting problems is that both the stock sheet and the pieces to be cut from the stock sheet are all shaped as rectangles. In some cases, the guillotine cutting pattern is assumed, i.e., all cuts must go from one edge of the rectangle to be cut to the opposite edge. In general, a 2-dimensional cutting problem can be described as follows: Given a rectangular stock sheet with length L and width W, and a set of rectangles R1, R2, ... Rn, determine a cutting pattern and the number of each rectangle to be cut from the large stock sheet such that the trim waste is minimized.
For more detailed discussions of cutting problems, interested readers are referred to the papers by Dyson et al.(1974), Christofides et al.(1977), Wang(1983), Dagli et al.(1990), Farley(1990), Oliveira(1990), Stadtler(1990), Wascher(1990). For a survey of cutting problems, see Dyckhoff(1990).
In the aircraft parking problem, the parking area (referred to as ``apron'' in the following) serves as the ``stock sheet'', and for parking purpose, each aircraft can be represented by a rectangle with fixed dimensions, and these rectangles correspond to the pieces to be cut in the cutting problem. The aircraft parking problem, however, differs from the traditional cutting problem in many ways and is more involved. One major difficulty here is that the aprons can be of any shapes. In addition, a number of rules governing aircraft parking must be considered:
Furthermore, some implicit requirements should also be addressed. e.g., due to maintenance and management reasons, aircraft of the same type should be parked together whenever possible.
From the above analysis for the similarity and differences between the aircraft parking problem and the 2-dimensional cutting problem, we can see that while some of the existing algorithms found in the Operations Research literature, with necessary modifications, could be useful in determining an optimal parking pattern, new algorithms should also be developed to handle the complexity inherited in this problem. The algorithms used in this application are described in more detail in the next section.
Based on the understanding of the Air Force's requirements for the aircraft parking planning and experience that Esri has obtained in developing various types of GIS projects, the Esri team used the following methodology to facilitate the development of the GIS in support of the aircraft parking planning. This methodology consists of six primary tasks:
In this paper, however, we focus on the description of the application development. This task involves coding, debugging and testing the optimization algorithms, and integrating the application into the configured environment. Coding includes developing a software application in C, writing ARC Macro Language (AML) procedures, or customizing a menu or other element of the graphical user interface. Testing is accomplished by inspection and demonstration at component level and at the system level to show that an end-to-end process for aircraft parking is accomplished.
Our parking optimization procedure contains four major steps:
Step 1: Prepare input data.
Step 2: Identify rectangles in each apron.
Step 3: Park aircraft in rectangles.
Step 4: Report and display results.
These steps are detailed below.
The input data required for the parking optimization include geographical data and parking specification data. The geographical data are originally provided with a CAD file or an image file. Our application can import a CAD file directly into an ArcInfo coverage, and then convert it into real world coordinate system by registering the four corners of the runway or any rectangle features. For an image file, our application has the capability to register it on the fly. Based on the type of image file the system is going to display, an image world file is created by using six-parameter affine transformation to georeference an image. The image is rectified based on the world file created.
The system also provides tools that allow users to digitize the features which will be used by the parking optimization. Users can optionally choose to use the CAD file or the rectified image as reference for digitizing. The system uses GIS technologies provided by the ArcInfo software to perform some advanced spatial analyses, e.g. edge touching, adjacent edge, spatial overlay or intersect, etc., to assist the optimization procedure. At the end of data conversion, some necessary attributes are also added for each geographical feature.
Most of the parking specification data are provided with text files. These are for the number and size of each type of aircraft to be parked, clearance distance, pavement requirement and parking direction for each aircraft type, apron and taxiway pavement specification, etc.
In this step, we identify a series of rectangles in each apron. The reasons for doing so are:
In the process of identifying rectangles from available aprons, we maintain two lists: a polygon list and a rectangle list. Initially, the polygon list contains all the polygons representing the aprons while the rectangle list is empty. Each time we take one polygon from the polygon list, and make a rectangle which lies on at least one edge of the polygon, and has the largest area. Then this rectangle is ``cut'' from the polygon and is put into the rectangle list. The remainder of the original polygon consists of one or more small polygons. Each of these small polygons is either discarded if its area is less than a pre-specified threshold, or put back to the polygon list. This process is repeated until the polygon list is empty. At the end of this step, the rectangle list contains all the rectangles that can be used to park aircraft in Step 3.
In this step, we apply some modified cutting algorithms to determine the parking pattern in each rectangle generated in Step 2. We also maintain two lists in this step: an aircraft list and a rectangle list. The aircraft list contains specifications for each aircraft type, including the number remained to be parked, parking priority, size, pavement requirement, taxiway requirement, etc. This list is sorted, first by parking priority, and then by size. The aircraft are then parked in the order as they are in the aircraft list. While the rectangle list is not empty, we choose the rectangle which is closest to a major taxiway and has the largest area. The parking direction in this rectangle is determined based on the relative position of the major taxiway that will be used by the aircraft parked in this rectangle. When we park an aircraft in a rectangle, we first check if the pavement for this rectangle supports this type of aircraft. In the rectangle, in addition to reserving parking space and clearance distance for each aircraft parked, we need also reserve taxiways along the edges for entrance and exit from parking positions. However, if two rectangles are adjacent then the taxiway is reserved in only one rectangle along the common edge. After parking in a rectangle, some space (a slack rectangle) could be left unused, and this space will be appended to an adjacent rectangle if a larger rectangle can be made. This process is repeated until the aircraft list is empty or the rectangle list is empty.
Given the data described in Step 1, our application generates an optimal parking layout which is displayed in Arcplot in polygon coverage format, with symbols representing aircraft parked at different angles. A report is also provided to summarize the number of each type of aircraft parked, the utilization of the parking aprons, etc.
A set of editing tools is included in this application to perform basic parking editing and a ``what-if'' analysis. For example, if a special type of aircraft is added to the aircraft list, the application will either remove some aircraft with low priority to give space for the newly added aircraft, or rerun the program to find a new parking pattern; or if the parking space is reduced by hazardous cargo clearance areas, our application will identify the reduced areas and then either remove the aircraft parked in those areas or adjust the aprons and rerun the program, based on the user's choice.
This paper described an application of GIS softwares and Operations Research techniques for the aircraft parking problem. The objective of this problem was to maximize the utilization of aprons which provide for parking areas for fixed- and rotary-wing aircraft. To achieve the objective while satisfying the standard requirements, we designed an efficient algorithm which first identifies a series of rectangles in parking aprons, and then finds an optimal parking pattern in these rectangles. Our algorithm considers the parking priority when there are different types of aircraft and can handle any irregularly shaped aprons. This algorithm was further enhanced by a ``what-if'' analysis to reflect the impact on the parking plan due to changed scenarios such as when a special type of aircraft is added or the parking space is reduced by hazardous cargo clearance areas. We used Esri products for data conversion, user interface and resulting parking layout display. The application was written in AML and C and was implemented on NT.
We may find many potential applications of the methodology and techniques used in solving the aircraft parking problem. First, the algorithms described here can be readily used in solving general parking problems; secondly, there are many situations where the stock sheet in the 2-dimensional cutting problem is irregularly shaped. In these cases our algorithms may provide promising solutions.
We may also have some extensions to the approach we have developed in this application. One extension is for the cutting or loading problems in the context of high dimensions, e.g., the ``mixed load'' problem (a 3-dimensional problem) and the vehicle loading problem with time window constraints (a 4-dimensional problem); another extension is to deal with the more challenging 2-dimensional problem when both the stock sheet and the pieces to be cut are irregularly shaped. We hope our effort made here could stimulate research in these directions.