Issue |
Int. J. Simul. Multisci. Des. Optim.
Volume 5, 2014
|
|
---|---|---|
Article Number | A03 | |
Number of page(s) | 3 | |
DOI | https://doi.org/10.1051/smdo/2013015 | |
Published online | 04 February 2014 |
Article
The capacitated plant location problem with customer and supplier matching and interval demands uncertainty
Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran
* e-mail: salahim@guilan.ac.ir
Received:
7
April
2013
Accepted:
23
October
2013
The capacitated plant location problem with customer and supplier matching can be modeled as a mixed integer linear program, where the product distribution from plants to customers and the material supply from suppliers to plants are considered together. In order to save allocation cost, distribution trip and a supply trip is merged into one triangular trip. Moreover, vehicles from plants visit a customer and a supplier for each trip. In this paper, we assume interval uncertainties in the demands of costumers. We show that the robust counterpart of the original model with interval uncertainty is equivalent to a larger mixed integer linear program. Finally, the original and robust models are compared on several randomly generated examples showing the impact of uncertainty.
Key words: Capacitated plant location / Matching / Mixed integer linear program / Interval uncertainty
© K. Mehdi et al., Published by EDP Sciences, 2014
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1 Introduction
The capacitated plant location problem (CPL) consists of locating a set of potential plants with capacities, and assigning a set of customers to these plants. The goal is to minimize the total fixed and shipping costs such that the demands of all customers are satisfied without violating the capacity of plants. The CPL is modeled as a mixed integer linear programming problems, where several heuristic algorithms are designed to solve it [2–6, 8].
A slightly different problem is CLP with customer and supplier matching. In this problem, customers, suppliers and a set of potential plants are mixed in a same network and each open plant holds its fleet of homogenous vehicles. It is assumed that the vehicles serve customers from a plant, the same vehicles visit suppliers from customers, and then the vehicles transport material/parts from suppliers back to the plant [9]. In this paper, first we describe CLP with customer and supplier matching and then present its robust counterpart when interval uncertainties are assumed for demands [1]. It is shown that the robust counterpart of CLP is a larger mixed integer linear program. Finally, on several randomly generated examples, original and robust problems are compared using Lingo 11 [7] to show the impact of the uncertainty.
2 CLP with customer and supplier matching
Let us consider a graph G = (N, A) where N denotes the nodes and A denotes the set of directed arcs between nodes [9]. Nodes are divided to three categories: a set of potential plants H, a set of customers I, and a set of potential suppliers J such that N = H ∪ I ∪ J. Each potential plant h ∈ H has a limited capacity bh and fixed cost fh. The limited capacity of suppliers are denoted by wj’s. The demand of each costumer i ∈ I is vi, where vi ≤ bh for all i, h and vi ≤ wj for all i, j. The trigonal distance dhij is equal to(1)which means the distance from the plant h visiting customer i, from customer i to supplier j, from supplier j back to plant h [9]. The optimizer’s goal is to design a model which minimizes the total opening costs of plants and allocation costs subject to the following constraints: each customer should be served by one plant and matched with one supplier, each open plants does not supply more than its capacity, suppliers capacity cannot exceeded. Moreover, xhij is equal to 1 if and only if customer i and supplier j are assigned to plant h, otherwise it is equal to 0. If plant h is open, then yh = 1, otherwise it is equal to 0. It should be noted that full truckloads are considered in the transportation process, namely the demands and capacities are multiples of truck capacity. In other words, vi, wj and bh are measured by the number of vehicles. The parameter c is the cost per unit distance per unit demand. Thus the problem can be formulated as the following binary integer linear program [9].
(2)
However, it is known that most of the real world problems are having certain uncertainty in problem data. In such a case, the solution of the previous model might not be optimal for the uncertain model. In the next section, we consider uncertainty on the demands of customers and show the robust counterpart of (2) is equivalent to a larger mixed integer linear program. Finally, the impact of uncertainty is shown using several randomly generated test problems.
3 Robust model
In this section, we consider uncertainty on demands vi’s. We assume(3)where
is its nominal value, zi = ±1 and
is the amount of uncertainty, which is a positive integer as demands and capacities are in the number of truckloads. Moreover we assume that
(4)where Γ is a given positive integer.
Now let us consider the third set of constraints in (2)(5)
Its robust counterpart is given by(6)
This should hold in the worst case for each xhij ∈ {0, 1}. Thus first we solve the following problem for ∀j ∈ J:(7)
Let us consider the following LP relaxation of (3):(8)
The dual of (8) is given by(9)
Therefore, the third set of constraints in the robust case is equivalent to:(10)
The robust counterpart of the second set of constraints can be worked out in the same manner. Because the objective function contains the demands and we have uncertainties with them, we take the second term of objective function into the constraints with variable t. Thus, the robust counterpart of (2) is(11)
The last two constraints are robust counterpart of the objective function which is taken into the constraints. As we see, the robust counterpart of (2) is a larger mixed integer linear program.
4 Numerical experiments
In this section, we present numerical experiments on the original and robust models for five different examples where the demands, capacity of plants, fixed costs, capacity of suppliers, and the distance between customers, plants and suppliers are randomly generated in the intervals [10, 50], [200, 600], [300, 600], [100, 400], [10, 60], respectively. For all examples we consider c = 1.0 and Γ = 15. We use Lingo 11 to solve the original and robust model and results are summarized in the following Table 1.
Comparison of original and robust models for five different examples.
The time increase is expected as the dimension of the robust problem is much larger than the original one. What we have observed is that in the robust problem the optimal solution might change, namely the assignment of costumers to plants and suppliers might be different if we consider uncertainty in the demands. For example when i = 20, j = 5, h = 5, in the optimal solution of the original problem(12) while in the optimal solution of the robust problem
(13)
This happens for the other choices of as well. Thus we conclude that it would be better to incorporate uncertainty in the model if there are possibilities of uncertainty, otherwise the solution obtained by the original model might lead to a completely different.
References
- Bertsimas D, Thiele A. 2006. A robust optimization approach to inventory theory. Operations Research, 54(1), 150–168. [CrossRef] [MathSciNet] [Google Scholar]
- Delmaire H, Di’az JA, Ferna’ndez E. 1999. Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem. INFOR, Canadian Journal of Operational Research and Information Processing, 37, 194–225. [Google Scholar]
- Domschke W, Drexl A. 1985. ADD-heuristics’ starting procedures for capacitated plant location models. European Journal of Operational Research, 21(1), 47–53. [CrossRef] [Google Scholar]
- Feldman E, Lehrer FA, Ray TL. 1966. Warehouse location under continuous economies of scale. Management Science, 12, 670–684. [CrossRef] [Google Scholar]
- Jacobsen SK. 1983. Heuristics for the capacitated plant location model. European Journal of Operational Research, 12(3), 253–261. [CrossRef] [Google Scholar]
- Kratica J, Tosic D, Filipovic V, Ljubic I. 2001. Solving the simple plant location problem by genetic algorithm. RAIRO Operations Research, 35, 127–142. [CrossRef] [EDP Sciences] [MathSciNet] [Google Scholar]
- Lingo 11, http://www.lindo.com. [Google Scholar]
- Sa G. 1969. Branch and bound and approximate solutions to the capacitated plant location problem. Operations Research, 17(6), 1005–1016. [CrossRef] [Google Scholar]
- Zhu Z, Chu F, Sun L. 2010. The capacitated plant location problem with customers and suppliers matching. Transportation Research Part E, 46(3), 469–480. [CrossRef] [Google Scholar]
Cite this article as: Mehdi K, Salahi M & Jamalian A: The capacitated plant location problem with customer and supplier matching and interval demands uncertainty. Int. J. Simul. Multisci. Des. Optim., 2014, 5, A03.
All Tables
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.