Sign Out
Logged In:
 
 
 
 
 
Tab Image

Ship Scheduling of Fertilizer Products

by Mike Fox and Dick Herden

This article describes a Mixed Integer Programming model to schedule ships with a variety of fertilizer products into eight ports on Australia's eastern and southern seaboards. The objective is to minimise freight, discharge and inventory holding costs while taking into account demand for product and warehousing constraints. Major planning decisions are made on a monthly basis for a 12-15 month planning horizon. To improve run-time performance extra integer variables are introduced to provide strong cuts and binary variables are introduced gradually throughout the planning horizon over several optimisation runs. The model is used for operational planning and budgetary purposes and interfaces to the outside world through a friendly matrix generator and a modern spreadsheet system.

-oo0oo-

Introduction and background

Incitec are a leading supplier of fertilizer to the Australian agricultural market and deal through major coastal distribution centres located on Australia's eastern and southern seaboards (see Figure 1). Each distribution centre is a navigable port and comprises warehousing and bagging facilities to supply local and inland properties via franchised dealers. In addition the centres at Brisbane and Newcastle each have a production capability for ammonia and either urea or ammonium nitrate. This paper is concerned with the supply of 4 ammonia products, MAP (~95000t p.a.), SMAP (50000t), DAP (150000t) and TSP (25000t), all supplied from Tampa, Florida.


Figure 1: Suppliers and Distribution Centres

The Logistics department are responsible for providing monthly shipping schedules of these products and they currently use ExcelTM spreadsheets to do this. Table 1 is indicative of DAP schedules for two distribution centres, Mackay and Brisbane. The table shows a pattern of opening stock, imports, usage and closing stock for each month in a 12 month planning horizon. This is repeated for each product at each centre and represents potentially 384 (= 4 products x 8 distribution centres x 12 months) import cells for consideration. The scheduler's job is to allocate values to the import rows of the spreadsheet, each import representing a product shipment. This entails deciding in which months to allocate ships, where to source the products (only Tampa for this study), the tonnage of each product and the quantity of product to be discharged at each centre. At the same time the scheduler must take care to satisfy expected product usage, warehouse maximum stock level constraints and various restrictions concerning minimum and maximum load and discharge tonnages for each product.

  AUG SEP OCT NOV DEC JAN FEB MAR APR MAY JUN JUL YEAR
                           
MKY DAP                          
OPENING STOCKS 983 3807 2442 1142 326 52 4091 4006 3769 3075 2399 1944 983
IMPORT 4250 0 0 0 0 4150 0 0 0 0 0 0 8400
USAGE 1426 1365 1300 816 274 111 85 237 694 676 455 954 8393
CLOSING STOCKS 3807 2442 1142 326 52 4091 4006 3769 3075 2399 1944 990 990
                           
BNE DAP                          
OPENING STOCKS 916 2539 431 2019 914 166 1241 244 3632 2097 297 2392 916
IMPORT 3650 0 3350 0 0 1800 0 4500 0 450 3400 0 17150
USAGE 2027 2108 1762 1105 748 725 997 1112 1535 2250 1305 1516 17190
CLOSING STOCKS 2539 431 2019 914 166 1241 244 3632 2097 297 2392 876 876
Table 1: Extract from a shipping plan

Incitec have known for many years that this problem can be formulated as a linear programme and early attempts to solve it were made by the supply manager in the late 1970's. Technology at that time relied on mainframe LP packages and the facilities available to Incitec often meant waiting for a weekend time-slot, with runs on simplified models taking over 24 hours.

The advent of modern PC based LP packages has revived interest and a new model has been developed using the XPRESS-MP1 matrix generator and optimisation package running on an Intel Pentium based PC. Coupled with ExcelTM spreadsheets, the new system now provides a fast engine to generate potential schedules which are linked to an interface already familiar to the users.

Model development – major costs

From the schedulers viewpoint, manually producing any schedule that meets the expected usage pattern and satisfies the major constraints is a difficult and time consuming task. To generate a schedule that minimises shipping costs as well is generally impossible by hand, although hard won experience produces satisfactory schedules.

The major costs involved in shipping product are:

  • Product Price
  • Freight
  • Port Charges
  • Inventory

An element of fixed and variable costs can be attributed to each of these items and while this model deals predominantly with the variable component, the two are often combined to provide a complete picture of overall costs.

Product price

