Introduction

The problem addressed in this paper is to minimize the distribution costs for satisfying the demand for pulp products for one of the world's largest suppliers of market pulp, Södra Cell AB. The supply chain considered in this project starts at the supply sources (ie pulp mills), located in Sweden and Norway, and ends at the customers' paper mills, located mainly elsewhere in Europe. Around 30 different products are transported from pulp mills to customers in the supply chain. Trains or lorries are used to reach customers in the Nordic countries. The most common way to reach the customers outside Sweden and Norway is by a shipping vessel. The vessels chartered long term are called TC-vessels (ie time-chartered vessels). They load at a harbour near one of the pulp mills, and unload at a terminal next to a harbour elsewhere in Europe. In addition to the TC-vessels, vessels that are chartered short term (ie spot vessels) can be used. It is also possible to use trains and lorries directly for export to Europe. Trains and lorries transport the pulp products further from the terminals to the customers.

The contribution of this paper is an optimization model for a combined terminal location and ship routing problem together with an industrial case study that shows its practical usage. The model is tested and evaluated through different scenarios at Södra Cell AB. The number of possible routes is estimated to be several thousands, and we have, thus, a priori generated a relevant subset of these. The model is a mixed integer linear programming model. The commercial solver CPLEX gives a solution, but it takes longer time than is acceptable. We have therefore developed various heuristics that can be used to get a good-enough solution within acceptable time limits. By using these heuristics, the problem can be solved within 11 min: a result that is 0.12% from the optimal solution for the given case studies. The results are used in the ongoing planning work at Södra Cell AB.

In the literature on ship scheduling on tactical and operative levels, the problems are often solved by formulating and solving a Set Partitioning (SP) problem (Christiansen et al, 2004). Each route represents a column, and the columns are often generated a priori. The column gives information about which places to visit on the current route. The constraints in the model state that all places have to be visited and that each ship is assigned exactly one route. This method for solving the ship routes problem can be found in Ronen (2000) and Butchers et al (2001). Daily operative planning of ships scheduling combined with distribution for Södra Cell AB can be found in Bredström (2003), where a mixed integer programming model was developed and a rolling horizon solution approach as well as a genetic algorithm were used to solve it.

A survey of applications and methods within the facility location area can be found in Drezner (1995). In the literature on forest, a review of locational issues in forest management can be found in Church et al (1998). Melkote and Daskin (2001a, 2001b), and Bhadury et al (2000) described different integrated models of facility location and transportation network design. Related problems of uncapacitated fixed charge network design problems were studied in Magnanti and Wong (1984), and in Balakrishnan et al (1989). Overall descriptions of modelling of multicommodity transportation in network design problems can be found in Crainic and Rousseau (1986).

Different approaches for the attempt to integrate the facility location problem with the vehicle routing problem are discussed and evaluated in Balakrishnan et al (1987). Other problems integrating location decisions with routing can be found in Min et al (1998), and in ReVelle and Laporte (1996). Other related problems include hub location problems. A review of hub location problems can be found in Campbell et al (2002). Studies integrating ship routing with inventory can also be found in Christiansen (1999), Christiansen and Nygreen (1998a, 1998b).

In the supply chain literature, there are several studies that include decisions concerning ship routes. Fagerholt and Rygh (2002) studied the problem of distributing fresh water, and the results concerned the number of shipping vessels, their capacity, and their speed. Mehrez et al (1995) worked with the problem of shipping bulk minerals from facilities to customers. Several time periods in the planning horizon were used, and decisions concerning the size of the fleet and which route to use were taken. Storage is possible at the warehouses, which are located near the harbours. Mehrez et al (1995) only consider ships that are chartered for a single voyage (ie spot trips), and these ships do not have to return to their origins, nor are they necessarily fully occupied by one company. We, however, also consider long-term chartered ships that are required to return to the origin in the right time. The problem presented in Mehrez et al (1995) was solved using a mixed integer programming model.

The outline of the remainder of the present paper is as follows. In the next section the combined terminal location and ship routing problem is described. Then, in the subsequent section, the mathematical model for the problem is formulated. In the following two sections, the solution methods are described and numerical results using data from a real-life case study are presented. The case is obtained from Södra Cell AB, and the results include an analysis of a number of different scenarios. Finally, in the last section some concluding remarks are made.

