The partitioning min–max weighted matching problem
Publication date
2015-06-20
Document type
Forschungsartikel
Author
Organisational unit
Universität Siegen
Scopus ID
Publisher
Elsevier
Series or journal
European Journal of Operational Research
ISSN
Periodical volume
247
Periodical issue
3
First page
745
Last page
754
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Assignment
Bipartite graph
Container transshipment
Maximum matching
Partitioning
Abstract
We introduce and analyze the Partitioning Min-Max Weighted Matching (PMMWM) Problem. PMMWM combines the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the strongly NP-hard Min-Max Weighted Matching (MMWM) Problem, that has recently been introduced in the literature. In contrast to PMMWM, the latter problem assumes the partitioning to be given. Applications arise in the field of intermodal container terminals and sea ports. We propose a MILP formulation for PMMWM and prove that the problem is NP-hard in the strong sense. Two heuristic frameworks are presented. Both of them outperform standard optimization software. Our extensive computational study proves that the algorithms provide high quality solutions within reasonable time.
Version
Published version
Access right on openHSU
Metadata only access