Ship routing and scheduling systems: forecasting, upscaling and viability

Said El Noshokaty (Elesteshary Information Systems, Alexandria, Egypt)

Maritime Business Review

ISSN: 2397-3757

Publication date: 20 August 2020

Abstract

Purpose

The purpose of this paper is to resolve three problems in ship routing and scheduling systems. Problem 1 is the anticipation of the future cargo transport demand when the shipping models are stochastic based on this demand. Problem 2 is the capacity of these models in processing large number of ships and cargoes within a reasonable time. Problem 3 is the viability of tramp shipping when it comes to real problems.

Design/methodology/approach

A commodity-trade forecasting system is developed, an information technology platform is designed and new shipping elements are added to the models to resolve tramp problems of en-route ship bunkering, low-tide port calls and hold-cleaning cost caused by carrying incompatible cargoes.

Findings

More realistic stochastic cargo quantity and freight can now be anticipated, larger number of ships and cargoes are now processed in time and shipping systems are becoming more viable.

Practical implications

More support goes to ship owners to make better shipping decisions.

Originality/value

New norms are established in forecasting, upscaling and viability in ship routing and scheduling systems.

Keywords

Citation

El Noshokaty, S. (2020), "Ship routing and scheduling systems: forecasting, upscaling and viability", Maritime Business Review, Vol. 6 No. 1, pp. 95-112. https://doi.org/10.1108/MABR-04-2020-0027

Download as .RIS

Publisher

:

Emerald Publishing Limited

Copyright © 2020, Pacific Star Group Education Foundation. Licensed re-use rights only.


1. Problem statement

Shipping optimization systems (SOS) is one of the shipping routing and scheduling systems which has been discussed by El Noshokaty (1988, 2013, 2014, 2015, 2017A, 2017B, 2018A, 2018B, 2018C, 2019A, 2019B). This paper extends the work of El Noshokaty by focusing on three problems. Problem 1 is the future cargo transport demand assessed by the stochastic nature of SOS mathematical model and whether it may result in an unrealistic solution. Problem 2 is the capacity of SOS and whether it may be unable to process large number of ships and cargoes within a reasonable time. Problem 3 is the viability of SOS tramp with regard to real shipping problems. The contribution of this paper is to develop a commodity-trade forecasting system able to support the stochastic model in producing more realistic stochastic cargo quantities and freights. Another contribution is to upscale the shipping problem to a larger size and process it in a reasonable time. Upscaling is accomplished by decomposing the shipping problem using Dantzig and Wolfe (1960) Decomposition Principle and using an information technology (IT) platform, known as high performance computing (HPC), capable of processing large number of ships and cargoes in a reasonable amount of time. By decomposition, the tramp-shipping problem is decomposed into sub-problems, one for each ship, under a master program. Under the Decomposition and HPC, the nowadays computers can process the decomposed sub-problems in parallel. So, unlike extra cargoes, extra ships will not require extra processing time as all ships are processed in parallel. Using this IT platform, many problems that have never been solved can now be fixed. The third contribution is to make SOS more viable by adding new shipping elements of ship en-route bunkering, port calls in low tide and hold cleaning cost caused by incompatibility among carried cargoes.

In the following section, a review of the literature is introduced to know what research work and information technologies are found related to the three problems addressed by this paper, namely, the cargo transport demand forecast, the processing of large number of ships and cargoes in time and the introduction of new viable shipping elements. The next three sections discuss the contribution of this research paper regarding the UN COMTRADE forecast, upscaling in time: the application of Dantzig-Wolfe decomposition principle using HPC and adding new shipping elements. The final section gives a concluding statement and future work recommendation.

2. Review of the literature

2.1 Cargo transport demand forecast

In cargo transport demand forecast, there are two research approaches in this concern. The first approach derives the cargo transport demand from the business transactions conducted between countries. This approach studies the bilateral trade for some years back to assess the future demand of cargo transport using some kinds of regression analysis.

In the area of the first approach of cargo transport forecast, Fite et al. (2002), Levine et al. (2009), Holguin-Veras et al. (2011) and Cantillo et al. (2012) have used the regression model, the gravity model and the conventional four-stage model. Chou et al. (2008) applied a fuzzy regression-forecasting model to predict the international cargo volume transported to and from Taiwan. Bagighni (2012) built regression models to analyze freight generation and attraction of commodity groups for counties in 48 US states with cargo flow information. Brocker et al. (2012) adopted the gravity model for predicting commodity-specific interregional trade flows in Europe. Boland (2018) examined the classic four-stage transport model as a point of reference and address its limitations. Profilidis and Botzoris (2018) constructed qualitative models and quantitative in choosing the most suitable solution for all types of transport applications.

The second approach considers the cargo transport as a service, same as other products and services, within an economic context of production and consumption and a context of saving and investment. This approach uses some social, educational and training, financial and economical parameters and indicators in each country in each year to compute the amount of future bilateral trade. To transform trade value data to flow of cargoes transportable by maritime transport network, the conventional four-stage model may be used. Stage 1 is the trade generation, where values and quantities of goods are identified. Input-output tables and computable general equilibrium (CGE) are two such methods to generate trade. Stage 2 is trade distribution, where flows of goods between origins and destinations are classified. One of the methods used in this stage is the gravity model that determines the flow between two countries based on their economic sizes and distances between them. Stage 3 is the modal split, where goods are allocated among transport modes. In this stage, elasticity-base models are used to study the effect of changing a transport element such as the transport cost on transport mode selection. Stage 4 is the assignment stage, where the flows of goods are assigned to the transport network and alternate routes and paths. In this stage, route optimization models may be used.

In the area of the second approach of cargo transport forecast, Marzano and Papola (2004), Bagighni (2012) and Brocker et al. (2012) have included regression analysis done with economic indicators, gravity model analyzing trade flows and input-output models. Shibasaki and Watanabe (2012) proposed a conceptual framework that uses a CGE model to predict cargo flow within the Asian-Pacific Economic Cooperation region. Lee et al. (2011) took a similar approach in evaluating the impact of the Economic Cooperation Framework Agreement between Taiwan and China on seaborne trade volume. Cheong and Cho (2013) modified the methodology used by Lee et al. (2011) to investigate the impact of free trade agreements between South Korea and its major trading partners on Korean maritime trade. Nguyena and Walther (2018) investigate the time-varying volatility patterns of some major commodities and the potential factors that drive their long-term volatility component.