Problem description

The supply sources in the present problem are pulp mills. Södra Cell AB owns three pulp mills in Sweden and two pulp mills in Norway. Figure 1 shows the location of the pulp mills. The raw materials for pulp production consist of wood logs and sawmill chips. Around 30 different pulp products are produced at the pulp mills. Most of the pulp products have to be transported to the nearest harbour in order to be shipped out of the two Nordic countries. This transportation carries a cost, and the size of this cost depends on the distance from the pulp mill to the harbour. The rest of the pulp is transported by train or lorry to final customers.

Figure 1.

Location of pulp mills (squares) and terminals (triangles).

Full figure and legend (119K)

The pulp products are exported by ship from Sweden and Norway to terminals elsewhere in Europe. There are two kinds of terminals: harbour terminals and inland terminals. The inland terminals are reached from harbour terminals by barges, trains, or lorries. Södra Cell AB uses 24 terminals, three of which are inland terminals. Figure 1 shows the location of the terminals. The terminals have different capacities to receive products and are rented on annual agreements. From each terminal, the pulp products are transported to a number of customers. The transportation from terminals to the final customer is done by trains or lorries, or a combination of both. The transportation from harbour terminals to inland terminals can be handled by trains, lorries, or barges.

The last link in the supply chain consists of the customer demand, both domestic and foreign. There are about 300 delivery points spread across Europe. About 80% of the volume is delivered outside Sweden and Norway. The 10 largest customers purchase half of the volume.

The most common way to supply the European customers is via shipping vessels to terminals, and then further by trains, lorries, or barges. Södra Cell AB uses three TC-vessels. The vessels deliver about 0.7 million tonnes of pulp products to international terminals. The vessel routes vary in journey time from a few days for short routes to about 25 days for longer routes (eg to Italy). Loading and unloading times at harbours are included in these journey times. The time for unloading a full shipping vessel is estimated to be 8 h and the ship capacity of a TC-vessel is 5600 tonnes.

We define two types of routes, simple routes and composite routes, in the problem, which will be referred to as A-routes and B-routes, respectively. The A-routes load at one pulp mill and go to one terminal for unloading. B-routes start at one pulp mill and visit one or several pulp mills or terminals and end at one terminal. An example of a B-route can be to load at the pulp mill in Mönsterås, go on to the pulp mill in Mörrum for additional loading, and finally unload at the terminal in Bremen. Another possible B-route can be to load at the pulp mill in Tofte, unload some of the products at the terminal in Aberdeen, and then go on to Bremen to unload the rest of the products. The spot vessels are chartered for a single voyage, from an origin (pulp mill) to a destination (terminal), and have different capacities. The smallest spot vessel can carry 2600 tonnes of pulp.

The annual planning of routes and terminal usage requires several types of decisions. With regard to the routes, the planners at Södra Cell AB have to decide which terminals to use, and how much (ie how large a total flow will be accepted for each terminal). The total flow at a terminal will also control the possible amount of products received on A-routes to the current terminal. The planner has to decide which A-routes and B-routes to use, as well as the total flow of products on the routes. In addition, Södra Cell AB wants to know whether it is profitable to use spot vessels or not and to what extent to use them.

Model formulation

Modelling issues

The A-routes go from one pulp mill to one terminal. The ship vessels always transport a full cargo of pulp products the shortest way, directly to the final destination. The planning period in the model is 1 year, but the customers have continuous demand (ie monthly). For terminals connected to customers that together have a large demand, the A-routes can bring full cargoes and deliver the pulp products monthly. However, there are problems in supplying the terminals connected to customers that together have a small demand. Using A-routes to these terminals would lead to delivery of the total annual demand of pulp products just once a year instead of once a month. There are no possibilities to store the pulp products because the pulp production capacity barely covers the total pulp demand. The use of A-routes in the model is only allowed for those terminals that are connected to customers that together have a large demand. For the other terminals another kind of route is used, namely B-route. A B-route visits several places, which means a longer journey. B-routes supply customers connected to different terminals, and the annual pulp demand of a specific customer can be divided on 12 different B-routes, which enables monthly delivery. The ship vessels using B-routes do not always bring full cargoes, which makes the B-routes expensive expressed in tonnes per kilometer, compared to the A-routes.

