Type of Publication: Article in Collected Edition

An Integrated Matching and Partitioning Problem with Applications in Intermodal Transport

Author(s):

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

Title of Anthology:

Proceedings of the 2015 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2015)

pages:

1758-1765

Location(s):

Cape Town, South Africa

Publication Date:

2016

Language:

Englisch

Keywords:

Containers, Cranes, Bipartite graph, Schedules, Mathematical model, Layout,​​​​​​​ Approximation methods

Digital Object Identifier (DOI):

doi:10.1109/SSCI.2015.245

Citation:

Download BibTeX

Abstract

We introduce a combination of the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the Min-Max Weighted Matching Problem. The resulting problem has applications in intermodal transport. We propose a mathematical model and prove the problem to be NP-hard in the strong sense. Two heuristic frameworks that decompose the problem into its partitioning and matching components are presented. Additionally, we analyze a basic implementation of tabu search and a genetic algorithm for the integrated problem. All algorithms outperform standard optimization software. Moreover, the decomposition heuristics outperform the classical metaheuristic approaches for the integrated problem. All algorithms outperform standard,,optimization software. Moreover, the decomposition heuristics outperform the classical metaheuristic approaches.