I don't think this relates to the physical loading of the containers on ships at all. It is concerned with 3 problems: "Network design determines the order in which vessels visit ports, network scheduling determines the times they arrive and leave, and container routing chooses the journey that containers take from origin to destination."
OP is not wrong about the bin packing, since it relates not only to physical loading of containers, but also the optimal "loading" of schedules in time!
The insight is to see time as a spatial dimension - then a set of shipping tasks - each with a length determined by time to complete the task - can be packed into a set of 1d bins representing boat schedules!
This is variously known as the supply chain optimization problem in logistics, the minimal makespan problem in manufacturing, and the multiprocessor scheduling problem in compsci. All of these problems have been classically formulated as bin packing problems.
Toy model: Single ship + Single container Bin Packing
Here is how it works for a single boat and a single package going between multiple ports. In this case, the problem is equivalent to a shortest path problem on a graph with weighted nodes, and more traditionally presented as a shortest path problem on a graph with weighted edges. I'll show the model and the graph translations!
The model consists of:
1. One bin - a 1 dimensional line representing the utilization of the ship over time
2. Line segments p_1 .. p_k representing the transit time for each of k possible shipping operations (taking the container from some port to some other port). For this model, assume p_1 = p_k = 0, representing the first and final transits
3. A port relation P_ik saying "transit k can immediately follow transit i," or equivalently, "transit i's arrival port is transit k's departure port"
A span is a sequence of line segments respecting the port relations, starting at p_0 and ending at p_k. The problem is to find a makespan - an optimal span.
This is the same as the shortest path on a directed graph G with nodes weighted p_1 .. p_k, where we draw an arrow i -> j iff P_ij.
This graph can also be "dualized" into a directed graph G' where nodes are ports, and arrows between ports are weighted by transit times. This is the most familiar form of this problem.
Define an equivalence relation i ~ j saying transit i and j are equivalent iiff P_ik = P_jk for all k (i and j arrive at the same port). Now give G' a node for each equivalence class [i], which we call ports. Finally, for any pair of ports [i] and [j], add an arrow [i] -> [j] with weight p_k if and only if there exists k such that
1. P_ik. (Transit k leaves from port [i])
2. k is in [j]. (Transit k arrives at port [j])
Now we have the traditional shortest route problem on a graph with weighted edges. However the bin packing model naturally scales to the case where we have many ships, larger cargo capacities, many containers, and complex transit constraints.
In this general case, we regain the geometric packing aspect as well! This is because the ships are represented by 4 dimensional bins, which are packed with containers in x, y, z AND t dimensions! The spatial part of this packing now has to obey efficiency constraints like minimizing the unpacking and reshuffling that happens at each port! Wild, huh?
> In this case, the problem is equivalent to a shortest path problem on a graph with weighted nodes, and more traditionally presented as a shortest path problem on a graph with weighted edges.
Exactly.
I was exposed to this sort of conception of the packing problem when implementing Ant Colony Optimization (ACO) for a programming challenge.
And there's also regulation IIRC dictating that more hazardous material should be packed at the center of the ship, to avoid falling off in case of accident.
Don't store some classes of hazardous materials near specific other classes of hazardous materials (keep your oxidizers away from the fuels), don't carry too much hazardous material, keep good records of what's in each container and where that container is...
Wow, that's a great insight. Not only how to pack optimally, but how to balance the load. Then not just balance the load for shipping, but also to optimize packing the load. Sort of like torquing the lug-nuts on tires one at a time to avoid tipping the car.
Compared to.. protein folding, nuclear fusion? Sounds like a handful of parameters to me. What are computers good for if not looking for solutions in this space?
It's strange to me that the cargo space has not been aggressively optimized. It's a pretty substantial part of civilization and, I believe, there's definitely some money sloshing around there.
A Panamax can carry ~5000 containers. 5000! (5000 factorial) is a BIG number. Bear in mind that 60! is more than the number of atoms in the observable universe. Combinatorial problems are hard.
For some reason, ignorance most likely, I'm not impressed. Looks relatively easy. Not for me, but for anybody with some math skills it looks easy to improve upon naive solutions.
To be fair, a completely optimal solution definitely seems out of reach, but I'm not interested in those.
Hmm. Let's say you're looking at that 5000 TEU (Twenty-foot Equivalent Units) ship with (the most common, IIUC) 40' containers. The state space for optimization has something like 2500! or 10^7400 states. Given 24 hours to optimize it at 1ns per state, you could look at 10^14 states or 10^-7384% of the state space.
There are also a lot more constraints than weight and balance and they're constantly changing; some may rule out big chunks of the state space which is very good, but it's still a Hard Problem.
But it's not like there aren't people already doing it.
The issue is in adequately capturing and encoding these constraints; particularly multi-crane piers that skip an intermediate autonomous shuttle truck to go directly onto trains are quite difficult.
Just imagine the contingency planning due to restrictions in unloading.
This is if you are looking in an naive way and are only interested in for THE BEST solution. However, there are many constraints and we are looking for a better solution not the best one.
Yes exactly, I'm reminded of solutions to find numerical approximation results for very difficult problems like this. One of the most famous are Markov chain approaches to resolving similar issues. Then, for the interested:
There's quite a lot of other constraints too. Lots of goods aren't allowed to sit side-by-side, for example, anything explosive goods cannot sit within n containers of hazardous chemicals. Because goods codification is so low-fidelity, lots of things which aren't actually explosive/hazardous can't be stored in close proximity, because we can't differentiate them from things which are actually hazardous/explosive.
It's very much wackier than that. In addition to mere physical constraints, there are the laws and regulations of individual countries and a goodly stack of international treaties and standards.
Wow, that's an entirely different set of constraints that I hadn't considered. I have a whole new respect for logistics professionals that handle that sort of thing.
All of the refrigerated containers I have seen have had a built in generator/AC unit...why would shippers care about heat loss, unless they are providing the energy to refrigerate the containers?
That generator is for very short periods of time spent in transit. Once it's on the ship it's directly connected to ships power. This also has implications for it's placement as not all rows of stacks on a ship have power cables run out to them.
Also, because of the short time requirement, and some extreme low temperature requirements on some cargo, it needs to be in a place where it can be disconnected and very quickly craned off the ship.
The engineer making and breaking the connections will generally have to manually log the time of these actions and the time of the unload. It's all a very interesting and somewhat complicated process.
I assume the shippers are providing the power for refrigerated containers. Otherwise they would need to have batteries or fuel that could last potentially weeks at sea. Anyone know?
They do but most reefers (refrigerated containers) have build in or portable gensets to provide power when they’re not on the ship and plugged in. They could easily spend days in the port stacks and having to plug them in every time they moved would make life a lot more difficult for the port. They can burn anywhere from a few hundred to a few thousand liters of diesel per week which isn’t actually that much to a 40ft shipping container.
How important do you think would a grid hookup be on European freight trains for reefers?
It should be straight forward to include full wagon power with the upcoming DAC4EU coupling (UIC 552 says that normal coaches are to have an 800A through connection that's regularly fed with 1000V 16.7Hz or 1500V 50Hz; this is single-wire earth(/track)-return).
Keep in mind that unlike North American freight trains, Europe mainline service is almost fully electrified. Thus the reefer would be grid-fed.
I'm asking because I'm looking to propose a change to the current plans for the electric coupler (use near-field RF instead of the currently-preferred single-pair Ethernet or it's fallback powerline; I think 802.11 has suitable PHY options, especially among the OFDM codes if the near-field chamber is dispersive and/or has problematic resonances in the channel), and throwing in "grid power for reefers" with actual numbers from the reefer container industry would be easy (a change to the coupler is a change, and the additional cable through the wagon shouldn't be that extensive either if it's an economical aluminum type; also this would allow passenger coaches that are currently using the pre-DAC4EU hook and chain coupling to be used with DAC4EU rolling stock).
I recommend talking to someone with experience shipping reefers in Europe because small seemingly irrelevant details will make or break the design. I assume that Europe uses a lot more international reefers that don't come with their own gensets so many trains would already have power in the form of generator cars. It might be impractical to hook them up to train power without a way to synchronize all the coolers so that they don't all turn on at once and brown out the train in the middle of a climb.
IIRC international reefers require three phase power with a 50 amp breaker so even 800 amps won't get you very far if they all start up at once.
It sounds like these are automated somehow, that the generator kicks in when it's not otherwise being powered - otherwise isn't it just as much work for the port to run around starting and stopping generators?
But an automated system sounds like it has its own problems, how does it make sure it has proper ventilation and comes on at the right time? Probably I don't want the container to start venting diesel fumes when it's deep in a stack of lego surrounded on all sides.
Reefers still get special treatment at ports because they have to be moved as quickly as possible. That includes not stacking them several layers deep horizontally so that ventilation is blocked (the gensets are very obvious from the outside). They’ll often get connected while in the port too, it’s just not a guarantee. Someone with more valuable produce will often pay for preferable treatment and a power connection to reduce risk from malfunction and running out of fuel.
It has to be automated since it’s a refrigeration unit that needs to know when to turn on the cooler. The control circuit starts up the generator if it senses no power connection at that time, usually off a standard marine lead acid battery.
Container ships do provide power to refrigerated containers. My understanding is that refrigerated containers are in row with the door accessible and power hookup. I was looking at photo of the row, and how container ships have extra power system to power them. It looked like it was far down with stacks of containers around and presumably on top.
Computer scientists are always so concerned with optimality. IMO it is sufficient to know an optimum exists and a way to converge on the solution, then finding quasi-optimal solutions is more than good enough.
Not at all. Plenty of people are researching finding satisfiable solution that are quasi-optimal at scale. Once you reach a certain scale of optimization problem, proven optimality in a reasonable time-frame is often infeasible
No, not really. Packing itself is a mostly solved problem. This is a combination of packing + traveling salesman, where the combinatorics of the traveling salesman part are highly variable since there's no requirement that any given ship must hit any given terminal.
Google OR improves existing solutions by 10%-20% utilization which is incredible.