1,637
Views
1
CrossRef citations to date
0
Altmetric
Research Article

Metaheuristic algorithm for ship routing and scheduling problems with time window

, & | (Reviewing editor)
Article: 1616351 | Received 13 Jul 2018, Accepted 28 Apr 2019, Published online: 19 May 2019
 

Abstract

This paper describes a Tabu Search (TS) heuristic for a Ship Routing and Scheduling Problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous ships. Constraints include delivery time windows imposed by customers, the time horizon by which all deliveries must be made, and ship capacities. The proposed algorithm aims to minimize the overall cost of shipping operation without any violations. The TS algorithm is compared with a similar method that uses the Set Partitioning Problem (SPP) in terms of solution quality and computational time. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the TS such neighborhood size. It is found that while the SPP method solves small-scale problems efficiently, treating large-scale problems with this method becomes complicated due to computational problems; however, the TS method can overcome this challenge. Furthermore, TS consistently returns near-optimal solution within a reasonable time.

PUBLIC INTEREST STATEMENT

This paper talks about the problem of scheduling the movement of vessels overseas to deliver goods of specific types (such as crude oil or coal) to customers, in the time required by the customer. On the other hand, to reduce the expenses of the movement of the fleet to the lowest possible. These expenses include fuel costs (bunker consumption), operation costs, and port dues. A mathematical algorithm tool called Tabu Search (TS) was presented to create a schedule for a fleet of vessels that could deliver goods to customers in a timely and cost-effective manner.

Additional information

Funding

This work was supported by the Khaled Moh Alhamad.

Notes on contributors

Khaled Alhamad

Khaled Alhamad is currently an associate professor, PhD and Head of Laboratory Technology Department, College of Technological Studies, Kuwait. His research interests include optimization, integer programming, heuristic method, scheduling, transportation.