Support for Long-Haul Oil Transportation Vessel Scheduling at Petrobras

Long-haul oil transportation is a multi-million dollar operation for large oil companies such as Petrobras. The difference between a reasonable and a good transportation schedule may involve millions of dollars in cost savings. To properly schedule each shipment, planners must find a match between cargos, vessels, and destinations.

Petrobras is one of the players in the spot market of chartering and renting out long-haul oil transportation vessels. How do they manage to combine the computational aspect of searching through the vast space of possible schedules and the human aspect of operating on the spot market of chartering and renting out vessels?

This blog post offers an insider’s look into the AIMMS-based decision support system (DSS) that is currently being used by Petrobras to tackle this ship scheduling challenge.

The process behind the DSS development

A few years back, Gustavo Diz, a member of the Petrobras scheduling team, took the initiative to analyze the company’s process for schedule creation. His analysis included an extensive literature review and interviews with other members of this team. He realized that there were two important aspects to the scheduling process, a computational aspect and a human aspect.

• The computational aspect: by generating alternative schedules automatically, many more of these alternatives could be explored. This ability to explore alternative scenarios becomes even more important as the company grows, given that the number of potential schedules grows exponentially with it.
• The human aspect: being a member of the scheduling team, Gustavo was also acutely aware that automatically produced schedules are only proposals to be refined or rejected by the scheduling team. Part of this human aspect is that some constraints on schedules cannot be formalized using mathematical notation. More important, however, is that this enables the comparison of various scenarios. Consider the following two scenarios. In the first scenario, all vessels owned by Petrobras are available for scheduling, and in the second scenario, one vessel is rented out. By comparing the schedules generated from these two scenarios, it can be easily checked whether or not the rent obtained by renting out that vessel outweighs the cost increase resulting from having fewer vessels available for scheduling.

What functionality is needed in a DSS to properly support both aspects?

1. The ability to compute alternatives,
2. The ability to play with data,
3. The ability to turn constraints on and off, and
4. The possibility to compare computed alternatives.

In short, the scheduling team needs support to answer the following question: taking cargos, vessels, destinations, deals, and forbidden combinations into account what is a good or even best possible schedule? By taking the initiative to develop the DSS as a support tool by Gustavo as a team member, the advantage of expert knowledge of the schedulers is retained. This expert knowledge is essential to evaluate a given proposal and further refine it after acceptance.

Understanding the computational aspect

Constructing a schedule consists of 4 steps:

• Constructing routes, taking into account time windows for cargos.
• Matching vessels to those routes.  These vessels are either owned or chartered.
• Compute for each allowed route, vessel combination their associated costs.
• Solving an optimization problem to minimize total costs.

The optimization problem ensures that the complete schedule will:

• Transport all cargos,
• Respect physical limitations (for instance, the fact that a single vessel cannot be used twice on the same day)

The costs taken into account include:

• Transportation costs
• Renting costs of chartered vessels
• Idle capacity costs of owned vessels

Understanding the human aspect

The human aspect is best illustrated with an example.

Consider the renting out of a vessel that is also scheduled. Does the revenue obtained by renting out that vessel outweigh the cost increase due to the use of other vessel(s) necessary to transport all the cargos?

The DSS can generate an alternative within seconds and compare it to the original schedule. This makes the decision to accept or reject the renting of a vessel much easier.  The DSS application consists of two parts, the part that contains the model and the interactive part. For the actual model, it turned out that the formal mathematical formulation of the model was easily transcribed into the AIMMS language. This includes all the necessary steps and the optimization problem described in the computational section above. Typically, the creation of a new schedule is done within a couple of seconds.

To solve the actual optimization problem, both CPLEX and GUROBI can be used. For the interactive part, AIMMS was used to create a set of pages consisting of tables, charts, and selection objects. Pages containing such objects make it easy to browse through the available data and even adapt it along the way. Not only are these objects user-friendly to use, but they are also easily created. The creation of such an object (table, chart, selection object) is merely a matter of selecting an object type, an area on the page, and the identifier to be visualized. Each of these three actions is achieved by merely pointing and clicking.

The Results

Petrobras calculated that the potential economic benefits of this scheduling solution were approximately $140 million from 2013 to 2016. A 3-month test period alone saved the company 7.5% during the transport of 70 crude oil cargos, which was equivalent to $10 million. In other words, they gain the investment in the development of the DSS more than one hundred times over every year! The company has also seen efficiency gains during scheduling as it transitioned from a primarily manual process to an optimization platform.  

References

This blog post is primarily based on the article “Decision Support System for Petrobras Ship Scheduling” by Gustavo Diz, Luiz Felipe Scavarda, Roger Rocha, and Silvio Hamacher, Interfaces, May 2014.

In addition, there were several private e-mails between the author and Gustavo Diz about the DSS and its development. If you want to know more about explaining optimization as a support tool to planners, read our blog – How to explain optimization to a planner.