In order to include restrictions on the size of the flow on the A-routes in the model, we have defined a number of levels with corresponding flow for each terminal. A specified maximal proportion of A-routes is designed to each of these levels. The levels give information about the total flow at each terminal. In the solution of the model, a terminal with large total flow is assigned an appropriate high level, allowing a corresponding high proportion of A-routes. A terminal with small total flow in the solution would, in contrast, be assigned a low terminal level with hard restrictions. Very small flow at a terminal will result in no acceptance at all for flow on A-routes, and large flow at a terminal will lead to an acceptance of receiving almost all the flow by A-routes. The maximal proportions of flow on A-routes and the terminal levels are presented in Figure 2, where 16 different levels are used. It requires a lot of experience to decide the number of terminal levels and their sizes. Södra Cell AB uses history of their routes and distribution structures to find the relevant information.

Figure 2.

Proportion of A-routes depending on the annual flow.

Full figure and legend (10K)

In order to model a B-route we need one link for each possible combination of mills and terminals included in the B-route. For example, a B-route that starts at a pulp mill, then goes to one terminal for unloading some of the products, and thereafter further to another terminal for unloading the remaining cargo is modelled as two types of links from the pulp mill: one link for the flow of each product to the first terminal and another link representing the flow of each product to the second terminal.

Mathematical model

The mathematical model of the combined terminal location and ship routing problem is a linear mixed integer programming model. We start the description of the model by introducing the necessary sets. Let I be the set of pulp mills, J the set of terminals, P the set of products, Q the set of customers, R the set of routes, and L the set of terminal flow levels. The set of pulp mills includes a subset for pulp mills in route k, I_k. The set of terminals includes subsets for harbour terminals, J_H, inland terminals, J_L, and terminals in route k, J_k. Finally, the set of routes includes subsets for A-routes, R_A, and for B-routes, R_B.

In general, we will use index i for pulp mills, j for terminals, k for routes, p for products, q for customers, and l for terminal flow levels. Unless otherwise stated, we assume that definitions using for example index i are valid for all iI.

Variables

First we define variables representing the transportation flows of products on A-routes and B-routes from pulp mills to terminals. We define them as

x_kijp^A

flow of product p on A-route k from pulp mill i to terminal j,

x_kijp^B

flow of product p on B-route k from pulp mill i to terminal j.

We also need variables for spot flows. We define them as

x_ijp^S

spot flow of product p from pulp mill i to terminal j.

All the routes end at a terminal. In order to model the time restriction for the A-routes and B-routes, we introduce a variable describing the return flows on routes from harbour terminals back to pulp mills. This flow does not include any products as the shipping vessel is empty. These variables can be defined as

x_ji^R

return flow from terminal j to pulp mill i.

The variables related to transportation by train and lorry can be formulated as follows:

y_iqp^train

flow of product p from pulp mill i to customer q transported by train,

y_iqp^lorry

flow of product p from pulp mill i to customer q transported by lorry.

The flows from terminals and at terminals can be defined as

y_hlp^T

flow of product p from harbour terminal h to inland terminal l,

y_j^tot

total flow of products at terminal j,

y_jqp^Q

flow of product p from terminal j to customer q.

All variables defined so far are continuous variables.

We also need some sets of binary variables in the model formulation. The set of variables concerning A-routes, B-routes, and spot trips can be expressed as

and

The set of variables related to the use of terminals is defined as

In order to model the restrictions on flows on A-routes to a given terminal, we define flow levels specifying the maximal allowed proportion of flow on A-routes entering the terminal. Terminals receiving a large volume of products are allowed a larger proportion of A-routes compared to terminals receiving a small volume of products. In order to model the levels we use the variables

Constraints

Let s_ip be the volume of product p available at pulp mill i. In order to ensure that the supply of a product at a pulp mill is not exceeded, we formulate the constraints

