Industrial ship routing problem with split delivery and two types of vessels. Issue 22 (1st December 2015)

• Record Type: Journal Article
• Authors: Lee, Jongsung; Kim, Byung-In
• Is Part Of: Expert systems with applications. Volume 42:Issue 22(2015)
• Page Start: 9012
• Page End: 9023
• Publication Date: 2015-12-01
• Subjects: Routing -- Large neighborhood search -- Split delivery -- Ship routing -- Industrial ship routing; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2015.07.059
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A maritime pickup and delivery problem is studied. A mixed integer programming model is developed. An adaptive large neighborhood search based heuristic is proposed. Thirty benchmark problem instances are developed. Computational results show the effectiveness of the proposed algorithm. Abstract: This paper introduces an industrial ship routing problem (ISRP) of a steel manufacturing company. Given a set of cargoes with pickup, delivery ports, and time windows, the problem determines how to route a fleet of heterogeneous ships to carry the cargoes. The cargoes can be split to be served by multiple ships if their time window is not violated. In addition, a ship can handle multiple cargoes within a route. The fleet of heterogeneous ships consists of two types of ships: company-owned ships and tramp ships. Each of both types consists of heterogeneous ships with different capacities. A company-owned ship can deliver cargoes from multiple supply ports to multiple delivery ports within a route, whereas a tramp ship can deliver a cargo directly from a supply port to a delivery port within a route. To reduce operation cost, the two types of the ships should be well coordinated and utilized. A mixed integer programming model for the problem is presented, and an adaptive large neighborhood search-based heuristic is proposed. Thirty benchmark problems are generated and categorized into three groups according to the number of vessels and cargoes. Computational experiments demonstrate the effectiveness of the proposed algorithm.