Efficient solution of large scale, single-source, capacitated plant location problems
- PDF / 175,825 Bytes
- 7 Pages / 595 x 842 pts (A4) Page_size
- 51 Downloads / 152 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $12.00 http://www.stockton-press.co.uk/jor
Ef®cient solution of large scale, single-source, capacitated plant location problems KS Hindi1* and K PienÂkosz2 1
Brunel University, Middlesex, UK and 2Warsaw University of Technology, Poland
The single-source, capacitated plant location problem is considered. This problem differs from the capacitated plant location problem by the additional requirement that each customer must be supplied with all its demand from a single plant. An ef®cient heuristic solution, capable of solving large problem instances, is presented. The heuristic combines Lagrangian relaxation with restricted neighbourhood search. Computational experiments on two sets of problem instances are presented. Keywords: location; lagrangian relaxation; restricted neighbourhood search
subject to
Introduction In the single-source capacitated plant location problem (SSCPLP), we are given n customers and m plants. Each customer, i, is to be supplied with a single commodity from a single plant, j. The demand of each customer, di , is known, as is the cost of assigning each customer to each plant, cij . The capacity of each plant, sj , is also known, as well as the ®xed charge, fj , incurred whenever plant j is used. It is required to choose a subset of the plants to operate and assign each customer to one of the chosen plants, such that the total cost is minimised and plant capacities are not exceeded. If the condition that each customer should be supplied with all its demand from one single plant is dispensed with, that is, if it is allowed to supply a customer from more than one plant, then SSCPLP reduces to the capacitated plant location problem (CPLP). SSCPLP can be formulated as follows. Let xij yj
1
if customer i is assigned to plant j;
0 1 0
otherwise if plant j is chosen; otherwise
Then, Z
p min
P ij
cij xij
P j
fj yj
1
*Correspondence: Professor KS Hindi, Department of Manufacturing and Engineering Systems, Brunel University, Uxbridge, Middlesex UB8 3PH, England. E-mail: [email protected]
P P i
j
xij 1
8i
2
di xij 4 sj yj 8j P P s j yj 5 di j
xij 2 f0; 1g
3
4
i
yj 2 f0; 1g
8i; j
5
Constraints (2) stipulate that each customer should be assigned to a single plant. Constraints (3) enforce the plant capacities, as well as ensure that a customer can be assigned only to a plant that is chosen. Constraint (4) stipulates that the total capacity of the chosen plants should be adequate to cover the total demand. CPLP may be obtained simply by relaxing the integrality condition on variables xij , that is, allowing them to vary continuously between zero and one, in which case xij denotes the fraction of the demand of i supplied from j. Constraint (4) is in fact redundant, since it is covered jointly by (2) and (3). However, it has been shown1±3 that adding such an aggregate capacity constraint leads to tighter lower bounds for CPLP. This is also the case for SSCPLP. Moreover, as will be
Data Loading...
