A Genetic Algorithm for Ship Routing and Scheduling Problem with Time Window
Affiliation(s)
College of Technological Studies, Public Authority for Applied Education and Training-Kuwait. College of Basic Education, Public Authority for Applied Education and Training-Kuwait.
College of Technological Studies, Public Authority for Applied Education and Training-Kuwait. College of Basic Education, Public Authority for Applied Education and Training-Kuwait.
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.
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.
Cite this paper
K. Al-Hamad, M. Al-Ibrahim and E. Al-Enezy, "A Genetic Algorithm for Ship Routing and Scheduling Problem with Time Window," American Journal of Operations Research, Vol. 2 No. 3, 2012, pp. 417-429. doi: 10.4236/ajor.2012.23050.
K. Al-Hamad, M. Al-Ibrahim and E. Al-Enezy, "A Genetic Algorithm for Ship Routing and Scheduling Problem with Time Window," American Journal of Operations Research, Vol. 2 No. 3, 2012, pp. 417-429. doi: 10.4236/ajor.2012.23050.
References
[1] U. Nation, “Review of Maritime Transportation,” United Nations Conference on Trade and Development (UNCTAD), 2011. [2] M. Christiansen, K. Fagerholt, B. Nygreen and D. Ronen, “Maritime Transportation,” In: C. Barnhart and G. Laporte, Eds., Transportation. Handbooks in Operations Research and Management Science, Vol. 14, 2007, pp. 189-284. doi:10.1016/S0927-0507(06)14004-9 [3] M. Christiansen, K. Fagerholt and D. Ronen, “Ship Routing and Scheduling: Status and Perspectives,” Transportation Science, Vol. 38, No. 1, 2004, pp. 1-18. doi:10.1287/trsc.1030.0036 [4] S. A. Lawrence, “International Sea Transport: The Years Ahead,” Lexington Books, Lexington, 1972. [5] M. Christiansen, K. Fagerholt, T. Flatberg, O. Haugen, O. Kloster and E. Lund, “Maritime Inventory Routing with Multiple Products: A Case Study from the Cement Industry,” European Journal of Operational Research, Vol. 208, 2011, pp. 86-94. doi:10.1016/j.ejor.2010.08.023 [6] D. Ronen, “Marine Inventory Routing: Shipments Planning,” Journal of the Operational Research Society, Vol. 53, 2002, pp. 108-114. doi:10.1057/palgrave/jors/2601264 [7] H. D. Sherali, S. M. Al-Yakoob and M. M. Hassan, “Fleet Management Models and Algorithms for an Oil Tanker Routing and Scheduling Problem,” IIE Transactions, Vol. 31, 1999, pp. 395-406. doi:10.1080/07408179908969843 [8] K. Al-Hamad, “Tabu Search Algorithm for Ship Routing and Scheduling Problem with Time Window,” Ph.D. Thesis, Brunel University, 2006. [9] A. Mehrez, M. S. Hung and B. H. Ahn, “An Industrial Ocean-Cargo Shipping Problem,” Decision Sciences, Vol. 26, No. 3, 1995, pp. 395-423. doi:10.1111/j.1540-5915.1995.tb01434.x [10] G. G. Brown, G. W. Graves and D. Ronen, “Scheduling Ocean Transportation of Crude Oil,” Management Science, Vol. 33, No. 3, 1987, pp. 335-346. doi:10.1287/mnsc.33.3.335 [11] D. O. Bausch, G. G. Brown and D. Ronen, “Elastic Set Partitioning: A Powerful Tool for Scheduling Transportation of Oil and Gas,” In: M. Breton and G. Zaccour, Eds., Advanced in Operations research in the Oil and Gas Industry, Editions Technship, Paris, 1991, pp. 151-162. [12] S. Liu, W. Huang and H. Ma, “An Effective Genetic Algorithm for the Fleet Size and Mix Vehicle Routing Problem,” Transportation Research, Part E, Vol. 45, 2008, pp. 434-445. doi:10.1016/j.tre.2008.10.003 [13] J. Holland, “Adaption in Natural and Artificial Systems,” University of Michigan, Ann Arbor, 1992
[1] U. Nation, “Review of Maritime Transportation,” United Nations Conference on Trade and Development (UNCTAD), 2011. [2] M. Christiansen, K. Fagerholt, B. Nygreen and D. Ronen, “Maritime Transportation,” In: C. Barnhart and G. Laporte, Eds., Transportation. Handbooks in Operations Research and Management Science, Vol. 14, 2007, pp. 189-284. doi:10.1016/S0927-0507(06)14004-9 [3] M. Christiansen, K. Fagerholt and D. Ronen, “Ship Routing and Scheduling: Status and Perspectives,” Transportation Science, Vol. 38, No. 1, 2004, pp. 1-18. doi:10.1287/trsc.1030.0036 [4] S. A. Lawrence, “International Sea Transport: The Years Ahead,” Lexington Books, Lexington, 1972. [5] M. Christiansen, K. Fagerholt, T. Flatberg, O. Haugen, O. Kloster and E. Lund, “Maritime Inventory Routing with Multiple Products: A Case Study from the Cement Industry,” European Journal of Operational Research, Vol. 208, 2011, pp. 86-94. doi:10.1016/j.ejor.2010.08.023 [6] D. Ronen, “Marine Inventory Routing: Shipments Planning,” Journal of the Operational Research Society, Vol. 53, 2002, pp. 108-114. doi:10.1057/palgrave/jors/2601264 [7] H. D. Sherali, S. M. Al-Yakoob and M. M. Hassan, “Fleet Management Models and Algorithms for an Oil Tanker Routing and Scheduling Problem,” IIE Transactions, Vol. 31, 1999, pp. 395-406. doi:10.1080/07408179908969843 [8] K. Al-Hamad, “Tabu Search Algorithm for Ship Routing and Scheduling Problem with Time Window,” Ph.D. Thesis, Brunel University, 2006. [9] A. Mehrez, M. S. Hung and B. H. Ahn, “An Industrial Ocean-Cargo Shipping Problem,” Decision Sciences, Vol. 26, No. 3, 1995, pp. 395-423. doi:10.1111/j.1540-5915.1995.tb01434.x [10] G. G. Brown, G. W. Graves and D. Ronen, “Scheduling Ocean Transportation of Crude Oil,” Management Science, Vol. 33, No. 3, 1987, pp. 335-346. doi:10.1287/mnsc.33.3.335 [11] D. O. Bausch, G. G. Brown and D. Ronen, “Elastic Set Partitioning: A Powerful Tool for Scheduling Transportation of Oil and Gas,” In: M. Breton and G. Zaccour, Eds., Advanced in Operations research in the Oil and Gas Industry, Editions Technship, Paris, 1991, pp. 151-162. [12] S. Liu, W. Huang and H. Ma, “An Effective Genetic Algorithm for the Fleet Size and Mix Vehicle Routing Problem,” Transportation Research, Part E, Vol. 45, 2008, pp. 434-445. doi:10.1016/j.tre.2008.10.003 [13] J. Holland, “Adaption in Natural and Artificial Systems,” University of Michigan, Ann Arbor, 1992