Art der Publikation: Beitrag in Zeitschrift

The Partitioning Min–Max Weighted Matching Problem

Autor(en):

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

Titel der Zeitschrift:

European Journal of Operational Research

Jahrgang (Veröffentlichung):

247 (2015)

Heftnummer:

3

Seiten:

745-754

Sprache:

Englisch

Schlagworte:

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

Digital Object Identifier (DOI):

doi:10.1016/j.ejor.2015.06.041

Volltext:

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

Zitation:

Download BibTeX

Kurzfassung

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.