Deakin University
Browse

Branch-And-Price Algorithm for the Tramp Ship Routing and Scheduling Problem Considering Ship Speed and Payload

Version 2 2024-06-05, 05:35
Version 1 2023-02-08, 22:11
journal contribution
posted on 2024-06-05, 05:35 authored by L Li, B Ji, Samson YuSamson Yu, S Zhou, X Fang
In recent years, increasing fuel prices, depressed market conditions and air pollution issues have brought huge challenges to the tramp shipping industry. This work investigates the tramp ship routing and scheduling problem considering ship speeds and payloads, aiming at minimizing ship fuel consumption. A mixed integer non-linear programming model with a discretized speed variable and a set partitioning model for this problem is established, and a branch-and-price algorithm is proposed to solve the problem. Through the column generation approach, the problem at each branch-and-bound node is decomposed into a linear programming master problem and a pricing problem of the elementary shortest path with resource constraints. A labeling algorithm is adopted for solving the pricing problem. Multiple groups of instances are generated to test the effectiveness of the proposed model and algorithm and analyze the impacts of ship speed, payload, and speed discretization on the solution. Computational experiments are conducted, which verifies the proposed scheduling routing method for tramp ships and confirms that adopting the proposed model can effectively reduce fuel consumption of tramp ships which can not only deepen the theory of tramp routing and scheduling, but also provide theoretical guidance to tramp ship company. The branch-and-price algorithm can effectively solve large-scale tramp ship routing and scheduling problems. Reasonable number of speed discretization points can bring a desirable trade-off between solution accuracy and algorithm runtime.

History

Journal

Journal of Marine Science and Engineering

Volume

10

Article number

ARTN 1811

Pagination

1811-1811

eISSN

2077-1312

Language

English

Publication classification

C1 Refereed article in a scholarly journal

Issue

12

Publisher

MDPI