Navigating the Future of AI-services: Behind Google OR’s publication on Maritime Networks Optimization and the recent historic partnership with CMA CGM
Google published on the 5th of June an article — Heuristics on the high seas: Mathematical optimization for cargo ships — on maritime networks optimization. The 18th of July, as we finished to write this Blog article and prepared for publication, CMA CGM announced a 5-years partnership with Google on the integration of advanced AI innovation tools across all its activities: from its media to shipping operations. This partnership is historic and shows how Google (like other major AI-pioneers) is developing its activities towards R&D & AI services and long-term innovation partnerships.
This article explores both the technical and commercial aspects of the solution published in June, with an emphasis on its business implications (mostly introduction & conclusion). The latter is particularly relevant considering the recent news about this partnership. It also serves as a reminder from Google that open source does not equate to unrestricted and cost-free access, their open R&D efforts are integral to a global strategic and development of their AI & Business services. This also applies to other GAFAMs as recent LLMs breakthrough led to various major partnerships.
At Sia Partners AI&Data Business Unit, we have been working on Maritime Network design for a few years now and the publication from Google OR caught our attention. As we keep a close eye on Google OR Tools’ publications and use cases, this one looked particularly promising in how it tackled this complex problem (still subject to active academic research). This article aims at presenting the algorithmic method, its innovative and powerful aspects, as well as its limitations (for the opensource and free version at least). What our analysis shows is that without a major partnership (like the one CMA CGM just announced) this type of tool is useless for major see freight actors.
We first define the problem (Part I) before examining the method developed by Google to solve the problem (Part II). Then we will present some KPIs on an instance we tested with their algorithm to see how effective it is (Part III). Finally, we will share our opinion on the reality of this tool (Part IV) and what it means in terms of Google’s commercial strategy.
I. The problem
The mathematical problem is also known as the Liner Shipping Network Design and Scheduling Problem. It can be broken down into 3 interdependent sub-problems:
- Determining the order in which the vessels visit the ports (network design)
- Planning when each vessel arrives at and leaves the ports (network scheduling)
- Determining the path of each container from origin to destination (container routing). Transshipment (when a container spends time at an intermediate port on its way from origin to destination) is also part of the modelling.
These problems are usually solved independently or in pairs. The approach adopted by Google addresses the issue by considering the three elements collectively. Through the use of multiple itineraries between ports, ships can vary their speed and fuel consumption accordingly. Setting transit times in each port is also possible with their tool.
II. Google OR Team approach
The Google OR Team provides several open-source tools useful in Operational Research. Emerging actors in the OR community, the team first developed solvers for constraints programming and linear programming to solve classical problems and provide basic tools for optimization problems. Now, instead of just providing classical solvers, Google OR also provides built-in algorithms to solve complex real-world industrial problems that cannot be solved with generic methods. Google developed non exact methods, called heuristic to quickly provide good solutions for specific problems, such as the Vehicle Routing Problem (on very large public transportation networks) or Capacity Planning Problem.
The modelling used in this approach can be defined through by three followings aspects:
A known method for solving this type of model is Column Generation. Column Generation is like starting with a few decision variables to solve a big problem, then gradually adding more helpful variables based on intermediate results until you find the best solution.
Google Team first developed 2 exact methods for the problem:
- Double column generation: Double column generation involves solving two related problems simultaneously: finding routes for the ships and paths for the containers, each with its own decision variables but connected (containers need vessels to travel from ports to ports).
Figure 2 presents the methodology, starting to solve the problem with initial sets of routes and paths (1). At the end of each resolution (2), new promising routes (3.a) and paths (3.b) are generated using the intermediate results of the other problem. Routes and paths are added to the problem to improve the objectives (4). The algorithm iterates (1) until no more routes or paths can be found that improve the objectives.
2. CP-SAT (Constraint Programming — Satisfiability): CP-SAT solver uses constraint programming to define and narrow down the problem space, while employing SAT-solving techniques to quickly find solutions within that space.
Both approaches struggle with real life scale situations (>50 ports & >100 vessels). Indeed, the column generation method must generate many routes, which is costly and may take time to converge to the optimal solution. In a different way, the Constraint Programming method suffers from the large number of solutions and struggles to find the best ones in a reasonable time. Therefore, OR Tools developed a local search approach combining:
- A Large Neighborhood Search. A part of the solution (ship A must be at port B at time T) is fixed before using an exact method, thus reducing the size of the problem. (figure 3)
- Variable Neighborhood Search¹, where the solution can be modified over both the network and schedule (parallelized exploration).
Their local search allows to tackle problems up to 500 vessels, 197 ports, and more than 138,000 containers and prove to be very efficient in comparison to the scientific literature. The LNS allows to intensify the search of solutions near the current solution while the VNS aims at diversifying the search by exploring far away the current solutions. These two methods are known to perform well in routing problems. Combining these two methods brings a good tradeoff between intensification and diversification while keeping computation time under control. The use of column generation provides a relative guarantee of the optimality of the solutions found in the explored neighborhoods.
We tested their algorithm on benchmark instances and saw that their API was easy to use on the literature instances. What we first observed is that as for any problem on real-life instances, costs and profits definitions are critical and must be as realistic as possible to generate meaningful solutions.
Fortunately, their API considers different types of costs and profits (consumption costs, canal usage costs, port tolls, individual container profits…). Small works might be needed to adapt real company data to the format used by OR Tool and to be sure to use their algorithm with all the capacity it provides.
Unfortunately, this tool cannot be used directly to deal with delays and disruptions, ships that must leave a particular port, crew scheduling or business constraints imposed by a ship owner.
III. Useful KPIs on the problem
To evaluate the performance of this new tool, we used the EuropeAsia instance of the opensource LINERLIB library (website), which contains 111 ports, 76 944 containers and 176 vessels. In our case, we have not included any charges for using the canals (Suez for the case of EuropeAsia). We tried several resolution times and report the results in Table 1 with 5 indicators: the number of vessels used, the number of containers shipped, the number of ports visited per vessel (min, mean, max), the number of nautical miles per vessel (min, mean, max) and the percentage of loading per vessel (min, mean, max).
As expected, the results improve as the solving time increases (from 26 315 containers shipped with 20s solving time to 49 749 containers with 500s solving time), this is due to the heuristic scheme used, finding better solutions gradually. For information, this API allows to use a maximum of 500s for the solution time with 200 ports and 10,000 requests.
If we look at the other indicators, we can see that there is quite a gap between the minimum and maximum values and that this gap tends to increase with the resolution time.
Looking at the fill rate, which is quite low for some vessels, one might get the impression that the solution could never be used in practice by a shipowner who wants to achieve a fill rate close to 100% for each vessel. In practice, if the fill rate is not satisfactory, the voyage is cancelled: the containers are cut and rolled onto the next voyage or another service line with similar port calls.
By nature, demand is asymmetrical as in our studied model, Asia exports a lot more than Europe. This is considered in the demand model and correctly reflected by the difference in freight rates between eastbound voyages (Europe-Asia) and westbound voyages (Asia-Europe). For a shipping line to work properly, carriers are incentivized to aim for a 100% fill rate on their strong leg voyages and can use the weak legs to reposition empty containers. Since empty containers are not considered in the model, a 100% fill rate would be achievable only with a perfectly symmetrical demand, which would be unrealistic. Moreover, carriers would tolerate lower fill rates for voyages with lower freight rates, and always aim for 100% fill rate on the highest freight rates voyages.
This brings us to another limitation of the Google algorithm: Inventory management. In fact, a shipowner may want to always keep containers in a port in order to fill each ship to maximum capacity while keeping the stock price relatively low. Considering a rolling demand in this case will lead to more industrial solutions by considering the temporal arrival rate of containers in each port.
The solution provided by Google allows the ship’s capacity to be expressed in containers (TEU, FEU), which remains accurate in most cases. However, if containers do not have the same weight, adding a capacity in kilograms will lead to more acceptable solutions for the business teams. The hypotheses do not include the weight of the containers: reaching maximum capacity by weight means not reaching maximum capacity by TEU, and therefore less profit. In real-life cases, the ship planner is mainly constrained by weight.
Additionally, containers are considered standard, we have not seen any mention of dangerous goods (explosive, corrosive, …), refrigerated cargos, out-of-gauge, etc… Constraints could easily be added to model of this caliber if it was not a black box behind an API.
IV. Concluding on Google OR’s opensource model reality and what it unveils about Google’s research and business strategy
Google OR’s new Maritime network design APIs come in handy and can be used to quickly generate solutions with ship service networks and commodity demand paths. However, their modelling suffers from the generality they are aiming for and does not integrate certain constraints or specifications that are critical for any shipowner — On purpose… or not.
Therefore, adaptation is required to use their APIs in order to have well-fitting and usable solutions. Here the adaptations could only be made by Google’s team, who are the only ones who can modify the source code, it obviously comes as a service and at a cost. It’s a well-known and efficient commercial strategy: Freemium.
Developing an algorithm that considers more industrial constraints, such as the minimum filling rate, container weights, container types, empty repositioning, inventory management or workload, will require time and resources for users as well as Google’s development and consulting services. This open-source model cannot be considered as a serious alternative for operational network management and design. Using Google’s off-the-shelf solution will help small and medium businesses make strategic decisions on network adaptations but won’t produce complete and fully integrated solutions without further improvements and industrial insights. The lack of business specificities and the restrained API call sizes limit Google’s solution scope. For a Shipowner, having access to a complete decision-support tool, based on accurate business constraints and therefore including the company’s specific features, still requires the development of a tailor-made solution. Whether these limits are on purpose or not, Google has demonstrated to the maritime industry its ability to deal with such advanced OR models (it wasn’t as obvious as it currently is in Machine & Deep Learning) and just lacks the business knowledge to convert it into a powerful decision-support tool.
When we wrote those lines, we didn’t expect CMA CGM to announce so quickly a partnership with Google for the integration of AI-powered tools across all its activities. This is major news that confirms the change in the AI-services landscape. However, AI is incomplete without a blend of data and business knowledge. While the technical expertise of Google’s teams is beyond question, the primary challenge will be in designing user-oriented solutions that closely align with operational business considerations. This will surely be the main challenge of CMA CGM and Google teams collaboration in the coming years.
APPENDIX — If you also want to play with Google API
You will find here a description of the addressed problem by Google, focusing on the reasons they develop their method. The benchmark is presented here and the instances can be found on this webpage. The API is available on the OR Tools website with a use case and code examples. The API is limited to 500s of computing time and is not allowed to target too big problems. We precise below the inputs needed and output provided by the APIs.
By providing our inputs:
- Ports (with restrictions and costs specific to ship class)
- Ship classes (capacity and fleet size)
- Possible connections between ports for a given duration and vessel class compatibility
- Requests between ports (with optional freight rates and transit time restrictions)
- Existing vessel services
We get our solution:
- Ship services network
- Commodity Demand Paths
Alexandre Orhan Jean Jodeau, Martin Lanchon, Thibaut Dion, Guilhem Catinon
¹Variable Neighborhood Search (VNS) is an optimization method that systematically changes the search area to escape local optima and find the global optimum by exploring progressively larger neighborhoods.