Analyzing the above-mentioned two approaches of cargo demand forecast, based on the research papers already published on these approaches, the author came up with the flowing observations:

  • Approach 2 is much complicated and expensive, methodology wise, than Approach 1 while the precision of its forecast does not justify these complications and expenses. On the other hand, although Approach 1 is much simple and less expensive its forecast is an extrapolation based on past data and not based on current and future indicators.

  • Approach 2 requires data on social, financial and economic indicators that is not available about all countries all the times. While in Approach 1, missing data of one country can be provided by other partner countries without the need for any indicators here or there.

  • Either approach, even with the four-stage model, fails to provide the shipowner of an estimate of his share in the forecast of cargo transport demand, classified by period, commodity, package, quantity in weight, volume and number, port of loading and port of discharging. These are the attributes, as displayed by any bill of lading, which define the ship owner’s prospective cargo transport demand. PIERS (2020) contains such historical data but for the US only.

Based on the above-mentioned analysis, the author has developed the UN COMTRADE forecast system to overcome the shortcomings in the two approaches of cargo demand forecast.

2.2 Upscaling in time

As for the processing of large number of ships and cargoes, all shipping research papers have used the current IT. However, very few of them have their shipping models being formulated the way that gets the benefit from the multi-core processor as to minimize the processing time. If the tramp-shipping problem can decompose into sub-problems, one for each ship, under a master program, then the problem can get benefit from the multi-core processor, where the computer assigns one core process to each sub-problem. The following few authors have their models decomposed into sub-problems to solve large problems. In Christiansen et al. (1999), a fleet of ships transports a single product (ammonia) between production and consumption harbors. They determined the quantities loaded and discharged, possible stock levels and the actual ship visiting the harbor. The paper described the real problem and the underlying mathematical model. Then, they solved the problem by a Dantzig-Wolfe decomposition approach including both ship routing sub-problems and inventory management sub-problems. The overall problem is solved by the branch-and-bound method. Vilhelmsen et al. (2017) has used a decomposition model with dynamic programming algorithm to solve a shipping problem by column generation. The model focuses on the time spread between voyages in response to a charter party clause, which requires the voyages to be “fairly evenly spread”. This requires the voyage to become the model decision variable with a predetermined route and full-load cargo to be transported in each voyage. Unfortunately, the previous research papers which use the decomposition principle in shipping are not reported to use the multi-core characteristic to speed up the processing of their models and run them in a reasonable time.

The upscaling procedure introduced in this paper has used the model decomposition to solve large problems and the multi-core characteristic to speed up the processing.

2.3 New shipping elements

As for the new shipping elements, thanks to Fagerholt and Lindstad (2007), who gave a summary of the most common components and planning requirements that a decision support systems for ship routing and scheduling should be able to handle.

This summary of common components inspires the author to develop the new shipping elements brought in this paper.

3. UN COMTRADE forecast

Based on the literature review, the shipowner would be uninterested in any forecast based on the four-stage model, whatever the forecast approach is. As the shipowner has his own data on the current cargo transport demand, he might be satisfied with a forecast of the percentage increase in this demand. Using Approaches 1 and 2 mentioned in the review of the literature, the percentage increase in cargo transport demand could be developed hereinafter as follows:

  1. From Approach 1, take the UN COMTRADE, which provides data on the international bilateral trade data classified by values of exports, year, reporter and partner countries and commodity. Construct a time series long enough from the UN COMTRADE, expressed in yearly values.

  2. Do the required forecast using a linear regression model.

  3. From approach 2, take the International Monetary Fund (IMF) which provides data on percentage increase in inflation rate classified by year and country.

  4. Discount the forecasted value by its corresponding data in (3) to come up with a non-inflated value, and then calculate the percentage increase in commodity quantity as its price is now non-inflated.

The viability of SOS is highly dependent on this forecast because of the stochastic nature of its mathematical model. The model in Appendix needs in equations (29)–(31) a probability distribution to be built for the cargo transport demand and a least probability the shipowner stipulates he can transport the cargo within this cargo demand. To support the shipowner in determining the least probability, the demand forecast will give him a better estimate. Table 1 shows some selected commodities, reporter countries, partner countries and the commodity-percentage-increase forecast for 2019, using 10-year time series. Using longer time series will most likely enhance the forecast.

Table 1 tells the shipowner that his ships sailing to the Fareast in 2019 should expect an increase in the transport demand of dairy products on his ships by a percentage increase of 8%. So, if his ships were used to transport say 500,000 mt of dairy products in 2018, he should expect a quantity around 540,000 mt in 2019.

4. Upscaling in time: the application of Dantzig-Wolfe decomposition principle using high performance computing

For the processing of large number of ships and cargoes, SOS has applied the Dantzig-Wolfe decomposition principle using HPC for tramp shipping and HPC for liner shipping. As SOS tramp model has a linear ratio objective, the block-angular linear ratio programming is used as a modified version of the Dantzig-Wolfe decomposition (El Noshokaty, 2014). The HPC hardware and network platform consist of a number of PCs with multiple cores and large memory connected by a network. The HPC contains the Message Passing Interface (MPI) software which helps assign the SOS master and sub-problems to core processes and enables the communications between them. Table 2 shows a comparison between the processing time taken by SOS to process the tramp 3-ship-30-cargo and 3-ship-40-cargo cases, with and without the decomposition and HPC. The comparison is made on one 64-bit PC with I5 processor and 20 G memory. One PC is quite enough as it has 4 cores which can process up to 8 processes simultaneously while the number of ships is only 3 which needs 2 processes for each ship (if integer numbers is required) plus one process for the master program.

