12 ms·

Mathematical Optimization for Cargo Ships

324 points by alphabetting 2y ago

algo_trader 2y ago
Apparently, container optimization was unsolved for very large fleets. I did not know this. Google OR improves existing solutions by 10%-20% utilization which is incredible.
- smarm52 2y ago
  It sounds like a packing problem. I'm not deeply familiar with the field, but I don't believe there is a general solution. https://en.wikipedia.org/wiki/Packing_problems https://en.wikipedia.org/wiki/Packing_problems
  - hermitcrab 2y ago
    Optimally placing containers on ships must be a very difficult problem. Consider you might want: -heavier containers at the bottom for stability -refrigerated containers on the inside to reduce heat loss -containers to be unloaded first near the top etc And all in 3 dimensions!
    - IncreasePosts 2y ago
      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?
      - hermitcrab 2y ago
        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?
        ianburrell 2y ago
        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.
        throwup238 2y ago
        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.
        dmurray 2y ago
        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.
        throwup238 2y ago
        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.
      - akira2501 2y ago
        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. [0]: https://www.youtube.com/watch?v=U75MZwtDCXA https://www.youtube.com/watch?v=U75MZwtDCXA
    - Terr_ 2y ago
      > -heavier containers at the bottom for stability In the same vein, port /starboard / bow / stern balance. > -containers to be unloaded first near the top Containers with the same destination in separate places so that multiple cranes can run in parallel without infringing on each other's work-zones. Truly an interesting project for people who get stuck trying to optimize too many things at once. :p
      - raverbashing 2y ago
        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.
        mcguire 2y ago
        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...
      - smarm52 2y ago
        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.
    - uoaei 2y ago
      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.
      - cerved 2y ago
        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
        uoaei 2y ago
        I'm not talking about academics I'm talking about your coworkers.
    - huygens6363 2y ago
      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.
      - hermitcrab 2y ago
        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.
        pineaux 2y ago
        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.
        smarm52 2y ago
        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: https://en.wikipedia.org/wiki/Markov_chain https://en.wikipedia.org/wiki/Markov_chain
        huygens6363 2y ago
        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.
        saagarjha 2y ago
        The constraints are not always easily evident, unfortunately.
    - Shrezzing 2y ago
      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.
    - mcguire 2y ago
      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.
      - smarm52 2y ago
        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.
  - xnx 2y ago
    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."
    - barfbagginus 2y ago
      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?
  - eitally 2y ago
    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.
- 3abiton 2y ago
  This is big news for supply chains!
  - pineaux 2y ago
    Maybe
whimsicalism 2y ago
I am very curious if anyone will actually use this API endpoint they're releasing https://developers.google.com/optimization/service/shipping/network_design https://developers.google.com/optimization/service/shipping/... It's very cool nonetheless
- mcint 2y ago
  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.
  - whimsicalism 2y ago
    oh yes i remember them! - they were the first company to reject me for a job
    - malfist 2y ago
      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.
    - 7thaccount 2y ago
      The had layoffs recently I think, so maybe you dodged a bullet
      - whimsicalism 2y ago
        oh i definitely did, landed a higher paying job and hear about lots of drama over there. interesting problem space, though
- thih9 2y ago
  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. [1]: https://killedbygoogle.com/ https://killedbygoogle.com/
mcint 2y ago
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 4 cranes * 50 containers/crane-hour * 24 hours/day = 1.2k containers / day https://en.wikipedia.org/wiki/Stowage_plan_for_container_ships#Logistical_factors https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi... Stowage plans for ships also have weight, balance, power, and value acceptability criteria beyond availability at a port. These overheads made me curious enough to write up some napkin math, since they mention cut-and-run early departures from ports.
- superice 2y ago
  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 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.
  - mcint 2y ago
    Cool! Thanks! I'm glad my post invited even more for me to learn -- not quite Cunninghamming it in full.
akasakahakada 2y ago
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?
- spankalee 2y ago
  The same Operations Research group has scheduling examples for restaurants: https://developers.google.com/optimization/service/scheduling/restaurant_scheduling_example https://developers.google.com/optimization/service/schedulin...
  - borelian 2y ago
    And a API for shift scheduling: https://developers.google.com/optimization/service/reference/rest/v1/scheduling https://developers.google.com/optimization/service/reference...
- mlawrenson 2y ago
  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.
