I'm in the terminal side of this business. While this seems very interesting, and I'm sure some line will poke at it, it seems very academic. I'm curious if they actually partnered with a shipping line to come up with this.
On the terminal side, all I can say is that I am knee-deep in container optimizations right now and it's a damn nightmare. Every terminal does things extremely differently, even if the terminal is owned by the same company. Even the terminology is often different within a company. You optimize for one terminal, and you have to build 80% of it from scratch for the next terminal. Any solution is incredibly difficult to scale.
When looking at industrial optimization problems, it always appears there's an insane amount of money left on the table (e.g. nurse scheduling in healthcare, train/cargo ship optimization, etc). In my experience there are always undocumented (human) constraints that massively complicate things:
- German engineers balked at tightening features on pre-production vehicles because it would prevent their use for recreational purposes
- Billions were spent in overtime in a healthcare setting, seemed trivial to improve scheduling to reduce overtime, but there were numerous union constraints and simply not enough hiring supply
I wonder how realistic this google solution is (Houthi missile constraints?). In my experience it's often more valuable to develop solutions that can easily adjust to unplanned changes rather than provably optimal ones
I work on these sort of industrial optimization problems, and you're absolutely right about the amount of money left on the table. I had one problem at a previous megacorp that I worked on for about 8 months, and then passed off as a two part solution. the first part was a new optimization engine design, but it also required a second part, a new physical process for crossdocking. To this day, 10 years later, my former colleagues still report actual measured savings of $300M/year, which I still find to be mind-boggling.
You're also right about the complications and the need to be adaptable to various situations that arise. Some of that just comes from people who are afraid of getting their hands dirty and really understanding the domain they're working on. Operations Researchers and Industrial Engineers are not much different from Computer Scientists: sometimes the desire for a beautiful and simple solution prevents you from building something useful. Sometimes in order to build something useful, your idealized fast-converging LP turns into a QP/MIP bastardized rat king that only converges on an optimal solution half the time, but still gets a better-than-before solution the rest of the time. And some of us really hate that it has to be that way. The rest of us laugh their way to the bank.
Indeed!
It is never simple. Sexy simplistic CP-SAT constraint programming solver versus containers with deep frozen goods or tons of fireworks. Both need to go into a very special place on the ship.
Then soft business requirements, keep a weekly schedule.
Plus the real business issue: 5-10% of invoices in logistics are incorrect! Mistakes like wrong rate.
(disclaimer: the stories I heard while trying to digitise end-to-end value chains. We failed.)
Yes, and that's leaving aside the explainability problem. Let say for arguments sake that you have an optimal planning algorithm, if you cannot explain to the people using it why it generates a certain solution, it will not get adopted.
As an employee at a terminal, you have a) no reason to trust some software people who may have never seen one of them steel boxes up close, b) if this works, you or your colleague gets laid off, and c) if it doesn't work, you're now stuck cleaning up the mess the computer will inevitably make for you, which is way less fun than planning things yourself.
The 5%-10% invoices being incorrect is probably on the low end, I'd probably say it's 5-10% in total invoice VALUE. Because of the sheer amount of containers, you need automated invoice calculation. But if you miss an edge case ("We are allowed to invoice a 5 buck surcharge if the container is filled with at least 100kg of explosive goods, AND was loaded during the night shift because dangerous goods handling requirements now require us to have a safety officer on call, which we normally don't have during the night shift") you are leaving serious amounts of money uninvoiced, and you will never know. One of the reasons not that much effort goes into optimization algorithms is that there is so much low hanging fruit left on getting your invoices out correctly...
>As an employee at a terminal, you have a) no reason to trust some software people who may have never seen one of them steel boxes up close, b) if this works, you or your colleague gets laid off, and c) if it doesn't work, you're now stuck cleaning up the mess the computer will inevitably make for you, which is way less fun than planning things yourself.
Also d.) It works sometimes so you get forced to use it and then it gets ransomwared and you're completely unable to work because they laid off so many people you can't fall back to manual operations.
This is so true! Worked in the past on flight optimization problems and the most obvious solution (fly in a direct trajectory, or almost direct but considering wind) would easily achieve a 10% reduction in fuel usage. Now implementing that would be a nightmare, with so many layers involved and the need for realtime comms between aircraft and ground to keep the solutions in sync and conflict free. Unfortunately reality is always more complicated
Nurse scheduling is weird. I worked on a project in this space. Basically the nurses had found their own optimization technique over the hospital’s scheduling methods.
I did not work in shipping, but I did work in manufacturing for 15 years, mostly with a focus on test engineering & automation, but also getting into warehouse/material management and shipping/logistics. My masters is in operations research for manufacturing.
I agree with you that objective optimization is largely academic. There are always reasons why it's impossible or impractical to adhere to the most efficient versions of standardized processes. Sometimes these are "stupid" (people) reasons, and frequently they're reasonable justifications that accommodate for any number of externalities (weather, downtime, supply chain disruptions, lumpiness in demand signals and forecasts based on seasonality, etc).
That said, it's almost always smart to start with the most efficient version of a process and then add exception-handling, rather than to create a standardized process based on known exceptions. If you let exceptions become the rule, you'll always be operating less efficiently than optimal.
Same here, I'm in the business of terminals as well as hinterland transportation companies. There is no shortage of people trying to solve the 'sexy' academic problems like stowage plan optimization, berth assignment problems, crane splits, etc, but only very little gets implemented in practice. It is a tough business, with an even tougher political landscape, since dock workers traditionally have very strong unions.
All of the problems you can neatly divide and name are interrelated in practice, and trying to have algorithms "magically" figure it out for users is pretty much guaranteed to fail. This business eats software hotshots who think they can swoop in and "just" run some algos, "because it's just a TSP / Constraint Solver / [insert your approach here] right?". This business can definitely use bright minds, but start humbly, and start by talking to real world users please.
You don't appear to have any contact details on your profile, but if you ever would like to exchange thoughts with another company in this business, shoot me an e-mail. I think we're doing some interesting stuff for the <1 million TEU/year segment of terminals, especially if they're heavy into multi modal.
> "it seems very academic. I'm curious if they actually partnered with a shipping line to come up with this."
Unlikely. I worked in this business and the idea of mathematical optimisation is always the first one to be suggested by someone who's new to this industry. Global shipping companies are clueless about tech and only do what they absolutely must to comply with the regulations, the rest is ignored. Give them an XML Schema for an EDI doc and they will stuff an Excel sheet into a CDATA. They know their game, they wore out the infinite patience of IBM who wanted to convince them to use blockchain to track shipments.
Shipping companies are clueless about tech, and tech companies are clueless about the day to day activities of shipping. They think they can tech their way through all problems.
We recently met with a big tech company who we were told to partner with. They start with an angle that made highly suspicious they basically wanted to build a fully automated terminal. When we told them just one fairly mild story of what union issues we deal with, they all gasped and said, "what?" and quickly dropped it.
Yes, as someone who used to work in that field for a bit in the customer side, I have to agree. Thisbis an operational topic, and those involve a ton of phone calls, people all over the place at multiple companies using multiple unconnected systems, a fair share of Excel and e-mail.
Some planning algorithm like this might work, for sure. But onpy if it is included in whatever software being used for this kind of planning. Otherwise, it is a nice academic excercise at best.
For the customers in my size category (50k to 1 million TEU / year) the answer is that they may have 2 or 3 planners, optimizing berthing slots and stowage plans, but other than that there is no coordinated effort.
You have to realize that these terminals are typically a lot smaller in terms of manpower than you might think. A terminal handling 1 million TEU/year may operate with 2-3 crews in a 16 hour/day schedule for handling ships and trucks, plus some extra people handling the empties. Let's say it's 60 dock workers a day. A typically office might only employ about 12 people in overhead: one for customs/quality stuff, one for invoicing and finance, one HR, a bunch of order entry / customer service people, and 2 or 3 yard/berth/stowage planners.
Unless you look at the biggest of biggest terminals, you have to essentially regard them as SMEs in a very non-sexy business, and they treat tech and fundamental research into optimization accordingly.
One day when I leave, I swear I'm going to write a tell-all book about this industry. Until then, here's some condensed info.
To set the stage, this is a blue-collar industry, and what happens, so I've been told, is quite common in blue-collar industries. A lot of good ol' boy networking, people getting promoted who have no business being promoted, and as a consequence, a lot of corruption, ineptitude, and inefficiencies. The software in this space just flat out suck and anyone at a FAANG company would be appalled at how we write software. It's literally longshoremen trying to run software businesses.
On the other hand, as a terminal, it's very hard not to make money, so there's a lot of players, and unfortunately a lot of, at least shady deals.
I'm involved with a company that sells to terminals that don't have home-grown software systems. I don't have that much info on terminals that have their own software staff, however, there just isn't that much breakthroughs in the space. It's a conservative industry with a lot of money already, so there traditionally have been little incentive with high risks.
In addition to the aversion to risk, there's a lack of software product and engineering strategy to invest in optimization properly. One major vendor, I was told by a colleague did invest substantially, failed, and "it almost bought the entire company down." My company has dabbled before. We've had a couple of PhDs on staff. We even had a neighbor search solution like in the article developed. It worked in simulation and testing, and failed miserably in real life. The customer didn't take it, and we never had the vision to actually salvage anything from the effort.
There are a few vendors in this space, but again, the landscape is pretty sad. I know of one that are flat out frauds. They exist because the CEOs used to be in the industry and have credibility. They're still around because they're able to con non-technical terminal managers and string them along for a while. A few more maybe have 1 or 2 competent data scientists, but that's not enough. I've worked with one company that is good and is easily the most qualified, but they have never had the marketing and leadership to make themselves the billions they should be worth. They also simultaneously price themselves out of range for most terminals.
The industry is changing, though, because private equity has gotten involved in many companies. They have taken over some internal initiatives and basically dragged many of these good ol' boys against their will, or forced them out. They've also forced companies to partner with tech giants to address these issues. IMO, this is the only way we will see supply chain optimization revolutions any time soon.
As someone in the industry as well for many years (coming from the business side having ventured into software), the main problem is always that the software just is not good enough and do not account for all the edge cases - leaving many users better off using pumped up Excel sheets combined with a few hours on the phone every day to account for all the nuances and changing customers/suppliers demands.
In short: It is not good enough. When it is good enough, customers adopt it.
This experience has given me first-hand experience of a PE takeover, and the standard line of PE guts the soul of a company and sells off everything is crap.
I don't know how many meetings I've been at where the PE team blatantly states over and over, let us help you, tell us what you want to do, tell us what you need, and we completely flub it. Sometimes our CEO is too paranoid, sometimes too prideful, sometimes too oblivious, but mostly just doesn't have the knowledge on how to run a software company.
PE is going to run out of patience soon, and it won't be good for us. There's going to be headlines of how PE gutted us, but in reality, we gutted ourselves.
I agree, mostly, but I've also seen (and been in) situations where the PE acquired a company for it's customer base and knew going in that it was going to gut the current leadership and install all new systems & processes [that would support 10x scaling]. This doesn't make PE bad or evil, but it's not accurate to state that PE overlords are always hands-off.
But what about the cases where the PE firm asset strips the company, loads it up with debt and then walks as the company implodes and everyone loses their job? That seems to be the model of some PE firms. But maybe those are the ones that mostly make the news. I would certainly hope they aren't all predatory vulture capitalists.
BTW the current state of English water companies is a not a good advert for private equity.
Not in shipping but in high volume manufacturing it's generally expected that anyone on the shop floor, or creating systems for the shop floor, is exerting at least some gray matter toward optimization. In most places of decent size, there will be at least one "manufacturing engineer" or "operations lead" whose primary job is to focus on optimization.
I just happen to be reading "The Box", about the early history of containerization... and boy am I enjoying it. I really really recommend it to anyone seeking a good enjoyable read that mixes engineering, design, business and history.
I totally believe you. I was trained as a merchant marine deck officer at a time when many of my instructors were still at sea as containers were beginning to become popular.
My Dry Cargo instructor in particular told of going in to SE Asia ports and expecting to be there for 3 weeks unloading & loading break-bulk cargo and getting drunk every night. After the switch to containers, they were lucky to be in port for 20 hours and had no time to go ashore.
That is a hard claim to verify. One might say impossible. It is because it makes a statement about the future without defining a time interval. The “are likely to ever achieve” part.
Before you start arguing about how little you think LLMs are worth and how great container ships are, that is not the problem. The problem is that to “verify” something with an “ever achieve” you either have to prove hard limits or wait forever. Proving hard limits rigorously is very hard. Waiting forever is impossible.
> statement about the future without defining a time interval
> The problem is that to “verify” something with an “ever achieve”
> That is a hard claim to verify
Sure, if we are going to litigate this on precision of the language use, then this would fail. Since it isn't a legal document but a short sentence on Hacker News.
Given an infinite timeline, LLMs can conceivably be more useful than containers.
However, this warning is relatively empty, especially since you have precluded any calculations between LLMs and containers
> Before you start arguing about how little you think LLMs are worth and how great container ships are.
We conclude that the original claim cannot be verified and we reformulate it in a more useful form.
Sometimes the correct answer is "we do not know", and we all should get more comfortable with that. Here it is even worse than that. It is a "we do not know and we will never know".
Or you can say "I think that statement is true." That is entirely up to you. It tells us about your mind state and you are the primary source of information on that.
Saying it is "easy to verify" is not the same kind of thing. It is about the statement itself.
The most substantial claims for LLMs today come from 2 general areas - code copilots (github published, google published), and reduction in time to proficiency for new hires. That said, it may unlock additional capabilities.
Additionally, language processing has a massive gap when it comes to languages that most of humanity speaks. (Gabriel Nichols, CDT paper)
Furthermore, having seen GenAI deployments in workplaces, they also suffer from those issues that plague all ML and AI projects.
As initially stated, Cargo containers work across cultures, are standardized across humanity, and underpin all our goods transport.
Given an infinite timeline, it is well likely that cargo containers will outperform LLMs, because the market for pure information will always be at the mercy of physical goods required to generate that information.
So even if LLMs magically improve and become all pervasive gods, they will still need to transfer goods using cargo containers.
Given that this is a HN comment, and not a dissertation, within that social context, I submit that the original postulate, was correct and sufficient.
I don't think this relates to the physical loading of the containers on ships at all. It is concerned with 3 problems: "Network design determines the order in which vessels visit ports, network scheduling determines the times they arrive and leave, and container routing chooses the journey that containers take from origin to destination."
OP is not wrong about the bin packing, since it relates not only to physical loading of containers, but also the optimal "loading" of schedules in time!
The insight is to see time as a spatial dimension - then a set of shipping tasks - each with a length determined by time to complete the task - can be packed into a set of 1d bins representing boat schedules!
This is variously known as the supply chain optimization problem in logistics, the minimal makespan problem in manufacturing, and the multiprocessor scheduling problem in compsci. All of these problems have been classically formulated as bin packing problems.
Toy model: Single ship + Single container Bin Packing
Here is how it works for a single boat and a single package going between multiple ports. In this case, the problem is equivalent to a shortest path problem on a graph with weighted nodes, and more traditionally presented as a shortest path problem on a graph with weighted edges. I'll show the model and the graph translations!
The model consists of:
1. One bin - a 1 dimensional line representing the utilization of the ship over time
2. Line segments p_1 .. p_k representing the transit time for each of k possible shipping operations (taking the container from some port to some other port). For this model, assume p_1 = p_k = 0, representing the first and final transits
3. A port relation P_ik saying "transit k can immediately follow transit i," or equivalently, "transit i's arrival port is transit k's departure port"
A span is a sequence of line segments respecting the port relations, starting at p_0 and ending at p_k. The problem is to find a makespan - an optimal span.
This is the same as the shortest path on a directed graph G with nodes weighted p_1 .. p_k, where we draw an arrow i -> j iff P_ij.
This graph can also be "dualized" into a directed graph G' where nodes are ports, and arrows between ports are weighted by transit times. This is the most familiar form of this problem.
Define an equivalence relation i ~ j saying transit i and j are equivalent iiff P_ik = P_jk for all k (i and j arrive at the same port). Now give G' a node for each equivalence class [i], which we call ports. Finally, for any pair of ports [i] and [j], add an arrow [i] -> [j] with weight p_k if and only if there exists k such that
1. P_ik. (Transit k leaves from port [i])
2. k is in [j]. (Transit k arrives at port [j])
Now we have the traditional shortest route problem on a graph with weighted edges. However the bin packing model naturally scales to the case where we have many ships, larger cargo capacities, many containers, and complex transit constraints.
In this general case, we regain the geometric packing aspect as well! This is because the ships are represented by 4 dimensional bins, which are packed with containers in x, y, z AND t dimensions! The spatial part of this packing now has to obey efficiency constraints like minimizing the unpacking and reshuffling that happens at each port! Wild, huh?
> In this case, the problem is equivalent to a shortest path problem on a graph with weighted nodes, and more traditionally presented as a shortest path problem on a graph with weighted edges.
Exactly.
I was exposed to this sort of conception of the packing problem when implementing Ant Colony Optimization (ACO) for a programming challenge.
And there's also regulation IIRC dictating that more hazardous material should be packed at the center of the ship, to avoid falling off in case of accident.
Don't store some classes of hazardous materials near specific other classes of hazardous materials (keep your oxidizers away from the fuels), don't carry too much hazardous material, keep good records of what's in each container and where that container is...
Wow, that's a great insight. Not only how to pack optimally, but how to balance the load. Then not just balance the load for shipping, but also to optimize packing the load. Sort of like torquing the lug-nuts on tires one at a time to avoid tipping the car.
Compared to.. protein folding, nuclear fusion? Sounds like a handful of parameters to me. What are computers good for if not looking for solutions in this space?
It's strange to me that the cargo space has not been aggressively optimized. It's a pretty substantial part of civilization and, I believe, there's definitely some money sloshing around there.
A Panamax can carry ~5000 containers. 5000! (5000 factorial) is a BIG number. Bear in mind that 60! is more than the number of atoms in the observable universe. Combinatorial problems are hard.
For some reason, ignorance most likely, I'm not impressed. Looks relatively easy. Not for me, but for anybody with some math skills it looks easy to improve upon naive solutions.
To be fair, a completely optimal solution definitely seems out of reach, but I'm not interested in those.
Hmm. Let's say you're looking at that 5000 TEU (Twenty-foot Equivalent Units) ship with (the most common, IIUC) 40' containers. The state space for optimization has something like 2500! or 10^7400 states. Given 24 hours to optimize it at 1ns per state, you could look at 10^14 states or 10^-7384% of the state space.
There are also a lot more constraints than weight and balance and they're constantly changing; some may rule out big chunks of the state space which is very good, but it's still a Hard Problem.
But it's not like there aren't people already doing it.
The issue is in adequately capturing and encoding these constraints; particularly multi-crane piers that skip an intermediate autonomous shuttle truck to go directly onto trains are quite difficult.
Just imagine the contingency planning due to restrictions in unloading.
This is if you are looking in an naive way and are only interested in for THE BEST solution. However, there are many constraints and we are looking for a better solution not the best one.
Yes exactly, I'm reminded of solutions to find numerical approximation results for very difficult problems like this. One of the most famous are Markov chain approaches to resolving similar issues. Then, for the interested:
There's quite a lot of other constraints too. Lots of goods aren't allowed to sit side-by-side, for example, anything explosive goods cannot sit within n containers of hazardous chemicals. Because goods codification is so low-fidelity, lots of things which aren't actually explosive/hazardous can't be stored in close proximity, because we can't differentiate them from things which are actually hazardous/explosive.
It's very much wackier than that. In addition to mere physical constraints, there are the laws and regulations of individual countries and a goodly stack of international treaties and standards.
Wow, that's an entirely different set of constraints that I hadn't considered. I have a whole new respect for logistics professionals that handle that sort of thing.
All of the refrigerated containers I have seen have had a built in generator/AC unit...why would shippers care about heat loss, unless they are providing the energy to refrigerate the containers?
That generator is for very short periods of time spent in transit. Once it's on the ship it's directly connected to ships power. This also has implications for it's placement as not all rows of stacks on a ship have power cables run out to them.
Also, because of the short time requirement, and some extreme low temperature requirements on some cargo, it needs to be in a place where it can be disconnected and very quickly craned off the ship.
The engineer making and breaking the connections will generally have to manually log the time of these actions and the time of the unload. It's all a very interesting and somewhat complicated process.
I assume the shippers are providing the power for refrigerated containers. Otherwise they would need to have batteries or fuel that could last potentially weeks at sea. Anyone know?
They do but most reefers (refrigerated containers) have build in or portable gensets to provide power when they’re not on the ship and plugged in. They could easily spend days in the port stacks and having to plug them in every time they moved would make life a lot more difficult for the port. They can burn anywhere from a few hundred to a few thousand liters of diesel per week which isn’t actually that much to a 40ft shipping container.
How important do you think would a grid hookup be on European freight trains for reefers?
It should be straight forward to include full wagon power with the upcoming DAC4EU coupling (UIC 552 says that normal coaches are to have an 800A through connection that's regularly fed with 1000V 16.7Hz or 1500V 50Hz; this is single-wire earth(/track)-return).
Keep in mind that unlike North American freight trains, Europe mainline service is almost fully electrified. Thus the reefer would be grid-fed.
I'm asking because I'm looking to propose a change to the current plans for the electric coupler (use near-field RF instead of the currently-preferred single-pair Ethernet or it's fallback powerline; I think 802.11 has suitable PHY options, especially among the OFDM codes if the near-field chamber is dispersive and/or has problematic resonances in the channel), and throwing in "grid power for reefers" with actual numbers from the reefer container industry would be easy (a change to the coupler is a change, and the additional cable through the wagon shouldn't be that extensive either if it's an economical aluminum type; also this would allow passenger coaches that are currently using the pre-DAC4EU hook and chain coupling to be used with DAC4EU rolling stock).
I recommend talking to someone with experience shipping reefers in Europe because small seemingly irrelevant details will make or break the design. I assume that Europe uses a lot more international reefers that don't come with their own gensets so many trains would already have power in the form of generator cars. It might be impractical to hook them up to train power without a way to synchronize all the coolers so that they don't all turn on at once and brown out the train in the middle of a climb.
IIRC international reefers require three phase power with a 50 amp breaker so even 800 amps won't get you very far if they all start up at once.
It sounds like these are automated somehow, that the generator kicks in when it's not otherwise being powered - otherwise isn't it just as much work for the port to run around starting and stopping generators?
But an automated system sounds like it has its own problems, how does it make sure it has proper ventilation and comes on at the right time? Probably I don't want the container to start venting diesel fumes when it's deep in a stack of lego surrounded on all sides.
Reefers still get special treatment at ports because they have to be moved as quickly as possible. That includes not stacking them several layers deep horizontally so that ventilation is blocked (the gensets are very obvious from the outside). They’ll often get connected while in the port too, it’s just not a guarantee. Someone with more valuable produce will often pay for preferable treatment and a power connection to reduce risk from malfunction and running out of fuel.
It has to be automated since it’s a refrigeration unit that needs to know when to turn on the cooler. The control circuit starts up the generator if it senses no power connection at that time, usually off a standard marine lead acid battery.
Container ships do provide power to refrigerated containers. My understanding is that refrigerated containers are in row with the door accessible and power hookup. I was looking at photo of the row, and how container ships have extra power system to power them. It looked like it was far down with stacks of containers around and presumably on top.
Computer scientists are always so concerned with optimality. IMO it is sufficient to know an optimum exists and a way to converge on the solution, then finding quasi-optimal solutions is more than good enough.
Not at all. Plenty of people are researching finding satisfiable solution that are quasi-optimal at scale. Once you reach a certain scale of optimization problem, proven optimality in a reasonable time-frame is often infeasible
No, not really. Packing itself is a mostly solved problem. This is a combination of packing + traveling salesman, where the combinatorics of the traveling salesman part are highly variable since there's no requirement that any given ship must hit any given terminal.
These OR APIs (in my professional experience working at Google Cloud between 2015-2023) is that they're 1) academic, and 2) used commercially as a way for Google Cloud solution architects & engineers to build customer-specific solutions that use these optimization APIs as a part of a business solution running on GCP. Case in point would be Route Optimization API, which was published just like this has been by the corporate OR team. Then, on top of that was built -- with input from a few alpha customers -- the Fleet Engine solution.
Until any of the OR APIs are exposed via Google Cloud, they won't have SLAs or any reliability guarantees and should not be used except academically. Just my $.02.
thank you - this is a very helpful perspective to understand how this is used for someone who doesn't have much experience working in a customer-facing cloud
Probably it'd be irresponsible not to try it. I'm curious if this is the full shape of the problems and constraints faced by planners. Flexport is the $3.3bn (revenue) company in this space also based in SF.
Don't worry, they imported an Amazon exec who laid waste to the culture, set everything on fire, didn't accomplish anything and then was fired. You know, the typical amazon exec.
With Google’s graveyard[1] growing so fast, I’m careful with new Google announcements. An API like this sounds particularly problematic to replace sometime in future.
The correct solution from a shipping company is not to engage with google.
Instead start a spreadsheet with all the people who worked on this product, and contact them as soon as Google announces it is shutting the API down. Or you notice a few people chaining their Linkedin status.
Omega Tau Podcast did a really great episode [0] on container shipping, including the optimization of container placement and route planning, highly recommended.
> Unlike airplanes ... cargo ships are in nearly constant operation
Cargo ships do do much of their maintenance underway, but other than that, I'd say the difference is a lot less. (Not that this is a big deal, more pedantic). Cargo ships turn around in ports over a few days, unloading, loading. They may also wait for hours or days for a berth.
Make me think of every shopowner or manager of local restaurants or something said they had headache planning schedule for part-time employees. Some even say that is the reason they are paid well. I thought, but why don't you just use some algorithms to solve it?
Many people don't like it when their shifts change dramatically. Sure, you can cover the night when half the staff takes off to see Taylor Swift, but calling all those people in means they in turn need their next shift covered, and so forth, and you end up with an entirely different schedule of people who have never worked together, etc. This is all fixable adding more constraints, but even just writing it all down and prioritizing them isn't trivial. They're not Legos.
This is actually the exact problem I want to solve. I hear the same thing from almost everyone I've met who makes schedules. Having an OR background, I always find it insane, their problems sound straightforward to model and solve with normal solvers and no fancy techniques - and they also always sound high value. I think the problem is that OR broadly just isn't accessible.
Most well supported solvers use a mathematical paradigm to define your problems, which "normal" people would look at and immediately get overwhelmed. There are nice off-the-shelf solutions for common scheduling problems, but unless you used it from the start, every business has some unique wrinkles which make fully adopting one of those solutions too hard. Either your wrinkle is not supported, or you cannot figure out how to wedge it into the tools provided. If you're really inclined to try to solve your scheduling problems better, the courses you'll find usually assume significant prior programming and/or mathematical knowledge.
I think it should be possible to lean on no-code paradigms to build a modelling environment for scheduling problems that is accessible for "normal" people who need more than Excel but can't hire an OR specialist.
Working in vehicle routing optimization for MSB, I would like to share a couple of insights/observations.
1. People can be very creative in solving their problems with your features (and bugs!), even completely unrelated at first thought. They just have to be (a) observable, (b) speaking the language your users understand, which mathematically oriented or generic packages do not.
2. On the other hand, the quite plausible (to me) approach of "obtain an initial solution — adjust for ad-hoc constraints — reoptimize the rest" constantly fails as "too complex" with users reverting to Excel instead.
However, I still stubbornly believe that mathematical optimization cannot do everything, and we should aim for domain-specific decision-support systems that are primarily manual where optimization is only a part of solution building, and UX really matters in that process.
I work in a restricted environment where I can't install or-tools. In order to solve our scheduling problem, I wrote a solution in Prolog that runs in a purely web-based "notebook" environment. It works well and has the benefit that non-technical users only have to deal with specifying simple "facts", then running a pre-defined query.
I also have access to Google's OR API as a trusted tester and have been toying with the solveShiftScheduling endpoint. Out of the box, I don't think I'll be able to easily represent some of our constraints to work with the API. Also, our management frequently want to change the scheduling behavior, so while I can reformulate the problem to make it work with the API now, I never know what's coming down the pipe.
Honestly, I think the problem is people, not tools. Any time a company wants to create an exception-based vs a rules-based process, it screws things up royally from an efficiency POV.
To give a stupid example, I was once responsible for all the enterprise apps at an F500 used by Finance, HR, and Supply Chain/Procurement. This included our internal travel request tool, which had embedded approval hierarchies based on HR hierarchies & levels -- as one would expect. In the 2008 recession, part of the belt tightening was a new policy that the CFO had to personally approve any international travel requests, no matter who submitted them. Theoretically it was a very easy change, but can you imagine how unpleasant it was to build that logic into the system in a non-destructive way ... but a way that also had exception-handling to deal with times the CFO wasn't personally available.
Travel software is hilarious one of "You think this should be simple." until you run into people.
If their title is X, they must get approval. EXCEPT This one really good sales person. Their title is X but they can fly first class if they want and doesn't need preapproval unless it's 10k where everyone else is 2k.
Everyone flies except that one Software Developer who has Doctor provided note about their flying phobia so they can take the train (Amtrak). If train schedule doesn't line up, they get to show up a day early or stay extra day to accommodate train schedule.
Anything dealing with People quickly becomes madness.
I think it will be very difficult to come up with a simple and visual way to model all the constraints that a real world scheduling problem might have.
As some other comment mentioned, these systems have been controversial, because some of them are used in ways that don't take into account normal human needs. E.g. some schedule back-to-back shifts, change with little notice, and can't take into account sorts of real life things (like child care) that a human manager might be able to.
I have some background is combinatorial optimization. I did consider writing some software in this area or something similar, like school time table planning. But I think the problem is that each business will have different constraints (have to have at least 1 first aider on a shift, Alice doesn't get on with Bob, you can't work 2 saturday in a row, shifts change every 2 weeks, you have to have at least 12 hours between shifts etc). Anything flexible enough to be used by a sizeable percentage of organizations will be too complex for them to use.
I still wonder about stowage plans for these. I guess t's the next level down to solve approximately after the route plan for each container. They come later and have constraints that are more contingent than the global system level view.
Ballpark, optimistically, shore cranes can do 30-50 moves per hour, 2 or 4, maybe 6 cranes per vessel, and you have to unpack shell layer by layer.
* Ultra Large Container Vessel (ULCV): 14,501 TEU and higher
* New Panamax: 10,000-14,500 TEU
* Post-Panamax: 5,101-10,000 TEU
* Panamax: 3,001-5,100 TEU
24,000 TEU (Twenty-foot Equivalent Units), say 12k 40-foot containers
There is a talk by the Technical University of Denmark (DTU) online by a researcher in this space, which is a pretty good introduction to the problem of stowage: https://www.youtube.com/watch?v=9ltz4G-lPdg
As somebody actively involved in the space, there are lots of ways you can make life easier for yourself. Planning in blocks per hatch cover, grouping containers by destination, size, and weight and treating those as mostly interchangeable are table stakes. You then want to send a plan from the ship to the terminal before start of operations, so the terminal can also optimize and shuffle given they know the position of containers in the yard.
Stowage planning is a lot easier if you decide you're going to ignore the details of each container and only occupy yourself with the groups. The end result is very similar for way less work, and you give a lot more flexibility to the terminal to optimize operations.
Sounds like they are beginning to offer OR-tools as a service. I’d be willing to pay for GCP compute to run it, if they can get me a better API than the Python bindings to ortools!
Count me excited for advances in AI that don't involve ML! If for no other reason than it is refreshing =). One thing that strikes me about the write up is that the team deeply understands what their model is actually _doing_.
AI meaning neural nets is a very recent turn of terminology =) this is a clear use of the word to my mind - optimisation, planning and control, performed by a computer.
Just last week I was looking into OptaPlanner [1] and MiniZinc [2]. OptaPlanner even has a real-time/continuous optimization mode. There are a whole bunch of other solutions, but these were the most interesting to me.
I wonder why Google didn't just go with an off the shelf solution and integrate it instead of building their own solution?
There is also the Timfold project [1], which continues OptaPlanner and offers ongoing support and further innovation [2]. You can find the documentation here [3] and some helpful examples here [4].
Googler here, but not working anywhere related to optimization problems.
Google developed its solver a while ago [1] and it has been open sourced more recently. Additionally, it is also a supported solver for Minizinc [2] so you can use it with a well known tool/syntax without having to rely on the python/C++ libraries. However, those give you access to some of the solvers specific features that can help you speed up solving time.
MiniZinc is a high-level CP language and tool chain, not a solver. Google has been developing their suite of OR tools for 15+ years, it's not like they built something from scratch just for this
This optimization exercise still assumes that a bunch of variables are constant, e.g. berthing slots at ports, port operational schedules, ship speed vs fuel consumption, etc. It makes me wonder how much more efficient the system as a whole could be, for companies, consumers and the planet. (Disclaimer: I'm not in the shipping business.)
I would be curious to understand the constraints for adding new lines. When viewed as purely a network or graph problem it might seem "easy", but not all waters are created equal. Do they have to avoid high seas? Storms? Pirates?
There are good reasons any company Google's size should devote resources to operations research. Google is really good at the research aspects, and has used the outputs to -- in some cases dramatically -- improve its own supply chain operations.
This seems pretty incredible but Im mostly surprised Google is dipping their toes into this domain at all. Feels fairly outside the Google wheelhouse. I could understand Alphabet having another company provide this kind of functionality but it just seems out of place.
They have a strong OR team who has been building an excellent open source solver (OR-tools) for more than a decade. It makes sense to start trying to commercialise this work. It's interesting seeing them do it through problem specific APIs though.
I wouldn't think of this as a full-fledged business yet, but as a way for the Operations Research team to get their work tried out in the real world.
If they're really improving the state-of-the-art, to the degree that real money is saved, and the industries are big enough, these APIs will probably get used a lot and moved out of research or licensed.
You're being facetious, but it probably should be. AI+combinatorial optimization seems like an underexplored research area IMO. These solvers assume a lot of deterministic / constant penalties that are in reality stochastic - if you want a system that optimizes both efficiency _and_ robustness, some kind of AI+optimization thing seems very interesting.
This is certainly an active area of research. When I saw the article, I actually assumed that Google was announcing progress in AI4CO and was surprised that the article stuck to fairly orthodox techniques.
Because they did not show they used any methodological approach that we don't know for the past 30 years.
And according to the PR they did not use gurobi (or any sota mip solver), just their in-house lp solver in combination with shortest path algorithms and the fix-and-optimize heuristic.
Likely your particular use case will not fit their model anyway (for example you may want to consider contracts of affreighent along with leasing entire vessels).
So yes, or scientist and gurobi will definitely win.
How do you come to this conclusion? They way I read it rather sounds like they use the CP-SAT solver with LNS and LS workers, parallelized over multiple machines
Strong agree. I did a bunch of work on capacitated vehicle routing problems - basically the same as this +/- some bespoke constraints for shipping context maybe.
I benchmarked OR-Tools extensively vs e.g. LKH3 + my own hand-written solvers ... it's not a remotely credible library for these things, last time I checked. So ... don't have a lot of faith in Google's offerings here.
On the terminal side, all I can say is that I am knee-deep in container optimizations right now and it's a damn nightmare. Every terminal does things extremely differently, even if the terminal is owned by the same company. Even the terminology is often different within a company. You optimize for one terminal, and you have to build 80% of it from scratch for the next terminal. Any solution is incredibly difficult to scale.