How We Optimized The Problem Of Global Containers Distribution
Recently I was invited by a coworker to join a project for a big company in Brazil that sells goods and services on a global scale.
The project involved transport optimization and was quite interesting – and challenging – so I'd like to write about it and how we solved the problem using the library cvxpy (also used to solve optimization problems at companies like Tesla, Netflix and Two Sigma).
Specifically, this post covers:
- The challenge of transporting containers globally with a set of several constraints.
- How we managed the company's data and described it as a set of linear transformations.
- How we adapted the variables and constraints to fit the Linear Programming formulation.
- Techniques used to guarantee the objective function and constraints were convex – Cvxpy's main restriction.
With no further ado, let's dive into it.
1. The Challenge
When the project started, the company revealed us that they already had a solution implemented on top of Microsoft Excel Solver to optimize how to best manage the containers. The Solver aimed to reduce costs of transportation, freight, storage, and operation while following a set of constraints.
The solution worked fine but as operations expanded the process began to halt and suffer with some bottlenecks, as the company explained. At times, they had so many containers to allocate that it would take the Solver a few days to process the whole dataset and come up with an answer.
They requested us to develop something new that could handle the workload of the system while also being flexible enough so that the system would accept new constraints on demand.
To begin with, the company has factories located across the country and containers are prepared by demand on each factory:
Each factory produces containers weekly according to its own demands, which means some factories will produce more containers than others. Each container carries its own goods so the sales price changes as well (this variable will be important soon).
The destiny of each container also varies; some will be transported to nearby countries whereas others have to cross the globe. Therefore, the company needs to send the containers to appropriate docks or it risks not succeeding with the delivery (due the lack of connection between the docks of each country).
Several new variables shows up when trying to connect factories to the appropriate docks. First, each factory may choose how to transport the containers: either by using trains – and, in doing so, there are various types of contracts to choose from – or by trucks (again, multiple types of contracts as well):
Now another challenge arises: each container has a specific destination and so does the ships available on each dock. Destinations must, therefore, match! If a container that should go to Hong Kong is transported to a dock where no ships will be going to Asia then we just sacrificed an entire container.
The matching problem means that, at times, factories may need to transport a container to a more distant dock (and expend more money) simply because it's the only remaining option for making the connection between Brazil and the rest of the world. Shippers will be another variable and they should be accounted for availability in terms of spaces on each ship and also the ship's destination.
Shippers may also allow for what is known as "overbooking spaces", that is, just like the concept applies to airline flights, it also applies to ships but here the concepts is a bit less restrictive: for a given week, shippers can inform an "overbooking factor" which gives us an idea of how many more containers can be added on each ship above the threshold capacity – with a higher freight, as expected. The optimizer can use this factor to allocate remaining containers and take advantage of cheaper transportation, for instance.
The optimizer must consider as well a set of rules to follow. Here's a brief list of requirements:
- Ships have a maximum capacity: each ship attends specific regions through what is called "trades". Each shipper have a maximum capacity of containers for each trade – this rule can be broken at times through overbooking.
- Connect factory and dock: factories can only send containers to docks with valid and available transportation – if a factory does not have a train station connection to a given dock then the optimizer must choose another transport.
- Transportation Limits: the company made clear that contracts and slots available for transportation can vary; they have agreements and licenses to use certain slots from trains monthly, which adds an upper cap on number of containers.
- Connect departure dock and shipper: the optimizer must send containers from factories to docks that contains shippers with spaces on ships and attend the trade where the container is going.
- Overbooking: overbooking can happen – like an extra trick at our disposal. Each shipper have a factor of how many slots may be used above the max cap. Containers under overbooking are much more expensive and it should happen only if all prior available spaces have already been consumed.
- Transport Or Not Transport: The optimizer may conclude that it's better to store a given container in the factory than transporting it, which affects the total costs expectation.
Are we there yet? Well, not really. In practice, the challenge is a bit more evolved as it should contain the time that factories take to transport each container and connect it to when shippers will be available at the docks. If we end up choosing a transport that is too slow we may miss the ship and either have to wait and hope that there is another ship going to the same destination or we basically just lose the container. This post does not consider the time variables as it makes development much more complex.
We have the challenge, now, let's see how we solved it