thinkingkong 2y ago
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. Who are they competing with?
- spankalee 2y ago
  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.
  - nerdponx 2y ago
    It also makes sense to continue diversifying away from ads and generative AI.
- mlawrenson 2y ago
  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.
  - verdverm 2y ago
    https://developers.google.com/optimization https://developers.google.com/optimization https://github.com/google/or-tools https://github.com/google/or-tools
oa8891 2y ago
[dead]
oa_8891 2y ago
[dead]
rapfaria 2y ago
It is really worth a try when demurrage is not even accounted for? https://developers.google.com/optimization/service/reference/rest/v1/shipping/designShippingNetwork#vesselcost https://developers.google.com/optimization/service/reference...
- macmac 2y ago
  Or detention for that matter.
- borelian 2y ago
  It goes here: https://developers.google.com/optimization/service/reference/rest/v1/shipping/designShippingNetwork#CommodityDemand https://developers.google.com/optimization/service/reference...
snapetom 2y ago
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.
- danielmarkbruce 2y ago
  Like the other comment - very curious about this. Could you explain what you are doing in more detail for folks not in this space?
- nickff 2y ago
  I'm very curious about what you folks do! How much effort is expended on this optimization? Perhaps in terms of FTE developers per terminal.
  - snapetom 2y ago
    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.
mezod 2y ago
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. It also ridiculizes my little coding problems x)
- huitzitziltzin 2y ago
  That is an outstanding book. I second the recommendation. I’ll even make a (sincere!) claim that I suspect will inspire a lot of angry attempts at rebuttals: The 20 foot shipping container has had a greater impact on the world than large language models are likely to ever achieve. Read the book first and then tell me why you think I’m wrong. (I’m not wrong :) )
  - Closi 2y ago
    We will have to wait 50 years to work out if you are wrong or not! (Assuming by LLM's we are broadly referring to AI, rather than LLM's as a specific technology)
  - intended 2y ago
    That’s not a hard claim to verify. They simply have. Gen Ai has a long way to go and multiple languages and cultures to mesh with before it achieves the ubiquity of a container.
    - krisoft 2y ago
      > That’s not a hard claim to verify. 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.
FireBeyond 2y ago
> 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. https://www.flightradar24.com/data/aircraft/n513dz https://www.flightradar24.com/data/aircraft/n513dz - Delta A350. Basically running 24/7 other than 3 hour turnarounds at airports.
- HPsquared 2y ago
  I'd call them "in operation" while they are [un]unloading.
  - FireBeyond 2y ago
    Fair, though by the same metric, aircraft are in operation when being embarked and disembarked. At the end of the day it's a minor comment, I suppose, not even rising to the level of 'quibble'. :)
del82 2y ago
Omega Tau Podcast did a really great episode [0] on container shipping, including the optimization of container placement and route planning, highly recommended. [0]: https://omegataupodcast.net/146-container-shipping/ https://omegataupodcast.net/146-container-shipping/
lloydatkinson 2y ago
I am surprised that three hours in and no one has mentioned constraint satisfaction yet: https://en.wikipedia.org/wiki/Constraint_satisfaction https://en.wikipedia.org/wiki/Constraint_satisfaction
- cerved 2y ago
  tbf, it's a constraint optimization problem
math_dandy 2y ago
Why isn’t this product infused with AI?
- dog0000 2y ago
  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.
  - math_dandy 2y ago
    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.
dougSF70 2y ago
It only runs when launched in a dockerized container from the terminal....you are welcome!
danpalmer 2y ago
I guess Google does have a lot of experience shipping containers all around the world...
ngneer 2y ago
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?
cwt137 2y ago
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? [1] https://www.optaplanner.org/ https://www.optaplanner.org/ [2] https://www.minizinc.org/ https://www.minizinc.org/
- deleted 2y ago
  [deleted]
- cerved 2y ago
  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
- marcyb5st 2y ago
  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. [1] https://developers.google.com/optimization/ https://developers.google.com/optimization/ [2] https://www.minizinc.org/doc-2.4.3/en/solvers.html#or-tools https://www.minizinc.org/doc-2.4.3/en/solvers.html#or-tools