The reason why Table 2 shows high processing times compared to those found in the literature is that the tramp problem here is using integer programming in addition to the Dantzig-Wolfe decomposition. Besides, the tramp model considers the following shipping elements and rules, which, in turn, require large number of variables and constraints (a formula number found in the model displayed in Appendix is written corresponding to each element or rule):

  • The total quantity of the cargoes to be carried on board a ship must target the maximum possible profit whether the ship is “full and down” or otherwise. Maximum possible profit is achieved by optimizing the stochastic gross-profit-per-day objective. (1)

  • The rate of loading or (and) discharging of a cargo may be limited to a nominal rate. The demurrage and dispatch may result if the actual rate is less or greater than the nominal rate, respectively. The demurrage and dispatch may be calculated for the loading and discharging separately (irreversible calculation) or for the loading and discharging combined (reversible calculation). (1)

  • Lightening of shipload via SUMED pipeline in Suez Canal. (1)

  • Lightening of shipload via “daughter-ship arrangement” in Suez Canal or Panama Canal. (1)

  • Time charter to be taken as an alternative venture to voyage charter. (1)

  • The ship has the option, if equipped enough, to heat or cool the cargoes while in ship holds. The cost of heating or cooling is added to the total cost. (1)

  • Additional charter party terms such as specifying multiple ships and cargoes in one contract of affreightments, with freight specified for each cargo or lump sum freight for all cargoes. (1)

  • A ship may be chartered-in to compete in carrying a certain cargo. (1) and (9)

  • The ship has the option, if permitted, to pass or (and) bypass the Suez Canal or (and) the Panama Canal, whichever contributes more to the gross profit per day. (1) to (25)

  • A differentiation is made to whether the ship is in laden or ballast condition, so that the sea fuel consumption is calculated accurately. (1) to (25)

  • Different open and close ports and dates are specified for each ship. (2) to (25)

  • Already booked cargo. If booked, ship name may or may not be specified. If the ship name is specified, booked cargo is assigned to this ship (if the ship name is not specified, booked cargo may be assigned to the ship contributing more to gross profit). (7)

  • Already loaded cargo. If loaded, cargo is assigned to the ship already carrying it. (8)

  • Deadweights other than winter deadweight, namely, summer and tropical deadweights. (8) to (16)

  • The total weight, volume and number of all cargoes carried on board the ship, at any time, must not exceed its deadweight (excluding capacities other than cargo), volume or (and) TEU capacity. (10) to (18)

  • The optimal cargo mix, i.e. choosing the best combination out of different cargoes, is always desired even if the quantity of the cargoes to be carried is less than the capacity of the ship. (10) to (18)

  • The ship has the option to carry one cargo or multiple cargoes at the same time. (10) to (18)

  • The date of loading or (and) discharging of a given cargo must be within its loading or (and) discharging time window. (20) to (23)

  • The ship starting and ending ports are restricted to the ports indicated by the schedule or the last calling ports. (20) to (23)

  • Weather condition as an element affecting ship speed. (20) to (25)

  • If the ship arrives before the cargo loading or discharging open date, the ship has to wait until this date. This waiting time is added to the total ship elapsed time. The cost of this waiting time is added to the total cost. (24)

  • The ship starting and ending dates of operation must be within a given schedule date window. (25)

As for the liner shipping, its model is much simpler than the tramp and its processing time is measured by seconds rather minutes. In the liner model, the cargo quantity may be offered in two options. Option 1 is to accept or reject the whole cargo shipment (same as tramp), which requires integer processing to be adopted. Option 2 allows a partial shipment. The latter option is useful in decreasing the number of variables requiring an accept-or-reject decision, the way which saves the computer processing time. Although liner-shipping problem is not decomposable, it uses HPC in solving its model’s integer numbers.

In Table 2, one may observe that the difference in times is considerable between the 3-ship-30-cargo case and the 3-ship-40-cargo case, with and without decomposition and HPC. It is expected that the time will increase for the without cases as the number of ships goes higher. Though not tested, the time is expected to reach many hours for the 3-ship-40-cargo case without Decomposition and HPC. The reason why the number of cargoes is limited to 40 cargoes is that SOS considers this number large enough for a problem of an operational planning span, where the planning period does not exceed three months at most. For problems of a tactical planning nature, SOS has a one year planning system that allocates the fleet units to cargo trade areas, given all cargo transport demand located in these areas. SOS also has a system of a strategic planning nature, where new ships are subject to appraisal.

5. Adding new shipping elements

5.1 Added elements

In addition to the 22 shipping elements, terms and rules mentioned earlier, which make SOS viable, this paper announces the addition of the following three shipping elements to make SOS for tramp shipping more viable (a formula number found in the model displayed in Appendix is written corresponding to each new element):

  • The discharged cargo from a ship is checked, holds cleaning wise, whether it is compatible with the new cargo to be loaded on board the same ship. If they are not compatible, a holds cleaning expense is incurred. (1)

  • The en-route bunkering of the ship is allowed when the bunker price from an en-route bunkering port will reduce the operating cost. (1) and (6)

  • The actual ship draught is measured according to the weight of the cargoes already loaded on board the ship. This allows the ship, if the actual draught permits, to pass canals and call at ports when tide is low. (2) to (25)

The above mentioned three shipping elements are taken into account when calculating the times shown in Table 2.

5.2 A case study

Ship 1, Ship 2 and Ship 3 are three oil tankers working as trampers in crude oil transport. In the final quarter of the year, these tankers are planned to compete in carrying 10 crude oil cargoes by non-demise voyage charter parties. Three of these cargoes are to be transported from Kuwait to USA, another three from Ukraine to China and four from Venezuela to Latvia. Relevant data on ships is shown in Table 3. For Ship 1 and Ship 3, the open port is Alexandria, Egypt. For Ship 2, the open port is Odessa, Ukraine. For all ships, the close port is the last port of call, the open date is 1/10 (dd/mm is the date format), the close date is 31/12, the voyage fixed cost is US$1,000 and the fixed time is 0.3 day. Relevant data on port is shown in Table 4. Before open date, the 10 crude oil cargoes are offered. Relevant data on cargo is shown in Table 5.

