Ship routing and scheduling systems: forecasting, upscaling and viability

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.

Citation

El Noshokaty, S. (2021), "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

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.

Table 1.

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

Table 2.

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	−

Table 3.

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

Table 4.

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

Table 5.

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, […], s₀} be the set of ships.

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

Q = {1,2,3, […], q₀} 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 r ∈ Q has a loading event and a discharging event.

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

D = {1,2,3, […], d₀} 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 = L ∪ D be the set of load and discharge events, combined.

E_f = E ∪ F be the set of open, load and discharge events, combined.

E_g = E ∪ G be the set of load, discharge and close events, combined.

E_fg = E_f ∪ G be the set of open, load, discharge and close events, combined.

p_i be port p ∈ P identified at event i ∈ E_fg.

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 k ∈ S on transport link ij while in position z ∈ Z. Gross profit equals freight plus demurrage (based on reversible or irreversible calculation), minus cooling/heating cost of cargo r ∈ Q at i ∈ L, minus handling cost of cargo r ∈ Q at i ∈ E, minus dispatch (based on reversible or irreversible calculation), minus port dues of port p ∈ P at i ∈ E_f, where p_i ≠ p_j and minus canal/strait dues and fuel consumption of main engine when sailing transport link ij while in position z ∈ Z, where p_i ≠ p_j.

Tgk be voyage close day of ship k ∈ S.

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

C0k be voyage fixed cost of ship k ∈ S, not considered elsewhere.

xijzk be the problem decision variable. It equals 1 if ship k ∈ S sails transport link ij while it is in position z ∈ Z, and it equals 0 otherwise. If xijzk =1 and i ∈ E, cargo r ∈ Q 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 j ∈ E, cargo r ∈ Q is loaded on board ship k, where j is its loading port or discharged from the ship if j is its discharging port.

y_i 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 r ∈ Q at i ∈ L, and it equals 0 otherwise. Cargo r ∈ Q at i ∈ L is transported by a chartered-in ship in this case. Variable y_i is introduced to represent the possibility of carrying a cargo at event i by a chartered-in ship rather than the owned ships, where y_i = 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 P_i be its voyage gross profit, t_i be its voyage time, C_i0 be its voyage fixed cost and t_i0 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 =∑k∈S(∑i∈Ef ∑j∈Eg ∑z∈Z pijzk xijzk−Cgk  Tgk−C0k)/Tgk+∑i∈L( Pi  yi − Ci0 )/(ti  yi  +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) ∑j∈Eg ∑z∈Z xfjzk≤1,k∈S,

• 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) ∑i∈Ef ∑z∈Z xiezk=∑j∈Eg ∑z∈Z xejzk, e∈E,and k∈S,

• 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) ∑i∈Ef ∑z∈Z xilzk=∑i∈E∑z∈Zxidzk, l∈L, d∈D, l and d are of same cargo r∈Q, and k∈S,

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

  (5) ∑z∈Z xijzk +∑z∈Z xjizk ≤1,i, j∈E,andk∈S,

• 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) ∑i∈Ef ∑j∈Eg ∑z∈Z xijz k=1, k∈S,

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

• Flow constraints which restrict the flow of transport links for ship k ∈ S toward load event l ∈ L of cargo r ∈ Q to be equal to one if the cargo is booked to be carried by this ship, given by:

  (7) ∑i∈Ef ∑z∈Z xilzk = 1, l∈L, l is of same cargo  r∈Q, and k∈S,

• Flow constraints which restrict the flow of transport links for ship k ∈ S toward discharging event d ∈ D of cargo r ∈ Q to one if the cargo is already carried by this ship, given by:

  (8) ∑i∈E  ∑z∈Z xidzk=1, d∈D, d is of same cargo  r∈Q., and k∈S,

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

  (9) ∑k∈S ∑i∈Ef ∑z∈Z xilz k+hl yl  ≤1, l∈L, hl=1 if yl is taken as an alternative decision and hl=0 otherwise.

Capacity constraints

Let:w_i be weight of cargo r ∈ Q at event i ∈ E, in mt,

v_i be volume of cargo r ∈ Q at event i ∈ E, in cum (if non-container),

n_i be number of TEU of cargo r ∈ Q at event i ∈ E (if container), be the remaining dwt capacity of ship k ∈ S after load or discharge of cargo r ∈ Q at event i ∈ E, in mt,

W0k be the min weight remaining on board ship k ∈ S which keeps the ship in laden position,

Vik be the remaining volume capacity of ship k ∈ S after load or discharge of cargo r ∈ Q at event i ∈ E, in cum (if non-container),

Nik be the remaining TEU capacity of ship k ∈ S after load or discharge of cargo r ∈ Q at event i ∈ E (if container),

W^k be the dead weight capacity of ship k ∈ S,

V^k be the volume capacity of ship k ∈ S (if non-container) and