The flow balance constraints for harbour terminals can be expressed as

The total inflow of products to a harbour terminal becomes

Constraints (2) assure that the inflow of each product to every harbour terminal equals the outflow of each product. Constraints (4) make sure that the total inflow to a harbour terminal equals the flow of products on the routes and the flow of products on the spot vessels passing the terminal. The flow out from a harbour terminal can be transported to an inland terminal or directly to a customer. The corresponding flow-balance constraints for inland terminals become

Constraints (4) make the flow of each product to each inland terminal equal the flow of each product from the inland terminal to the customers. The total inflow of products to an inland terminal becomes

Constraints (5) ensure that all flow of products transported from harbour terminals to an inland terminal equals the total flow at the inland terminal. Let the capacity at terminal j be denoted by b_j. The capacity constraints at terminals can then be formulated as

Constraints (6) also ensure that nothing can be transported from or to a terminal which is not opened (z_j^T=0). Let the amount of flow associated with level l be denoted by t_l and let the interval flow for the levels be denoted by N. To assure that the terminals have the right level of flow, we formulate

and

Constraints (7) ensure that the total flow at each terminal does not exceed the amount of flow associated with the chosen terminal level, and constraints (8) make sure that the right level of the terminal is chosen. The constraints

ensure that one level of flow is chosen to each terminal. In order to limit the A-routes, we use the constraints

where p_l denotes the maximal proportion of flow on A-routes with terminal level l. Larger total flow of products to terminals means higher levels, and that, in turn, means larger allowed proportions of flow of products on A-routes. We have to express constraints ensuring that the demand of the customers is satisfied. The demand for product p of customer q is denoted by d_qp. The demand constraints are

Constraints (11) show the different transportation modes used to fulfil the demand: the flow from terminals, train flow, and, finally, lorry flow. There are time restrictions for TC-vessels. Let r denote the total time, in working days per year, available for TC-vessels, let s^H denote the total capacity of each shipping vessel, and let m denote the number of TC-vessels. The ship capacity of each one of the TC-vessels is 5600 tonnes. Further, let t_k^A denote the used time (in days) for A-route k and let t_k^B denote the corresponding time for B-route k. The transportation time from terminal j back to pulp mill i is denoted by t_ji^R. To ensure that the time limits are not exceeded we express

This constraint is an approximation, as parts of a full shipping vessel will be modelled as using parts of the time compared to a full shipping vessel. However, the routes use at least two vessels. The route balance constraints can be formulated by

Constraints (13) ensure that the outflow from a pulp mill equals the return flow to the same pulp mill. To assure that nothing is transported on routes that are not chosen, we need the constraints

and

Constraints (14) and (15) are related to A-routes and B-routes, respectively, and constraints (16) concern spot trips. The constant M is a big number and in our cases we have used M=1 000 000 (related to the sum of the demand outside of Scandinavia). If the binary variable for a route is zero, the right-hand side in the constraint becomes zero, and there is no possibility to use the corresponding flow variable on the route in the left-hand side. Large flow on routes means many shipping voyages. Let b^A, b^B, and b^S denote the minimal number of shipping vessels per year on A-routes, B-routes, and spot trips, respectively. The flow of products on A-routes has to be large in comparison with B-routes and spot trips. The customers have continuous demand, and they therefore have to be visited many times a year, which means several shipping vessels per year. In the case of B-routes, there are several possibilities to visit the terminal using different B-routes, so the number of shipping vessels transporting pulp products on B-routes is allowed to be smaller. In our cases, the minimal number of shipping vessels on an A-route is 10 and on a B-route is two. Finally, the spot trips are chartered short term, so the only restriction regarding the number of ship voyages is that a shipping vessel gets filled (ie brings at least 2600 tonnes). In order to get a certain number of shipping vessels on routes, we need the following constraints to guarantee a minimal size of flows on routes:

and

B-routes consist of several links of varying length, and all these links have to be utilized. Otherwise, the route can be misclassified as an A-route. In order to get a certain proportion of flow on each link in a route we need the constraints

where n denotes the share of the flow on a link in a route compared to the total flow on the given route. In order to strengthen the linear programming relaxation we add the redundant constraints