- zepfred 2y ago
  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]. [1] - https://timefold.ai/ https://timefold.ai/ [2] - https://timefold.ai/blog/red-hat-optaplanner-end-of-life-notice https://timefold.ai/blog/red-hat-optaplanner-end-of-life-not... [3] - https://docs.timefold.ai/timefold-solver/latest/quickstart/overview https://docs.timefold.ai/timefold-solver/latest/quickstart/o... [4] - https://github.com/TimefoldAI/timefold-quickstarts/ https://github.com/TimefoldAI/timefold-quickstarts/
primitiveData 2y ago
[dead]
whatever1 2y ago
Nothing new, nothing to learn here. Pure pr. Aka give me one OR guy and a gurobi license and we will beat their result. Bonus at the end of the excercise you will have an or guy that can help you solve other use cases as well.
- dog0000 2y ago
  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. http://vrp.galgos.inf.puc-rio.br/index.php/en/updates http://vrp.galgos.inf.puc-rio.br/index.php/en/updates - where's Google?
  - dvaun 2y ago
    How does one end up in this space of work?
    - whatever1 2y ago
      Operations research related studies and work for a logistics company or a company that does some logistics itself (e.g. oil and gas, airlines etc)
- bubblyworld 2y ago
  From an outsider... why does it seem that easy to you? They had a team of OR people working on this and presumably the money to buy a gurobi license.
  - whatever1 2y ago
    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.
wodenokoto 2y ago
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!
abpavel 2y ago
[flagged]
bubblyworld 2y ago
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_.
- nsajko 2y ago
  Is any computing "AI" now?
  - bubblyworld 2y ago
    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.
- deleted 2y ago
  [deleted]
raverbashing 2y ago
Good But the question here is why any of the shipping companies should adopt this given the fact that Google likes to deprecate things at a whim? Shipping companies mostly do this internally already
strnisa 2y ago
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.)
ape4 2y ago
When are they going to ship this software (joke attempt)
factorymoo 2y ago
Why does Google even work on this type of problem? I am genuinely at a loss here.
- verdverm 2y ago
  The more general problem has broad applications, for Google you could see Waymo being another application. Google Cloud is also building industry specific solutions. Showing you are a leader of research will be helpful in attracting customers. https://cloud.google.com/solutions/supply-chain-logistics/ https://cloud.google.com/solutions/supply-chain-logistics/
- eitally 2y ago
  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. https://research.google/teams/operations-research/ https://research.google/teams/operations-research/
- mkoubaa 2y ago
  Google is known for their work on containers

324 points by alphabetting 2y ago

Apparently, container optimization was unsolved for very large fleets. I did not know this. Google OR improves existing solutions by 10%-20% utilization which is incredible.

smarm52 2y ago
It sounds like a packing problem. I'm not deeply familiar with the field, but I don't believe there is a general solution. https://en.wikipedia.org/wiki/Packing_problems https://en.wikipedia.org/wiki/Packing_problems
- hermitcrab 2y ago
  Optimally placing containers on ships must be a very difficult problem. Consider you might want: -heavier containers at the bottom for stability -refrigerated containers on the inside to reduce heat loss -containers to be unloaded first near the top etc And all in 3 dimensions!
  - IncreasePosts 2y ago
    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?
    - hermitcrab 2y ago
      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?
      - ianburrell 2y ago
        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.
      - throwup238 2y ago
        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.
        dmurray 2y ago
        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.
        throwup238 2y ago
        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.
    - akira2501 2y ago
      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. [0]: https://www.youtube.com/watch?v=U75MZwtDCXA https://www.youtube.com/watch?v=U75MZwtDCXA
  - Terr_ 2y ago
    > -heavier containers at the bottom for stability In the same vein, port /starboard / bow / stern balance. > -containers to be unloaded first near the top Containers with the same destination in separate places so that multiple cranes can run in parallel without infringing on each other's work-zones. Truly an interesting project for people who get stuck trying to optimize too many things at once. :p
    - raverbashing 2y ago
      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.
      - mcguire 2y ago
        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...
    - smarm52 2y ago
      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.
  - uoaei 2y ago
    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.
    - cerved 2y ago
      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
      - uoaei 2y ago
        I'm not talking about academics I'm talking about your coworkers.
  - huygens6363 2y ago
    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.
    - hermitcrab 2y ago
      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.
      - pineaux 2y ago
        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.
        smarm52 2y ago
        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: https://en.wikipedia.org/wiki/Markov_chain https://en.wikipedia.org/wiki/Markov_chain
      - huygens6363 2y ago
        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.
        saagarjha 2y ago
        The constraints are not always easily evident, unfortunately.
  - Shrezzing 2y ago
    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.
  - mcguire 2y ago
    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.
    - smarm52 2y ago
      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.
