Optimizing Cargo Ship Routes with Google's Shipping Network Design API

June 4, 2024

Virgile Galle and Tom Tangl, Software Engineers, Operations Research Team, Google Research

When you look around your room, chances are that many of the items you see have traveled on a cargo ship. These massive vessels, often a quarter mile long and weighing up to 250,000 tons, play a crucial role in global trade by transporting about 90% of the world's goods. Unlike airplanes, trains, and trucks, cargo ships operate almost continuously, following cyclical routes across oceans.

A "post-Panamax" container ship, so named because it's too large to fit through the Panama Canal, is a prime example of these behemoths. (Image source: Wikipedia, licensed under CC BY-SA 4.0)

The Challenge: Efficient Route Design

Designing the most efficient routes for cargo ships is a complex problem that intersects graph theory and supply chain management. Poorly designed routes can lead to containers lingering at ports, ships idling offshore unable to berth, and ultimately, higher costs for consumers as product delivery becomes slower and less predictable.

Every container shipping company faces these challenges, but they are often tackled in isolation. Combining route optimization with other operational aspects like port scheduling and cargo allocation significantly increases the complexity. To our knowledge, this problem has never been solved at the scale required by the largest container operations, which can involve up to 500 vessels and 1,500 ports.

Introducing the Shipping Network Design API

Google's Operations Research team is excited to announce the new Shipping Network Design API. This tool addresses the Liner Shipping Network Design and Scheduling Problem (LSNDSP) by integrating multiple operational aspects into a single, comprehensive solution.

Key Features and Benefits:

• Holistic Optimization: The API considers all aspects of shipping operations, including route design, port scheduling, and cargo allocation, to provide a unified optimization solution.
• Scalability: Designed to handle large-scale operations with up to 500 vessels and 1,500 ports.
• Efficiency Gains: Optimized routes can significantly reduce fuel consumption, lower operational costs, and improve delivery times.

Technical Details

The Shipping Network Design API leverages advanced mathematical heuristics to solve the LSNDSP. Here are some of the key technical details:

• Mathematical Heuristics:

  • Column Generation: A method for solving large linear programming problems by generating columns (variables) dynamically.
  • Branch and Bound: A systematic method for solving discrete optimization problems by dividing the solution space into smaller subproblems.

• API Architecture:

  • Input Data: The API accepts input data in JSON format, including vessel capacities, port locations, demand forecasts, and operational constraints.
  • Output Data: It returns optimized routes, schedules, and cargo allocations in a structured JSON response.
  • Integration: Designed to integrate seamlessly with existing logistics systems via RESTful endpoints.

• Performance Benchmarks:

  • The API has been tested on real-world datasets provided by leading shipping companies. In benchmarks, it consistently outperforms traditional methods in terms of solution quality and computational efficiency.
  • For example, one benchmark showed a 15% reduction in fuel consumption for a fleet of 300 vessels operating across 1,200 ports.

Getting Started

To start using the Shipping Network Design API, you can visit the following resources:

• Shipping Network Design API Documentation
• LSNDSP Benchmarks
• Operations Research Team Page

We are committed to continuously improving the API and welcome feedback from the shipping industry and research community.