How We Optimized The Drawback Of International Containers Distribution | by Will Fuks | Aug, 2024

Not too long ago I used to be invited by a coworker to affix a mission for an enormous firm in Brazil that sells items and companies on a worldwide scale.

The mission concerned transport optimization and was fairly attention-grabbing — and difficult — so I’d like to put in writing about it and the way we solved the issue utilizing the library cvxpy (additionally used to unravel optimization issues at firms like Tesla, Netflix and Two Sigma).

Particularly, this publish covers:

1. The problem of transporting containers globally with a set of a number of constraints.
2. How we managed the corporate’s information and described it as a set of linear transformations.
3. How we tailored the variables and constraints to suit the Linear Programming formulation.
4. Strategies used to ensure the target perform and constraints had been convex — cvxpy’s essential restriction.

With no additional ado, let’s dive into it.

When the mission began, the corporate revealed us that they already had an answer carried out on high of Microsoft Excel Solver to optimize the best way to finest handle the containers. The Solver aimed to scale back prices of transportation, freight, storage, and operation whereas following a set of constraints.

The answer labored superb however as operations expanded the method started to halt and undergo with some bottlenecks, as the corporate defined. At occasions, that they had so many containers to allocate that it will take the Solver a couple of days to course of the entire dataset and provide you with a solution.

They requested us to develop one thing new that might deal with the workload of the system whereas additionally being versatile sufficient in order that the system would settle for new constraints on demand.

To start with, the corporate has factories positioned throughout the nation and containers are ready by demand on every manufacturing facility:

Every manufacturing facility produces containers weekly based on its personal calls for, which suggests some factories will produce extra containers than others. Every container carries its personal items so the gross sales worth adjustments as properly (this variable will probably be necessary quickly).

The future of every container additionally varies; some will probably be transported to close by international locations whereas others should cross the globe. Due to this fact, the corporate must ship the containers to applicable docks or it dangers not succeeding with the supply (due the dearth of connection between the docks of every nation).

A number of new variables reveals up when attempting to attach factories to the suitable docks. First, every manufacturing facility could select the best way to transport the containers: both by utilizing trains — and, in doing so, there are numerous kinds of contracts to select from — or by vehicles (once more, a number of kinds of contracts as properly):

Now one other problem arises: every container has a selected vacation spot and so does the ships out there on every dock. Locations should, subsequently, match! If a container that ought to go to Hong Kong is transported to a dock the place no ships will probably be going to Asia then we simply sacrificed a whole container.

The matching drawback implies that, at occasions, factories might have to move a container to a extra distant dock (and expend more cash) just because it’s the one remaining choice for making the connection between Brazil and the remainder of the world. Shippers will probably be one other variable and they need to be accounted for availability when it comes to areas on every ship and in addition the ship’s vacation spot.

Shippers can also permit for what is named “overbooking areas”, that’s, similar to the idea applies to airline flights, it additionally applies to ships however right here the ideas is a bit much less restrictive: for a given week, shippers can inform an “overbooking issue” which provides us an concept of what number of extra containers will be added on every ship above the brink capability — with a better freight, as anticipated. The optimizer can use this issue to allocate remaining containers and reap the benefits of cheaper transportation, as an illustration.

The optimizer should contemplate as properly a algorithm to comply with. Right here’s a short record of necessities:

• Ships have a most capability: every ship attends particular areas by way of what known as “trades”. Every shipper have a most capability of containers for every commerce — this rule will be damaged at occasions by way of overbooking.
• Join manufacturing facility and dock: factories can solely ship containers to docks with legitimate and out there transportation — if a manufacturing facility doesn’t have a prepare station connection to a given dock then the optimizer should select one other transport.
• Transportation Limits: the corporate made clear that contracts and slots out there for transportation can differ; they’ve agreements and licenses to make use of sure slots from trains month-to-month, which provides an higher cap on variety of containers.
• Join departure dock and shipper: the optimizer should ship containers from factories to docks that accommodates shippers with areas on ships and attend the commerce the place the container goes.
• Overbooking: overbooking can occur — like an additional trick at our disposal. Every shipper have an element of what number of slots could also be used above the max cap. Containers beneath overbooking are way more costly and it ought to occur provided that all prior out there areas have already been consumed.
• Transport Or Not Transport: The optimizer could conclude that it’s higher to retailer a given container within the manufacturing facility than transporting it, which impacts the overall prices expectation.

