Geoscience Reference
In-Depth Information
n
D
10; 20; 30; 40; 60.(2)
Number of suppliers
: p is the second factor
with three levels for each choice of n: p
Db
n=5
cC
1;
b
n=2
c
;4
b
n=5
c
.(3)
Type of problem
: Each -vector is associated with a different objective function.
Its levels are designed depending on the value of n as follows: (a) -vector
corresponding to the p-median problem, i.e.
D
.1;:::;1/
2
n
;(b)-vector
R
n
;(c)-vector
corresponding with the
b
n=4
c
-centrum problems; and (d) -vector corresponding to
the .k
1
;k
2
/-trimmed mean problem, i.e.
D
.0;:::;0;1;:::;1;0;:::;0/
2
corresponding to the p-center problem, i.e.
D
.0;:::;0;1/
2
R
n
where k
1
Db
0:2n
c
, k
2
Db
0:2n
c
.(4)
Demand of facilities
: Each demand is
considered integer and uniformly drawn from Œ10;20.(5)
Capacity of suppliers
:We
consider that the capacities are uniformly discrete random variables in the interval
R
Œ1:1
P
iD1
a
i
=p;1:4
P
iD1
a
i
=p. This choice ensures feasibility of the considered
problems. (6)
Transportation cost
: We assume free self service and integer costs.
The values c
ij
, i
¤
j, are drawn uniformly in Œ0;200.
We solve five instances for each possible combination of levels and we report
the average and maximum: running time, gap at the root node and number of nodes
in the branch-and-bound tree for this formulation. All computational studies were
performed on a PC with a
Genuine Intel(R) CPU U4100
with two processors at
1.30 GHz and 4 GB of RAM. To solve the different instances of the problems
we used XPRESS-IVE solver version 7.5, with a code implemented in XPRESS-
MOSEL version 3.4.2.
The information of our computational test is reported in Table
10.8
that sum-
marizes the results for the four considered problems types. The organization of the
table is the following: columns show the results for the different sizes of n and p.A
superindex in some values of p states the number of instances for the corresponding
combination of n and p exceeding the CPU time limit (1 h). Each block of rows
reports the results of the instances based on the formulation (
10.43
)-(
10.51
).
Within each block of rows we report on the
GAP
at the root node (average -
Ag- and maximum -Mg-),
CPU
-time to solve the integer problems (average -At-
and maximum -Mt-) and number of
NODES
in the branch-and-bound tree (average
-An- and maximum -Mn-).
We observe, from the results in Table
10.8
that we could solve most of the
instances, even medium sized n
D
60, within 1 h of CPU time. This fact shows a
good performance of the formulation. In addition, it is worth noting that the quality
of the lower bounds provided by this formulation depends on the type of problem.
In general, the lower bounds are rather poor for larger values of p relative to n.On
the other hand, for small to medium values of p relative to n the performance of
the lower bounds are good for median and trimmed mean problems, reasonable for
k-centrum (less than 50 %) and poor for the center problem. These results show that
there is room for further investigation on the polyhedral structure of this formulation
in order to develop valid inequalities that could be integrated in a Branch & Cut
algorithm to solve faster, larger problem sizes.
In conclusion, the formulation of the CDOMP based on covering, (
10.43
)-
(
10.51
), is a promising approach. Moreover, it can be also strengthen with known
