A Genetic Algorithm for Ship Routing and Scheduling Problem with Time Window

• 作者: Eiman Al-Enezy Khaled Al-Hamad Mohamed Al-Ibrahim
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 医学
• 关键词: GENETIC ALGORITHM TRANSPORTATION SPP SRSP
• 年，卷（期）: mgycxqkyw_2012,（3）
• 页码范围: 417-429
• 页数: 13页
• 分类号: R73

摘要

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.