Heuristics on the high seas: Mathematical optimization for cargo ships
June 4, 2024
Virgile Galle and Tom Tangl, Software Engineers, Operations Research Team, Google Research
We present a previously unknown solution to the Liner Shipping Network Design and Scheduling Problem, which is part of our new Shipping Network Design API.
Look around you. Chances are that something in your line of sight sailed on a cargo ship. 90% of the world's goods travel over the ocean, often on cargo vessels mammoth in scale: a quarter mile long, weighing 250,000 tons, holding 12,000 containers of goods collectively worth a billion dollars. Unlike airplanes, trains, and trucks, cargo ships are in nearly constant operation, following cyclical routes across oceans.
A "post-Panamax" container ship, so named because it's too large to fit in the Panama Canal. Image source: Wikipedia, licensed under CC BY-SA 4.0.
But, what are the best, most efficient routes for these ships? To a computer scientist, this is a graph theory problem; to a business analyst, a supply chain problem. Done poorly, containers linger at ports, ships idle offshore unable to berth, and ultimately, products become pricier as the flow of physical items becomes slower and unpredictable. Every container shipping company needs to solve these challenges, but they are typically solved separately. Combining them multiplies the complexity, and, to the best of our knowledge, is a problem that has never been solved at the scale required by the largest container operations (500 vessels and 1500 ports).
Google's Operations Research team is proud to announce the Shipping Network Design API, which implements a new solution to this problem. Our approach scales better, enabling solutions to world-scale supply chain problems, while being faster than any known previous attempts. It is able to double the profit of a container shipper, deliver 13% more containers, and do so with 15% fewer vessels. Read on to see how we did it.
Background
There are three components to the Liner Shipping Network Design and Scheduling Problem (LSNDSP). 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. Every container shipping company needs to solve all three challenges, but they are typically solved sequentially. Solving them all simultaneously is more difficult but is also more likely to discover better solutions.
Solutions to network design create service lines that a small set of vessels follow: for instance, sailing between eastern Asia, through the Suez canal, and to southern Europe. These service lines are published with dates, so that shippers can know when and where to have their containers ready at port.
Part of a network design for a hypothetical ocean shipper, showing how vessels might cycle between nine ports.
Container vessels can't dock at ports whenever they like; they have pre-arranged berthing slots. As they approach a port, they linger at an anchorage area, an offshore location where they can drop anchor until their berth becomes free. When a port is congested, vessels may end up staying in the anchorage area for hours or days. And so the precise network schedule of the vessels becomes important: not just what day to dock, but what hour, and whether to increase velocity to arrive at a particular time (or conversely, to decrease velocity to save fuel).
Once the vessel docks at the port, cranes offload the containers into stacks, and then load other containers onto the vessels for the next leg of the voyage. If the vessel falls behind schedule, it will sometimes cut-and-run: leaving the port before all the intended containers have been loaded, relying on later vessels to pick up the containers. When a container spends time at an intermediate port en route from origin to destination, it’s called transshipment. This multiplies further the number of possible solutions to LSNDSP. Transshipment is just one of several constraints that come into play when generating container routes.
A container vessel berthed at port, underneath the cranes that load and unload containers. Image is in the public domain.
Solving these three problems — network design, network scheduling, and container routing — at scale involves a staggeringly large search space.
Methods
Every optimization problem has three components: variables (e.g., ships and ports), constraints on those variables (e.g., a ship can fit only so many containers onboard), and an objective function to be minimized or maximized (e.g., maximize the number of containers shipped). The variables and constraints are often represented as a matrix in which the columns are the variables and the rows are the constraints.
A common technique to decompose such large problems is column generation, in which only a subset of the variables are considered at first, and then new variables — that is, new columns — are generated to more closely approximate the original problem. To help manage this, we developed a software library that analyzes the problem and predicts which columns are best to generate. This library will be open sourced via MathOpt, our mathematical programming framework.
With this in hand, we defined two basic approaches to solve the problem:
- Double Column Generation
We considered network design and container routing as two coupled problems, each consisting of a primary selection problem (choose the best option) and a subsidiary generation problem (identify reasonable options). We applied a shortest-path algorithm to each pair of problems to generate reasonable options, followed by a linear program (using our linear programming solver, Glop) to choose the best options for each. We applied the column generation technique to both at the same time, using intermediate results on each problem to influence progress on the other. This double column generation approach enabled us to find provably optimal solutions, but it only scaled well to moderate sized problems. - CP-SAT
We then tried an implementation based on constraint programming, using our CP-SAT constraint programming solver. This also worked well up to mid-sized networks, but did not scale to the worldwide shipping problem.
These two approaches enabled us to find provably optimal solutions, but they only scaled well to small and medium sized problems. To improve their scalability, we applied a heuristic strategy using two variants of local search in which we examine neighborhoods around existing solutions to find opportunities for improvements.
- Large neighborhood search
We fixed parts of the solution (e.g., "this vessel will visit Los Angeles on alternate Tuesdays") before applying either of the methods described above. This improves scalability by reducing the search space. - Variable neighborhood search
We explored neighborhoods over both the network and the schedule. We parallelize the exploration and distribute it over multiple machines to evaluate many neighborhoods simultaneously. This also improves scalability by limiting the search space, while also allowing us to incorporate knowledge from Operations Research and the shipping industry.
With both of these approaches, we made use of incrementalism: locking down promising portions of a solution so that we could start from a known good solution to make it better.
Finally, we also took into consideration transit times. Previous attempts to solve this problem didn't take transit times into account, since they make the problem much more difficult to solve. We found that inclusion of transit times significantly improved the solution quality.
A small modification to the network discovered with neighborhood search can affect shipping profits. In this example, the model might suggest a new connection that makes it possible to ship containers between ports that weren’t previously connected.
Results
To quantify the performance of our solutions, we use LINERLIB, an industry benchmark for shipping network design problems, including container shipping scenarios: fleets, ports, and container demands. We tested our solution on three scenarios: WorldSmall, EuropeAsia, and the beastly WorldLarge, the latter of which contains 500 vessels, 200 ports, and nearly 140,000 containers.
Below is the comparison of five LINERLIB scenarios.
A comparison of our solutions to the previously best known solutions. The size of the bubble corresponds to the number of ports, indicating the scale of the problem. Our solutions consistently reduce the number of vessels needed for a given volume of containers.
In any optimization scenario, it's important to specify the objective. Want to maximize the number of containers shipped? Easy: throw more ships at the problem, ballooning operating costs. Want to minimize the number of vessels used? Again, easy: have one ship deliver every container in the world, with ludicrously long delivery times.
The LINERLIB benchmark balances these by calculating the estimated profit: the revenue from on-time deliveries minus the costs of sailing and handling containers at port. The next figure depicts how our solution's profit compares to previous attempts.
Improvements in weekly profit from our solutions compared to the previously best available solutions. Profits are based on the economic assumptions in the LINERLIB dataset.
Compared to the baseline, our method was able to route more containers with fewer vessels. For each of the LINERLIB scenarios, our solutions improved the overall efficiency, increasing the throughput (35% more containers for WorldSmall, 14% for EuropeAsia, 35% for Pacific, 32% for Mediterranean) while using fewer vessels (7%, 15%, 4%, and 23% respectively). Based on the economic assumptions in LINERLIB, our solutions also improved projected profit margins considerably.
Conclusion
As our results show, the careful selection of advanced optimization techniques can have a remarkable effect on the efficiency of shipping networks. We believe our method is the first able to solve the network design and scheduling problem at the scale of WorldLarge. You can examine our results in more detail on our benchmark page. We hope that this work will inspire additional research into this domain with the goal of building more efficient and smooth global supply chains.
The Shipping Network Design API is one of a set of Operations Research APIs that we'll be adding to in the future as we look for other industries to optimize.
-
Labels:
- Algorithms & Theory
Other posts of interest
-
May 1, 2024
Scaling hierarchical agglomerative clustering to trillion-edge graphs- Algorithms & Theory ·
- Machine Intelligence
-
April 19, 2024
Improving Gboard language models via private federated analytics- Algorithms & Theory ·
- Distributed Systems & Parallel Computing ·
- Product ·
- Security, Privacy and Abuse Prevention
-
April 16, 2024
Solving the minimum cut problem for undirected graphs- Algorithms & Theory