Benchmark Problems for

J. Lee and B. Kim ¡°Industrial Ship Routing Problem with Split Delivery and Two Types of Vessels,¡± working paper, 2015

 

1.       Introduction

Lawrence (1972) classified ocean transportation types into three groups according to operation modes, namely, industrial, tramp, and liner. Industrial operation is a popular ocean transportation mode used to carry bulk products. Cargo owners operate a fleet of vessels in industrial shipping. All the given cargoes should be served, and the objective is to minimize operating cost. In tramp shipping, the objective is to maximize profit by selecting profitable cargoes for a given fleet of ships. Tramp ships deliver available cargoes from point to point, much like taxis. Tramp ships also carry spot cargoes, which are temporary customer requests of transportation. The cargoes should be directly delivered from pickup ports to delivery ports within specific times. Usually, a tramp ship transports a cargo for a single customer at a time. Liners follow a given itinerary and schedule similar to a bus line and usually transport cargoes for many customers.

This paper introduces an industrial SRP (ISRP) faced by a real-world steel manufacturing company that delivers raw materials from supply ports to steelworks. The subject company operates a fleet of company-chartered heterogeneous vessels. Each cargo has a specific quantity, type, time window, and supply (pickup) and demand (delivery) ports. The company planner generates the schedules of the fleet to pick up and deliver the given cargoes. Some cargoes may not be served by the fleet after a schedule made by the planner. Such cargoes are treated as spot cargoes and are served by tramp ships. More tramp ships in the schedule results in increased financial burden on the company because the delivery cost of tramp ships is more expensive than that of a company-chartered fleet. In addition, the cost of tramp ships is difficult to fix at the planning stage because a delivery plan is made 45 days before every quarter starts and the cost fluctuates frequently following the global economy. Thus, the planner attempts to utilize the company-owned fleet to serve cargoes as much as possible (i.e., minimize the use of tramp ships). Cargoes can be split and loaded by more than one ship if the time windows of the cargoes at pickup and delivery ports are not violated. The cargoes can also be picked up from multiple supply ports and delivered to multiple demand ports. In other words, split delivery and combining cargoes are allowed.

ISRP can be considered a variant of the pickup and delivery vehicle routing problem with split delivery (PDSL). Compared with PDSL that considers VRP with split loads, the proposed ISRP has additional considerations, namely, two types of vessels are used to deliver cargoes and mixed loading is allowed. This paper presents a mathematical model for the problem. For a solution procedure, an adaptive large neighborhood search (ALNS) heuristic is developed. Computational results on thirty benchmark problem instances show the effectiveness of the proposed solution.

 

 

2.       Benchmark Problems

To the best of our knowledge, no available benchmark data for ISRP exist. Thus, 30 benchmark instances were developed based on practical data used in the subject company. Three data sets were created to reflect the practical data. Each data set, which contains 10 benchmark instances, was distinguished according to the number of vessels and cargoes. The first set has five vessels and 10 cargoes; the second set has 10 vessels and 50 cargoes; and the third set has 20 vessels and 100 cargoes. Table 1 shows the summary of the data sets.

The cargoes and vessels of the benchmark problems were generated using real-world data. The steel company provided a list of cargoes for this paper. A total of 10 cargoes were randomly selected from the list for each problem instance of data set 1, 50 for data set 2, and 100 for data set 3. All cargo amounts were scaled down because of the confidentiality of the original data. In a similar way, the vessels of the benchmark problem instances were generated, and the vessel capacities were scaled down. Each vessel has ID, load_spd, emp_spd, capa, and unit_cost. ID denotes the identification number of the vessel. load_spd and emp_spd denote the speed of vessel when it has cargoes on or not, respectively. capa and unit cost denote the capacity of the vessel and the travel cost of the vessel per an hour. The generated cargo weight ranged between 30 and 270 tons for each cargo. About 100 cargoes are handled within a single quarter in practice. The time windows of the cargoes and the position of ports were generated based on real-world data. The distance between ports ranges from 1 mile to 20,167 miles in practical data.

 

Table 1. Benchmark data summary

Data set

No. of vessels

No. of cargoes

1

5

10

2

10

50

3

20

100

 

 

The 30 benchmark data sets can be downloaded by click here.

Required data can be calculated or retrieved as follows:

ž   Travel time (days) from port i to port j by vessel k (Tijk) = Euclidean distance between the coordinates of the ports/(24¡¿the speed of the vessel).

ž   Travel cost from port i to port j by vessel k (Cijk) = (24¡¿Tijk¡¿unit_cost) + port fee of j

ž   The total amount of cargo at port i (Li) = Amt_load

ž   Anchoring time at port i (Si) = anchoring_days

ž   Maximum loading capacity of vessel k (Hk) = capa

ž   Early and late time windows of cargo i at the pickup port(Ei, Fi) = (e_pick, f_pick)

ž   Early and late time windows of cargo i at the delivery port(Ei, Fi) = (e_del, f_del)

ž   Reference cost of tramp ships for the cargo i (Ri) = 10000.0