Extrait
ii
Abstract
In this thesis, metaheuristic solution approaches for the decentralized capacitated
facility location problem are deduced, implemented and assessed. As the
mentioned problem is a combinatorial bilevel problem it is not easily solvable by
means of linear programming. Therefore, different metaheuristic techniques,
namely Tabu Search and Simulated Annealing, are used. Each of them is split into
several variants. Tabu Search has turned out to deliver better results than
Simulated Annealing and converges also from bad initial solutions towards the
global optimum. However, the performance of the algorithms is highly dependent
on the concrete parameter settings. Thus, the gap between the optimum found and
the global optimum can vary from 0 to a multiple of the global optimum
depending on the used variant.
iii
Table of Contents
Table of Content
List of Figures
List of Tables...vi
List of Symbo
1
1
2
3
2.1
3
2.1.1 General
3
2.1.2 A Bilevel Decentralized Capacitated Facility
4
2.2
7
2.2.1
8
2.2.1.1 Basic
8
9
1
2.2.1.5 Evaluation Metrics and Candidate
List S
4
6
2.2.2
0
2.2.2.1 Basic
iv
2.2.2.3 Inhomogeneous and Homogeneous
2.2.2.5 Modification
3
Development and Implementation of
3.1
3.1.1
3.1.2
3.1.3
3.2
3.2.1
4
3.2.1.1 Actualization of the Tabu List and
6
3.2.2
3.3
3.3.1
3.3.2
4
1
5
9
v
List of Figures
Figure 1: Structure of an iterative heuristic method
.29
Figure 2: Tabu Search structure
...3 5
Figure 3: Actualization of the tabu list
...36
vi
List of Tables
Table 1: Comparison of different problem instances
solved with Tabu Search variant TS-T1
Table 2: Comparison of different Tabu Search variants
for solving instance i300_2
4
Table 3: Comparison of different candidate list and
intensification strateg
5
Table 4: Comparison of different problem instances
solved with Simulated Annealing variant SA-A-3
Table 5: Comparison of different Simulated Annealing variants
for solving instance i300_2
vii
List of Symbols
General Mathematical Symbols:
Spaces, Matrices and Numbers:
the natural numbers
the real numbers
the n-dimensional real vector space
a matrix with line index and column index
limit approaching 0 from above or below
Sets and Set Operators:
set contains the elements
set is a subset of set
set is a proper subset of set
set is a superset of set
set is a proper superset of set
is an element of set
set contains the element
set is an empty set
set-theoretic difference
set-theoretic union
set-theoretic intersection
cardinality of set
closed interval from to
open interval from to
viii
Relational Operators, Quantifiers and Arithmetic Operators:
definition signs
identical equality sign
relational operators: less, less or equal, much less
relational operators: greater, greater or equal, much greater
universal quantifier
existential quantifier
negation
vertical bar for set properties
not further specified composition
difference operator
summation operator
Functions:
a function mapping
to
natural exponential function
natural logarithm function
maximum or minimum of a set
argument of the maximum or minimum of a function
limit of a function
as approaches
derivative of
with respect to
Stochastic Symbols:
probability that takes the value
indicator function
continuous uniform distribution in the interval
ix
Globally used Problem-specific Variables and Parameters:
Linear Programming:
minimization of the objective function
subject to all constraints contained in the vector
Problem-specific Sets:
set of potential plants
set of product types
subset of products that can be produced on plant ;
and
subset of plants that are able to produce product ;
and
Problem-specific Parameters:
opportunity cost per unit of unused production capacity if
plant is opened
demand of product
capacity consumption per unit for the production of product
in plant
production cost per capacity unit in plant
production capacity in plant
transportation cost of product produced in plant
setup cost for plant
large positive number
x
Problem-specific Decision Variables:
fraction of demand of product produced in plant
else
,
up
set
is
plant
if
,
i
additional decision variables for the transformed model
Other Frequently Used Parameters:
solution space
set of moves
current solution
neighborhood function of a solution
general symbol for proximate solution from
selected proximate solution from
tabu list
tally parameter for Homogeneous Simulated Annealing
move value of the move leading from to
molar gas constant
Boltzmann constant
1
1 Introduction
The thesis on hand describes the comparison of different metaheuristics in order
to generate solutions for the bilevel decentralized capacitated facility location
problem. This optimization problem consists of choosing a set of facilities to be
opened out of a superset of potential facilities. The objective is to minimize cost,
while taking certain constraints into account.
In this thesis, however, this usual facility location model, which can relatively
easily be solved as a linear optimization problem, becomes expanded. There is an
additional submodel that is intended to develop an optimal production plan for the
facilities chosen within the superordinate model. On the sublevel, also cost has to
be minimized and as one major constraint the entire external demand has to be
satisfied. Such a bilevel problem containing two hierarchically arranged objective
functions cannot be solved using the usual methods of linear programming any
more.
The problem just described is a combinatorial one. Therefore, it is for larger
instances either not possible to perform a brute-force search that examines every
single candidate solution, because it is always an NP-hard problem due to its
exponential complexity (Audet et al., 1997). If there are positions to be
occupied by one of alternatives there are
possibilities to do this. In this case
, because the decision whether to open a facility or not is a binary one. This
leads to
possible solutions, if is the number of potential facilities in big O
notation
. For example, if 100 facilities are considered, there are
theoretically
possibilities how to solve this problem. For
instances that are still larger, this number increases accordingly in an exponential
Of course,
not all of these solutions come into consideration as potentially best solutions, as
some are infeasible (e.g. the null vector, i.e. choosing not a single plant which will
not satisfy the demand constraint) and others are not meaningful (e.g. selecting all
plants, which will produce enormous costs).
In view of these obstacles, other ways of solving such an optimization problem
have to be considered. For the bilevel facility location problem a combination of
heuristic search and linear programming suggests itself, because the subordinate
2
problem can be solved as a linear program with adequate software, whereas this is
not possible for the problem as a whole. Thus, the subordinate problem can be
embedded into a heuristic superstructure that optimizes the superordinate
objective function taking account of the sublevel problem. The applied heuristics
can be derived from different metaheuristics such as Tabu Search, Simulated
Annealing, Evolutionary Algorithms, Ant Colony Algorithms or Neural
Networks. As these methods are heuristic they cannot guarantee the global
optimality of the solution, but they can nevertheless generate good results
Within the scope of this thesis, existing literature on this topic is reflected first.
The problem on hand is described and two metaheuristic methods (Tabu Search
and Simulated Annealing) are introduced. One reason for comparing just these
two metaheuristics is the fact that one of them is deterministic and one
randomized, which enables statements on the meaningfulness of randomization.
Finally, different variants of applying these metaheuristics on the decentralized
capacitated facility location problem are worked out. The resulting algorithms
have been implemented with Xpress IVE. Test data have been used to evaluate
and compare the different approaches.
3
2 Review on Literature and Research
This chapter should give an overview of the theoretical foundations of bilevel
programming as well as metaheuristic methods. In particular, the two
metaheuristics that have been implemented within the scope of this thesis are
explained in detail.
2.1 Literature on Bilevel Programming
In this section general aspects of multilevel problems are introduced. Moreover,
the decentralized capacitated facility location problem is further described and
formulated as a linear programming model.
2.1.1 General Definition of Bilevel Programs
Linear optimization problems can be classified by the number of objective
functions, each of them nested in the superordinate ones. The case which is by far
most simple is a problem with only one objective function, a so-called monolithic
problem. Monolithic linear optimization problems are solvable with common
software using for example the Simplex method.
Multilevel problems, however, possess more than one objective function and are
much more difficult to be solved than monolithic ones. Let
with
,
and
be a set of objective functions. Let
further be
the set of all solutions of this program
and
a constraints vector. can be partitioned into subsets with the
following relation:
(1)
4
A multilevel problem can thus be described as an entity of hierarchically nested
programming problems
(Bialas, Karwan, 1978):
(2)
Bilevel problems are a special case of such hierarchical multilevel problems with
two objective functions (
). They consist of an outer and an inner problem,
whereupon the inner one contains the constraints as can be seen in the foregoing
figure.
Solving multilevel problems and hence also bilevel ones is by no means trivial. As
an optimality-guaranteeing approach is rather difficult, heuristic methods are
applied. In order to make a statement regarding the performance of different
heuristics, several methods have to be compared.
2.1.2 A Bilevel Decentralized Capacitated Facility Location Problem
As the facility location problem is regarded in a decentralized environment it is
not easily possible to represent this problem by a monolithic model (Cao, Chen,
2004). Instead, the decision-making process consists of two hierarchical levels.
On the upper level the so-called
, which means that the
plants to be opened are selected centrally. The second level decision the
however, has been delegated over all selected plants. As this sublevel decision
also affects the upper level due to its consequences on the arising cost, the
relationship between the two levels is a reciprocal one. Therefore, the problem on
hand can also be seen in a game-theoretical context with a leader and a follower.
Cao and Chen (2004) have formulated the following bilevel optimization model
out of this problem, whereupon a redundant constraint has been discarded here:
Fin de l'extrait de 63 pages
- Citation du texte
- Florian Grodeke (Auteur), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, Munich, GRIN Verlag, https://www.grin.com/document/336709
Textes similaires
Devenir un auteur
✕
Extrait de
63
pages
Commentaires