Table of Contents:
Abstract
Problem Definition
Problem Solution
Expected Results
Final Report
Interim Report
Problem Definition:
Cargo loading is generally considered a fairly simple problem, and has been solved in some form by numerous programs in the past. It consists of prioritizing packages and perhaps accounting for balance. We aim to increase the complexity of the project by minimizing the free space in the cargo hold so as to accommodate the most packages and to prevent packages from shifting during motion. These features we feel are important to accurately modeling a cargo hold and improving transportation safety.
Problem Solution:
In optimizing a cargo hold, it becomes necessary to fit as many packages as possible into a finite space and to carry as much as possible. This necessity constitutes an instance of the "knapsack" problem, since we aim to maximize masses while limiting volumes. Since no known polynomial time algorithm exists for solving such a problem (Pisinger 9), we intend to use a dynamic programming approach. Namely, our approach will use a neural network to optimize for the desirable criteria.
Initially, we will program a solution for the simplest relevant problem. Our packages will all be of uniform size, possess randomly generated weights, and be loaded by one of several methods. These loading methods will then be compared to determine how to optimize speed and carrying capacity. We aim to eventually write a program capable of determining the best way to load any given set of packages. Time allowing, we will expand into packages of various sizes and into three-dimensional solutions.
The type of artificial neural network we intend to use is the self-organizing map, developed by professor Teuvo Kohonen. Self-organizing maps (SOMs) are used to cause a computer to respond in a similar fashion to similar input. This is appropriate for our purposes, since we hope to eventually provide our program with any set of packages and receive output describing the loading method that is best for dealing with such a set.
SOMs begin by randomly generating values for each node in an array. It then compares the characteristics of input nodes iteratively to each output node, determines which node is closest (a node referred to as the Best Matching Unit, or BMU) and changes the characteristics of each output node by the following formula:
where Wv(t) is the vector representation of the output node, θ(v) is a function based on the distance from the BMU within which it is appropriate to update the node, α(t) is a learning coefficient that decreases over time, and D(t) is the input vector ("Self-organizing map"). We will use SOMs to respond to sets of packages with the best combination of one of several loading methods, one focusing on balance, one focusing on speed, and potentially other methods.
Expected Results:
We hope to eventually write a program capable of analyzing sets of packages based on number, volume, and mass. In SOM format, such a program would allow the user to find an effective solution tailored to each set of input packages. This ultimate solution would also require that the computer be capable of combining elements from various loading procedures to best accommodate for a set of packages.
Sponsoring teachers:
Jennifer Keller
Steve Schum