Author: John Sooter | Major: Industrial Engineering | Semester: Fall 2022
My name is Blake Sooter; I am an honors student in the department of Industrial Engineering. This Fall marked my second semester of funded research.
My research mentor is Dr. Chase Rainwater, whom I met through two semesters of programming courses. Dr. Rainwater’s guidance has been tremendously impactful on my experience at the University of Arkansas. His knowledge of computing and optimization has been critical to this research effort and to my education. We are fortunate to have faculty at the University of Arkansas who care about the undergraduate student experience.
My research interest is in operations research, a discipline that has heavy overlap with industrial engineering and is focused on quantitative approaches to decision making. I have spent the past two semesters looking at the optimization of last-mile grocery delivery services to minimize energy consumption, and, by extension, carbon emissions and fuel costs. I selected this topic due to the explosion of last mile delivery services in all parts of our economy that was accelerated by the onset of COVID-19.
Routing problems belong to a class of problems referred to as NP-hard, meaning that thus far, no computationally feasible exact algorithm has been found to solve them. In a simple example, if I were to leave my home, visit 10 friends exactly once, and return to my home, there are over 3 million possible routes by which to do so. In real world applications, there are far more “friends”, drivers, and additional requirements such as vehicle capacity and time windows that quickly make an already difficult problem intractable. This reality has motivated a rich literature on the vehicle routing problem, metaheuristic solution approaches, various problem statements and formulations, and real-world applications. A quick search on Google Scholar reveals over 900,000 academic works on the subject.
For my research, I identified three goals for how I wanted to expand on the plethora of previous work on the Vehicle Routing Problem over the past 50 years. First, I wanted to apply the methods identified in historical literature to a newly relevant context. This objective was achieved in two ways: 1) by applying a cutting-edge energy consumption model from the National Renewable Energy Lab to minimize carbon emissions, and 2) by optimizing grocery delivery, an industry still in its infancy in the United States that has developed far differently than a more traditional logistics network like UPS or FedEx operates.
Second, I wanted to make use of real data for customer and store addresses, route characteristics, and fuel consumption that has become much more available in the past decade and is underutilized in academic research. Even in the technology-centric, data rich environment of 2022, introducing real world complexity to a clean analytical model was a significant undertaking. I setup local Docker instances of Openrouteservice and openstreetmap, customized their configurations to meet the needs of the project, and obtained access to a local copy of the default RouteE energy model. For Openrouteservice, I created a Java wrapper around their API to consume routing data into my optimization model. In addition, I wrote code to parallelize requests to Openrouteservice, which significantly stretched my coding knowledge and prevented a “pre-optimization” step from becoming a burdensome bottleneck. To use these technologies together in a harmonious fashion required significant iteration. Git version control was vital to keeping everything together. My proficiency with various technical frameworks was dramatically expanded by this project.
Lastly, I wanted to provide concrete evidence that optimization based on energy costs leads to reduced energy consumption without any vehicle fleet changes or modifications to operating procedures. I have found an ~1% savings in computational experiments.
I am in the process of submitting a conference paper to the IISE Operations Research Division Undergraduate Student Research competition at IISE annual in May 2023. I am looking forward to sharing the following key takeaways:
- To provide a fair comparison between models with energy/distance/duration objectives, the arc cost parameters must be recomputed to select the best arc for the objective criteria.
- Metaheuristic solution approaches are required to find solutions to realistically sized problem instances, and even these can present computational challenges when seeking quality solutions.
- The problem can be discretized into various subproblems to reduce the computational complexity of each problem instance and aid the metaheuristic in providing results that are closer to the true optimal solution.
- Grocery delivery provides an approximately 67% reduction in energy consumption vs traditional grocery shopping.
- Without any changes to operational procedures or vehicle fleet, optimization based on energy consumption provides a ~1% energy savings without generating unreasonable tradeoff distance or duration costs.
In the future, I hope to further develop the subproblem approach to obtaining an approximate solution to the problem, and I would like to further evaluate the role of maximum driving speeds in energy consumption. Furthermore, I would like to evaluate differences in model outcomes between electric and internal combustion engine vehicles.
For Spring and Fall of 2023, I will be working on an Honors College Research Grant to develop a low-code, web-based optimization tool on top of the Google OR-Tools framework.