where L_f denotes the set of terminal flow levels with flow greater than zero.

Objective function

The objective is to minimize the total distribution cost for satisfying the customers. The total cost can be expressed as

where

C^routes

transportation cost for routes,

C^spot

spot cost,

C^train/lorry

train and lorry cost,

C^term–term

transportation cost between terminals,

C^distr

distribution cost between terminals and customers,

C^return

cost for return routes,

C^flow

flow cost at terminals, and

C^fix–term

fixed terminal cost.

Let c_k^A be the transportation cost per unit (tonnes) for A-route k, and let c_k^B be the corresponding transportation cost per unit for B-route k. Further, let c_i^MP be the transportation cost per unit from pulp mill i to the corresponding harbour. The shipping vessels are chartered on long term. Hence, the fixed cost regarding these shipping vessels is considered to be sunk costs.

The total transportation cost for routes can now be expressed as

Let c_ij^S be the transportation spot cost per unit between pulp mill i and terminal j. We can express the total spot cost as

Let c_iq^train and c_iq^lorry be the train and lorry cost, respectively, between pulp mill i and customer q. We can express the total train and lorry cost as

Let c_hl^T be the transportation cost between harbour terminal h and inland terminal l. We can express the total transportation cost between terminals as

Let c_jq^TQ be the transportation cost between terminal j and customer q. We can express the total transportation cost between terminals and customers as

The transportation between terminals, as well as from terminals to customers only, consists of the cheapest mode of transportation on each specific distance by either train, lorry, or barge. A customer can be supplied with pulp products from different terminals.

Let c_ji^R be the unit cost for the return route between terminal j and pulp mill i. We can express the total return route cost as

Let c_j^T be the unit cost for flow at terminal j, and let further f_j^T be the fixed cost at terminal j. The flow cost at terminals is a variable cost of operating a terminal as a function of volume. The fixed cost of using a terminal consists of a cost regarding continuous operation of a terminal. We can express the total flow cost at terminals and the total fixed terminal cost as

and

Solution methods

One solution approach was to use the commercial solver CPLEX 7.0 directly, with default settings. The modelling language AMPL (version 10.6.16) was used to model the problem. The problem was solved in about 3 h using a PC with a Pentium 4 processor, with 1.7 GHz clock frequency and 1 Gb RAM. However, when the number of B-routes is large, the time required to solve the problem directly is too long. We have therefore developed heuristics which enable us to obtain a solution within practical time limits. Below follows a short description of the heuristics.

Heuristic Heur1

We start by solving the problem without binary variables for the B-routes, u_k^B, and without the related constraints (18) that guarantee a minimal size for the B-routes, and without constraints (15) that prevent flow on routes when the corresponding binary variable is zero. The resulting new problem will be a relaxation of the original problem. The flow on the B-routes in this solution can be too small. Therefore, we add binary variables for the B-routes used in the solution. The corresponding constraints that were relaxed in the previous solution are also added, and finally the rest of the possible B-routes are removed, and the problem is resolved. This generates a feasible integer solution. The main steps of the heuristic Heur1 can be summarized as follows.

1. Solve the problem:
   1. without binary variables for the B-routes, and
   2. without the related constraints, guaranteeing a minimal size of the B-routes, and
   3. without the constraints preventing flow on routes with binary variables equal to zero.
      This gives a tentative solution.
2. Introduce binary variables for the B-routes used in the solution obtained in step 1, and add the constraints of type (ii) and (iii) that include these binary variables.
3. Fix the flow on the other B-routes to zero.
4. Solve the problem to obtain a feasible integer solution.

Heuristic Heur2

This heuristic is very similar to Heur1 described above; however, step 2 differs. The approach in Heur2 is based on the use of reduced costs for the B-routes. The size of the reduced cost for the B-routes that are not used gives us information about which B-routes are most attractive. We study the linear programming reduced costs for the links in the B-routes that are obtained when the original binary variables are fixed at their optimal values. The reduced costs on links on the B-routes are summed up and compared. Then, the sums less than a given positive value are chosen. Binary variables for these corresponding B-routes are then added to the problem. This strategy will include the B-routes used in the first solution, because they have a reduced cost of zero. To summarize, Heur2 consists of the same steps as Heur1, except that step 2 is replaced by the following:

