Excerpt

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:

Excerpt out of 63 pages

- Quote paper
- Florian Grodeke (Author), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, Munich, GRIN Verlag, https://www.grin.com/document/336709

Publish now - it's free

Comments