N^k be the TEU capacity of ship k ∈ S (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 j ∈ E to be at least equal to remaining weight at start event i ∈ L of any transport link minus weight of cargo r ∈ Q at i ∈ L, given by:

  (10) Wjk≥Wik−wi ∑z∈Z xijzk, i∈L, j∈E, and  k∈S, where  ∑z∈Zxijzk=1,

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

M(1−∑z∈Z xijzk)+ Wjk ≥ Wik−wi ∑z∈Z xijzk, i∈L, j∈E and  k∈S,

where M is a large number. So  Wjk≥Wik−wi∑z∈Zxijzk will hold true only when  ∑z∈Zxijzk= 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 r ∈ Q at event i ∈ L, given by

  (11)  Vjk≥ Vik−vi∑z∈Z xijzk, i∈L,j∈E,and k∈S,   where  ∑z∈Zxijzk=1,

• Load remaining TEU constraints which restrict remaining TEU on board each container ship at end event j ∈ E to be at least equal to remaining TEU at start event i ∈ L of any transport link minus TEU of cargo r ∈ Q at event i ∈ L, given by

  (12)  Njk ≥ Nik−ni∑z∈Z xijzk, i∈L,j∈E,and k∈S,where ∑z∈Z xijzk=1,

• Discharge remaining weight constraints which restrict remaining weight on board each ship at end event j ∈ E to be at least equal to remaining weight at start event i ∈ D of any transport link plus weight of cargo r ∈ Q at event i ∈ D, given by:

  (13)  Wjk≥Wik+wi∑z∈Z xijzk, i∈D,j∈E,and k∈S,where ∑z∈Z xijzk=1,

• Discharge 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 ∈ D of any transport link plus volume of cargo r ∈ Q at event i ∈ D, given by:

  (14)  Vjk≥ Vik+vi∑z∈Z xijzk, i∈D,j∈E,and k∈S,where ∑z∈Zxijzk=1,

• Discharge remaining TEU constraints which restrict remaining TEU on board each container ship at end event j ∈ E to be at least equal to remaining TEU at start event i ∈ D of any transport link plus TEU of cargo r ∈ Q at event i ∈ D, given by:

  (15)  Njk≥ Nik+ni∑z∈Z xijzk, i∈D,j∈E,and k∈S,where ∑z∈Zxijzk=1,

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

  (16) Wik≥Wk, i∈D,and k∈S,where ∑z=3,4xigzk=1,g∈G,

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

  (17) Vik≥Vk, i∈D,and k∈S,where ∑z=3,4xigzk=1,g∈G,

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

  (18) Nik≥Nk, i∈D,and k∈S,where ∑z=3,4xigzk=1,g∈G,

• 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 i ∈ L, and is considered so if i ∈ D 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) Wik≥W0k, i∈D,and k∈S,where ∑z=1,2xijzk=1, j∈E,

Time constraints

Let:a_i be laycan open day of cargo r ∈ Q at event i ∈ E,

b_i be laycan close day of cargo r ∈ Q at event i ∈ E,

tik be the number of days taken to handle cargo r ∈ Q at event i ∈ E by ship k ∈ S plus waiting days at port p ∈ P at event i ∈ E,

tijzk be the number of days taken to sail the transport link from event i ∈ E_f to event j ∈ E_g by ship k ∈ S while it is in position z ∈ Z, plus waiting days at sea, where p_i ≠ p_j,

Tik be the arrival day of ship k ∈ S at event i ∈ E_fg, assuming Tfk=0,

T0k be voyage fixed days of ship k ∈ S, not considered elsewhere,

Tsk be voyage slack days of ship k ∈ S, if it arrives earlier than a_ri, aggregated for all r ∈ Q and i ∈ E,

T^k be total allowable days of ship k ∈ S,

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

• Event arrival time constraints which restrict arrival day at end event j ∈ E_g to be at least equal to arrival day at start event i ∈ E_f of any transport link plus handling days of cargo r ∈ Q at i ∈ E_f, waiting days in port p ∈ P at i ∈ E_f, sailing days on link ij, and waiting days at sea, given by:

  (20)  Tjk≥Tik+ti+∑z∈Z tijz kxijzk, i∈Ef,j∈Eg, and k∈S,where tifzk=0, and ∑z∈Zxijzk=1,

• Event time precedence constraints which control arrival times so that arrival day at discharge event d ∈ D succeeds arrival day at load event l ∈ L of cargo r ∈ Q, given by:

  (21)  Tdk≥Tlk, l∈L, d∈D, l and d are of same cargo  r∈Q, and  k∈S, where ∑i∈E∑z∈Zxidzk=1

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

  (22)  Tjk≥ai, j∈E,and k∈S,where∑i∈Ef∑z∈Zxijzk=1,

  (23)  Tjk≤bi,  j∈E,and k∈S,where∑i∈Ef∑z∈Zxijzk=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) ∑i∈Ef∑j∈Eg∑z∈Z(tik+ tijzk ) xijzk + Tsk+T0k=Tgk, k∈S,

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

  (25) Tgk≤Tk, g∈G, k∈S,where ∑z=3,4xigzk=1 and i∈D,

Non-negativity and integrality constraints

Non-negativity constraints of continuous variables, given by:

(26) Wik,Vik,Nik,Tik≥0,i∈Eg, k∈S,Tsk≥0,k∈S,

• integrality constraints of integer variables, given by:

  (27) xijzk=0,1, i∈Ef, j∈Eg,k∈S,

  ∑z∈Zxijzk≤1, i∈Ef, j∈Eg, k∈S,

  (28) yi =0, 1, i∈L.

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) y≤d¯,

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. { y≤D}≥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) y≤d¯

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.