Probabilistic tabu search algorithm for container liner shipping problem with speed optimisation

Abstract

This paper considers a container liner shipping problem with speed optimisation (CLSP-SO) to minimise the total costs of the fleet, which includes operating costs, capital costs and voyage costs. A mixed-integer nonlinear programming model is first formulated to illustrate the problem, in which the oil consumption of ships is treated as a cubic function of speeds. Then, the computational complexity of the problem is analysed and a lower bound is given based on the theoretical optimised speed of ships. To solve the problem, a probabilistic tabu search (PTS)-based algorithm is developed considering the NP-hardness of the problem. Extensive computational experiments on randomly generated data and a real-world case are conducted and the performance of the proposed method is compared with the lower bound and that of the basic tabu search (TS) algorithm. The results show that the proposed PTS-based algorithm obtains satisfactory solutions with respect to lower bounds in reasonable computation time and it outperforms the basic TS-based algorithm.

Keywords:

• Container liner shipping
• speed optimisation
• probabilistic tabu search
• generalised assignment problem
• mixed-integer nonlinear programming model

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China (NSFC) under grants 71571135 and 71971155. The work was also supported by the Fundamental Research Funds for the Central Universities.

Notes on contributors

Shijin Wang

Shijin Wang received the B.Eng. degree from the Department of Industrial Engineering, Zhejiang University of Technology, Zhejiang, China, in 2002; and the Ph.D. degree from the Department of Industrial Engineering and Management, Shanghai Jiaotong University, Shanghai, China, 2009. From 2009-Present, he worked as Associate Professor at the Department of Management Science and Engineering, School of Economics and Management, Tongji University, Shanghai, China. His current research interests include combinatorial optimisation, production scheduling, artificial intelligence-based algorithms, and supply chain optimisation.

Qianyang Zhao

Qianyang Zhao received the B.Eng. degree from the School of Civil Engineering, Hunan University, China, in 2018. He is currently working as a Master Student at the School of Economics and Management, Tongji University and his major research interests include heuristic algorithms related to logistics and transportation.