From Table 5, the shipowner wants to find for each ship, at the low speed level (most economic), the route and the cargo mix (no partial cargoes) which give the maximum gross profit per day, summed for all ships. The model in Appendix suggests El Kosseir selects “Crude Oil 10” from Maracaibo to Riga, Safaga selects “Crude Oil 4” from Odessa to Shanghai (directly) and Sidi Kirear selects “Crude Oil 2” from Shuaiba to Baltimore (directly), followed by “Crude Oil 5” and “Crude Oil 7” from Maracaibo to Riga. The total gross profit per day is US$48,628. Upon reviewing the results, the shipowner requested that the following elements should further be considered when applying the model:

  • All ships arriving Riga may experience a low tide of 9.6 m high and high tide of 9.9 m high every 12 h.

  • El Kossier which starts its voyage with a bunker quantity of only 500 mt of main-engine fuel and 50 mt of auxiliary-engine fuel at the prices shown below Table 1, needs to call at Antwerp for bunkering of extra 500 mt main-engine fuel at $290/mt and 50 mt of auxiliary-engine fuel at $400/mt. This requires the ship to deviate 200 miles from its main route.

  • Crude Oil 2, as a commodity, is in fact incompatible with Crude Oil 5 and 7 which causes an extra cost of $5,000 for the cleaning of Sidi Kirear holds in Maracaibo.

According to the above-mentioned elements, the model suggests El Kosseir selects “Crude Oil 10” from Maracaibo to Riga, Safaga selects “Crude Oil 3” from Odessa to Shanghai (directly), followed (via Panama Canal) by “Crude Oil 7” from Maracaibo to Riga and Sidi Kirear selects “Crude Oil 8” from Shuaiba to Baltimore (directly), followed by “Crude Oil 6” from Maracaibo to Riga. Total gross profit per day is US$33,330. In comparison with the old results, the new shipping elements have changed the results for Sidi Kirear due to the tide and cargo incompatibility restrictions. Results of Safaga have indirectly changed because of the changes in the results of Sidi Kirear. The results of El Kosseir remain unchanged.

Again, upon reviewing the results, the ship owner requested that the analysis has to be made as to whether accelerating the ship speed will give better results. At medium speed, the model suggests the same results as the low speed level but with a gross profit per day decreased to US$32,472. At high speed, the model suggests El Kosseir selects “Crude Oil 1” from Shuaiba to Baltimore (directly), followed by “Crude Oil 10” from Maracaibo to Riga, Safaga selects “Crude Oil 4” from Odessa to Shanghai (directly) and Sidi Kirear selects “Crude Oil 8” from Shuaiba to Baltimore (directly), followed by “Crude Oil 6” from Maracaibo to Riga. The gross profit per day is increased to US$42,671.

6. Conclusion and future work recommendation

This paper has made SOS more viable by developing a system of cargo transport demand forecast, building an IT platform capable of processing large number of cargoes and ships in a reasonable time and introducing three new shipping elements. The new shipping elements include en-route ship bunkering, port calls in low tide and hold cleaning cost caused by incompatibility among cargoes.

Information displayed by Tables 1 to 5 and the analysis brought about them demonstrates that SOS is now becoming more viable and more supportive to ship owners in making sound shipping decisions. Table 1 showed that the shipowner is now able to forecast the cargo quantities transportable on his ships. Table 2 showed that the shipping problem may be upscaled in a reasonable time. Tables 3 to 5 of the case study and the analysis brought about them showed that the new shipping elements made the shipping problem more realistic. Despite all this support provided by SOS, it does not require the shipowner to have pre-existing knowledge on operations research or statistical methods. Without the need to repeat it in this paper, El Noshokaty (2013 and 2017A) has shown that, in interactive sessions, SOS is able to perform sensitivity and what-if analysis with regard to ship speed and fuel consumption, cargo quantity and freight and cargo handling rate and charges. By doing these sessions, SOS is more and more viable as the shipowner can validate the fixed parameters associated with ship and cargo characteristics.

Further recommendation is that stochastic and profit-per-day models need more attention. Cargo transport demand needs more study on the construction of probability distribution of the transport demand for main types of cargo.

Percentage increase forecast of some selected commodities for 2019

Commodity (SITC code) Reporter country Partner country Percentage increase forecast for 2019
Dairy products (02) China Hong Kong 8
Fish (03) Norway Denmark −1
Coffee (07) Brazil Germany 15
Live animals (00) Australia Japan −10
Vegetables (05) France Philippine 16
Petroleum products (33) Germany Hungary −7

Time taken by SOS to process the tramp 3-ship-30-cargo and 3-ship-40-cargo cases, with and without the decomposition and HPC

Decomposition and HPC 3-ship-30-cargo time in minutes 3-ship-40-cargo time in minutes
With 8 105
Without 20

Ship data

Tanker data item Ship 1 Ship 2 Ship 3
Deadweight in mt* (capacities other than cargo are ignored) 40,000 50,000 70,000
Weight in mt* per 1 meter of ship draught 3,921 4,428 5,112
Low, medium and high speed in knots 15, 17 and 19 14, 16 and 18 13, 15 and17
Main engine** laden fuel consumption in mt*/day 37, 54 and 75 35, 52 and 74 35, 55 and 79
Main engine** ballast fuel consumption in mt*/day 22, 32 and 44 22, 33 and 47 20, 31 and 45
Auxiliary engine*** fuel consumption in mt*/day 0.5 0.6 1
Heating fuel consumption in mt* of main engine**
fuel/day/100 mt* of cargo 0.125 0.11 0.1
Sues Canal dues, laden and ballast in US$ 158,960; 135,180 172,310; 146,560 185,650; 157,940
Panama Canal dues, laden and ballast in US$ 79,000; 62,900 98,250; 78,150 117,500; 93,400
Bosporus and Dardanelles dues in US$ 9,640 12,150 13,850
Running cost in US$/day 5,000 7,000 7,700
Notes:

*

mt = metric ton;

**

Fuel cost of main engine is $315/mt;

***

Fuel cost of auxiliary engine is $472.5/mt

Port data

