TITLE:
A Genetic Algorithm for Ship Routing and Scheduling Problem with Time Window
AUTHORS:
Khaled Al-Hamad, Mohamed Al-Ibrahim, Eiman Al-Enezy
KEYWORDS:
Genetic Algorithm; Transportation; SPP; SRSP
JOURNAL NAME:
American Journal of Operations Research,
Vol.2 No.3,
September
19,
2012
ABSTRACT: This paper develops an efficient variant of a Genetic Algorithm (GA) for a ship routing and scheduling problem (SRSP) with time-window in industrial shipping operation mode. This method addresses the problem of loading shipments for many customers using heterogeneous ships. Constraints relate to delivery time windows imposed by customers, the time horizon by which all deliveries must be made and ship capacities. The results of a computational investigation are presented and the solution quality and execution time are explored with respect to problem size. The proposed algorithm is compared, in terms of solution quality and computational time, with an exact method that uses Set Partitioning Problem (SPP). It is found that while the exact method solves small scale problem efficiently, treating large scale problems with the exact method becomes involved due to computational problem, a deficiency that the GA can encounter. Meantime, GA consistently returns better solution than other published work using Tabu Search method in term of solution quality.