(373ap) A New Miqcp Continuous-Time Formulation for a Class of Maritime Inventory Routing Problems

To meet the target of reducing carbon intensity by 40%, shipowners are required to collect data for reporting their annual operational carbon intensity indicator and rating [1]. One of the things that can be done to improve the rating without switching to a low-carbon fuel, is by limiting voyage speed and implementing measures of routing optimization [2]. Speeds affect sailing costs and the profit of operating a fleet can be significantly improved when speeds on the different sailing legs are decision variables [3]. Increasing speed makes it possible to carry more cargo over a given time horizon, while reducing speed results in less fuel consumption per distance travelled. Typically, a quadratic function is assumed to relate fuel consumption and speed, leading to a mixed-integer quadratically constrained problem (MIQCP).

In this paper, we address the management of deep-sea floating production storage and offloading (FPSO) units, which process and store crude oil from nearby oil platforms while waiting for a shuttle tanker belonging to a heterogeneous fleet, to arrive and collect it. Crude oil production occurs at a constant rate throughout the time horizon. The goal is to achieve an environmentally friendly solution, which may require renting additional tankers to maintain production. The optimization will decide on the number and type of tankers to use, their route, involving a port refinery and one or more FPSO units, and travelling speed.

The novelty of the MIQCP formulation relates to the use of a continuous-time representation featuring a common grid for determining the duration of the coarse transportation tasks, and multiple time grids [4] to detail the timing of waiting, travelling, and loading/unloading tasks. The MIQCP formulation is built from a Generalized Disjunctive Program (GDP) [5,6] with nested decisions [7,8], by relying on a sharp convex hull reformulation [9-11]. Another important aspect is the use of reset variables to identify the arrival of a vessel to a node, which was first used in the context of product-centric formulations for scheduling the transportation of refined petroleum liquid products by pipeline [12,13].

Eight benchmark instances of varying size were generated based on data from [14,15] and the resulting MIQCPs were solved by commercial solvers GUROBI 10.0 and BARON 23.6. These are difficult instances in the sense that all but one cannot be solved to global optimality up to five hours of wall-clock time. GUROBI outperformed BARON by at least one order of magnitude, generating feasible solutions for 7 vs. 4 instances. The largest instance solved featured 9 source nodes, 8 tankers vessels and led to a problem with over 15,000 binary variables, 39,000 constraints and 400 nonlinear matrix elements. The optimal routes typically involved multiple voyages for some of the vessels (up to 3) that weren’t repetitions of the first.

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through project UIDB/04028/2020.

References:

[1] International Maritime Organization 2022. Rules on ship carbon intensity and rating system enter into force. https://www.imo.org/en/MediaCentre/PressBriefings/pages/CII-and-EEXI-entry-into-force.aspx. Accessed January 31, 2024.

[2] Fagerholt, K., Hvattum, L.M., Papageorgiou, D.J., Urrutia, S. 2023. Maritime inventory routing: recent trends and future directions. Intl. Trans. In Op. Res. 30, 3013-3056.

[3] Norstad, I., Fagerholt, K., Laporte, G. 2011. Tramp ship routing and scheduling with speed optimization. Transportation Research Part C: Emerging Technologies 19 (5), 853–865.

[4] Harjunkoski, I., Maravelias, C.T., Bongers, P., Castro, P.M., Engell, S., Grossmann, I.E., Hooker, J., Méndez, C., Sand, G., Wassick, J. (2014). Scope for industrial application of production scheduling models and solution methods. Comput. Chem. Eng. 62, 161-193.

[5] Balas, E. 1979. Disjunctive programming. Annals of Discrete Mathematics 5, 3-51.

[6] Raman, R., Grossmann, I. E. 1994. Modelling and computational techniques for logic based integer programming. Comput. Chem. Eng. 18 (7), 563–578.

[7] Vecchietti, A., Grossmann, I. E. 2000. Modeling issues and implementation of language for disjunctive programming. Comput. Chem. Eng. 24, 2143-2155.

[8] Perez, H. D., Grossmann, I.E. 2023. Extensions to generalized disjunctive programming: hierarchical structures and first-order logic. Optimization and Engineering. https://doi.org/10.1007/s11081-023-09831-x.

[9] Balas, E. 1985. Disjunctive programming and a hierarchy of relaxations for discrete optimization. SIAM J Algebraic Discrete Methods 6 (3), 466-486.

[10] Jeroslow, R.G., Lowe, J.K., 1984. Modelling with integer variables. Mathematical Programming Studies, 22. Amsterdam, North-Holland, pp. 167–184.

[11] Castro, P.M., Grossmann, I.E., 2012. Generalized disjunctive programming as a systematic modeling framework to derive scheduling formulations. Ind. Eng. Chem. Res. 51, 5781–5792.

[12] Castro, P.M. 2017. Optimal scheduling of multiproduct pipelines in networks with reversible flow. Ind. Eng. Chem. Res. 56, 9638-9656.

[13] Castro, P.M., Mostafaei, H. 2017. Product-centric continuous-time formulation for pipeline scheduling. Comput. Chem. Eng. 104, 283-295.

[14] Xin, X., Wang, X., Tian, X., Chen, Z., Chen, K. 2019. Green scheduling model of shuttle tanker fleet considering carbon tax and variable speed factor. Journal of Cleaner Production 234, 1134-1143.

[15] Li, H., Huang, W., Li, R., Yu, M., Tai, N., Zhou, S. 2023. The multi-visit-multi-voyage scheduling of the heterogeneous shuttle tanker fleet via inventory-oriented joint planning. Applied Energy 334, 120354.