An exact algorithm for the single liner service design problem with speed optimisation

ABSTRACT

This paper models a single liner service design and operations problem. The model selects the ports to be included, their sequence, the sailing speed of vessels, the number of vessels and the amounts of cargo to transport by the service. The objective is to maximise profit. First, a relaxation with a mixed-integer nonlinear programming (MINLP) formulation is proposed. We show how to obtain the optimal speed value. Once this value is obtained, the mathematical programming formulation becomes a mixed-integer linear program (MILP). Then, a two-step exact algorithm is presented to solve the problem. Using real data, the optimal solution was found in less than 1 min for small-size problems and in few hours for relatively large-size problems. More tests were carried out on randomly generated data sets with up to 25 ports. The results of these tests are rather promising, and they enabled us to identify the performance limits of the algorithm.

Keywords:

• Liner shipping
• vessel routing
• sailing speed optimisation
• integer programming
• exact algorithm

Acknowledgments

The authors are grateful to the referees and the associate editor for their constructive comments. The authors also acknowledge the financial support of their corresponding institutions for the implementation of this project.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

Nadjib Brahimi

Nadjib Brahimi is Associate Professor at the department of Supply Chain Management and IS at Rennes School of Business. He received his PhD in Logistics and Production Systems from the University of Nantes and IMT Atlantique (ex-Ecole des Mines de Nantes). His research interests include optimisation and simulation in production planning, scheduling, and transport.

Ali Cheaitou

Ali Cheaitou is Associate Professor and Chairman of the Industrial Engineering and Engineering Management Department, University of Sharjah. He earned his PhD in Industrial Engineering from Ecole Centrale Paris (Paris Saclay University). His main research interests are in production planning and inventory control, supply chain management, and maritime transportation.

Pierre Cariou

Pierre Cariou is currently working as Senior Professor in Shipping and Port Economics at the Department of Operation Management of KEDGE Business School. He received is PhD from the Faculty of Economics and Business Administration of University of Nantes. His research interests are on Maritime Economics & Strategy and Marine Safety & Environmental Protection.

Dominique Feillet

Dominique Feillet works as a Professor of Operations Research at Mines Saint-Etienne. He received an engineering degree in Computer Sciences from ENSIMAG (Grenoble, France) and holds a PhD in Industrial Engineering from Ecole Centrale de Paris (France). He joined Mines Saint-Etienne in 2008, where he is the head of the Center of Microelectronics of Provence since 2020. His primary research interest concerns the development of relevant discrete optimisation models and methods with regards to new practices in transportation and distribution.