Are we there but? Nicely, not likely. In observe, the problem is a little more developed because it ought to include the time that factories take to move every container and join it to when shippers will probably be out there on the docks. If we find yourself selecting a transport that’s too sluggish we could miss the ship and both have to attend and hope that there’s one other ship going to the identical vacation spot or we principally simply lose the container. This publish doesn’t contemplate the time variables because it makes improvement way more complicated.

Now we have the problem, now, let’s see how we solved it 🥷!

Linear Programming (LP) is an optimization method that additionally accepts a set of constraints represented as linear transformations.

Mathematically, we’ve one thing like the next:

f is the goal perform (or price perform) and for our problem it represents the prices related to every transportation, ship, whether or not containers had been saved on overbooking standing and the trade-offs between leaving the containers within the factories or not.

The values x characterize the variables the optimizer should manipulate so as to decrease the target. In our case, it’ll be which transport, ship, dock and overbooking standing to decide on.

To make the idea extra tangible and related with the principle problem on this publish, let’s start with a quite simple implementation on high of cvxpy.

3.1 Easy Instance

Suppose the next setting:

• The corporate produced 4 containers in a given week, all in the identical manufacturing facility. Their values is: [$200, $300, $400, $500].
• The manufacturing facility can use just one sort of transportation.
• The manufacturing facility is related to only one dock.
• On this supposed week, two shippers could have ships out there on the dock. Shippers fees $100 and $130 per container respectively.
• First shipper has 2 remaining slots out there; the second has simply 1.

The primary aim of the optimizer is to distribute the 4 containers on the out there areas on ships whereas minimizing complete prices of transportation.

How will we implement it in cvxpy? Nicely, it’s fairly easy truly. First we’d like a variable x that represents the alternatives that the optimizer could make. Greatest strategy to characterize x on this case is as a boolean array with form (4, 2) — every row corresponds to a given container, and a couple of columns as there are 2 shippers out there:

A price of “1” on a row means the optimizer allotted the corresponding container to the respective shipper at that column. On this instance, the primary and second containers go to the primary shipper and the third and fourth containers go to the second shipper. Discover that every row can include just one worth expressed as “1” and the opposite have to be “0” as in any other case it will imply {that a} given container was allotted to each shippers on the similar time, which is invalid.

The problem of the optimizer will probably be, subsequently, to maintain altering this array till it finds a minimal worth of complete prices, whereas nonetheless respecting the necessities.

Prices could have two elements: one related to the shippers and one other to the container itself. If a given container is just not allotted to any ship then its worth must be added to the ultimate prices — it’s higher, subsequently, to prioritize allocation of the $500 container as an alternative of the $200 one.

As for the code implementation, that is one risk:

Key factors to contemplate:

• cvxpy requires the set of variables, constraints and at last the price expression.
• The road constraint0 = cx.sum(x_shippers, axis=1) <= 1 is a constraint that cvxpy should obey when optimizing x. As a normal rule, they need to hold the optimization course of convex (which ensures convergence) and might both be an equality expression or an higher certain equality. On this case, the sum operator occurs on axis=1 which suggests “sum by way of columns”.
  The rule imples that the summation of every row of x_shippers will be at most equal to 1, which ensures {that a} given container gained’t be assigned to a number of shippers on the similar time.
  Because the summation constraint follows the <= rule, then a given row will be of simply 0’s, which suggests a given container is probably not assigned to any ship in any respect (this will occur due lack of accessible areas on ships, as an illustration).
• constraint1 = cx.sum(x_shippers, axis=0) <= shippers_spaces works equally to constraint0. It principally interprets that each one containers assigned for every ship can’t surpass their most capability.
• Then we arrive on the coronary heart of the issue: the price perform, given by: price = cx.sum(x_shippers @ shippers_cost.T) + container_costs @ (1 — cx.sum(x_shippers, axis=1)) . The primary part cx.sum(x_shippers @ shippers_cost.T) principally categorical all prices for allocating every container to every shipper. “@” represents the dot product so the results of the operation is already the price related to every container, which must be summed for the overall price.
  Second part container_costs @ (1 — cx.sum(x_shippers, axis=1)) is arguably extra attention-grabbing as right here we begin to see the methods we will use to precise our issues in cvxpy. Through the use of the 1 matrix minus the row values expressed as cx.sum(x_shippers, axis=1) , we basically get a (4, 1) matrix the place every row signifies whether or not the container was ever assigned to some shipper or not.
  The dot container_costs @ not chosen containers tracks which containers weren’t routed and sum their price worth.