Data item
Port name
Cost/call in US$
(lights, towage)
Cost/day in US$
(quay services)
Waiting days*
(anchor, idle)
Cargo handling
(mt/day)
Alexandria (Egypt) 1,500 150 0 34,000
Baltimore 12,000 1,200 0.3 40,000
Shuaiba (Kuwait) 8,000 800 0.5 37,000
Maracaibo 10,700 1,070 0.5 37,000
Odessa 10,000 1,000 0.5 35,000
Riga (Latvia) 11,000 1,100 0.3 35,000
Shanghai 9,000 900 0.4 35,000
Antwerp 10,000 1,000 0.5 37,000
Note:

*

Not part of any demurrage or dispatch time count

Cargo data

Data item cargo* Shipping event Load port Load laycan Discharge port Discharge laycan Weight in mt Freight in US$/mt**
Crude oil 1 Offered Shuaiba 1–10/10 Baltimore 1–11/11 40,000 50
Crude oil 2 Offered Shuaiba 20–27/10 Baltimore 20–27/11 60,000 60
Crude oil 3 Offered Odessa 5–15/10 Shanghai 5–15/11 35,000 40
Crude oil 4 Offered Odessa 3–16/11 Shanghai 3–16/12 40,000 50
Crude oil 5 Offered Maracaibo 5–15/12 Riga 20–30/12 30,000 30
Crude oil 6 Offered Maracaibo 20–28/11 Riga 10–25/12 45,000 35
Crude oil 7 Offered Maracaibo 1–10/12 Riga 20–30/12 40,000 40
Crude oil 8 Offered Shuaiba 1–31/10 Baltimore 1–30/11 51,000 50
Crude oil 9 Offered Odessa 1–30/11 Shanghai 1–31/12 42,000 45
Crude oil 10 Offered Maracaibo 1–30/11 Riga 1–30/11 36,000 35
Notes:

*All cargoes require heating. Crude oil 1, 2 and 8 are transported directly (10,147 miles with 1.5 days waiting) or via Suez Canal (8,602 miles with 2 days waiting), Crude oil 3, 4 and 9 are transported directly (14,169 miles with 1 day waiting) or via Suez Canal (8,264 miles with 1 day waiting) and Crude oil 5, 6, 7 and 10 are transported only directly (5,274 miles with 0.5 day waiting). Distance of ballast transport links may be found in any distance table (waiting days are assumed 0 for these links). All cargoes are sorted according to the shipping-event-date-and-time ascending order.

**Freight is FIO base, load or discharge laydays are restricted to 35,000 mt per day, reversible laydays are subject to demurrage rate of US$8,000 per day and dispatch rate of US$4,000 per day

Appendix. SOS voyager mathematical model and solution methodology

In this model, it is assumed that each ship starts its voyage at home port (open event) and returns back to its home port (close event). In this model let:

S = {1,2,3, […], s0} be the set of ships.

P = {1,2,3, […], p0} be the set of ports of a working trade area.

Q = {1,2,3, […], q0} be the set of cargoes available for transport between ports of this area. It is assumed that cargoes are compatible with the ship carrying them and can be mixed together on board the ship with ship stability maintained. Each cargo rQ has a loading event and a discharging event.

L = {1,2,3, […], l0} be a set of loading events, one for each cargo.

D = {1,2,3, […], d0} be a set of discharging events, one for each cargo.

F = {f} be a one-element set of open event f.

G = {g} be a one-element set of close event g.

E = LD be the set of load and discharge events, combined.

Ef = EF be the set of open, load and discharge events, combined.

Eg = EG be the set of load, discharge and close events, combined.

Efg = EfG be the set of open, load, discharge and close events, combined.

pi be port pP identified at event iEfg.

Z = {1, 2, 3, 4} be an index representing two combined positions: “pass or bypass Suez or Panama Canal” as alternative route position and “laden or ballast” as ship load position. Z element of “1” represents ship passing canal while in laden position, “2” represents ship bypassing canal while in laden position, “3” represents ship passing canal while in ballast position and “4” represents ship bypassing canal while in ballast position.

pijzk be the gross profit earned by ship kS on transport link ij while in position zZ. Gross profit equals freight plus demurrage (based on reversible or irreversible calculation), minus cooling/heating cost of cargo rQ at iL, minus handling cost of cargo rQ at iE, minus dispatch (based on reversible or irreversible calculation), minus port dues of port pP at iEf, where pipj and minus canal/strait dues and fuel consumption of main engine when sailing transport link ij while in position zZ, where pipj.

Tgk be voyage close day of ship kS.

Cgk be the cost of fuel consumption of auxiliary engine per day plus daily fixed cost of ship kS.

C0k be voyage fixed cost of ship kS, not considered elsewhere.

xijzk be the problem decision variable. It equals 1 if ship kS sails transport link ij while it is in position zZ, and it equals 0 otherwise. If xijzk=1 and iE, cargo rQ is loaded on board ship k, where i is its loading port or discharged from the ship if i is its discharging port. Likewise, if xijzk=1 and jE, cargo rQ is loaded on board ship k, where j is its loading port or discharged from the ship if j is its discharging port.

yi be another problem decision variable, alternative to xijzk. It equals 1 if xijzk=0 for all ships sailing all transport links to pick up cargo rQ at iL, and it equals 0 otherwise. Cargo rQ at iL is transported by a chartered-in ship in this case. Variable yi is introduced to represent the possibility of carrying a cargo at event i by a chartered-in ship rather than the owned ships, where yi = 1 in this case. If this happens, all the variables representing the possibility of carrying the cargo by the owned ships should equal to 0. For the chartered-in ship, let Pi be its voyage gross profit, ti be its voyage time, Ci0 be its voyage fixed cost and ti0 be its voyage fixed time. Each one of these parameters is to have a value ≠ 0 if the chartered-in ship is taken as an alternative and a value = 0 otherwise.

It is required to maximize sum of voyage gross profit per day for all ships, given by:

(1) G=kS(iEfjEgzZpijzkxijzkCgkTgkC0k)/Tgk+iL(PiyiCi0)/(tiyi+ti0)

Subject to:

Flow constraints