• (2) Introduce binary variables for the B-routes with the sum of the reduced costs less than a given value in the tentative solution, and add the corresponding constraints (ii) and (iii).

More binary variables for B-routes are added in step 2 than in Heur1. The number depends on the size of the given number in step 2.

Heuristic Heur3

We have also developed an iterative heuristic. This was accomplished by starting by solving the relaxed problem, expanding the set of B-routes that is binary, and finally solving the problem again. The time required for getting an optimal solution using this heuristic is however not considered to be acceptable. Therefore, we interrupt the procedure after a given number of iterations. Finally, all the B-routes that are not yet binary are fixed to zero, so a feasible integer solution is guaranteed in the end.

We noted that using Heur1, Heur2, and Heur3 will never result in infeasible solutions since there are always alternatives to using the A-routes and B-routes, such as using spot trips, or using transportation by trains and lorries.

Results

Cases

The case study from Södra Cell AB is based on data from the period April 2002 to March 2003. There are only four pulp mills involved in the test cases. The pulp mill Folla in Norway is excluded due to its special distribution system, which prevents easy comparison. All the possible A-routes and spot trips are generated and included in the test cases. Regarding the B-routes, there is a large set of possible routes. In order to restrict the number of B-routes we have chosen the types of B-routes presented in Table 1. The choice of these types of B-routes is based on planning experience at Södra Cell AB. The total number of places visited is restricted to four, due to the fact that routes including more places are rarely used by Södra Cell AB. The visiting order of the pulp mills and terminals is not considered. That is, a route from a pulp mill to terminal 1 and then to terminal 2 is considered as the same route as starting at the pulp mill, visiting terminal 2 first, and then visiting terminal 1. The reason for that is that annual decisions are only considered in the model, since there are no other time periods included. Information about the size of the test problem is given in Table 2. The size of the problem is very large, motivating the development of the heuristics.

Table 1 - Different kinds of routes.

Full table

Table 2 - Size of the problem in the basic case.

Full table

It is not easy to obtain the costs for spot vessels. There are often different agreements that decide the levels of the costs, and there are other parameters besides the length of the transportation to consider. The used spot rates are mainly obtained through historical data. The possibility of using the spot vessels for return flow can be important for the price setting.

We have generated six scenarios (problems) to test the model and the efficiency of the solution procedures. The problems are presented below. Each case is based on specific interest from Södra Cell AB for their tactical decision making.

The first problem (P1) is the basic case, and all other problems are modifications of this problem. Every customer has at least two possible terminals to get pulp from. The corresponding numbers of components as well as the size of the basic case are presented in Table 2. In problem P2 the terminal in Terneuzen is made available for all customers in Italy. In addition, the costs from Terneuzen to customers in Italy are decreased by 20%. In problem P3 the terminals in Sunderland and Grimsby are made available for all customers in Great Britain. In problem P4 the terminals in Sunderland and Grimsby are made available for all customers in Great Britain, and simultaneously only one of these terminals is allowed to be used. In problem P5 the terminals in Kiel, Ghent, Boulogne, and La Pallice are removed. In addition, the flow cost at terminals are decreased for the terminals in Terneuzen and Bremen. All the routes in the basic case use the Kiel Canal for routes not involving Tofte and Värö. In problem P6 the possibility to round Denmark instead of using the Kiel Canal is investigated. Rounding Denmark will be cheaper due to Canal costs, but the journey time of the routes will be longer. This is going to result in a larger problem because the number of routes is considerably increased. This problem includes 2393 B-routes, compared to the basic case, where the number of B-routes is 1873.

Numerical results

The objective values from solving the six problems using the CPLEX directly as the solution method are given in Table 3. We also show the objective function values for the corresponding LP-solutions to the different problems. In all the cases, the time to get an LP-solution is short and the optimal integer solution is close to the LP-solution. We have also used the options in CPLEX with the LP-solvers Baropt and Dualopt and both use computational times very similar to the default option (within 10% of each other). The objective function values are given in cost units, not to reveal the actual commercial values.

