Printer Friendly

Ship Scheduling in the Tramp Spot Market Based on Shipper's Choice Behavior and the Spatial and Temporal Shipping Demand.


In the tramp spot shipping market, the choice of a shipper and the spatial and temporal shipping demand affect decisions regarding task choices and ship routing of the carrier. From the perspective of a carrier, this article divides the entire shipping planning horizon into a series of time windows and converts the carriers' market shares into shippers' choice inertia. Based on the spatial and temporal shipping demand, the obtained market shares in different time windows are analyzed, and the ship scheduling schemes, including the amount of shipped cargos, the sailing routes and the ships used, are determined with the objective of maximizing the carrier's profits. Finally, a numerical test is conducted using the Pacific tramp shipping market as an example.



Tramp spot shipping, shipper's choice inertia, shipping demand, ship scheduling

Ship scheduling in the tramp shipping market includes decisions pertaining to sailing routes, transport tasks, and times for each ship. Shipping dry-bulk cargo comprises contracted shipments and spot shipments. Contracted shipments constitute the long-term, static demand, whereas spot shipments constitute the short-term, dynamic demand. In theory, a carrier always desires as much cargo as possible and arranges the ships to transport the cargo to maximize its earnings. The carriers and shippers are the supply and demand sides of the market, respectively. Both parties have the right to choose the other. For a spot shipment, the decision will certainly be concluded in a fully competitive market. In the market, the person (a supposed carrier here) holding vessels seeks to find cargos rather than shippers, whereas the person (maybe a shipper or forward) holding cargos attempts to find vessels rather than carriers. For any vessel/cargo in the market, there must be at least 5-10 reliable candidate cargos/vessels as potential counter parties. It is usually easy for a shipper to know the carriers through the vessels. However, it is hard for a carrier to know the shippers through their cargos. Because shippers have choice inertia when they purchase the service, the services offered by carriers will affect the choices of shippers.

With regard to ship scheduling, Appelgren (1971) proposed the Dantzig-Wolfe decomposition method to select the optimal cargo for each ship to maximize the carrier's benefits. The method has since been widely used. Xie (1992) and Xie, Li, and Ji (1989) solved the fleet deployment problem using the simplex method and studied the effects of certain factors on sailing cost using a sensitivity analysis. Yu (1997) built a linear programming model to solve the sailing schedule and ship assignment problems. He used the index method to obtain an approximate solution based on a matrix of transportation cost coefficients. Fagerholt (2003) found that nearly all shipping companies schedule their ships based on prior experience and designed a tramp shipping decision support system based on certain key experiences. He proved that the system designed based on the key experiences was considerably better than the programming model in terms of reflecting the interactions between the users and the system.

Jin and Zhao (2007) compared the ship scheduling problem with the traveling salesman problem (TSP) and used an ant colony algorithm to solve the scheduling model, representing an innovative algorithmic approach to the tramp scheduling problem. Su, Wang, and Wang (2007) proposed an updated particle swarm optimization (PSO) algorithm based on stochastic and fuzzy simulation to address the ship deployment problem with uncertain routes, and they solved the premature solution issue using constraint factors and chaos theory. Bronmo, Christiansen, and Nygreen (2007) and Bronmo, Nygreen, and Lysgaard (2010) used a multi-origin local search method for the tramp ship scheduling model; this method uses the shipments as the decision variable and solves the model using the Dantzig-Wolfe decomposition method. Korsvik, Fagerholt, and Laporte (2011) proposed a tramp ship scheduling model and used a large neighborhood search heuristic to solve a model of dispatching several ships from one port simultaneously. Ding et al. (2015) considered the uncertainty in sailing time and demand time windows to build a ship scheduling model with the objective of minimizing cost, which is a vehicle routing problem (VRP) and can be converted to a TSP by the scanning method. The model was solved by the tabu search algorithm.

