Comparison of Optimization Techniques in Large-scale Transportation Problems
Location
CSU 255
Start Date
13-4-2004 10:30 AM
End Date
13-4-2004 12:15 PM
Student's Major
Computer Information Science
Student's College
Science, Engineering and Technology
Mentor's Name
Susan Schilling
Mentor's Department
Computer Information Science
Mentor's College
Science, Engineering and Technology
Description
The transportation problem is a classic Operations Research problem where the objective is to determine the schedule for transporting goods from source to destination in a way that minimizes the shipping cost while satisfying supply and demand constraints. Although it can be solved as a regular Linear Programming problem, other methods exist. Linear Programming makes use of the "Simplex Method," an algorithm invented to solve a linear program by progressing from one extreme point of the feasible polyhedron to an adjacent one. The algorithm contains tactics like pricing and pivoting. For a transportation problem, a simplified version of the regular Simplex Method can be used, known as the "Transportation Simplex Method." This paper will discuss the functionality of both of these algorithms, and compare their run-time and optimized values with a heuristic method called the "Genetic Algorithm." Genetic Algorithms, pioneered by John Holland, are algorithms that use mechanisms similar to those of natural evolution to encourage the survival of the best intermediate solutions. The objective of the study was to find out how these algorithms behave in terms of accuracy and speed when solving a large-scale problem.
Comparison of Optimization Techniques in Large-scale Transportation Problems
CSU 255
The transportation problem is a classic Operations Research problem where the objective is to determine the schedule for transporting goods from source to destination in a way that minimizes the shipping cost while satisfying supply and demand constraints. Although it can be solved as a regular Linear Programming problem, other methods exist. Linear Programming makes use of the "Simplex Method," an algorithm invented to solve a linear program by progressing from one extreme point of the feasible polyhedron to an adjacent one. The algorithm contains tactics like pricing and pivoting. For a transportation problem, a simplified version of the regular Simplex Method can be used, known as the "Transportation Simplex Method." This paper will discuss the functionality of both of these algorithms, and compare their run-time and optimized values with a heuristic method called the "Genetic Algorithm." Genetic Algorithms, pioneered by John Holland, are algorithms that use mechanisms similar to those of natural evolution to encourage the survival of the best intermediate solutions. The objective of the study was to find out how these algorithms behave in terms of accuracy and speed when solving a large-scale problem.
