The University Scholars Program

Mathematical optimization of complex systems is a relatively new area of research that is rapidly growing due to its importance in addressing real-world problems. With the price of travel increasing and congestion steadily rising, it is important to find more efficient approaches to solving problems such as those presented in routing and monitoring. My research project will ultimately try and tackle a large scale "Close Enough" Traveling Salesman Problem which implies finding the shortest distance to visit a set of regions and return to our starting node. Our model decomposes the United States of America into a series of independent convex regions that must be visited, though the model will be flexible enough to allow the user to provide inputs from any set of (possibly non-convex) bodies. Large scale Traveling Salesman Problems are generally very heavy computationally and it was our goal to develop a model that alleviated some of this strain and sped up the process. We achieved this by using a method known as Benders Decomposition that breaks the problem into a Master Problem and Sub Problem that are iterated over adding constraints as they are needed. This provides a much quicker and more efficient convergence than many other conventional methods. This method was implemented in a computer modeling program known as GAMS (General Algebraic Modeling System) that allows us to solve and modify the problem as needed. This model can be used in those situations where it is only necessary to be within a certain region to perform an action (e.g. broadcast a signal, monitor an area, deliver a package, etc). Due to the flexibility of the model, it can easily be transformed to fit any of the applications listed above extending the depth of this project beyond just the United States model provided.