Shipping demand for dry-bulk cargo exhibits temporal fluctuations and spatial imbalance. In the time domain, the shipping demand changes seasonally. The degree of fluctuation differs for different types of cargo, and the peak and trough points also differ. In the spatial aspect, the demand is a unidirectional flow. Due to the importance and complexity of the tramp shipping of dry-bulk cargo, ship scheduling is an important topic in the seaborne transport field. Considerable research has been conducted on ship scheduling in the tramp shipping market, with certain studies dating back to the late 1960s. Appelgren (1969) studied how to arrange a fleet reasonably. He proposed a ship dynamics decomposition model and solved it using dynamic programming and linear programming to maximize the profits of the shipping company. Bausch, Brown, and Ronen (1998) graphically displayed an optimized fleet deployment schedule with hourly time windows over a planning horizon of 2-3 weeks in a context in which each vessel customarily makes several voyages and many port calls to load and unload products during this time period. Christiansen, Fagerholt, and Ronen (1999) presented a real ship planning problem comprising a combined inventory management problem and a routing problem with time windows. The quantities loaded and discharged were determined by the production rates of the harbors, possible stock levels, and the actual ship visiting the harbor. Christiansen, Fagerholt, and Ronen (2004) reviewed state-of-the-art studies on ship scheduling and presented additional study topics regarding future trends and an optimization-based decision support system for ship routing and scheduling.

To investigate the factors influencing ship scheduling for tramp shipping, Bronmo, Christiansen, and Nygreen (2007) changed the fixed sizes of the contracted cargo in the previous research and presented an MP-model (the two-valued neuron model proposed by W. S. Mcculloch and W. A. Pitts, 1943) to solve the multiship pickup and delivery problem with time windows and flexible cargo sizes. Norstad, Fagerholt, and Laporte (2011) described the relationship between the sailing speed and trip fuel consumption and proposed a tramp ship routing and scheduling problem with speed optimization to determine the optimal speed for each sailing leg on a given shipping route. Reinhardt and Pisinger (2012) and Halvorsen-Weare and Fagerholt (2013) built a tramp shipping model based on the path network structure from the aspects of fuel consumption and sailing speed. The routing and scheduling decisions were decomposed, with the routing decision determining which shipments were served and the scheduling decision determining the time to start the service while satisfying inventory and berth capacity constraints with the goal of optimizing cost, speed, and fuel consumption. Pang, Xu, and Li (2011) and Vilhelmsen, Lusby, and Larsen (2013) used delivery time as the primary condition and built a tramp ship scheduling model with time constraints. Based on the operational aspect of tramp shipping, which involves numerous shipments, ships, ports and routes, Tang, Xie, and Wang (2013) comprehensively considered the nonlinear effects on time and cost to propose a nonlinear network programming model to address the choice of routes and the variable-speed ship scheduling problem. Qian and Zhou (20t4) considered the dynamic demand, multiple ship types, and uncertain shipping routes to build a multi-objective ship scheduling model with rolling windows to minimize shipping costs and proposed real-time optimal strategies based on an SRPRW (the ship scheduling problem with rolling windows and multi-objective) model to adjust the shipping routes to correspond to dynamic demands. In terms of simulating dynamic demand, these papers provide valuable methods. However, the choice behaviors of shippers have not been addressed.

Choice inertia implies that past decisions remain in the memory of the decision-makers, who are more likely to adopt the current decision behavior. Garling and Axhausen (2003) described the choice habit in detail and analyzed its impacts and function on travel choices. Garvill, Marell, and Nordlund (2003) conducted a field experiment and proved that people with strong habits have obvious inertia and prefer to retain the original alternatives. Cantillo, Ortuzar, and Williams (2007) assumed that travelers had choice inertia with respect to travel mode and studied the effect of travel choice inertia on travel mode and traffic policies. Cherchi and Manca (2011) used a mixed dataset of RP-SP to study the effects of previous experiences on current choice. Zhao and Huang (2014) represented inertia with "satisfaction" to consider the route preferences of travelers and traveler satisfaction heterogeneity. They developed the characteristics of the flow distribution and obtained the conditions under which bounded rational user equilibrium exists. Zhang and Yang (2015) defined the choice inertia in route choice accurately and proposed an inertial user equilibrium traffic assignment mode. Lu et al. (2016) proposed a timetable optimization model for an airport coach system by incorporating the reactions of loyal airport passengers to coach service quality. They simulated the changes in the passengers' choice inertia using cumulative prospect theory.

Although many studies have been conducted on choice inertia, few studies have been conducted on shipping (and tramp shipping in particular). For liner shipping, Chen et al. (2016) considered the seasonal demand fluctuation and shippers' choice inertia to optimize the shipping network and fleet deployment simultaneously with the objective of maximizing the profits of the liner carrier. For tramp shipping, scholars have paid more attention to the long-term contract and ignored the effects of shippers' choice inertia on carrier profit in the spot market. Existing studies on tramp ship scheduling mainly address single time-point decisions on cargo selection, sailing speed, and ship deployment under a fixed shipping demand. These decisions are static. The resulting schemes cannot satisfy carriers' demands in a dynamic market.