In order to ensure the certainty of delivery Incitec negotiate fixed term contracts with their suppliers for a minimum tonnage in a 12 month period. However, fertilizer prices are decided on both a contracted and spot basis. Products are sold on the world market as commodities and prices can vary by up to about 50% over 12 months. An astute buyer can take advantage of these variations provided a) that s/he can forecast the changes and b) that stockholding capacity is sufficient to accumulate stock ahead of a price rise. In practice, the company has decided there are more pressing problems such as demand forecasting in the face of variable rainfall which are more immediate and tend to override any possible gains from an elusive price forecast. Nevertheless, the model has a provision for varying product prices on the basis that even the smallest gain in this area can give the company substantial cost savings.

Freight costs

Freight costs are a reflection of negotiated shipping contracts:


Figure 2

The contract specifies 4 potential ship sizes, 25000t, 29000t, 33500t and 43500t, here represented by T1, T2, T3, T4. These sizes are not absolute and they can be varied up or down at the ship owners discretion. This variation is called MOLOO (more or less – owners option) and is often about 5%. In practice it means that tonnages stated in the contract can be increased by about 5%. The contract can also allow for "excess" tonnage, in particular between sizes T3 and T4. Unit costs C1, C2, C3, C4 are expressed in $US/tonne. C4 is the excess tonnage cost for ships above 33500 tonnes (T3).

The ship owner will always charge on the basis of a full ship so that although the costs appear variable (ie $/tonne), in practice they are fixed and dependent on the ship sizes chosen.

In order to model an instance of the contract, binary variables A1, A2, A3 are introduced to decide the tonnes and costs as follows:

Define tk to represent tonnage if ship size Sk is chosen. E is excess tonnage, assuming in this case that a ship of size S3 or larger is chosen. The following constraints resolve the tonnes and costs by using a special ordered set, which specifies that only one of Ak can be non-zero.

A1 + A2 + A3 1 (special ordered set)

t1 S1 A1, t2 S2 A2,

t3 S3 A3, E (S4 – S3 ) A3,

Tonnes = t1 + t2 + t3 + E

Cost = C1 S1 A1 + C2 S2 A2 + C3 S3 A3 + E C4

Discharge costs

The shipping contract is written on the basis of one load port and one discharge port. There is a flat fee of approximately $50 000 for each additional load or discharge port. For this model there is only one source port (Tampa), so the charge only comes into effect off-loading in Australian ports. For example, a ship carrying products to Cairns, Mackay, Brisbane and Newcastle would incur a total of $150 000 in multi port charges. Comparative freight charges are of the order of $500 000.

These costs are modelled by summing the number of port discharges, then subtracting the number of ships and multiplying the result by $50 000.

Inventory holding costs

Warehouse capacities vary between 3000 tonnes and 12000 tonnes depending on the product and distribution centre. The demand for fertilizer depends entirely on the growing season and rainfall, and forecasting demand is a particularly difficult exercise. There is a natural tendency to ensure plenty of stock is to hand for the growing season. The opportunity cost is currently set to 8% per annum of stock value, leading to an overall cost of approximately $500 000 in the cost equation. This rate provides a buffer of approximately 4% above prevailing interest rates (4%) to cover insurance etc.

Total holding costs are modelled by multiplying end-of-month stock levels by the product price at the nominal interest rate (8% pa).

Model development - constraints

The overall scheduling objective is to minimise costs comprising freight (~$6.5M), discharges (~$1M) and inventory (~$½M). These costs compete and the model calculates an economic balance that minimises the overall total cost, subject to the following constraint classes:

a) stock levels
b) minimum discharge tonnage
c) ship holds
d) number of ships per month

a) Stocks are constrained by warehouse capacities at the distribution centres. There is also a need to have sufficient stock on hand at all times. In practice and because this is a multi-period model month-end stocks are used as a measure of adequacy. These stock levels must be at least a given proportion of the next months expected usage (usually 2 weeks expected demand).

b) For a ship to discharge at a port, a reasonable minimum quantity of all products must be unloaded. For example, to unload 100 tonnes from a 25000 tonne ship would be uneconomic. In this model the minimum discharge is nominally set to 2000 tonnes, but is data driven via the controlling spreadsheet application.

c) Bulk carrier ships usually have 5 or 6 holds and because of the shape of a ship, fore and aft holds are generally smaller than centre holds. A ship can carry several bulk products, but only one product per hold. To ensure that suitable product quantities are loaded the model assumes a minimum hold size of approximately 15% of total ship size.

d) A general formulation would allow for several ships per month, but this formulation limits the number of ships to a maximum of 1. Over a period of 15 months experience and overall tonnage suggest there are likely to be between 7 and 9 ships, with only one or two of those months requiring more than one ship. In practice, these high demand months are broken down into fortnightly periods so that a restriction of one ship per period is maintained.