Table 3 - Optimal objective function values and CPU-times in the different problems using CPLEX directly.

Full table

Table 4 presents the results of solving the problems using the different heuristics. We have chosen to present the result after five iterations in Heur3, due to the fact that the time for solving the problem then becomes less than 1 h. Regarding the Heur2, we present the problem solved with the sum of the reduced costs (red. cost) less than 1500, for the same reason. It should be noted that the times for solving the problems by using Heur1 and Heur2 are similar.

Table 4 - Optimal objective function values in different problems using the proposed heuristics.

Full table

It should be noted that in Heur3 around 30 binary variables connected to B-routes are added in the beginning and only a few (two to four) are added towards the end. To use the Heur3 on the basic case to the end requires 73 iterations, and takes around 165 h. The number of included binary variables connected to B-routes in the last iteration is 403.

Analysis of cases

The results from the six different scenarios are presented in Table 5. The figures within parentheses represent the total possible number of the components, respectively. Around five terminals are not used in the cases, which is in accordance with Södra Cell AB's ambition to use fewer terminals. It should be noted that only a small part of the possible routes are used. The restrictions regarding the size of the routes have decreased the amount of routes. The number of voyages on used A-routes and B-routes is based on the fact that the TC-vessels have a capacity of 5600 tonnes. In all the cases all possible times for running routes are used, explaining almost the same proportion of train and lorry transportation in all instances. The spot trips selected by the model are mainly trips to distant destinations. The maximum number of voyages on used spot trips is based on the fact that the capacities of the spot vessels are from 2600 tonnes.

Table 5 - Results from the different scenarios using CPLEX directly.

Full table

As many as 19 of totally 24 terminals are used in P1. Two of the three inland terminals are used. The number of B-routes used is only 24 out of 1873 possible. The B-routes are usually used for nearer destinations. Regarding long routes, for instance, to Genova, the spot trips are chosen to a greater extent. By using spot ships to these distant destinations, Södra Cell AB can make more A- and B-routes to the close destinations.

If the distribution costs from Terneuzen to the customers located in Italy could be decreased by at least 20% as described in problem P2, it would be better for Södra Cell AB to close the terminal in Genova and use the terminal in Terneuzen more. The main disadvantage with this action is that the distance from the terminal to the customers in Italy would be longer, which could mean less good service.

Södra Cell AB has several terminals in Great Britain and is striving to reduce the number. We can see that if all customers can use the terminals in Sunderland and Grimsby as in problem P3, the costs would decrease, in spite of the fact that neither Sunderland nor Grimsby is used in the basic case. The costs would increase marginally if just one of the two terminals in Sunderland and Grimsby is allowed to be used as described in problem P4. For making a complete comparison, other circumstances, not included in the model, have to be considered.

The results concerning problem P5 indicate that it would be cost efficient to close the terminals Kiel, Ghent, Boulogne, and La Pallice, and instead use the terminals Terneuzen and Bremen more frequently. However, the loss in value for customers located close to the terminals that would be closed is hard to estimate. There is a trade-off between availability of products at the larger terminals versus longer distances to some customers.

We can see from the results of problem P6 that all the longer routes rounding Denmark have been chosen at the expense of the shorter routes via the Kiel Canal. There is no loading or unloading in the weekends for the staff in Södra Cell AB, which will mean even more savings by using these longer routes. Since many routes in the present situation include waiting time for loading or unloading, using this time for transport could be as good as waiting at the harbour.

Concluding remarks

The strategic decisions on location of terminals for distributing the pulp at Södra Cell AB are regularly reconsidered. It has been the aim of the company to reduce the number of terminals for the last couple of years. One argument for reducing the number of terminals is to concentrate volumes which makes shipping to the terminals more efficient. Having a higher volume assigned to a terminal also means a bigger 'bargaining power' when discussing handling costs and service with the operating company. Another argument is that availability can be improved by having the full assortment of products in stock for quick delivery to customers. There are, however, problems associated with taking away terminals. The main disadvantage is that the distance to some customers increases, which means increased transportation costs. There are also other aspects, which are harder to express in numbers, and therefore are difficult to include in a numerical model. One such aspect can be how the relationship with an important customer is influenced if a terminal is removed.

