Roll cutting has attracted a great deal of research attention. However, most of the development of models and methods in academic research has not considered some key industrial requirements. These are practical production aspects that often create non-tractable optimization problems. In this paper, we study two important problems and show how these can be solved efficiently in an industrial setting. These are operative roll cutting where the number of reels and different patterns should be minimized and real-time cutting, when defects and quality restrictions on ordered rolls are included.
We study the supply chain problem of a large international pulp producer with five pulp mills located in Scandinavia. The company currently uses manual planning for most of its supply chain, which includes harvesting and transportation of pulp, production scheduling and distribution of products to customers. We have developed two new mixed integer models that determine daily supply chain decisions over a planning horizon of three months. One model is based on column generation, where the generation phase is to find new production plans using a shortest path network. The second, slightly less flexible, has the daily production decisions explicitly included in the model. In order to solve the models within practical time limits we use a flexible approach that aggregates together the less immediate decisions. We also introduce a novel constraint branching heuristic. The models and solution approaches are intended to become an integrated component in the company’s new management system. In tests and comparisons with today’s manual planning, we have found new strategic policies that significantly reduce the company’s supply chain costs.
In this paper we present a branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. The synchronization constraints are used to model situations when two or more customers need simultaneous service. The synchronization constraints impose a temporal dependency between vehicles, and it follows that a classical decomposition of the vehicle routing and scheduling problem is not directly applicable. With our algorithm, we have solved 44 problems to optimality from the 60 problems used for numerical experiments. The algorithm performs time window branching, and the number of subproblem calls is kept low by adjustment of the columns service times.
In this paper we present a genetic algorithm for the pulp distribution problem at a large pulp producer in Scandinavia. The distribution is a major part of the company's supply chain and includes transports with cargo vessels, by train and trucks and storages at terminals in port, at pulp mills and in customer locations. The problem we focus on is to find ship schedules and pulp deliveries in order to minimize the total cost of distribution.
The genetic algorithm utilizes two linear programming models. The first model optimizes all transport flows given a schedule and the second model approximates the performance of a schedule, measured in the total distribution cost. In the computational experiments we use instances from the real world and compare the results with an exact mixed integer programming approach.
We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where the temporal constraints, in the literature, usually are remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usability. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct usage of a commercial solver against the proposed heuristic where the latter approach can find high quality solutions within distinct time limits.
In this paper we consider a combined supply chain and ship routing problem for a large pulp producer in Scandinavia. The problem concerns the distribution of pulp to customers, with route scheduling of ships as a central part of modeling. It is an operative planning problem with daily ship routing decisions over a 40 days period. The pulp supply is determined by fixed production plans, and the transport flows and storages are modeled with the requirement to satisfy the demand in a cost-optimal way. We develop a mixed integer programming model with binary variables for route usage of a vessel.
The problem is solved with a heuristic solution method, based on a rolling time horizon and a standard branch and bound algorithm. We apply the heuristic on problem instances with real world data, and compare results from reduced problem instances with the results from an exact branch and bound search. The computational experiments indicate that real world problems are solvable with the solution method and that it in many cases can be very effcient.
Distribution is a major factor in the supply chain for Sodra Cell, a leading manufacturer of pulp intended for paper production. Each year, the company transports large quantities of pulp using ships, trains, and trucks; here we focus on scheduling the ships and optimizing deliveries to minimize distribution costs.
The use of supply chain management and optimisation is of increasing importance in the forest industry. The overall wood-flow starts with standing trees in forests and continues with harvesting, bucking, sorting, transportation to terminals, sawmills, pulp mills, paper mills and heating plants, conversion into products such as pulp, paper, lumber, and ends at different customers. Many planning problems arise along the chain and these cover different time horizons. Co-ordinating the wood-flow is a vital concern for many companies. We study Södra, one of the larger Swedish forest companies, which is involved in all stages of the wood-flow. We focus in particular on Södra Cell AB, a company within Södra, which is responsible for pulp production. We describe the operations at Södra Cell and the decision support tools used for supply chain planning. We describe five major projects or cases which focus on improving their supply chain management and optimisation. These cases include the introduction of new technologies for sales and orders, new distribution structures using terminals, and the development of integrated optimisation models and methods. © 2004 Elsevier B.V. All rights reserved.
The health care system in Sweden and many other countries is facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. At the same time, health care systems are often very labor and staff intensive. In this paper, we focus on a staff planning problem arising in Sweden where people receive home care from the local authorities. The objective is to develop visiting schedules for care providers that incorporate some restrictions and soft objectives. Each visit has a particular task to be performed, for example: cleaning, washing, personal hygiene and/or nursing activities. Each staff member has skills and each client should, if possible, be visited by the same contact person. The operational situation is continuously changing and planning is done each day. We describe the development of a decision support system Laps Care to aid the planners. The system consists of a number of components including information data bases, maps, optimization routines, and report possibilities. We formulate the problem using a set partitioning model and, for a solution method, we make use of a repeated matching algorithm. The system is currently in operation at a number of home care organizations. We report on the practical impact of the system in the health care organization which was involved in the development. The savings are considerably in terms of saved planning time and in the quality of the routes, as well as the measured quality for the clients. Numerical experiments of the system are presented.
By taking the guesswork out of the equation, operations research-based process control system helps cut costs, reduce environmental impact at Swedish paper mill.
Systems analysis in forestry has continued to advance in sophistication and diversity of application over the last few decades. The papers in this volume were presented at the eighth symposium in the foremost conference series worldwide in this subject area. Techniques presented include optimization and simulation modelling, decision support systems, alternative planning techniques, and spatial analysis. Over 30 papers and extended abstracts are grouped into the topical areas of (1) fire and fuels; (2) networks and transportation; (3) forest and landscape planning; (4) ecological modeling, biodiversity, and wildlife; and (5) forest resource applications. This collection will be of interest to forest planners and researchers who work in quantitative methods in forestry.
In this paper, the integrated planning of production and distribution for a pulp company is considered. The tactical decisions included regard transportation of raw materials from harvest areas to pulp mills; production mix and contents at pulp mills; inventory; distribution of pulp products from mills to customers and the selection of potential orders and their levels at customers. The planning period is one year and several time periods are included. As a solution approach we make use of two different heuristic approaches. The main reason to use heuristics is the need for quick solution times. The first heuristic is based on a rolling planning horizon where iteratively a fixed number of time periods is taken into consideration. The second heuristic is based on Lagrangian decomposition and subgradient optimization. This provides optimistic bounds of the optimal objective function value that are better than the LP relaxation value, which can be used as a measure of the heuristic (pessimistic) solution quality. In addition, we apply the proposed rolling horizon heuristic in each iteration of the subgradient optimization. A number of cases based on real data is analysed which shows that the proposed solution approach is simple and provides high quality solutions.
We study the problem of deciding when and where forest residues are to be converted into forest fuel, and how the residues are to be transported and stored in order to satisfy demand at heating plants. Decisions also include whether or not additional harvest areas and saw-mills are to be contracted. In addition, we consider the flow of products from saw-mills and import harbors, and address the question about which terminals to use. The planning horizon is one year and monthly time periods are considered. The supply chain problem is formulated as a large mixed integer linear programming model. In order to obtain solutions within reasonable time we have developed a heuristic solution approach. Computational results from a large Swedish supplying entrepreneur are reported.
In this paper, we consider a combined terminal location and ship routing problem at Södra Cell AB. The purpose is to supply the customers' annual demand for pulp products while minimizing the distribution costs. Customers are supplied with various pulp products from pulp mills in Scandinavia by ships, trains, or lorries. The ship routes go from the pulp mills to terminals in Europe. From each terminal, the products are transported to customers by lorry, train, or barge. Some customers can be supplied directly from the pulp mills by trains or lorries. We have developed a mathematical model to select which terminals to use and, at the same time, determine the shipping routes. The mixed integer programming model was solved directly using a commercial solver. When the number of routes generated is large, the time required to obtain an optimal solution is too long. Hence, we have developed heuristics in order to obtain an acceptable solution in reasonable time. In addition to the basic case, five different scenarios were tested. Our heuristics provide solutions that are within 0.12% of the optimal ones.
In this paper we consider integrated planning of transportation of raw material, production and distribution of products of the supply chain at Södra Cell AB, a major European pulp mill company. The strategic planning period is one year. Decisions included in the planning are transportation of raw materials from harvest areas to pulp mills, production mix and contents at pulp mills, distribution of pulp products from mills to customer via terminals or directly and selection of potential orders and their levels at customers. Distribution is carried out by three different transportation modes; vessels, trains and trucks. We propose a mathematical model for the entire supply chain which includes a large number of continuous variables and a set of binary variables to reflect decisions about product mix and order selection at customers. Five different alternatives regarding production mix in a case study carried out at Södra Cell are analyzed and evaluated. Each alternative describes which products will be produced at which pulp mills.
The electricity market in Sweden has changed during recent years. Electricity for industrial use can now be purchased from a number of competing electricity suppliers. Hence, the price for each kilowatt-hour is significantly lower than it was just two years ago and interest in electricity conservation measures has declined. However, part of the electricity tariff, i.e. the demand cost expressed in Swedish Kronor (SEK) for each kilowatt, is almost the same as before. Attention has thereby been drawn to load management measures in order to reduce this specific cost. Saving one kWh might lead to a monetary saving of between SEK 0.22 and SEK 914, this paper demonstrates how to eliminate only those kWh that actually save a significant amount of money. A load management system has been installed in a small carpentry factory that can turn off equipment based on a pre-set priority and number of minutes each hour. The question now is what level of the electricity load is optimal in a strictly mathematical sense, i.e. how many kW should be set in the load management computer in order to maximise profitability? In this paper, we develop a mathematical model that can be used as a tool both to find the most profitable subscription level and to control the choices to be made. Numerical results from a case study are presented. Copyright (C) 2004 John Wiley Sons, Ltd.
When designing a telecommunication network, one often wish to include some kind of survivability requirement, for example that there should be at least two paths between every pair of nodes in the network. A design model who fulfills this requirement is a network build up with rings. The network design problem is to choose links from a given network, and compose them into a number of rings. The rings are connected to each other at certain transit nodes. The number of possible rings is enormous, and each possible ring is associated with a certain fixed cost. A ring has a fixed capacity, however, we model it as a linear cost depending on the traffic using the ring and the length of the ring. We describe the problem, and model it is a set covering model, where a column describes how a specific ring is used. Even with a small set of rings, number of possible columns in the model is large. Therefore, a column generation approach is used to solve the set covering model with a given set of rings. An important part of the problem is to generate new rings, were the dual solution from the set covering model gives rewards on the nodes, representing a nodes’ wish to be included in a new ring. The ring generation problem is a modification of a traveling salesman subtour problem. New rings are generated using a heuristic. We present some computational results for a real data network and a number of random generated networks.
We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The work design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem. We find a feasible solution to the problem by first find good rings in the network using two heuristics, and then solve the optimization model using only these rings. Finally, we give some computational results for different networks.
The development of optical fibers in telecommunications has lead large changes in the field. When design a telecommunication network, capacity nowadays is cheap, and the minimal cost design tends to be a tree. Since such a design is very vulnerable for link or node failures, one often wish to include some kind of survivability requirement, for example that the network should be two-edge-connected or two-node-connected. Another form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a give network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Traffic between rings may pass through other rings, which is an important element of the problem. Finally, reserve capacity allocation according to certain principles is included. We describe the problem, modeled as a linear integer programming problem, and discuss different formulations and different solution methods. As the problem is quite difficult, we focus on heuristic solution methods, including elements of column generation and Lagrangean relaxation.
We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The network design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem, and a heuristic solution method, based on column generation and Lagrangean relaxation.
Systems analysis in forestry has continued to advance in sophistication and diversity of application. This work features papers, which were presented at the eighth symposium focusing on techniques which include optimization and simulation modelling, decision support systems, alternative planning techniques, and spatial analysis.
Harvest planning includes decision on different levels, both spatial and temporal,and is typically hierarchical in nature. Strategic forest planning includes decisions about nationwide forests and aims to maximize the sustainable production while preserving natural ecosystem processes and recreation areas on time horizons of one or several rotations, each representing 20-200 years. Tactical harvest planning decides which stands (or harvest areas) to be harvested over a several year rolling planning horizon under consideration of spatial aspects, e.g. road building and environmental concerns. On an operational level, annual plans are required for budgeting, contracting harvest teams and transportation companies and assuring road access. Moreover, managers decide weekly and monthly schedules for harvesting and transportation based on customer requirements. We provide an overview of hierarchical harvest planning and present the Swedish case. We also describe decision support systems, Operations Research (OR) models and methods more specific for the Swedish case, together with an international view of OR work within this problem area.
The problem we consider is annual harvesting planning from the perspective of Swedish forest companies. The main decisions deal with which areas to harvest during an annual period so that the wood-processing facilities receive the required amount of assortments. Each area has a specific size and composition of assortments, and the choice of harvesting areas affects the production level of different assortments. We need to decide which harvest team to use for each area, considering that each team has different skills, home base, and production capacities. Also, the weather and road conditions vary during the year. Some roads cannot be used during certain time periods and others should be avoided. The road maintenance cost varies during the year. Also, some areas cannot be harvested during certain periods. Overall decisions about transportation and storage are also included. In this paper, we develop a mixed integer programming model for the problem. There are binary variables associated with harvesting, allocation of teams, and road-opening decisions. The other decisions are represented by continuous variables. We solve this problem directly with CPLEX 8.1 within a practical solution time limit. Computational results from a major Swedish forest company are presented.
The problem we consider is short-term harvesting planning for a total planning period of 4–6 weeks where we want to decide the harvest sequences or schedules for harvest crews. A schedule is an order or sequence of harvest areas assigned to each crew. The harvesting of areas is planned in order to meet industrial demand. The total cost includes harvesting, transportation, and storage. One considerable cost is due to the quality reduction of logs stored at harvest areas. There are a number of restrictions to be considered. Areas are of varying size and the composition of assortments in each area is different. Each harvest team has different skills, a different home base, and different production capacity. Another aspect is the road network. There is a cost related to road opening (restoring, snow removal). In this paper, we develop a mixed integer programming (MIP) model for the problem. The schedules are represented by 0/1 variables. With a limited number of schedules, the problem can be solved by a commercial MIP solver. We have also developed a heuristic solution approach that provides high-quality integer solutions within a distinct time limit to be used when more schedules are used. Computational results from a major Swedish forest company are presented.