ALEPS: The Automated Logistics Element Planning System

1 Load Planning

Freedom's resupply/return fleet will include Pressurized Logistics Modules (PLMs) and Unpressurized Logistics Carriers (ULCs). PLMs are cylindrical carriers designed to transport cargo used in the Station's habitable interior. The floor, ceiling, and sides of PLMs are lined with several smaller modular carriers, called racks, filled with scientific experiments and variable-sized individual stowage drawers for loose items. The ULC provides flat pallet-like mounting surfaces to accommodate large unpressurized cargo and subcarriers, such as the cryogenic tanks. The task of determining what cargo to take, when to take it, where to place it, and how and when to return it to Earth is known as load planning.

2 ALEPS

To help satisfy load planning requirements, the Boeing Huntsville Advanced Computing Group is teaming with the Boeing Launch Operations and Resupply Group to build ALEPS, a comprehensive, multi-user planning and automation tool designed to ease the complex load planning task. ALEPS provides its users with two major features: an integrated set of graphical user interfaces designed to support the development, analysis, and integration of load plans, and a set of fully automated optimization algorithms which "pack" cargo carriers and perform other load planning tasks.

The current ALEPS prototype, implemented in Common Lisp, CLOS, and CLIM, provides interactive

David Michael Brady

Boeing Huntsville Advanced Computing Group 499 Boeing Blvd., MS JY-58 P.O. Box 240002

Huntsville, AL 35824-6402

Phone: (205)-464-4950

E-mail: mike@hsvaic.boeing.com

editors and browsers for every level of load planning including: packing cargo items into stowage drawers, stowage drawers into racks, racks in the pressurized modules, cargo and subcarriers on the ULC, and cargo carriers in the shuttle payload bay. The system automatically integrates packing geometry, resource utilization, and physical characteristics including weight, volume, and center of gravity across all levels of the packing hierarchy.

3 Near-Optimal Cargo Packing

The problem of generating cargo carrier load plans can generally be described as packing m cargo items into n three-dimensional spaces subject to constraints. This problem is in the class of nonlinear multidimensional knapsack and bin packing problems, well known to be NP­ complete. The Boeing ALEPS team has developed and continues to enhance a suite of algorithms designed to provide near-optimal solutions to several of the load planning tasks in this class, including the automated positioning of cargo into carriers, selection of carriers based on the cargo to pack, and the configuration of racks in the PLM. Algorithms developed so far employ a variety of techniques, including simple greedy approaches, heuristically-guided search schemes, and simulated annealing. In several test cases, the simulated annealing and heuristically-guided algorithms have outperformed human packers, producing higher-quality solutions in significantly less time. Some basic research into problem size estimation and reliable convergence to near-optimal solutions has also been done.

4 Future Work

Plans for future ALEPS research and development include algorithms for minimal replanning (to be used in last­ minute repacking scenarios), more powerful tools/algorithms for performing long-range strategic load planning, and the continued study of robust problem solving techniques.