That is an instance of the end result:

print(x_shippers.worth)
array([[0., 0.], [0., 1.], [1., 0.], [1., 0.]])

Container 0 was not assigned to any ship (because it’s the most affordable so it was not prioritized).

Some ideas earlier than we transfer on:

1. You may run experiments with cvxpy utilizing Colab. Simply run !pip set up cvxpy and you might be just about able to go.
2. You may run some checks to verify you might be heading in the right direction when implementing your fashions. One method I like to make use of is to, as an illustration, set the variables with an preliminary worth, equivalent to x_shippers = cx.Variable((2, 2), worth=[[1, 0], [0, 1]]. Then, after operating operations (equivalent to r=A @ x_shippers ), you’ll be able to print the end result r.worth attribute to verify if every little thing is working as anticipated.
3. When working with cvxpy, at occasions you’ll get some errors when operating the optimization. One frequent drawback is the error message:

That is the notorious Disciplined Convex Drawback (DCP for brief) which consists of a algorithm that have to be adopted to ensure that restrictions and goal will probably be convex. As an illustration, if as an alternative of the sum operator we used max , we’d get the very same end result however when attempting to run it we’d getDCPError . DCP means then that each one operations used to precise the price and constraints should comply with the foundations of convexity.

The earlier instance works properly for a delicate introduction to the cvxpy API. Let’s now contemplate a bit extra developed drawback on the identical theme.

3.2 Medium Instance

Let’s contemplate once more the identical 4 containers with similar prices and situations. This time, the primary and third container are going to vacation spot “0” whereas second and fourth containers should go to destine “1” and out there areas are the identical as earlier than ([2, 1]). The enter we’d get for this drawback is one thing like this:

All containers are produced on the identical manufacturing facility however this time there are 2 choices to select from for transportation: prepare and vehicles, with respective prices [$50, $70]. For this thought-about week, we’ll be capable to allocate at most 2 containers on prepare.

Earlier than transferring on, take into consideration how you’d resolve this one. Keep in mind the important steps really useful for working with Linear Programming:

1. What are the variables required to explain the issue? x_shippers = ...
2. How you can categorical the price perform? price = ...
3. How you can use constraints expressed by way of matrices and mathematical operations (that follows DCP) to formulate the entire drawback? destines <= x_shippers...

(you can too use Colab for attempting it out)

…

…

…

…

…

…

…

…

…

…

…

…

Right here’s one attainable resolution:

General it follows the identical construction as earlier than. Some notes in regards to the code:

• Now we’re optimizing two variables, x_shippers and x_transport.
• We use mappers for trains and for linking shippers to their vacation spot. The title of the mappers variables begin, by our conference, because the title of the variable within the rows area after which the columns one. As an illustration, destine_shippers implies that rows represents destines and columns the shippers.
  In particular, the results of the road dest_ships_arr = destine_shippers_map[containers[:, 1]] is a matrix with 4 rows whose strains accommodates the ships that attend the locations of the respective containers. To make it extra clear:

Mappers permits enter information for use on constraints and the price perform. Within the earlier instance, the optimizer is restricted to solely assign shipper 0 to the primary container and shipper 1 to the second, as an illustration. That is carried out as: constraint02 = x_shippers <= dest_ships_arr .

• Comparable method is utilized in: constraint11 = cx.sum(x_transports @ train_map.T) <= 2), the dot matrix operation tracks all transports related to trains. Closing summation is equal to all containers that had been assigned to trains, which have to be decrease or equal to 2.
• Constraints obtain two numbers (“00” or “10”) as an illustration. That is to group all constraints for a selected theme. On this instance, the primary 0 pertains to all constraints relating to ships and 1 pertains to transport. We accomplish that as a result of if afterward we have to enhance the variety of constraints then we will simply add new numbers after “0” and extends the ultimate array.

