Modelling a Clustered Generalized Quadratic Assignment Problem

Judith Scagnetti; Andreas Beham; Stefan Wagner; Michael Affenzeller

Modelling a Clustered Generalized Quadratic Assignment Problem

Judith Scagnetti, Andreas Beham, Stefan Wagner, Michael Affenzeller

Research output: Chapter in Book/Report/Conference proceedings › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

This paper is about the modelling of an assignment problem motivated by a real world problem instance. We consider multiple pieces of equipment which need to be assigned to several locations taking into account capacities as well as relations between equipment and distances between locations. Additionally, a clustering of locations is taken into account that groups locations into areas or fields. It is forbidden to assign the same equipment to locations in different fields. The problem arises in many real world applications such as facility layout or location problems. We discuss the complexity of the problem and prove its NP-hardness. Further two linearization approaches are presented as well as computational studies of the original and the linearized models are conducted. Experimental tests are carried out using CPLEX.

Original language	English
Title of host publication	27th European Modeling and Simulation Symposium, EMSS 2015
Editors	Michael Affenzeller, Francesco Longo, Lin Zhang, Agostino G. Bruzzone, Yuri Merkuryev, Emilio Jimenez
Publisher	DIPTEM University of Genova
Pages	307-313
Number of pages	7
ISBN (Electronic)	9788897999485
Publication status	Published - 2015
Event	The 27th European Modeling & Simulation Symposium EMSS 2015 - Bergeggi, Italy Duration: 21 Sept 2015 → 23 Sept 2015 http://www.msc-les.org/conf/emss2015/

Publication series

Name	27th European Modeling and Simulation Symposium, EMSS 2015

Conference

Conference	The 27th European Modeling & Simulation Symposium EMSS 2015
Country/Territory	Italy
City	Bergeggi
Period	21.09.2015 → 23.09.2015
Internet address	http://www.msc-les.org/conf/emss2015/

Keywords

Generalized quadratic assignment problem
Linearization
Location problem
Logistics

Cite this

Scagnetti, J., Beham, A., Wagner, S., & Affenzeller, M. (2015). Modelling a Clustered Generalized Quadratic Assignment Problem. In M. Affenzeller, F. Longo, L. Zhang, A. G. Bruzzone, Y. Merkuryev, & E. Jimenez (Eds.), 27th European Modeling and Simulation Symposium, EMSS 2015 (pp. 307-313). (27th European Modeling and Simulation Symposium, EMSS 2015). DIPTEM University of Genova.

Scagnetti, Judith ; Beham, Andreas ; Wagner, Stefan et al. / Modelling a Clustered Generalized Quadratic Assignment Problem. 27th European Modeling and Simulation Symposium, EMSS 2015. editor / Michael Affenzeller ; Francesco Longo ; Lin Zhang ; Agostino G. Bruzzone ; Yuri Merkuryev ; Emilio Jimenez. DIPTEM University of Genova, 2015. pp. 307-313 (27th European Modeling and Simulation Symposium, EMSS 2015).

@inproceedings{00ce14da40a94fb3a8f354dcb252eed7,

title = "Modelling a Clustered Generalized Quadratic Assignment Problem",

abstract = "This paper is about the modelling of an assignment problem motivated by a real world problem instance. We consider multiple pieces of equipment which need to be assigned to several locations taking into account capacities as well as relations between equipment and distances between locations. Additionally, a clustering of locations is taken into account that groups locations into areas or fields. It is forbidden to assign the same equipment to locations in different fields. The problem arises in many real world applications such as facility layout or location problems. We discuss the complexity of the problem and prove its NP-hardness. Further two linearization approaches are presented as well as computational studies of the original and the linearized models are conducted. Experimental tests are carried out using CPLEX.",

keywords = "Generalized quadratic assignment problem, Linearization, Location problem, Logistics",

author = "Judith Scagnetti and Andreas Beham and Stefan Wagner and Michael Affenzeller",

year = "2015",

language = "English",

series = "27th European Modeling and Simulation Symposium, EMSS 2015",

publisher = "DIPTEM University of Genova",

pages = "307--313",

editor = "Michael Affenzeller and Francesco Longo and Lin Zhang and Bruzzone, {Agostino G.} and Yuri Merkuryev and Emilio Jimenez",

booktitle = "27th European Modeling and Simulation Symposium, EMSS 2015",

note = "The 27th European Modeling & Simulation Symposium EMSS 2015 ; Conference date: 21-09-2015 Through 23-09-2015",

url = "http://www.msc-les.org/conf/emss2015/",

}

