In this paper we study a class of multi-item lot-sizing problems with dynamic demands, as well as lower and upper bounds on a shared resource with a piecewise linear cost. The shared resource might be supply, production or transportation capacity. The model is particularly applicable to problems with joint shipping and/or purchasing cost discounts. The problem is formulated as a mixed-integer program. Lagrangean relaxation is used to decompose the problem into a set of simple sub-problems. A heuristic method based on sub-gradient optimization is then proposed to solve a particular case often encountered in the consumer goods wholesaling and retailing industry. Our tests show that the heuristic proposed is very efficient in solving large real-life supply planning problems.
In the consumer goods wholesaling and retailing industry, a large number of stock keeping units must be managed on a regular basis. The items are typically purchased in families, each family being associated to a specific external vendor, and usually they are shipped together. The transportation costs thus incurred account for a significant part of the items price, and their structure may incorporate economies of scale, as well as constraints on the total load which can be carried. In some cases, the transportation costs are included in the item prices and they are not paid directly by the buyer. In such cases, however, the vendor often offers discounts on the total amount of the order and imposes constraints on its size. In either case, this give rise to the class of dynamic multi-item lot-sizing problems with joint piecewise linear resource costs studied in this paper. Piecewise linear cost functions can also be used to model several production lot-sizing situations and the methodology proposed can be used to solve these problems.
The problem studied is a generalization of several of the dynamic lot-sizing problems that have been treated in the literature. Much work has been done to find exact and heuristic methods to solve the numerous versions of the dynamic lot-sizing problem. The complexity of the problem depends largely on whether it deals with a single item or several items, on the resource constraints imposed on the lot sizes (unconstrained or joint lower bounds and/or joint upper bounds) and on the type of cost structure which applies.
A dynamic programming algorithm to solve the basic single-item case was published by Wagner and Whitin (1958). Comparisons of the numerous heuristics that have been developed to solve the single-item problem can be found in Zoller and Robrade (1988). Bitran and Yanasse (1982) provide a review and analysis of the problem under capacity constraints. When several items are involved, additional complexity is introduced by cost interactions and/or by resource interactions. The simplest multi-item case is the one where the interaction is due only to a joint setup (or order) cost. Dynamic programming algorithms to solve this problem were proposed by Zangwill (1966), Veinott (1969), Kao (1979), Silver (1979) and Haseborg (1982). Atkins and Iyogun (1988) developed a heuristic procedure. Maes and Van Wassenhove (1986) reviewed the case where the interaction is due only to capacity constraints and where costs are stationary. They also provide a comparison of three “simple” heuristics. An integer programming approach with strong cutting planes was proposed by Barany et al. (1984), Pochet and Wolsey (1991), Belvaux and Wolsey (2001) and Lagrangean relaxation procedures were developed by Thizy and Van Wassenhove (1985), Gelders et al. (1986), Trigeiro et al. (1989), Diaby et al. (1992) and Sox and Gao (1999). A number of set partitioning and column generation heuristics are also proposed by Cattrysse et al. (1990).
To the best of our knowledge, little work was done on the case where the interaction is caused by joint order cost functions as well as by restrictions on the amount of resources used/available. Such situations are very common in the consumer goods wholesaling and retailing industry and occur when shipment costs depend on the total amount of transportation resources used by all the items, and/or when all-units or incremental discounts are offered by vendors on the total invoice value, instead of on the quantity ordered for individual items, as is usually assumed in the literature. A particular case with joint piecewise linearly increasing freight rates is discussed by van Norden and van de Velde (2005).
In practice, shipping costs depend on several factors. Pricing mechanisms are not the same for private fleets and for public carriers. In the former case, for our purposes, only variable costs related to specific shipments are relevant. In the latter case, freight-rate structures depend on the mode used, the shipping distance and weight, the type of shipment (TL or LTL), and the commodity class of the item shipped. For this reason, few studies have attempted to model freight-rate structures explicitly. Buffa and Munn (1989) and Swenseth and Godfrey (2002) provide reviews of the work done in this area. Most of the currently available models that incorporate a realistic representation of freight-rate structures deal only with the single-item, constant-demand case.
Little work has been done on the modeling of joint discounts based on total invoice value. Some aspects of the problem are studied by Chakravarty (1984) and by Silver and Peterson (1985) for the unconstrained constant-demand case. To the best of our knowledge, however, no previous work is available on joint discounts for the multi-item dynamic-demand problem treated in this paper.
The paper is organized as follows. In Section 2 the problem is defined and formulated as a mixed-integer program. In Section 3 Lagrangean relaxation is used to decompose it in a set of simple sub-problems. A heuristic method based on subgradient optimization is then proposed. Finally, Section 4 presents the experiments performed to assess the solution method and it discusses computational results.
We have formulated a mixed-integer linear programming model to plan the supply of a family of items under piecewise linear resource costs. The model accommodates switches between transportation modes based on volumes, various types of discounts that may be offered in practice on transportation and/or purchasing prices, as well as convex or concave production capacity costs. Mathematical properties of a Lagrangean relaxation of the model were developed and a Lagrangean heuristic procedure that exploits these properties was presented. The Lagrangean heuristic appears to be efficient and robust for solving large real-life supply planning problems.
