Blake Sooter

Author: John Sooter | Major: Industrial Engineering | Semester: Spring 2022

My name is Blake Sooter; I am a student in the department of Industrial Engineering conducting research under Dr. Chase Rainwater. This spring, I began my first semester of funded research.

I met Dr. Rainwater through two semesters of coding courses; his teaching and 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. My research interest is 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 as a novel application area for linear optimization, a large sub-field of industrial engineering.

The simple example of routing optimization is as follows– a Travelling Salesman leaves his/her home, visits 5 cities exactly one time, and then returns home. What is the shortest route? This problem is extremely easy to state but computationally difficult to solve. In this small-scale example, there are 5!  = 120 possible routes. If you increase the number of cities up to 10, suddenly there are over 3 million possible routes that satisfy the problem statement. This problem has been a subject of inquiry for decades and attracted significant attention during a Procter and Gamble competition in 1962.

Now take this simple case and add multiple vehicles, customers who demand certain delivery times, vehicle capacities, etc., and you arrive at a realistic “Vehicle Routing Problem” that represents complex situations like grocery delivery. In the case of grocery delivery, the actual delivery of goods is often conducted by independent contractors using their personal vehicles, all of which have different energy consumptions for a possible route, yet another factor that must be considered.

At the start of this semester, I identified three goals for how I wanted my research to expand on the plethora of previous work on the Vehicle Routing Problem over the past 50 years.

1. Model a novel problem context that applies the methods identified in historical literature to a newly relevant context.
2. Use of real-world 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.
3. Optimize delivery routing on energy consumption rather than proxy factors such as distance or duration to minimize environmental impact and fuel costs.

To do so, I first had to evaluate several data sources and build up an environment that allowed me to easily access those data sources in code—Java is my language of choice. For routing services and address data, I chose open route service and OpenStreetMap. I set up a local instance of the open route service server and wrote a Java wrapper around their API to allow me to request routing data as inputs to my optimization model. To estimate carbon emissions, I sought out and received local access to the state-of-the-art RouteE energy consumption model developed at the National Renewable Energy Lab, which allows me to accurately estimate the energy consumption of a route for a variety of vehicle types based on distance, speed, and elevation attributes queried from openrouteservice. Elements of the RouteE model are responsible for the new eco-routing features rolled out in Google Maps late last year.

As I wrote code to morph these data sources into clean parameters for an optimization model, I was reminded of how many times I had written similar code to read CSV files, so I created a CSV utility package that reads CSV files into a list of custom objects automatically. Writing this package, while secondary to the research goal, helped me gain a broader understanding of how to write generalizable code, and the necessary documentation, packaging, licenses, and other processes related to starting an open-source project.

I formulated my linear program using Google OR-Tools and their CP-SAT solver, one of the fastest general use solvers to apply to Vehicle Routing formulations. It has numerous advantages, especially important to this problem are its incorporation of multiple solving methods and excellent multi-threading support, which will allow me to maximize the abilities of the Arkansas High Performance Computing Center down the road. Importantly, every required component of my code is open source except for RouteE, which has large parts of its output available through a public API and whose source code may become publicly available in the future.

So, what is the result of this semester’s efforts? I have successfully identified and made accessible in the Java programming language all datasets/routing engines needed to feed my optimization model. I have formulated, implemented in code, and ran to completion small instances of the model. The results of these instances strongly suggest the following—The use of energy consumption as the objective of routing optimization leads to significantly reduced emissions and fuel costs both from assigning energy intensive routes to the most fuel-efficient vehicles in the fleet and from better selection of the best route between two points from the set of possible routes using energy consumption as the selection criteria. This has provided a robust proof of concept both that an optimization model using the described data sources is feasible and that the result of such a model provides value and is worth pursuing further.

What’s next? I have begun work on, and will continue over the summer, getting the correct environment set up on the Arkansas High Performance Computing Center’s Pinnacle cluster so that I can run instances of my model that are larger and faster than what I can achieve on my desktop PC. This Fall, I will develop problem instances that are designed to further illuminate the relationship between fleet mixtures, customer flexibility, and optimization objective on overall energy consumption.