In the strategic decision process as well as tactical decision making in the annual budgeting process it is important to be able to quantify the impact of different scenarios. The suggested model does exactly this and is used by Södra Cell AB as a support tool. Even though some aspects exist that are hard to include, the developed model is an important tool in weighing the different measurable aspects against each other. It is also a tool for measuring the actual cost of keeping a terminal just to maintain a good relationship with a certain customer. Such information can also be valuable in negotiations with the customer. In the tests we have found that the six case studies can be solved by CPLEX directly, and for instances including a considerable amount of B-routes, we have developed heuristics to obtain good solutions within practical time limits.

References

1. Balakrishnan A, Ward JE and Wong RT (1987). Integrated facility location and vehicle routing models: recent work and future prospects. Am J Math Mngt Sci 7(1–2): 35–61.
2. Balakrishnan A, Magnanti TL and Wong RT (1989). A dual-ascent procedure for large-scale uncapacitated network design. Opns Res 37: 716–740.
3. Bhadury J, Chandrasekharan R and Gewali L (2000). Computational complexity of integrated models of network design and facility location. Southwest J Pure Appl Math 1: 30–43.
4. Bredström D (2003). Optimization models and methods for production planning and ship scheduling in the pulp industry. Licentiate thesis, LiU-TEK-LIC-2003:1056, Linkoping Institute of Technology, Sweden.
5. Butchers ER, Day PR, Goldie AP, Miller S, Meyer JA, Ryan DM, Scott AC and Wallace CA (2001). Optimized crew scheduling at air New Zealand. Interfaces 31(1): 30–56. | Article |
6. Campbell JF, Ernst AT and Krishnamoorthy M (2002). Hub location problems. In: Drezner Z and Hamacher HW (eds). Facility Location:Applications and Theory, Chapter 12, Springer: Berlin.
7. Christiansen M, Fagerholt K and Ronen D (2004). Ship routing and scheduling: status and perspectives. Transport Sci 38(1): 1–18. | Article |
8. Christiansen M (1999). Decomposition of a combined inventory and time constrained ship routing problem. Transport Sci 33(1): 3–16.
9. Christiansen M and Nygreen B (1998a). Modelling path flows for a combined ship routing and inventory management problem. Ann Opns Res 82: 391–412. | Article |
10. Christiansen M and Nygreen B (1998b). A method for solving ship routing problems with inventory constraints. Ann Opns Res 81: 357–378. | Article |
11. Church RL, Murray AT and Weintraub A (1998). Locational issues in forest management. Location Sci 6: 137–153. | Article |
12. Crainic TG and Rousseau JM (1986). Multicommodity, multimode freight transportation: a general modeling and algorithmic framework for the service network design problem. Transport Res B:Meth 20(3): 225–242. | Article |
13. Drezner Z (1995). Facility Location: A survey of Applications and Methods. Springer-Verlag: New York.
14. Fagerholt K and Rygh B (2002). Design of a sea-borne system for fresh water transport: a simulation analysis. Belg J Opns Res, Statist Comput Sci 40(3–4): 137–146.
15. Magnanti TL and Wong RT (1984). Network design and transportation planning: models and algorithms. Transport Sci 18(1): 1–55.
16. Mehrez A, Hung MS and Ahn BH (1995). An industrial ocean-cargo shipping problem. Decision Sci 23(3): 395–423.
17. Melkote S and Daskin MS (2001a). An integrated model of facility location and transportation network design. Transport Res A 35: 514–538.
18. Melkote S and Daskin MS (2001b). Capacitated facility location/network design problems. Eur J Opl Res 129: 481–495. | Article |
19. Min H, Jayaraman V and Srivastava R (1998). Combined location-routing problems: a synthesis and future research directions. Eur J Opl Res 108: 1–15. | Article |
20. ReVelle CS and Laporte G (1996). The plant location problem: new models and research prospects. Opns Res 44: 864–874.
21. Ronen D (2000). Scheduling charter aircraft. J Opl Res Soc 51(3): 258–262. | Article |