Closing resolution is: x_shippers = [[1, 0], [0, 0], [1, 0], [0, 1] and x_transport = [[1, 0], [0, 0], [1, 0], [0, 1] (each equal by coincidence). The optimizer didn’t route the second container as there’s solely 3 complete areas on ships. First container goes to shipper 0 by prepare so does the third and final container goes to shipper 1 by truck.

Let’s now step it up a notch a bit and enhance the problem now.

3.3 Full Instance

Let’s use the identical instance as earlier than however now add one other variable: the docks. Now, the manufacturing facility can transport the containers to 2 attainable out there docks. Trains and vehicles can attain Dock 0 with prices [$50, $70] and Dock 1 will be reached solely by vehicles with price $60. Each shippers attend each docks with similar prices.

How would you resolve this drawback?

You’ll in all probability notice that this straightforward addition of the docks variables make issues tougher. Many makes an attempt to attach docks and transportation leas to DCPErrors. See if you’ll find methods to ensure their modeling as anticipated.

…

…

…

…

…

….

….

….

….

….

….

….

Did you succeed? Right here’s one attainable resolution:

It’s equal to the earlier instance for probably the most half. However discover now that we’ve the AND variables which hyperlinks the variables docks and transports.

Principal level is: when the optimizer selects a price for x_transport it finally ends up affecting the alternatives out there for x_docks. However when it chooses the dock it additionally impacts the transport in return! So as to resolve this drawback, we implement AND variables such that the optimizer discerns the impression of its selections on the similar time.

That is carried out first with the y variable: y_docks_and_transp = cx.Variable((4, 4), boolean=True, title="docks AND transportations"). This variable will probably be additionally up to date by the optimizer however we’ll pressure it to be the AND mixture between two different information sources, as we’ll see quickly. The method we used creates a template on columns as a reference, i.e., it combines, on this case, docks and transports:

The columns will probably be a tree like construction. As within the variable title "y_docks_and_transp” the primary title to look is "docks” then it implies that docks would be the first reference after which transports will comply with, as proven above. Taking the second row for example, there’s a price “1” on the second column. Because of this it selects Dock 0 and Transport 1 (truck).

With this template we will create different information and constraints that work on each dock and transport variables on the similar time. As an illustration, right here’s how we specify prices: transport_and_dock_costs = np.array([[50, 70, 0, 60]]) , which suggests Dock 0 and Transport 0 (prepare) prices $50 as an illustration.

The optimizer can use the template to transpose every x variable to the docks and transportation setting. For doing so, we used the mappers as follows:

If the optimizer chooses transport 0 then it’s mapped to the primary row of the left picture. Do not forget that trains don’t attend Dock 1 in order that’s why it’s a “0” on the third column. Additionally, discover that the title of the variables additionally follows a sample: transp_dock_transp_map implies that rows characterize the transports and it maps to the AND conjunction between docks and transports, the place docks comes first.

That is the place we use y_docks_and_transp . When the optimizer adjustments the x variables we map it to the area of docks and transports. However then we have to mix each mappings to know precisely which level corresponds the dock AND the transport variables:

Because the picture above reveals, first we transpose the x variables to the dock and transport area. We then take the outcomes and apply an AND operation to seek out particularly, for every container, which docker AND transport had been chosen:

First row means the optimizer selected Dock 0 and Practice. Second row means it selected Dock 1 and Truck. Discover that as Dock 1 is just not related with Practice then third column won’t ever be “1” so this solves the issue of legitimate connections as properly.

Nicely, however this isn’t that straightforward truly as most makes an attempt to implement this AND operation raises DCPError. To unravel it, we used helper constraints:

x1 = x_transports @ transp_dock_transp_map
x2 = x_docks @ dock_dock_transp_mapconstraint12 = y_docks_and_transp >= x1 + x2 – 1
constraint13 = y_docks_and_transp <= x1
constraint14 = y_docks_and_transp <= x2
constraint15 = (
cx.sum(y_docks_and_transp, axis=1) == cx.sum(x_shippers, axis=1)
)

By doing so, y_docks_and_transp is pressured to be “1” solely at factors the place x1 AND x2 are “1” as properly. This method can be utilized when an AND operation is required.
constraint15 is a security clause to ensure that solely routed containers will stay.

Right here’s the ultimate values of x and y:

x_ships = [[1, 0], [0, 0], [1, 0], [0, 1]]
x_transports = [[1, 0], [0, 0], [1, 0], [0, 1]]
x_docks = [[1, 0], [0, 0], [1, 0], [0, 1]]
y_docks_and_transp = [[1, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1]]. 

First container goes to first shipper by prepare on Dock 0 and second container remained on the manufacturing facility.

With all of the examples and the concepts mentioned, we will lastly resolve the problem the corporate provided us. Let’s sort out it down now!

4.1 Enter Information

We acquired details about shippers, transportation and their respective freights:

From the primary desk, we acquire that transporting a container from Factory 0 to the dock positioned at Santos by Road (truck) utilizing Third Occasion contract prices $6000. Additionally, Shipper 0 can take the container to Hong Kong by way of the Far East commerce charging $8000 per container.

As for areas on shippers, we acquired one thing like this:

Every shipper can attend sure trades (and subsequently a gaggle of nations) and the areas they’ve on the ship varies on a weekly foundation, as depicted by the numbers from 1 to 52.

And at last, the record of containers, the manufacturing facility they had been made, its vacation spot and internet price:

Discover that the final columns are principally the ultimate end result we’re searching for. The aim of the algorithm is to seek out the set of shippers and their transportation minimizing freight prices whereas following some restrictions.

We additionally acquired one other desk associated to the timings related to every transportation and shipper however as mentioned earlier than it gained’t be used on this publish.

This information wants to show into matrices that we will use afterward. That is truly fairly easy. Let’s take shippers for example: when studying the file containing information about shippers, we affiliate every new shipper to a counter worth that retains rising as extra ships are added in:

Now we all know that on any matrix related to shipper, if the result’s “0” index then it means it refers to “Shipper 0” and so forth. Each part in our mannequin (ports, transportation, factories) follows the identical concept.

Given the information, let’s see the ultimate resolution.

4.2 Resolution

We have already got the enter information. The problem now, particularly, is: the best way to route every container by selecting transportation, docks and shippers such that prices are minimized whereas following the constraints already mentioned on this publish?

The concepts offered on earlier examples had been a prelude of what the ultimate resolution seems to be like. Right here’s how we solved this drawback:

The perform optimize receives as first parameter data_models the place all information enter from the corporate is processed and remodeled into matrices that can be utilized by cvxpy. Particularly, the information enter containers is a bit totally different from earlier examples:

The general concept although is precisely the identical. Factors to contemplate:

• At line 72 the code shipper_shipper_trade_arr = x_shippers @ shipper_shipper_and_trade_map.matrix transforms the shippers selections to the area of shippers and trades. By doing we will sum up the overall containers allotted for every commerce and shipper.
• constr23 is designed to pressure overbooking if and provided that the optimizer already consumed all areas from shippers earlier than. That is executed by translating x_ob_shippers (“ob” means overbooking) into the shippers and trades area:

shipper_ob_trade_indices works as a mapping for which factors are overbooked. We then use this info to put in constr23 by saying that shippers at these factors have to be at most capability. By doing so, we pressure the rule that overbooking ought to occur if and provided that all common areas had been already consumed.

• Constraints 3- use the AND method as mentioned on earlier examples. This permits us to mix which shipper and dock the optimizer chosen thus far and use this info to put in different constraints and prices.
• constr55 combines details about docks and transportation linked to factories. It forces the optimizer, by way of y_origin_and_transp to decide on a dock and transport that connects to the corresponding manufacturing facility the place the container is positioned.
• Price perform is equal to what was mentioned on earlier examples.

And there we’ve it. The entire system able to optimizing distribution of containers all through the globe. Earlier than delivering the code to the corporate, we wished so as to add a layer of safety to have some ensures it was working as meant.

4.3 Is It Working?!

To ensure the code is working, we determined to implement some unit exams by simulating some situations. Right here’s an instance:

It makes use of Django because the backend of the system was constructed on high of it. Within the instance above, the take a look at creates an enter information that forces the optimizer to overbook a ship. We then examine outcomes to what’s anticipated to verify it’s working.

A number of exams had been carried out to extend the possibilities that every little thing is working correctly.

This problem was fairly thrilling. At first it wasn’t that easy to implement this resolution on high of cvxpy. We in all probability noticed a whole lot of occasions the error DCPError and it took some time till determining the workarounds to the difficulty.

As for outcomes, I suppose in all probability let’s imagine that there’s not even the best way to examine the earlier Solver as carried out in Excel to the brand new one constructed. Even testing the algorithm with hundreds of containers the entire processing took a couple of seconds on a i5 CPU @ 2.20GHz. On high of that, the answer carried out is already extra in-depth than the present resolution as price perform and constraints have extra gadgets.

Potential downsides is that implementation can also be extra complicated (way more) and so as to add new constraints the entire code might have altering, which suggests it’s not that versatile as in all probability the corporate would really like it to be. Given the benefits nonetheless, that was a great trade-off to make.

Nicely, that was an important expertise. Hopefully you realized and loved it as a lot as we did. It was powerful however price it.

And, as at all times, see you subsequent mission ;)!