A complete model formulation is given in the appendix.

Implementation

The model is implemented as a mixed integer program with approximately 1300 rows and 200 binary variables for a 15 period model. The overall size of the model is not large, but the complexity is considerable because the three major costs compete strongly and large (but loosely associated) sections of the search tree must be examined. It was realised early in the analysis that a practical heuristic approach would be needed to compete with current solutions.

In order to speed up the search, two useful techniques were implemented:

  1. Extra integer variables2 were introduced to create strong cuts.
  2. Integer and binary variables are initially relaxed for later periods in the model.

Early experimentation with the model showed that a good deal of time was consumed branching on low priority binary variables. To manage the branching process the XPRESS-MP package provides priority values that can be applied to integer variables (lowest value means highest priority) and these were combined with new integer variables to represent the key decisions to be made in the process. The new variables were, in order of importance:

  • Total number of ships, ST (priority 1)
  • Total number of discharges, SD (priority 3)
  • The number of products on a ship, for each period, SPt (priority 8)

Once implemented, these new integer variables were clearly evident early in the branching process and helped in a significant way to prune the search tree and reduce run times. Priority values were also applied to the key binary variables representing ship arrival in each month (Tt, priority 5), product supply (Ppt, priority 40) and distribution centre discharge (Dct, priority 50 to 100). See the Appendix for details of these variables.

However, this technique was not sufficient in itself to guarantee good solutions quickly. The key to faster solutions is to reduce the number of binary variables.

To do this in the 15-period case, binary and integer variables defined for periods 1 to 15 were fixed,

Optimisation
Pass
Fixed Resolved
To 0 - 1
Relaxed Total Cost ($)
1 - 1 – 4 5 – 15 7 482 000
2 1 – 3 4 – 7 8 – 15 7 626 000
3 1 – 6 7 – 10 11 – 15 7 701 000
4 1 – 9 10 – 13 14 – 15 7 814 000
5 1 - 12 13 - 15 - 8 088 000
Table 2: Time periods for fixing, resolving and relaxing integer variables

relaxed or resolved to 0-1 values in five or more optimisation passes. Table 2 shows an example run, beginning with a continuous solution of $ 7 121 000.

This scheme produced good schedules in 2 hours computing processing and, while the approach is sub-optimal, each optimisation pass was solved to optimality, the overall results improving on manual solutions by approximately $400 000. This contrasts with the global approach (resolve all 15 time periods) which is optimal, but slow to produce good schedules. An overnight global run on the same data set produced 106 branch and bound nodes in 10 hours on a 200MHz Pentium Pro. It found a solution with cost $ 10 740 000 after 4 hours and 4 x 105 nodes, but could not improve on this result in the remaining time.

From a set-up and presentation viewpoint it is important to get the LP solution file back into a system which can be readily manipulated and evaluated. At all stages data connectivity is handled via an ODBCTM connection to an ExcelTM spreadsheet. The XPRESS-MP matrix generator system provides the means to easily pick up values for the important variables and display these in a spreadsheet table. To handle the fixing of integer variables a separate worksheet was set up under the control of a macro to store the status and values of the variables for subsequent optimisation passes. LP-MODEL, the matrix generator supporting the modelling process, provides a good range of input/output and algebraic facilities for manipulating spreadsheet data.

Conclusions

This shipping model, first conceived 20 years ago, has only recently come of age. Earlier attempts at a solution were thwarted by insufficient computing power and the need to oversimplify some aspects of the real world in order to run the model at all. The current model and solution strategy is now considered useful and scalable and has demonstrated potential savings of the order of $400 000 per annum. Actual savings are less determinate because many factors can interfere to upset a good tactical plan, such as the ability to produce good usage forecasts, which are partly based on weather forecasts. From a strategic viewpoint the model is showing its worth in a number of areas including:

  • optimising the allocation of existing storage between products
  • developing economic justifications for additional storage capacity and new distribution centres
  • quantifying the savings from co-ordinating shipping arrangements with other parties.

Extensions to the model are planned for (1) optimising supply of the potassium/nitrogen products (MOP, SOP, Urea) which involves more than one supply port and (2) evaluating a strategic approach to the general sourcing problem. In this latter problem supply centres will be considered worldwide, but demand in Australia can be rolled up to a single point, emphasising overall supply strategy among a large number of potential suppliers.

