Type of Publication: Article in Journal

The Partitioning Min–Max Weighted Matching Problem

Author(s):

Kress, D.; Meiswinkel, S.; Pesch, E.

Title of Journal:

European Journal of Operational Research

Volume (Publication Date):

247 (2015)

Number of Issue:

3

pages:

745-754

Language:

Englisch

Keywords:

Assignment, Partitioning, Maximum matching, Bipartite graph, Container transshipment

Digital Object Identifier (DOI):

doi:10.1016/j.ejor.2015.06.041

Fulltext:

The Partitioning Min–Max Weighted Matching Problem (439 KB)

Citation:

Download BibTeX

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.