- xnx 2y ago
  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."
  - barfbagginus 2y ago
    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?
- eitally 2y ago
  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.
3abiton 2y ago
This is big news for supply chains!
- pineaux 2y ago
  Maybe

whimsicalism 2y ago

I am very curious if anyone will actually use this API endpoint they're releasing https://developers.google.com/optimization/service/shipping/network_design https://developers.google.com/optimization/service/shipping/... It's very cool nonetheless

mcint 2y ago
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.
- whimsicalism 2y ago
  oh yes i remember them! - they were the first company to reject me for a job
  - malfist 2y ago
    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.
  - 7thaccount 2y ago
    The had layoffs recently I think, so maybe you dodged a bullet
    - whimsicalism 2y ago
      oh i definitely did, landed a higher paying job and hear about lots of drama over there. interesting problem space, though
thih9 2y ago
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. [1]: https://killedbygoogle.com/ https://killedbygoogle.com/

mcint 2y ago

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 4 cranes * 50 containers/crane-hour * 24 hours/day = 1.2k containers / day https://en.wikipedia.org/wiki/Stowage_plan_for_container_ships#Logistical_factors https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi... Stowage plans for ships also have weight, balance, power, and value acceptability criteria beyond availability at a port. These overheads made me curious enough to write up some napkin math, since they mention cut-and-run early departures from ports.

superice 2y ago
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 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.
- mcint 2y ago
  Cool! Thanks! I'm glad my post invited even more for me to learn -- not quite Cunninghamming it in full.

akasakahakada 2y ago

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?

spankalee 2y ago
The same Operations Research group has scheduling examples for restaurants: https://developers.google.com/optimization/service/scheduling/restaurant_scheduling_example https://developers.google.com/optimization/service/schedulin...
- borelian 2y ago
  And a API for shift scheduling: https://developers.google.com/optimization/service/reference/rest/v1/scheduling https://developers.google.com/optimization/service/reference...
mlawrenson 2y ago
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.

thinkingkong 2y ago

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. Who are they competing with?

spankalee 2y ago
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.
- nerdponx 2y ago
  It also makes sense to continue diversifying away from ads and generative AI.
mlawrenson 2y ago
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.
- verdverm 2y ago
  https://developers.google.com/optimization https://developers.google.com/optimization https://github.com/google/or-tools https://github.com/google/or-tools

oa8891 2y ago

[dead]

oa_8891 2y ago

[dead]

rapfaria 2y ago

It is really worth a try when demurrage is not even accounted for? https://developers.google.com/optimization/service/reference/rest/v1/shipping/designShippingNetwork#vesselcost https://developers.google.com/optimization/service/reference...

macmac 2y ago
Or detention for that matter.
borelian 2y ago
It goes here: https://developers.google.com/optimization/service/reference/rest/v1/shipping/designShippingNetwork#CommodityDemand https://developers.google.com/optimization/service/reference...

snapetom 2y ago

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.

danielmarkbruce 2y ago
Like the other comment - very curious about this. Could you explain what you are doing in more detail for folks not in this space?
nickff 2y ago
I'm very curious about what you folks do! How much effort is expended on this optimization? Perhaps in terms of FTE developers per terminal.
- snapetom 2y ago
  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.

mezod 2y ago

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. It also ridiculizes my little coding problems x)

huitzitziltzin 2y ago
That is an outstanding book. I second the recommendation. I’ll even make a (sincere!) claim that I suspect will inspire a lot of angry attempts at rebuttals: The 20 foot shipping container has had a greater impact on the world than large language models are likely to ever achieve. Read the book first and then tell me why you think I’m wrong. (I’m not wrong :) )
- Closi 2y ago
  We will have to wait 50 years to work out if you are wrong or not! (Assuming by LLM's we are broadly referring to AI, rather than LLM's as a specific technology)
- intended 2y ago
  That’s not a hard claim to verify. They simply have. Gen Ai has a long way to go and multiple languages and cultures to mesh with before it achieves the ubiquity of a container.
  - krisoft 2y ago
    > That’s not a hard claim to verify. 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.

FireBeyond 2y ago

