A quadratically constrained mixed-integer non-linear programming model for multiple sink distributions

Sweet Mama’s Tomato Mix is a tomato-paste produced by the Weddi Africa Tomato Processing and Agro Farm. Weddi is a vertically integrated wholesaler: it operates the farm, it runs the processing plant, and it owns the distribution centers. It delivers five products (pastes in various-sized containers) directly to retailers in its own fleet of trucks, driven by its own drivers.

The company operates in Ghana, in or around the city of Kumasi, a metropolitan area that is home to nearly 4 million residents. Weddi's main factory is about a hundred miles outside of the city, but its distribution hubs are closer to the city limits.

Weddi is a mid-sized business, offering commodity products in a competitive market. So naturally, margins are tight. Weddi is looking for efficiency gains, and they've turned their eyes to their transportation costs. Those costs are high, but a solution to bring them down isn’t readily apparent. Here are the factors complicating the situation:

• They deliver to multiple locations.
• Each location has an acceptable set of delivery-days and times.
• Each location has a unique demand-level for each of Weddi's five products. This means that every delivery is unique in terms of product assortment.
• In some locations traffic causes delays at regular times, but also occasionally at unexpected times.
• Their vehicle fleet is heterogeneous: they have multiple different trucks, with different fuel efficiency levels, and different payload capacity.
• They do a combination of long-haul trucking (from the factory to the distributors) and shorter runs (from the distributor to the retailer).
• In order to prevent delays at the retailers, trucks must be loaded as a LIFO queue of pallets (Last In First Out). In order for this to work, the delivery-order must be known prior to packing the truck.

Weddi is aware that there's likely waste and inefficiency somewhere in their system, but creating a route-planner that factors in all of these variables is non-trivial. That's where today's paper comes in. The authors picked Weddi as a case-study, and decided to develop a solution specifically for the company.

They framed the challenge as a Constraint Satisfaction Problem, or more specifically an HC-VRP: a Heterogeneous Capacitated Vehicle Routing Problem. There is a huge amount of literature on vehicle routing problems. So before they did anything new, the authors considered a whole host of out-of-the-box solutions. This included models like North-West Corner, Least Cost, Vogel’s Approximation and more. But after a review they found that the existing options were all missing something. They either omitted:

• The fact that Weddi's fleet of vehicles was heterogeneous.
• The fact that Weddi's products had different weight and volume profiles.
• Or the fact that Weddi's system needed to incorporate real-time traffic data.

The authors weren't able to find any pre-built solution that would accommodate all of these parameters, so they decided to create their own model. Specifically, they set their sights on a QC-MINLP, a Quadratically Constrained Mixed Integer Non-Linear Programming model.

Side note: Before we continue, if you’d like a quick refresher on Linear Programming and Mixed-Integer Linear Programming please go back to our episode from September 17th, 2024 titled "the Fog Node Location Problem". In that episode I do a run-down of those concepts. If you don’t have access to that episode just reply to today’s email so I can send it your way.

Unlike solutions we've discussed in other episodes, these authors were developing a model that in addition to being MINLP, has the added quality of being Quadratically Constrained. All that means in a nutshell is that the equations that act as constraints can have exponents on the variables, specifically the number 2. In other words, the constraint equations can have variables that are squared. Remember, quadratic means raised to the power of 2, cubic is 3, quartic is 4 etc. So if this was called a Cubically Constrained problem it would be the same except the exponents on variables in the constraints could be 3 instead of 2.

So anyway, they needed to create a QC-MINLP. But how on earth does one do that? Well, there are a few ways. In their case, they turned to AMPL. AMPL is a programming language that most people (and even most Software Engineers) have never heard of. Its obscurity is due to the fact that it’s not a general-purpose programming language. It’s an AML: an Algebraic Modeling Language. This language exists to solve optimization problems. At a high level, the process of using it goes like this:

• You define the input parameters, for data entering the system.
• You define all the static variables and constants in the system.
• You define all the mutable variables. Some of these will be the "decision variables" you’ll be asking the program to solve for.
• You define constraints and equations that relate the variables to each other.
• You write an objective function that represents the goal.
• You choose a "solver". A solver can be a single algorithm or a collection of them. They're almost like mini models in themselves. There are many solvers to choose from, and just like any other algorithm they have different strengths and weaknesses.
• You gather data so that you can provide the solver with meaningful inputs.
• You execute the solver and let it “solve” (optimize) the problem for the set of inputs you provide.
• The solver returns the solution: the optimal values for your decision variables.

The above is an oversimplification, but the broad strokes are true. With AMPL as their chosen tool, the authors now just needed to follow those steps to generate a solution. So that’s what they did:

• They defined a set of basic variables and constants, and then 11 compound variables. These compound variables were things like MDWP: the quantity of each product P transported from a warehouse W on a day D. Or variables like YV: the number of trips each vehicle V can make in a day.
• They defined 26 input parameters. These included things like the weight of each vehicle, the current fuel price per liter, the capacity of each warehouse, the distance between a given warehouse and a retailer, etc.
• They defined the objective function as minimizing the sum of all vehicle operational costs.
• They defined 17 constraints, and then over a dozen additional variable conditions and parameter definitions. So all together they wrote over 30 individual equations.
• They chose the Gurobi solver package. This is a proprietary solver by the Gurobi Optimization company. So unfortunately it is a bit of a black box in regards to its inner workings.
• They gathered data from four sources: They got delivery-vehicle information from Weddi’s fleet management team. They got product-weights and dimensions from Weddi’s factory production team. They calculated route distances and travel times from GPS data, historical traffic patterns, and Google Maps. And finally they got product-demand data from the company's historical sales records.
• They passed all of this input data to the Gurobi solver and let it run.

The solver returned recommended routes, recommended vehicles, departure dates, departure times, vehicle loading procedures, and logic rules for handling traffic congestion. Overall, the results were remarkable: they saw a 27.59% reduction in total transportation costs.

That being said, the authors noted that the solution they generated wasn’t necessarily scalable. The computational complexity of the solution, they believe, will increase disproportionately as the system scales, making it best suited for smaller/mid-sized businesses and not large enterprises.
​
So, what can we take away from this paper? I’m hoping you’ll remember two things:

1. No matter how daunting an optimization problem is, it can always be broken down into small pieces, and then systematically solved. It might take forever, it might require that you go through the extremely tedious process of defining dozens of equations and variables. But at the end of the day, it is doable. As they saying goes: How do you eat an elephant? One bite at a time.
2. In some cases, Algebraic Modeling Languages like AMPL may be better suited to your task than a general purpose language. Tools like AMPL allow you to write in what feels like normal mathematical notation. So embracing these kinds of tools don’t require that you learn an entirely new language. You only need to learn how to use their platform.

This paper included a number of diagrams, route maps, equation lists, variable lists and more. If you’d like to check out any of these materials, I recommend that you download the paper.