Using the above-mentioned denotations, the flow constraints can be formulated as follows:

  • The flow constraints which restrict the flow of transport links for each ship originating from open event to only one link at most, given by:

    (2) jEgzZxfjzk1,kS,

  • Flow constraints which restrict the flow of transport links for each ship toward event e ∈ E to be equal to the flow of transport links outward from this event, given by:

    (3) iEfzZxiezk=jEgzZxejzk,eE,andkS,

  • Flow constraints which restrict the flow of transport links for each ship toward load event l ∈ L of cargo r ∈ Q to be equal to the flow of transport links toward discharging event d ∈ D of same cargo, given by:

    (4) iEfzZxilzk=iEzZxidzk,lL,dD,landdareofsamecargorQ,andkS,

  • Flow constraints which prohibit the flow of transport link of each ship in two opposite directions, given by:

    (5) zZxijzk+zZxjizk1,i,jE,andkS,

  • Flow constraints which restricts the flow of transport link of each ship passing by the en-route bunkering port to only one link (optional):

    (6) iEfjEgzZxijzk=1,kS,

    where link i, j passes by the en-route bunkering port.

  • Flow constraints which restrict the flow of transport links for ship kS toward load event lL of cargo rQ to be equal to one if the cargo is booked to be carried by this ship, given by:

    (7) iEfzZxilzk=1,lL,l is of same cargo rQ, and kS,

  • Flow constraints which restrict the flow of transport links for ship kS toward discharging event dD of cargo rQ to one if the cargo is already carried by this ship, given by:

    (8) iEzZxidzk=1,dD,d is of same cargo rQ., and kS,

  • Flow constraints which restrict the flow of transport links of all ships toward loading event lL of cargo rQ plus their alternative decision of acquiring a charter-in ship, to only one at most, given by:

    (9) kSiEfzZxilzk+hlyl1,lL,hl=1 if yl is taken as an alternative decision and hl=0 otherwise.

Capacity constraints

Let:wi be weight of cargo rQ at event iE, in mt,

vi be volume of cargo rQ at event iE, in cum (if non-container),

ni be number of TEU of cargo rQ at event iE (if container), be the remaining dwt capacity of ship kS after load or discharge of cargo rQ at event iE, in mt,

W0k be the min weight remaining on board ship kS which keeps the ship in laden position,

Vik be the remaining volume capacity of ship kS after load or discharge of cargo rQ at event iE, in cum (if non-container),

Nik be the remaining TEU capacity of ship kS after load or discharge of cargo rQ at event iE (if container),

Wk be the dead weight capacity of ship kS,

Vk be the volume capacity of ship kS (if non-container) and

Nk be the TEU capacity of ship kS (if container).

Using the above-mentioned denotations, the capacity constraints can be formulated as follows:

  • Load remaining weight constraints which restrict remaining weight on board each ship at end event jE to be at least equal to remaining weight at start event iL of any transport link minus weight of cargo rQ at iL, given by:

    (10) WjkWikwizZxijzk,iL,jE, and kS, where zZxijzk=1,

Constraints (10) can be re-written as follows:

M(1zZxijzk)+WjkWikwizZxijzk,iL,jE and kS,
where M is a large number. So WjkWikwizZxijzk will hold true only when zZxijzk=1.
  • Load remaining volume constraints which restrict remaining volume on board each non-container ship at end event j ∈ E to be at least equal to remaining volume at start event i ∈ L of any transport link minus volume of cargo rQ at event iL, given by

    (11) VjkVikvizZxijzk,iL,jE,andkS,   where zZxijzk=1,

  • Load remaining TEU constraints which restrict remaining TEU on board each container ship at end event jE to be at least equal to remaining TEU at start event iL of any transport link minus TEU of cargo rQ at event iL, given by

    (12) NjkNiknizZxijzk,iL,jE,andkS,wherezZxijzk=1,

  • Discharge remaining weight constraints which restrict remaining weight on board each ship at end event jE to be at least equal to remaining weight at start event iD of any transport link plus weight of cargo rQ at event iD, given by:

    (13) WjkWik+wizZxijzk,iD,jE,andkS,wherezZxijzk=1,

  • Discharge remaining volume constraints which restrict remaining volume on board each non-container ship at end event jE to be at least equal to remaining volume at start event iD of any transport link plus volume of cargo rQ at event iD, given by:

    (14) VjkVik+vizZxijzk,iD,jE,andkS,wherezZxijzk=1,

  • Discharge remaining TEU constraints which restrict remaining TEU on board each container ship at end event jE to be at least equal to remaining TEU at start event iD of any transport link plus TEU of cargo rQ at event iD, given by:

    (15) NjkNik+nizZxijzk,iD,jE,andkS,wherezZxijzk=1,

  • Weight capacity constraints which restrict remaining weight on board each ship after discharge of all cargoes at end event gG so that it does not exceed ship dwt capacity, given by:

    (16) WikWk,iD,andkS,wherez=3,4xigzk=1,gG,

  • Volume capacity constraints which restrict remaining volume on board each non-container ship after discharge of all cargoes at end event gG so that it does not exceed ship volume capacity, given by:

    (17) VikVk,iD,andkS,wherez=3,4xigzk=1,gG,

  • TEU capacity constraints which restrict remaining TEU on board each container ship after discharge of all cargoes at end event gG so that it does not exceed ship TEU capacity, given by:

    (18) NikNk,iD,andkS,wherez=3,4xigzk=1,gG,

  • Laden-or-ballast load position constraints which restricts ship load position to either laden or ballast. Ship is assumed to be in laden position on transport link ij if iL, and is considered so if iD and remaining weight on board the ship at this event is greater or equal to the min remaining weight W0k, which is given by:

    (19) WikW0k,iD,andkS,wherez=1,2xijzk=1,jE,

Time constraints

Let:ai be laycan open day of cargo rQ at event iE,

bi be laycan close day of cargo rQ at event iE,

tik be the number of days taken to handle cargo rQ at event iE by ship kS plus waiting days at port pP at event iE,

tijzk be the number of days taken to sail the transport link from event iEf to event jEg by ship kS while it is in position zZ, plus waiting days at sea, where pipj,

Tik be the arrival day of ship kS at event iEfg, assuming Tfk=0,

T0k be voyage fixed days of ship kS, not considered elsewhere,

Tsk be voyage slack days of ship kS, if it arrives earlier than ari, aggregated for all rQ and iE,