> 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. https://www.flightradar24.com/data/aircraft/n513dz https://www.flightradar24.com/data/aircraft/n513dz - Delta A350. Basically running 24/7 other than 3 hour turnarounds at airports.

HPsquared 2y ago
I'd call them "in operation" while they are [un]unloading.
- FireBeyond 2y ago
  Fair, though by the same metric, aircraft are in operation when being embarked and disembarked. At the end of the day it's a minor comment, I suppose, not even rising to the level of 'quibble'. :)

del82 2y ago

Omega Tau Podcast did a really great episode [0] on container shipping, including the optimization of container placement and route planning, highly recommended. [0]: https://omegataupodcast.net/146-container-shipping/ https://omegataupodcast.net/146-container-shipping/

lloydatkinson 2y ago

I am surprised that three hours in and no one has mentioned constraint satisfaction yet: https://en.wikipedia.org/wiki/Constraint_satisfaction https://en.wikipedia.org/wiki/Constraint_satisfaction

cerved 2y ago
tbf, it's a constraint optimization problem

math_dandy 2y ago

Why isn’t this product infused with AI?

dog0000 2y ago
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.
- math_dandy 2y ago
  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.

dougSF70 2y ago

It only runs when launched in a dockerized container from the terminal....you are welcome!

danpalmer 2y ago

I guess Google does have a lot of experience shipping containers all around the world...

ngneer 2y ago

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?

cwt137 2y ago

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? [1] https://www.optaplanner.org/ https://www.optaplanner.org/ [2] https://www.minizinc.org/ https://www.minizinc.org/

deleted 2y ago
[deleted]
cerved 2y ago
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
marcyb5st 2y ago
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. [1] https://developers.google.com/optimization/ https://developers.google.com/optimization/ [2] https://www.minizinc.org/doc-2.4.3/en/solvers.html#or-tools https://www.minizinc.org/doc-2.4.3/en/solvers.html#or-tools
zepfred 2y ago
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]. [1] - https://timefold.ai/ https://timefold.ai/ [2] - https://timefold.ai/blog/red-hat-optaplanner-end-of-life-notice https://timefold.ai/blog/red-hat-optaplanner-end-of-life-not... [3] - https://docs.timefold.ai/timefold-solver/latest/quickstart/overview https://docs.timefold.ai/timefold-solver/latest/quickstart/o... [4] - https://github.com/TimefoldAI/timefold-quickstarts/ https://github.com/TimefoldAI/timefold-quickstarts/

primitiveData 2y ago

[dead]

whatever1 2y ago

Nothing new, nothing to learn here. Pure pr. Aka give me one OR guy and a gurobi license and we will beat their result. Bonus at the end of the excercise you will have an or guy that can help you solve other use cases as well.

dog0000 2y ago
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. http://vrp.galgos.inf.puc-rio.br/index.php/en/updates http://vrp.galgos.inf.puc-rio.br/index.php/en/updates - where's Google?
- dvaun 2y ago
  How does one end up in this space of work?
  - whatever1 2y ago
    Operations research related studies and work for a logistics company or a company that does some logistics itself (e.g. oil and gas, airlines etc)
bubblyworld 2y ago
From an outsider... why does it seem that easy to you? They had a team of OR people working on this and presumably the money to buy a gurobi license.
- whatever1 2y ago
  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.

wodenokoto 2y ago

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!

abpavel 2y ago

[flagged]

bubblyworld 2y ago

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_.

nsajko 2y ago
Is any computing "AI" now?
- bubblyworld 2y ago
  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.
deleted 2y ago
[deleted]

raverbashing 2y ago

Good But the question here is why any of the shipping companies should adopt this given the fact that Google likes to deprecate things at a whim? Shipping companies mostly do this internally already

strnisa 2y ago

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.)

ape4 2y ago

When are they going to ship this software (joke attempt)

factorymoo 2y ago

Why does Google even work on this type of problem? I am genuinely at a loss here.

verdverm 2y ago
The more general problem has broad applications, for Google you could see Waymo being another application. Google Cloud is also building industry specific solutions. Showing you are a leader of research will be helpful in attracting customers. https://cloud.google.com/solutions/supply-chain-logistics/ https://cloud.google.com/solutions/supply-chain-logistics/
eitally 2y ago
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. https://research.google/teams/operations-research/ https://research.google/teams/operations-research/
mkoubaa 2y ago
Google is known for their work on containers