Each optimization downside has three parts: variables (e.g., ships and ports), constraints on these variables (e.g., a ship can match solely so many containers onboard), and an goal operate to be minimized or maximized (e.g., maximize the variety of containers shipped). The variables and constraints are sometimes represented as a matrix wherein the columns are the variables and the rows are the constraints.
A standard method to decompose such massive issues is column era, wherein solely a subset of the variables are thought-about at first, after which new variables — that’s, new columns — are generated to extra carefully approximate the unique downside. To assist handle this, we developed a software program library that analyzes the issue and predicts which columns are finest to generate. This library can be open sourced by way of MathOpt, our mathematical programming framework.
With this in hand, we outlined two fundamental approaches to resolve the issue:
- Double Column Era
We thought-about community design and container routing as two coupled issues, every consisting of a major choice downside (select the best choice) and a subsidiary era downside (determine affordable choices). We utilized a shortest-path algorithm to every pair of issues to generate affordable choices, adopted by a linear program (utilizing our linear programming solver, Glop) to decide on the perfect choices for every. We utilized the column era method to each on the identical time, utilizing intermediate outcomes on every downside to affect progress on the opposite. This double column era strategy enabled us to search out provably optimum options, but it surely solely scaled properly to reasonable sized issues. - CP-SAT
We then tried an implementation based mostly on constraint programming, utilizing our CP-SAT constraint programming solver. This additionally labored properly as much as mid-sized networks, however didn’t scale to the worldwide delivery downside.
These two approaches enabled us to search out provably optimum options, however they solely scaled properly to small and medium sized issues. To enhance their scalability, we utilized a heuristic technique utilizing two variants of native search wherein we study neighborhoods round current options to search out alternatives for enhancements.
- Giant neighborhood search
We fastened components of the answer (e.g., “this vessel will go to Los Angeles on alternate Tuesdays”) earlier than making use of both of the strategies described above. This improves scalability by lowering the search house. - Variable neighborhood search
We explored neighborhoods over each the community and the schedule. We parallelize the exploration and distribute it over a number of machines to guage many neighborhoods concurrently. This additionally improves scalability by limiting the search house, whereas additionally permitting us to include information from Operations Analysis and the delivery trade.
With each of those approaches, we made use of incrementalism: locking down promising parts of an answer in order that we might begin from a recognized good resolution to make it higher.
Lastly, we additionally took into consideration transit occasions. Earlier makes an attempt to resolve this downside did not take transit occasions under consideration, since they make the issue rather more tough to resolve. We discovered that inclusion of transit occasions considerably improved the answer high quality.