Tk be total allowable days of ship kS,

Using the above-mentioned denotations, the time constraints can be formulated as follows:

  • Event arrival time constraints which restrict arrival day at end event jEg to be at least equal to arrival day at start event iEf of any transport link plus handling days of cargo rQ at iEf, waiting days in port pP at iEf, sailing days on link ij, and waiting days at sea, given by:

    (20) TjkTik+ti+zZtijzkxijzk,iEf,jEg,andkS,wheretifzk=0,andzZxijzk=1,

  • Event time precedence constraints which control arrival times so that arrival day at discharge event dD succeeds arrival day at load event lL of cargo rQ, given by:

    (21) TdkTlk,lL,dD,l and dareofsamecargorQ,andkS, where iEzZxidzk=1

  • Time window constraints which restrict ship arrival day at event jE so that it does not violate cargo laycan open and close days at this event, given by:

    (22) Tjkai,jE,andkS,whereiEfzZxijzk=1,
    (23) Tjkbi,jE,andkS,whereiEfzZxijzk=1,

  • Closing time constraints which restrict final closing day for each ship so that it equals total cargo handling days and waiting days in port, sailing days and waiting days at sea, waiting days before cargo open day, and voyage fixed days, given by:

    (24) iEfjEgzZ(tik+tijzk)xijzk+Tsk+T0k=Tgk,kS,

  • Allowable closing time constraints which restrict closing day for each ship to a maximum allowable days, given by:

    (25) TgkTk,gG,kS,wherez=3,4xigzk=1andiD,

Non-negativity and integrality constraints

Non-negativity constraints of continuous variables, given by:

(26) Wik,Vik,Nik,Tik0,iEg,kS,Tsk0,kS,
  • integrality constraints of integer variables, given by:

    (27) xijzk=0,1,iEf,jEg,kS,
    zZxijzk1,iEf,jEg,kS,
    (28) yi=0,1,iL.

The stochastic version (or chance-constrained as named by Charnes and Cooper, 1962) of the above-mentioned model can be described using the following simple denotations, assuming one ship and one cargo. The transport demand of this cargo is unconfirmed, assumed to be random variable having a known probability distribution. The probability distribution is the marginal distribution of demand. Let:d be the deterministic cargo transport demand, expressed in quantity units,

D be the random cargo transport demand, expressed in quantity units,

P be the least probability ship owner stipulates to transport cargo within D and,

y be the quantity of cargo to be transported.

Transport demand constraint implied by the model is given by:

(29) yd¯,

In the chance-constrained model, this constraint reads: the probability of transporting cargo within demand; Prob. {y D}, has to be greater or equal to P, as indicated by:

(30) Prob.{yD}P,

The chance constraint is considered when the cargo transport demand is a random variable, where y is the quantity of cargo to be transported, D is the cargo transport demand and P is a probability value. In other words, it says: the probability of transporting a cargo within its demand has to be at least equal to P. If P can be anticipated, then following the argument mentioned next, the value of y, say y can be determined, which is called the deterministic-equivalent value of y.

Constraint (30) is called “chance-constraint.” If at D = d the descending cumulative probability of transport demand of cargo has a value just greater or equal to P, then (28) in this case implies:

(31) yd¯

Equation (31) is the deterministic-equivalent constraint to Equation (30). It is different from equation (29). The difference is that d in equation (29) is the quantity of cargo r confirmed offer, while d in equation (31) is a deterministic-equivalent quantity of cargo random demand, as described earlier. To illustrate, assume for discrete cargo demand D, Prob. {D < 5 units} = 0.0, Prob. {D = 5 units} = 0.2, Prob. {D = 10 units} = 0.5, Prob. {D = 15 units} = 0.3 and Prob. {D >* 15 units} = 0.0. According to the additive rule of the probability theory, the demand descending cumulative probability distribution reads: Prob. {D ≥ 5 units} = 0.2 + 0.5 + 0.3 + 0.0 = 1.0, 0.8 ≤ Prob. {D ≥* 10 units} < 1.0 and 0.3 ≤ Prob. {D ≥ 15 units} < 0.8. Now suppose P = 0.9. This value falls in second class, which implies a deterministic-equivalent demand value of 10 units (neither 5 nor 15 units), i.e. at d =*10.

As defined earlier, the chance-constrained model is exactly equations (1) to (28) after converting implied equations (29) to (31). Use the same illustration mentioned above to convert quantities in Table 4 to deterministic-equivalent quantities as shown in Table 5.

The model is solved by the state-of-the-art block-angular linear ratio programming algorithm (El Noshokaty, 2014). In this algorithm, the problem mathematically takes a block-angular form, with a block of objective and constraints assigned to each ship. The model is transformed to a linear form and solved by a modified mixed continuous 0–1 linear programming algorithm. In this algorithm, a modified branch and bound technique is used to solve the mixed continuous 0–1 linear program. At each node in the branch, the problem is decomposed into sub-problems, one for each ship, and then solved by a modified simplex method as indicated by the algorithm. The reason for formulating the model the way mentioned earlier is that it is amenable to the above-mentioned techniques and methods, which are highly efficient and reliable, even if the model has a very large number of variables and constraints.

References

Bagighni, S. (2012), “Volume estimation models for generation and attraction of freight commodity groups using regression analysis”, PhD dissertation. University of Alabama, Tuscaloosa.

Boland, S. (2018), “Freight demand forecasting models: the different approaches”, A master’s thesis presented to Louvain School of Management (LSM), Belgium.

Brocker, J., Korzhenevych, A. and Riekhof, M. (2012), “Predicting freight flows in a globalizing world”, Research in Transportation Economics, Vol. 31 No. 1, pp. 37-44.

Cantillo, V.M., Jaller, M.A. and Holguin-Veras, J. (2012), “Development of National Freight Demand Model with Limited Data and Resources”, Presented at 91st Annual Meeting of the Transportation Research Board, Washington, D.C.

Charnes, A. and Cooper, W. (1962), “Programming with linear fractional functionals”, Naval Research Logistics Quarterly, Vol. 9 Nos 3/4, pp. 181-186. No