Scagnetti, J, Beham, A, Wagner, S & Affenzeller, M 2015, Modelling a Clustered Generalized Quadratic Assignment Problem. in M Affenzeller, F Longo, L Zhang, AG Bruzzone, Y Merkuryev & E Jimenez (eds), 27th European Modeling and Simulation Symposium, EMSS 2015. 27th European Modeling and Simulation Symposium, EMSS 2015, DIPTEM University of Genova, pp. 307-313, The 27th European Modeling & Simulation Symposium EMSS 2015, Bergeggi, Italy, 21.09.2015.

Modelling a Clustered Generalized Quadratic Assignment Problem. / Scagnetti, Judith; Beham, Andreas; Wagner, Stefan et al.
27th European Modeling and Simulation Symposium, EMSS 2015. ed. / Michael Affenzeller; Francesco Longo; Lin Zhang; Agostino G. Bruzzone; Yuri Merkuryev; Emilio Jimenez. DIPTEM University of Genova, 2015. p. 307-313 (27th European Modeling and Simulation Symposium, EMSS 2015).

Research output: Chapter in Book/Report/Conference proceedings › Conference contribution › peer-review

TY - GEN

T1 - Modelling a Clustered Generalized Quadratic Assignment Problem

AU - Scagnetti, Judith

AU - Beham, Andreas

AU - Wagner, Stefan

AU - Affenzeller, Michael

PY - 2015

Y1 - 2015

N2 - This paper is about the modelling of an assignment problem motivated by a real world problem instance. We consider multiple pieces of equipment which need to be assigned to several locations taking into account capacities as well as relations between equipment and distances between locations. Additionally, a clustering of locations is taken into account that groups locations into areas or fields. It is forbidden to assign the same equipment to locations in different fields. The problem arises in many real world applications such as facility layout or location problems. We discuss the complexity of the problem and prove its NP-hardness. Further two linearization approaches are presented as well as computational studies of the original and the linearized models are conducted. Experimental tests are carried out using CPLEX.

AB - This paper is about the modelling of an assignment problem motivated by a real world problem instance. We consider multiple pieces of equipment which need to be assigned to several locations taking into account capacities as well as relations between equipment and distances between locations. Additionally, a clustering of locations is taken into account that groups locations into areas or fields. It is forbidden to assign the same equipment to locations in different fields. The problem arises in many real world applications such as facility layout or location problems. We discuss the complexity of the problem and prove its NP-hardness. Further two linearization approaches are presented as well as computational studies of the original and the linearized models are conducted. Experimental tests are carried out using CPLEX.

KW - Generalized quadratic assignment problem

KW - Linearization

KW - Location problem

KW - Logistics

UR - http://www.scopus.com/inward/record.url?scp=84949510523&partnerID=8YFLogxK

M3 - Conference contribution

T3 - 27th European Modeling and Simulation Symposium, EMSS 2015

SP - 307

EP - 313

BT - 27th European Modeling and Simulation Symposium, EMSS 2015

A2 - Affenzeller, Michael

A2 - Longo, Francesco

A2 - Zhang, Lin

A2 - Bruzzone, Agostino G.

A2 - Merkuryev, Yuri

A2 - Jimenez, Emilio

PB - DIPTEM University of Genova

T2 - The 27th European Modeling & Simulation Symposium EMSS 2015

Y2 - 21 September 2015 through 23 September 2015

ER -

Modelling a Clustered Generalized Quadratic Assignment Problem

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this