Heuristics on the high seas: Mathematical optimization for cargo ships

🌈 Abstract

The article discusses the challenges and solutions in optimizing the design and scheduling of global shipping networks, which are critical for the efficient transportation of 90% of the world's goods. It introduces Google's Operations Research team's new Shipping Network Design API, which solves the Liner Shipping Network Design and Scheduling Problem (LSNDSP) at a large scale.

🙋 Q&A

[01] Shipping Network Design and Scheduling Problem

1. What are the three main components of the Liner Shipping Network Design and Scheduling Problem (LSNDSP)?

• Network design: Determines the order in which vessels visit ports
• Network scheduling: Determines the times vessels arrive and leave ports
• Container routing: Chooses the journey that containers take from origin to destination

2. Why is solving these three problems simultaneously more difficult but more likely to discover better solutions? Solving the network design, network scheduling, and container routing problems simultaneously is more complex, but it is more likely to find better overall solutions compared to solving them sequentially.

3. What are some of the constraints and challenges involved in solving the LSNDSP at scale?

• The search space is staggeringly large, involving a large number of variables (ships and ports) and constraints (e.g., a ship can only carry a certain number of containers).
• Vessels have pre-arranged berthing slots at ports and may have to wait in an anchorage area if the port is congested.
• Containers may need to be transshipped at intermediate ports, further increasing the number of possible solutions.
• Previous attempts to solve this problem did not consider transit times, which significantly improves solution quality.

[02] Google's Shipping Network Design API

1. What are the two basic approaches used by Google's team to solve the LSNDSP?

• An approach using column generation to consider only a subset of variables at first and then generate new variables to better approximate the original problem.
• A heuristic strategy using two variants of local search to examine neighborhoods around existing solutions and find opportunities for improvement.

2. How did Google's team improve the scalability of these approaches?

• They applied a heuristic strategy using two variants of local search to examine neighborhoods around existing solutions and find opportunities for improvement.
• They made use of incrementalism, locking down promising portions of a solution so they could start from a known good solution and make it better.

3. How did Google's solution perform compared to previous attempts?

• For the LINERLIB benchmark scenarios, Google's solution was able to route more containers (up to 35% more) with fewer vessels (up to 23% fewer).
• The solutions also improved the projected profit margins considerably compared to the baseline.

4. What are the key benefits of Google's Shipping Network Design API?

• It is the first solution able to solve the network design and scheduling problem at the scale of the WorldLarge scenario (500 vessels, 200 ports, 140,000 containers).
• It can double the profit of a container shipper, deliver 13% more containers, and do so with 15% fewer vessels.