Cheong, I. and Cho, J. (2013), “The impact of Korea’s FTA network on seaborne logistics”, Maritime Policy and Management, Vol. 40 No. 2, pp. 146-160.

Chou, C.C., Chu, C.W. and Liang, G.S. (2008), “A modified regression model for forecasting the volumes of Taiwan's import containers”, Mathematical and Computer Modelling, Vol. 47 Nos 9/10, pp. 797-807.

Christiansen, M., Hooghiemstra, J., Kroon, L., Odijk, M., Salomon, M. and Zwaneveld, P. (1999), “Decomposition of a combined inventory and time constrained ship routing problem”, Transportation Science, Vol. 33 No. 1, pp. 3-16.

Dantzig, G. and Wolfe, P. (1960), “Decomposition principle for linear programs”, Operations Research, Vol. 8 No. 1, pp. 101-111.

El Noshokaty, S. (1988), “Optimum Ship Selection of Ports, Route, and Cargoes”, PhD thesis, University of Wales.

El Noshokaty, S. (2013), “Shipping optimisation systems (SOS): liner optimisation perspective”, International Journal of Shipping and Transport Logistics, Vol. 5 No. 3, pp. 237-256.

El Noshokaty, S. (2014), “Block-angular linear ratio programmes”, International Journal of Operational Research, Vol. 19 No. 3, pp. 338-357.

El Noshokaty, S. (2015), “Shipping optimisation systems (SOS): port development perspective”, presented to the Conference on Port and Logistics Connectivity, HongKong, May 21-22.

El Noshokaty, S. (2017A), “Shipping optimisation systems (SOS): tramp optimisation perspective”, Journal of Shipping and Trade, Vol. 2 No. 1, pp. 1-36, doi: 10.1186/s41072-017-0021-y.

El Noshokaty, S. (2017B), Linear Optimization of Operational Systems: New Extensions to the Coupled Systems Applied to Liner and Tramp Shipping in Maritime Cargo Transport. Create Space, Amazon, USA.

El Noshokaty, S. (2018a), “Global profit optimization in multiple production systems of time-sensitive production cycle”, Journal of Advanced Research in Economics and Business Management, Vol. 5 Nos 1/2, pp. 1-4.

El Noshokaty, S. (2018b), “Global optimization in multiple production systems employing different mixes of production factors in the production cycle”, Journal of Advanced Research in Economics and Business Management, Vol. 5 No. 3, pp. 1-7.

El Noshokaty, S. (2018c), “Tramp shipping optimization: a critical review”, Global Journal of Management and Business Research, Vol. 18 No. 1, pp. 1-13.

El Noshokaty, S. (2019a), “The implications of the stochastic gross-profit-per-day objective on the cargo ship profitability, capacity, and speed”, Maritime Business Review, Vol. 4 No. 3, doi: 10.1108/MABR-04-2019-0016.

El Noshokaty, S. (2019b), “The coupled operational systems: a linear optimisation review”, Journal of Economic Science Research, Vol. 2 No. 2, pp. 40-49.

Fagerholt, K. and Lindstad, H. (2007), “TurboRouter: an interactive optimisation-based decision support system for ship routing and scheduling”, Maritime Economics and Logistics, Vol. 9 No. 3, pp. 214-233.

Fite, J.T., Taylor, G.D., Usher, J.S., English, J.R. and Roberts, J.N. (2002), “Forecasting freight demand using economic indices”, International Journal of Physical Distribution and Logistics Management, Vol. 32 No. 4, pp. 299-308.

Holguin-Veras, J., Jaller, M., Destro, L., Ban, X., Lawson, C. and Levinson, H.S. (2011), “Freight generation, freight trip generation, and the perils of using constant trip rates”, Transportation Research Record: Journal of the Transportation Research Board, Vol. 2224 No. 1, pp. 68-81.

Lee, T.C., Wu, C.H. and Lee, P.T.W. (2011), “Impacts of the ECFA on seaborne trade volume and policy development for shipping and port industry in Taiwan”, Maritime Policy and Management, Vol. 38 No. 2, pp. 169-189.

Levine, B., Nozick, L. and Jones, D. (2009), “Estimating an origin-destination table for US imports of waterborne containerised freight”, Transportation Research Part E: Logistics and Transportation Review, Vol. 45 No. 4, pp. 611-626.

Marzano, V. and Papola, A. (2004), “Modelling freight demand at a national level: theoretical developments and application to Italian demand”, In Proceedings of European Transport Conference, Strasbourg, France.

Nguyena, D. and Walther, T. (2018), “Modeling and forecasting commodity market volatility with long-term economic and financial variables”, MPRA Paper No. 84464, Online at https://mpra.ub.uni-muenchen.de/84464/

PIERS (2020), https://ihsmarkit.com/products/piers.html

Profilidis, V. and Botzoris, G. (2018), “Modeling of transport demand: analyzing, calculating, and forecasting transport demand, ScienceDirect”.

Shibasaki, R. and Watanabe, T. (2012), “Future forecast of trade amount and international cargo flow in the APEC region: an application of trade-logistics forecasting model”, Asian Transportation Studies, Vol. 2 No. 2, pp. 194-208.

Vilhelmsen, C., Larsen, J. and Lusby, R.M. (2017), “Tramp ship routing and scheduling with voyage separation requirements”, Or Spectrum, Vol. 39 No. 4, pp. 1-31.

Corresponding author

Said El Noshokaty can be contacted at: selnoshokaty@elesteshary.com

About the author

After a Bachelor’s degree in commerce, the author received higher diplomas and a master’s degree in Operations Research, Statistical methods, and Management Systems from Cairo University and American University in Cairo (AUC), Egypt, and a Ph.D. in Operations Research in shipping from the University of Wales Institute of Science and Technology (UWIST), UK. The author has a career path in computers and information systems in both business in the National Cash Register (NCR) and education in the Arab Academy for Science and Technology and Maritime Transport (AASTMT), Egypt. He has been teaching - as a visiting professor - at the Central Michigan University (CMU), USA. He has several publications in Operations Research and its applications in shipping of cargo in maritime transport.The author is now Professor of Information Systems. His primary interest is in developing OR-based information systems in cargo transportation.