[HN Gopher] Mathematical Optimization for Cargo Ships
___________________________________________________________________
Mathematical Optimization for Cargo Ships
Author : alphabetting
Score : 304 points
Date : 2024-06-05 00:00 UTC (1 days ago)
(HTM) web link (research.google)
(TXT) w3m dump (research.google)
| algo_trader wrote:
| 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 wrote:
| 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
| hermitcrab wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| namibj wrote:
| 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).
| throwup238 wrote:
| 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.
| akira2501 wrote:
| 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
| Terr_ wrote:
| > -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 wrote:
| 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 wrote:
| 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...
| uoaei wrote:
| 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 wrote:
| 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
| huygens6363 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| huygens6363 wrote:
| 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 wrote:
| The constraints are not always easily evident,
| unfortunately.
| namibj wrote:
| 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.
| mcguire wrote:
| 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.
|
| https://www.herbert-abs.com/cargomax-for-container-ships
|
| https://www.lineroptimizer.com/
| hermitcrab wrote:
| Everything is easy to the person that doesn't have to do
| it.
| Shrezzing wrote:
| 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 wrote:
| 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.
| xnx wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| This is big news for supply chains!
| pineaux wrote:
| Maybe
| whimsicalism wrote:
| I am very curious if anyone will actually use this API endpoint
| they're releasing
| https://developers.google.com/optimization/service/shipping/...
|
| It's very cool nonetheless
| mcint wrote:
| 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 wrote:
| oh yes i remember them! - they were the first company to
| reject me for a job
| malfist wrote:
| 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 wrote:
| The had layoffs recently I think, so maybe you dodged a
| bullet
| whimsicalism wrote:
| oh i definitely did, landed a higher paying job and hear
| about lots of drama over there. interesting problem
| space, though
| thih9 wrote:
| 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/
| spitfire wrote:
| 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.
| eitally wrote:
| 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.
|
| https://developers.google.com/maps/documentation/transportat...
| whimsicalism wrote:
| 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
| mcint wrote:
| 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_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 wrote:
| 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.
| akasakahakada wrote:
| 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 wrote:
| The same Operations Research group has scheduling examples for
| restaurants:
| https://developers.google.com/optimization/service/schedulin...
| borelian wrote:
| And a API for shift scheduling: https://developers.google.com
| /optimization/service/reference...
| mlawrenson wrote:
| 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.
| viceconsole wrote:
| 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.
| hermitcrab wrote:
| 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.
| eitally wrote:
| 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.
| stackskipton wrote:
| 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.
| tedunangst wrote:
| 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.
| akasakahakada wrote:
| Think about this
|
| Go players: Go is so difficult. So many options and constrain
| blah blah blah
|
| AlphaGo: Oh yah?
| hermitcrab wrote:
| The optimization space for Go is very large, but the rules
| are relatively simple.
| raverbashing wrote:
| Think about this: People are not Go stones
|
| (ok, maybe managers of low margin business are, but I
| digress)
| zetazzed wrote:
| This is a really important problem, and a lot of software
| attacks it. Pretty much every big HR/workforce management
| system includes options for it, e.g.
| https://www.workday.com/en-us/products/workforce-management/...
| and https://www.oracle.com/human-capital-management/workforce-
| ma..., plus a lot of dedicated providers.
|
| 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.
| hermitcrab wrote:
| 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.
| thinkingkong wrote:
| 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 wrote:
| 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 wrote:
| It also makes sense to continue diversifying away from ads
| and generative AI.
| mlawrenson wrote:
| 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 wrote:
| https://developers.google.com/optimization
|
| https://github.com/google/or-tools
| rapfaria wrote:
| It is really worth a try when demurrage is not even accounted
| for?
|
| https://developers.google.com/optimization/service/reference...
| macmac wrote:
| Or detention for that matter.
| borelian wrote:
| It goes here:
| https://developers.google.com/optimization/service/reference...
| snapetom wrote:
| 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.
| nickff wrote:
| 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 wrote:
| 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.
| bendtb wrote:
| 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.
| hermitcrab wrote:
| Interesting. So a private equity company might have
| actually done something good? That's news!
| snapetom wrote:
| 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.
| eitally wrote:
| 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.
| hermitcrab wrote:
| 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.
| fuzzfactor wrote:
| IOW, mathematics is only a small part of the equation.
| superice wrote:
| 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.
| eitally wrote:
| 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.
| danielmarkbruce wrote:
| Like the other comment - very curious about this. Could you
| explain what you are doing in more detail for folks not in this
| space?
| yyyfb wrote:
| The benchmark data that they've used to assess their
| performance comes from Maersk https://github.com/blof/LINERLIB
| superice wrote:
| 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.
| hef19898 wrote:
| 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.
| inasio wrote:
| 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
| synctext wrote:
| 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.)
| superice wrote:
| 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...
| philip1209 wrote:
| 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.
| theolivenbaum wrote:
| 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
| darksaints wrote:
| 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.
| bjornasm wrote:
| >it seems very academic
|
| From an academic standpoint it seemed a bit to little academic
| in presentation though, I would like to see the problem
| formulation! :)
| gessha wrote:
| My dad worked as a shipmaster for a while and did some work on
| practical port terminal organization.
|
| I couldn't look up his work exactly because our names are
| highly generic but if you're interested, I can forward you his
| work.
| surfingdino wrote:
| > "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.
| snapetom wrote:
| 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.
| eitally wrote:
| 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.
| mezod wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| Eduard wrote:
| Wikipedia article about "The Box":
| https://en.m.wikipedia.org/wiki/The_Box_(Levinson_book)
| hammeiam wrote:
| They give this book out to all the new hires at Flexport, or at
| least they did a few years ago
| FireBeyond wrote:
| > 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 - Delta A350.
| Basically running 24/7 other than 3 hour turnarounds at airports.
| HPsquared wrote:
| I'd call them "in operation" while they are [un]unloading.
| FireBeyond wrote:
| 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 wrote:
| 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/
| lloydatkinson wrote:
| I am surprised that three hours in and no one has mentioned
| constraint satisfaction yet:
| https://en.wikipedia.org/wiki/Constraint_satisfaction
| cerved wrote:
| tbf, it's a constraint optimization problem
| math_dandy wrote:
| Why isn't this product infused with AI?
| dog0000 wrote:
| 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.
| danpalmer wrote:
| I guess Google does have a lot of experience shipping containers
| all around the world...
| ngneer wrote:
| 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 wrote:
| 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/ [2] https://www.minizinc.org/
| cerved wrote:
| 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 wrote:
| 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/ [2]
| https://www.minizinc.org/doc-2.4.3/en/solvers.html#or-tools
| dougSF70 wrote:
| It only runs when launched in a dockerized container from the
| terminal....you are welcome!
| whatever1 wrote:
| 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 wrote:
| 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 - where's
| Google?
| dvaun wrote:
| How does one end up in this space of work?
| whatever1 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| bubblyworld wrote:
| On the other hand they cleared an open source benchmark by
| a long way, for which people have had plenty of time to
| apply existing approaches, right?
|
| This is just a PR article, it's hard to say what they did
| or didn't try before arriving at this solution.
| whatever1 wrote:
| Because frankly nobody gives a sh about throwing
| resources and finding just better (not globally optimal)
| solutions to synthetic benchmarks.
|
| Academics care about proving optimality. Businesses care
| about their own specific use case and not synthetic
| benchmarks.
| bubblyworld wrote:
| Okay, well, thanks for your thoughts.
| chaoxu wrote:
| > Because frankly nobody gives a sh about throwing
| resources and finding just better (not globally optimal)
| solutions to synthetic benchmarks.
|
| This does not align with my experience of people working
| in OR.
| cerved wrote:
| 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
| chaoxu wrote:
| A heuristic using problem specific structure can beat
| Gurobi which is for solving general mip.
| cerved wrote:
| they do have a Gurobi license
| wodenokoto wrote:
| 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!
| bubblyworld wrote:
| 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 wrote:
| Is any computing "AI" now?
| bubblyworld wrote:
| 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.
| raverbashing wrote:
| 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 wrote:
| 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 wrote:
| When are they going to _ship_ this software (joke attempt)
| factorymoo wrote:
| Why does Google even work on this type of problem? I am genuinely
| at a loss here.
| verdverm wrote:
| 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/
| eitally wrote:
| 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/
___________________________________________________________________
(page generated 2024-06-06 23:02 UTC)