Acknowledgements

  1. Thanks are due to Incitec staff Jim McLeod, Lindsay Hollingworth, Doug Smythe and Doug Butterworth for their support and constructive criticism. Also to Michael Forbes of OPCOM for input to modelling discussions.
  2. Excel, ODBC are trade mark names of Microsoft Corporation.

Note:

Usage and shipping data shown in Table 1 has been adjusted to preserve Incitec Fertilizers commercial interests.

For the interested reader

  • XPRESS-MP Reference Manual (1996) Dash Associates, Blisworth House, Church Lane, Blisworth, Northants, UK.
  • Williams H P (1993) Model Building in Mathematical Programming (Ch 10). Wiley: New York.

MIKE FOX is currently principal consultant with Opcom Pty Limited in Brisbane, Australia. Opcom specialise in scheduling software, notably for rail/bus crewing and for postal logistics. He previously worked in the computer industry for ICL/Fujitsu and for Mount Isa Mines (Australia) and Unilever (UK) in the 1970's. He has lived in Brisbane for 18 years with his wife and two daughters. In addition to scheduling he enjoys climbing, bridge and guitar. Contact: mfox@opcom.com.au

DICK HERDEN is currently Manager - Strategic Analysis with Crop Care Australasia Pty Limited in Brisbane, Australia. Crop Care Australasia, a subsidiary of INCITEC Pty Ltd, formulates, packages and distributes agricultural chemicals. He previously worked in the Logistics Department of the Fertilizer Division of INCITEC Ltd. Contact: dick.herden@cropcare.com.au

Ship Scheduling of Fertilizer Products - Appendix
Shipping model formulation

Indexes

t time period
p product
c distribution centre
b contract break points

Variables

St Total quantity of all products shipped in period t
QPp Quantity of product p shipped in period t
IMPpct Import of product p at distribution centre c in period t
STKpct Stock level of product p at at centre c at end of period t
QXSbt Excess quantity shipped beyond contract break-point
FRT Total Freight Cost
DIS Total Discharge Cost
INV Total Inventory Cost
TCOST Total Cost (= FRT + DIS + INV)
Tt = 1 if ship arrives in period t; else 0
ST Sum of Tt over t
Ppt = 1 if product p supplied in period t; else 0
SPt Sum of Ppt over p and t
Dct = 1 if any products discharged at centre c in period t; else 0
SD Sum of Dct over c and t
Abt Special Ordered Sets (type 1) to handle contract break-points (b ranges from 1 to 4, and A1t = 1 implies no ship in period t)

Data

USAGEpct Monthly usage of product p, centre c, period t
OSTKpc Opening stock levels at beginning of planning horizon
MXSTKpc Maximum stock capacity for product p at centre c (~ 5-10000t)
MNH Minimum hold size as a proportion of ship size (~15%)
MXH Maximum hold size as a proportion of ship size (100%)
MXSHIP Maximum size ship (~ 43500 tonnes)
MNDISTON Minimum discharge tonnage at a centre (~2000 tonnes)
MXSb Maximum excess at break-point b of contract
SSZb Ship size at break-point b of contract
SCOSTb Fixed cost for ship size SSZb
TECb Variable cost of QXSbt
DROP Drop cost for second and subsequent ports (centres) (~$50000)
PCOSTp Unit cost of product p (~$135)
HCOST Holding cost (opportunity cost + insurance/admin etc ~8%)

Objective

Minimise TCOST = FRT + DIS + INV

 

Constraints

Costs

FRT =
( SCOSTb . A b+1 t + TECb . QXSbt )
DIS = DROP . (Dct - Tt )
INV =
HCOST . PRODCOSTp . STKpct

Product balance

QPpt = IMPpct

Stock levels

STKpct = STKpct-1 + IMPpct - USAGEpct
STKpc0 = OSTKpc
STKpct ½ USAGEp c t+1
(lower bounds:- 2 weeks usage)

Minimum/maximum discharge

IMPpct MNDISTON . Dct
IMPpct MXSTKpc . Dct

Minimum hold conditions

QPpt - MNH . St MXSHIP . (Ppt –1)
QPpt - MXH . St MXSHIP . (1 - Ppt)
QPpt MXSHIP . Ppt

SOS1 sets used for shipping contract

Abt = 1
Abt = Tt

Ship tonnage using shipping contract

St = QPpt (balancing)
QXSbt MXSb . A b+1 t
St = SSZb . A b+1 t + QXSbt

High priority branching variables

ST = Tt
SD = Dct
SPt = Ppt
First published to members of the Operational Research Society in OR Insight April - June 1999