9 ms·

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

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.
        namibj 2y ago
        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).
    - 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

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.
      - namibj 2y ago
        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).
  - 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