Industrial ship routing problem with split delivery and two types of vessels

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. (C) 2015 Elsevier Ltd. All rights reserved.