© K. Mehdi et al., Published by EDP Sciences, 2014

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 b_h and fixed cost f_h. The limited capacity of suppliers are denoted by w_j’s. The demand of each costumer i ∈ I is v_i, where v_i ≤ b_h for all i, h and v_i ≤ w_j for all i, j. The trigonal distance d_hij 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, x_hij 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 y_h = 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, v_i, w_j and b_h 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 v_i’s. We assume(3)where is its nominal value, z_i = ±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 x_hij ∈ {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.

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

All Tables