Therefore, this article considers the effects of the services at a pre-order segment on obtaining the subsequent market share at the same segment to schedule tramp ships. This issue is a dynamic decision-making issue, and an equation must be developed to calculate the relationships between the utility of a shipper's choice and the amount of service completed by carriers on a segment based on shippers' choice behavior, particularly their fostered choice inertia. The probabilities of shippers choosing carriers in each time window can then be calculated using the logit model. Moreover, the dry-bulk cargo being transported and the freight rates for each segment in every season are determined according to seasonal demands. Based on the total shipping demand and the market share of a carrier on each segment, the transport tasks of a carrier on the corresponding segment in the current time window are determined. Finally, ship scheduling schemes that can maximize a carrier's profits over the entire planning horizon are designed.

Problem Description

In the tramp spot shipping market, carriers are assumed to provide a service with the same price in the same market such that over 10-12 months shippers are more likely to choose the carrier who has offered stable and liable service. Thus, a carrier who has transported more shipments on a segment may obtain more orders from the shippers on the corresponding segment in the future. The shippers in different shipping segments maybe viewed as an integrated shipper, and their choice inertias affect the number of shipments of carriers. Therefore, the choice inertias may be reflected by the market shares of carriers on shipping segments. In the tramp spot shipping market, a carrier should consider the effects of its current service on its future market share. The problem can be illustrated in detail by the example below.

In the example, a carrier provides tramp shipping services among four ports in two time windows using one ship. A ship can sail two segments in each time window. Figure 1 shows the ports, segments, and spot shipping demands in the current time window ([t.sub.1]) and the potential shipping demands in the future time window ([t.sub.2]). In this case, if the carrier measures the benefits without considering the shippers' choice inertias (fig. 1a), it would like to have the schemes operated in the first and second time windows as "[R.sub.1]: 1-3-2" and "[R.sub.2]: 2-1-4". The total amount of cargo transported is [9t (on segment 1-3) + 6t (on segment 3-2)] in window [t.sub.1] + [9t (on segment 2-1) + 12t (on segment 1-4)] in window [t.sub.2] = 36t.

However, because in time window [t.sub.1] the carrier does not offer service on segment 1-4, the shipper of cargos on segment 1-4 may choose the rival carrier due to its larger inertias on the rival. Therefore, the carrier may be able to get only the tasks on segments 2-3 and 3-1, and the schemes operated in the first and second time windows are "[R.sub.1]: 1-3-2" and "[R.sub.2]: 2-3-1." Correspondingly, the total amount of cargo transported is [9t (on segment 1-3) + 6t (on segment 3-2)] in window [t.sub.1] + [8t (on segment 2-3) + 8t (on segment 3-1)] in window [t.sub.2] = 31t.

If the carrier takes shippers' choice inertias into account, it would like to have the schemes operated in the first time window as "[R.sub.1]: 1-4-2". As a result, the shippers' choice inertias may become larger, and in the second time window, the carrier will be selected to ship the cargos on segment 1-4. Therefore, in this case, the schemes operate in the first and second time windows as "[R.sub.1]: 1-4-2" and "[R.sub.2]: 2-1-4" (fig- 1-b)- Correspondingly, the total amount of cargo transported is [7t (on segment 1-4) + (on segment 4-2)] in window [t.sub.1] + [9t (on segment 2-1) + 12t (on segment 1-4)] in window [t.sub.2]=36t.

Mathematical Model


The choice inertia of shippers on a carrier can be represented by the accumulated service offered by the carrier up to the current time window. The following assumptions are made when building the model:

A1: Carriers in the tramp spot shipping market are divided into two categories, namely the target carrier and the alternate. Their service prices are identical.

A2: There is no trans-shipment; the shipping demand can be transported on only one voyage, and there is only one loading port and one unloading port.

A3: The effects of the types, ages, and dead-weights of ships are neglected, and the sailing speeds are given.

A4: The effects of uncontrollable factors on shipping, such as bad weather, are neglected. Each port meets the relevant channel depth and berth length requirements.

A5: The main operational costs of carriers are the sailing costs; at-port costs are not considered.

A6: The freight rate depends only on the transported distance and season.

A7: All shipping demand tasks must be served.

A8: Factors apart from the accumulated services offered by a carrier on a segment can be represented by the size of a carrier.

