Author: John Sooter | Major: Industrial Engineering | Semester: Fall 2023
My name is Blake Sooter; I am an honors student in the Department of Industrial Engineering. Fall 2024 represented my 4th semester of funded research. Throughout my time at U of A, my research mentor has been Dr. Chase Rainwater, who I connected with through his introductory programming classes. Since then, I’ve benefited hugely from his mentorship on my own projects while also working as an undergraduate teaching assistant and research assistant. Building relationships with faculty has made a tremendous difference in my college experience!
This year, I’ve been building a web-app to deliver the power of Google OR-Tools’ suite of optimization algorithms to everyday users. The idea for this came from my interest in coding, my own desire to apply optimization to others’ lives, and the need for industrial engineering to better explain what it is that industrial engineers do.
There is an immense set of problems that can be solved using what you might call the “classics” in Operations Research: linear and integer programming, shortest path algorithms, metaheuristics, etc. All these approaches are widely available as open-source software—if you can merge the right data, algorithms, and formulation for your problem. It can be a lot of work to apply optimization your own life—what I’ve attempted here is to create use-cases that are easy to interact with and more relevant to the everyday person than a classical corporate example like oil blending, discounting schemes, or worker scheduling. To do so, I’ve integrated the problems with the relevant data sources, displayed solutions with appropriate visualization, and made the application readily available online. To do this, I’m using a phenomenal software package called Streamlit that allows anyone with Python programming experience to build and deploy a web-based application alongside their normal scientific computing workflow.
I’ve created five use cases: running route generation, trip planning, time blocking, linear programming, and the classic knapsack problem. You can check out any of the use cases here.
In the development process, I learned a lot about both optimization algorithms and open-source software. There’s too much to go through here, but I’ll use the running route generation as an example. The core idea is simple: how can I take a starting location (preferably my address) and find an out and back route that provides me the distance I need to run surrounded by a safe and enjoyable environment, avoiding Fayetteville hills where I can? This roughly amounts to a shortest path problem and can be solved by Dijkstra’s algorithm with time complexity scaling with the number of nodes. Unfortunately, there are various complications. For a run, how do I pick a destination node? There’s no required destination like if you were driving to school or work. Amongst a car-focused infrastructure, what portions of the street network should be considered for running? You don’t want to jog down the interstate. How should I define ‘cost’? Clearly, the quantity I want to optimize is some representation of quality for running, not simply distance. What guarantees generated routes will be of at least a certain distance? Can all of these questions be answered as heuristic modifications around Dijkstra’s Algorithm, rather than resorting to math programming, which is NP-hard and even worse than runtime, a particular problem when you may want to generate many routes for the runner to choose from?
To answer these questions, I went through many iterations (and continue to iterate) as I did my own research and got feedback from a couple of my peers. I have enjoyed going back and forth with them about their experience using the tool. To find destination nodes, I used osmnx to query the graph of an area that was half the desired route distance based on the shortest possible network distance to that location from the origin, and then ran the same query for a distance 1.1x the size. The nodes that were included in the larger network but not the smaller network are candidate destination nodes, geometrically guaranteed to provide a route no shorter than desired, no matter the optimization criteria. Then, as runners are notoriously partial to ending their runs at an exact mileage, solution routes are iteratively trimmed until the out and back distance is within a small tolerance of the preferred mileage. To narrow the network down to safe roadways, I developed a filter query to only include arcs such as footways, sidewalks, residential roadways, and other friendly designations like greenways and trails. This is a very “constrained” approach, limiting the solution set because it could introduce discontinuities from origin to destination in the resulting network, but the custom filter allows this scope to be expanded as more tags are tested and found to be appropriate. To create a cost function, there were two key hurdles to overcome—1) what should the factors be, and 2) how to weight them. By constraining myself to the factors that have a high prevalence in openstreetmap data, and are important to runners, I composed a cost function of roadway speed, turns, grade, and roadway type, equally weighted (but adjustable by the user), and multiplied by the length of the arc, so that a long bad arc cost proportionally more than for short bad arcs.
Though my research project period is coming to an end, I’ll continue to develop this project on the side as I think up improvements to the user interface and new problem instances. If you’re reading this, feedback on any of the existing app or suggestions for new features are welcome and appreciated!