Variable and Parameter

1. Decision Variable [x.sub.ijvn] = 1 if ship v sails segment (i,j) on voyage n and = o otherwise.

2. Other Variables and Parameters
[R.sub.ijt]       -- The business revenue on segment (i,j) in time
                     window t, determined by the freight rate and ship

[K.sub.ijt]       -- The number of ships deployed by the carrier on
                     segment (i, j) in time window t

[CS.sub.ij]       -- The cost of a ship sailing segment (i, j), mainly
                     the fuel cost

[f.sub.ijt]       -- The freight rate on segment (i,j) in time window t

[lambda]          -- The correlation coefficient between the freight
                     rate andshipping distance

I                 -- The set of loading ports, i [member of] I

V                 -- The set of a carrier, v [member of] V

[y.sub.r]         -- The size of carrier r

t'                -- The current time window

[V.sub.cap]       -- The ship capacity

[[alpha].sub.a]   -- The seasonal freight rate coefficient, which can
                     be calculated based on the Baltic Exchange Freight
                     Index (BFI),

[d.sub.ij]        -- The distance from port i to port j

a=1, 2,3,4        -- The location of a window in the planning horizon

[l.sub.ijt']      -- The number of ships that the target carrier could
                     deploy on segment (i,j) in time window t'

[n.sub.ijt]       -- The number of ships deployed on segment (i,j) by
                     the target carrier in time window t', namely,
                     the amount of cargo obtained on segment (i,j) in
                     time window t' divided by the ship capacity.

s=14 knots        -- The sailing speed (estimated based on Clarkson's

[DELTA]t          -- The length of each time window

[]        -- The time window in which the starting time of
                     ship v on voyage n is located

[]        -- The starting time of ship v on voyage n

[[delta].sub.vnt] -- 0 or 1, representing whether the starting time of
                     ship v on voyage n is in time window t' or not

[Q.sub.ija]       -- The shipping demand on segment (i, j) during
                     season a

[[rho].sub.t'a]   -- 0 or 1, representing whether time window t' is in
                     season a o or not

[V.sub.ijrt]      -- The utility determined by the accumulated tasks
                     completed by carrier r on segment (i,j) before
                     time window t' and the size of the carrier

[[??].sub.ijt'r]  -- The possible shipping demand in time window t' of
                     carrier r on segment (i,j)

[P.sub.ijt'r]     -- The current market share of carrier r on segments
                     (i,j) in time window t'

r                 -- 1 or 2, indicates the target carrier of the
                     alternate carrier

J                 -- The set of unloading ports, j [member of] J

Note: Based on Clarkson's statistics, the laycan for dry bulk is
typically 5 days. Thus, we use 5 days as the time span of one time
window, resulting in 18 time windows in one season.

Model Structure

[x.sub.ijvnt] = 1 if ship v sails segment (i, j) on voyage n in time t and = o otherwise

[mathematical expression not reproducible] (1)

S.T.: [R.sub.ijt] = [f.sub.ijt] x [V.sub.cap] [for all]i, j,t (2)

[f.sub.ijt] = [lambda] x [d.sub.ij] x [[alpha].sub.a] [for all]t (3)

[mathematical expression not reproducible] (4)

[K.sub.ijt'] = Min([l.sub.ijt'], [n.sub.ijt']) [for all]i,j (5)

[mathematical expression not reproducible] (6)

[] = [[]/[DELTA]t] [for all]v,n (7)

[mathematical expression not reproducible] (8)

[l.sub.ijt'] = [[summation].sub.v] [x.sub.ijvn] x [[delta].sub.vnt'] [for all]i,j (9)

[n.sub.ijt'] = [[[??].sub.ijt']/[V.sub.cap]] [for all]i,j (10)

[[??].sub.ijt'r] = [P.sub.ijt'r] x [[summation].sup.4.sub.a=1] ([[rho].sub.t'a] x [Q.sub.ija])/(90/[DELTA]t)] [for all]i, jr = 1 (11)

[mathematical expression not reproducible] (12)

[mathematical expression not reproducible] (13)

[mathematical expression not reproducible] (14)

[mathematical expression not reproducible] (15)

[[summation].sub.i] [[summation].sub.j] [x.sub.ijvn] = 1 [for all]v,n (16)

[mathematical expression not reproducible] (17)

Equation 1 maximizes the total tramp shipping profits of the target carrier. The first part on the right side is the business revenue, and the second part is the operational cost on segments in each time window. Equation 2 calculates the revenues. Equations 3 and 4 calculate the freight rate on each segment in different seasons. Equation 4 describes the relationships between time window t and season a. Equation 5 determines the needed vessels on segment (i, j) in the current time window. Equations 6-10 count the number of ships deployed by the carrier on segment (i, j) in the current time window. Equation 11 calculates the total amount of shipping demand on segment (i, j) in time window [[rho].sub.t'a], and 90/[DELTA]t is the number of time windows in each season; Pea represents whether time window t' is in season a; [[summation].sup.4.sub.a=1] ([[rho].sub.t'a] x [Q.sub.ija]) represents the total shipping demand in season a, which contains time window t'. Equation 12 is 0-1 variables representing whether time window t' is in season a. Equations 13 and 14 are a logit model used to calculate the market share of a carrier on segment (i,j), The basic logit model is [P.sub.ij] = Exp([V.sub.ij]) [[summation].sub.n.sub.k=1] [V.sub.ik]. Here [V.sub.ij] is the utility and is usually determined by several factors. The utility factors are the accumulated service quantity offered by a carrier on a segment and the carrier's size. Equation 15 is 0-1 variables. Equation 16 indicates that ship v can sail only the segment on voyage n. Equation 17 shows the continuity of voyages.

Model Solution

We solve this problem using a genetic algorithm (GA) with the following process:

Step 1: Coding. A real number is used to code the chromosomes, which represent the tramp shipping route. The first gene represents the ship code, and the second gene represents the initial port of the ship. Starting with the third gene, gene i represents the [(i-2)] ports of call. The chromosome in figure 2 shows that ship 1 starts the voyage from port 2, and the ports of call are ports 5-3-1-6-4-6-5-3-2.

Because of the differences in sailing times and distances for different voyages, the number of ports of call may differ for different chromosomes. To ensure that all chromosomes have the same numbers of genes, we should add additional genes behind the essential genes in the chromosomes for certain short voyages. For example, for a horizon of 90 days, among the four ports shown in figure 3, the maximum number of voyages of a ship is 15. For this maximum case, the chromosome has 17 genes. However, for the shipping route 2-4-3-1-2-4-1-4-3-2-4, there are only 10 voyages over 85 days. It is impossible for the ship to make another voyage in the remaining 5 days. In this case, the chromosome has 11 genes. Therefore, we add another 5 genes.

Step 2: Fitness. The value of the objective function is defined as the fitness value directly.

Step 3: Selection. The chromosomes with higher fitness values are placed in the next generation using the combined Roulette method and elitist strategy. The elitist parameter is set to 2, which means that the best two chromosomes are retained in the offspring generation directly.

Step 4: Crossover operation. This operation randomly chooses two chromosomes and exchanges certain genes (except the first gene because it represents the ship) according to a probability.

Step 5: Mutation operation. After crossover, two adjacent genes maybe identical. In this case, the second one must be mutated and replaced by a randomly generated real number.

Step 6: Termination determination. If the difference in the average fitness values among several subsequent generations is smaller than a certain threshold, and the indication of computational burden is 300, then the calculation is terminated when meeting one of these two conditions.

Empirical Study

According to Clarkson's statistics (, dry-bulk cargo purchasers and vendors are mainly located near the Pacific Ocean. For this study, we select the Asia-Pacific region as the study area and use a tramp shipping company operating in this region as the target carrier. The planning horizon is one year, which is partitioned into four seasons. The seasonal shipping demands between ports are determined based on the seasonal fluctuations. The amount of cargo on each segment in the current time window is calculated based on the carrier's market share.

Data Collection

It is assumed that the carrier has 6 dry-bulk ships with a capacity of 6 x 75,000 tons for operation in the Pacific Ocean. The dry-bulk cargos are mainly iron ore, coal, and grain. The major shipping endpoints are Australia, Indonesia, China, Russia, Canada, the United States, and Brazil. The main ports in these countries are Hedland, Tanjung Bara, Qingdao, Vostochny, Seven Islands, Houston, and Tubarao, which are labeled ports 1-7, respectively, and these ports represent the origins/destinations of the shipping segments.

According to Clarkson's statistics, the shipping demands for iron ore, coal, and grain in 2015 are shown in table 1.

Based on their seasonal fluctuations and spatial attributes, the shipping demands in each season and the seasonal fluctuation coefficients of various cargos on segments 5-3 and 6-3 are shown in figures 5 and 6.

From Clarkson's database, we obtain the freight rates for 10 routes of the same cargo category (iron ore) for the same shipper, ship type, and season. Using data fitting, the relationship between the freight rate and shipping distance is [f.sub.ijt] = 0.147 x [d.sup.07367.sub.ij] x [[alpha].sub.a]. Furthermore, the seasonal freight rates between ports are obtained based on the BFI in 2015. We also obtain the basic data in each quarter offered by some carriers on 10 segments in 2015 (including the number of ships on each segment and the number of ships of each carrier). Then, based on the data in the first three quarters and the market share of each carrier in the fourth quarter, we calibrated the logit model (eqs. n and 12) to obtain[[beta].sub.1]= 0.08 and [[beta].sub.2] = 1.6.

Optimized Results

One of the seven ports is randomly assigned as the initial port of a ship. By calculating 260 generations, the solutions of the model over the entire planning horizon are shown in table 2, which shows the annual profit, number of voyages, and ports of call of each ship. The total expected profit for the six ships is 1,057.7 million USD. The shipping routes for ship 1 are shown in figure 7. The ship will make voyages among the ports of Hedland, Qingdao, Seven Islands, Houston, and Tubarao. Its shipping route includes 12 voyages (among these, 5 are ballast voyages) and generates an annual profit of 196.20 million USD.

Solution Analysis

Table 2 illustrates that certain ships sail ballast voyages first and then sail loaded voyages. For example, ship 4 will sail from port 6, which is its initial site, to port 5 without cargo first and then make the voyage from 5 to 3 with cargo. There is an initial shipping demand from port 6 to port 3 with an operating profit of 0.436 million USD. If only the profit in the current time window is considered, the ship will serve this current demand immediately; thus, the shipping route for the entire horizon will be 6-3-1-6-3-16-3-1-6-3-1. The first two shipping segments are 6-3 and 3-1, which have a total sailing time of 56 days. The voyage on the second segment will be completed in the 12th time window, and the business profit is 0.248 million USD. Conversely, in the optimized scheme, the first two segments are 6-5 and 5-3, which have a total sailing time of 58 days and a profit of 0.301 million USD. In both cases, the voyages on the second segment will be completed in the same time window, but the profit of the latter approach is 53,000 USD more than that of the former.

Although serving the demand on segment 6-3 in the first time window is profitable, if the demand features and shippers' choice inertias are considered, a ballast voyage on segment 6-5 in the first time window may help maximize the profit over the entire planning horizon, which means that a carrier may forego cargo to make ballast voyages first to obtain greater market share and profits during subsequent time windows. The reasoning in this study can be further explained as follows:

The cargo from port 5 to port 3 is mainly iron ore and grain from Canada to China, whereas the cargo from port 6 to port 3 is mainly coal and grain from the United States to China. In quarter 1, the shipping demand on segment 5-3 is less than that on segment 6-3. However, in the first three quarters, the demand on segment 5-3 is considerably higher than that on segment 6-3. If carriers make decisions only one time window at a time without considering the effects of their previous services on subsequent market share and shippers' choice inertia, they may suffer lost opportunity costs. Therefore, although offering service on segment 6-3 in quarter 1 is profitable, in the context of seasonal demand fluctuation and shippers' choice inertia, the carrier should make a ballast voyage first so that it can obtain greater market share and profit over the entire operational period.

To test the efficiency of the algorithm, we use the combination of functions tic/toc. If we set both the generation and the population size as 2, the elapsed time of the main program is 26.51s (Matlab; CUP: Core i3,3.4 GHz). To obtain the solution to the case study, we set the generation to 300 and population size to 10; the elapsed time of calculation is then 131 minutes. The result tends to converge from the 273rd generation, which means that the algorithm is effective enough.


This article optimizes tramp spot shipping scheduling by considering shippers' choice inertias, causality between carriers' completed services and subsequent market share, and the temporal and spatial fluctuation of bulk cargo shipping demands. The shippers' choice inertia is expressed as the accumulated services offered by the carriers. The logit model is used to calculate the market share of carriers in each shipping segment, which is influenced by the carrier's size and the number of services completed on a segment.

In the case study, we consider a shipping company that operates the Pacific Ocean route as an example to solve the model and to obtain several conclusions. The results demonstrate that, in certain cases, the carrier should make a ballast voyage first instead of transporting cargo in the current time window to avoid lost opportunity costs during subsequent time windows and to maximize its profit over the entire planning horizon.

In a real situation, tramp shipping companies consider long-term profits when they develop schemes for ship charter and dispatching. Therefore, these companies have annual plans, quarterly plans, and monthly plans. However, because spot decisions are often made separately by several small teams, the implemented scheduling decisions are often based on the current situation. Using an example, a theoretical proof, and a numerical test, we illustrate the role of cooperative decision-making across multiple time windows and shippers' choice inertias in maximizing the profit of a carrier over a planning horizon, and we offer a useful operational tool for carriers. In conclusion, the proposed model and algorithm can help carriers achieve the maximum benefit in a spot shipping market in a relatively short period (i.e., 12 months).


This research is supported by the key project of Natural Science Foundation of China (Grant No. 71431001), Fundamental Research Funds for the Central Universities (Grant No. 3132016303); sponsored by K. C. Wong Magna Fund in Ningbo University.

Yiran Zhao

Dalian Maritime University

Zhongzhen Yang

Corresponding Author

1 Dalian Maritime University

2 Ningbo University


Appelgren, L. H. 1969. "A Column Generation Algorithm for a Ship Scheduling Problem." Transport Science 3 (1): 53-68.

--. 1971. "Integer Programming Methods for a Vessel Scheduling Problem." Transportation Science 5 (1): 64-78.

Bausch, D. O., G. G. Brown, and D. Ronen. 1998. "Scheduling Short-Term-Marine Transport of Bulk Products." Maritime Policy and Management 25 (4): 335-48.

Bronmo, G., M. Christiansen, and B. Nygreen. 2007. "Ship Routing and Scheduling with Flexible Cargo Sizes." Journal of the Operational Research Society 58 (9): 1167-77.

Branmo, G., B. Nygreen, and J. Lysgaard. 2010. "Column Generation Approaches to Ship Scheduling with Flexible Cargo Sizes." European Journal of Operational Research, 139-50.

Cantillo, V., J. D. D. Ortuzar, and H. C. W. L. Williams. 2007. "Modeling Discrete Choices in the Presence of Inertia and Serial Correlation." Transportation Science 41 (2): 195-205.

Chen, K., D. X. Chen, X. S. Sun, and Z. Z. Yang. 2016. "Container Ocean-Transportation System Design with the Factors of Demand Fluctuation and Choice Inertia of Shippers." Transportation Research Part E 95:267-81.

Cherchi, E., and R. Manca. 2011. "Accounting for Inertia in Modal Choices: Some New Evidence Using a RP/SP Dataset." Transportation 38 (4): 679-95.

Christiansen, M., K. Fagerholt, and D. Ronen. 1999. "Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem." Transportation Science 33 (1): 3-16.

--. 2004. "Ship Routing and Scheduling: Status and Perspectives." Transportation Science 38 (1): 1-18.

Ding, Y., Y. Zhong, G. L. Ling, and X. Wen. 2015. "Ship Route Scheduling Problem in Tramp Shipping with Soft Time Windows and Random Sailing Time." Journal of Central China Normal University (natural science edition), 3:387-91.

Fagerholt, K. 2003. "A Computer-Based Decision Support System for Vessel Fleet Scheduling--Experience and Future Research." Decision Support Systems 37 (1): 35-47

Garling, T., and K. W. Axhausen. 2003. "Introduction: Habitual Travel Choice." Transportation 30 (1): 1-11.

Garvill, J., A. Marell, and A. Nordlund. 2003. "Effects of Increased Awareness on Choice of Travel Mode." Transportation 30 (1): 63-79.

Halvorsen-Weare, E. E., and K. Fagerholt. 2013. "Routing and Scheduling in a Liquefied Natural Gas Shipping Problem with Inventory and Berth Constraints." Annals of Operations Research 203 (10): 167-86.

Jin, Y., and Y. Zhao. 2007. "Utilization of Ant Colony Algorithms in Shipping Arrangement." Computer Engineering and Application 43 (25): 231-33.

Korsvik, J. E., K. Fagerholt, and G. Laporte. 2011. "A Large Neighborhood Search Heuristic for Ship Routing and Scheduling with Split Loads." Computers and Operations Research 38 (1): 474-83.

Lu, J., Z. Z. Yang, H. Timmermans, and W. D. Wang. 2016. "Optimization of Airport Bus Timetable in Cultivation Period Considering Passenger Dynamic Airport Choice Under Conditions of Uncertainty." Transportation Research Part C 67:15-30.

Norstad, I., K. Fagerholt, and G. Laporte. 2011. "Tramp Ship Routing and Scheduling with Speed Optimization." Transportation Research Part C19 (5): 853-65.

Pang, K. W., Z. Xu, and C. L. Li. 2011. "Ship Routing Problem with Berthing Time Clash Avoidance Constraints." International Journal of Production Economics 131 (1): 752-62.

Qian, Y., and L. Zhou. 2014. "Optimization Model of Tramp Ship Scheduling Based on Genetic Algorithm." Computer and Digital Engineering 42 (4): 601-5.

Reinhardt, L. B., and D. Pisinger. 2012. "A Branch and Cut Algorithm for the Container Shipping Network Design Problem." Flexible Services and Manufacturing Journal 24 (3): 349-74

Su, S. J., L. Z. Wang, and C. F. Wang. 2007. "Mathematical Model and Method Research of Ships Routing for Indeterminate Route." Ship and Ocean Engineering 36 (4): 100-103.

Tang, L., X. L. Xie, and C. W. Wang. 2013. "Model of Tramp Ship Scheduling with Variable Speed Based on Set Partition Approach." Journal of Shanghai Jiaotong University 47 (6): 909-15

Vilhelmsen, C., R. Lusby, and J. Larsen. 2013. "Routing and Scheduling in Tramp Shipping--Integrating Bunker Optimization." objects/orbit:132090/datastreams/file_oee22C9a-c790-47CO-826c-7e25 993399eo/content.

Xie, X. L. 1992. "The Dynamic Model and Algorithm of Fleet Deployment." China Shipbuilding 3:102-10.

Xie, X. L., S. F. Li, and Z. S. Ji. 1989. "Study and Application on Linear Model of Fleet Deployment." China Shipbuilding 3:61-68.

Yu, S. M. 1997. "The Mathematical Optimization Method of Planning Routes and Fleet." Transportation and Calculation 5 (15): 36-49.

Zhang, J., and H. Yang. 2015. "Modeling Route Choice Inertia in Network Equilibrium with Heterogeneous Prevailing Choice Sets." Transportation Research Part C 57:42-54.

Zhao, C. L., and H. J. Huang. 2014. "Properties of Boundedly Rational User Equilibrium Under Satisficing Rule in Traffic Assignment Problem." System Engineering Theory and Practice 34 (12): 3073-78.

Caption: Figure 1 Schematic Diagram of Sailing Routes under Two Different Demand Situations

Caption: Figure 2 Coding of a Shipping Scheduling Scheme

Caption: Figure 3 Routings in the Planning Horizon

Caption: Figure 4 Initial Genes and Added Genes in a Chromosome

Caption: Figure 5 Seasonal Shipping Demands on Segments 5-3 and 6-3

Caption: Figure 6 Seasonal Fluctuation Coefficient of the Cargo

Caption: Figure 7 Shipping Routes of Ship 1
Table 1/Annual Shipping Demand of Dry Bulk Cargos between
Ports (million tons)

Destination/     Qingdao   Houston

Port Hedland     35,752      15
Tanjung Bara      7,237       0
Oingdao             0         0
Vostochny         2,910       0
Seven Islands      155       11
Houston            128        0
Tubarao           1,672      38

Note: Destination for Hedland, Tanjung Bara, Vostochny,
Seven Islands, Tubarao are all zero, and so are
not listed in the table.

Table 2/Shipping Scheduling Schemes

Ships    Annual Profit   Number of   Number of     Shipping Routes
         (million US$)    Voyages     Ballast

1           196.20          12           5       1-6-7-6-3-1-6-5-3-1-

2           179.38          14           7       2-3-4-3-1-6-7-3-1-6-

3           172.77          17           7       7-6-4-3-2-3-1-6-5-6-

4           242.26          12           5       6-5-3-1-6-3-1-6-3-2-

5            94.77          16           8       5-6-5-6-7-6-3-2-1-6-

6           172.35          15           7       5-3-2-3-1-6-5-3-4-3-
COPYRIGHT 2018 American Society of Transportation and Logistics, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Zhao, Yiran; Yang, Zhongzhen
Publication:Transportation Journal
Date:Jun 22, 2018
Previous Article:Evaluation of Ship Repair Services: A Case Study of Taiwan Shipping Companies' Selection.
Next Article:APICS: Request for Proposals.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters