Art der Publikation: Beitrag in Sammelwerk

An Integrated Matching and Partitioning Problem with Applications in Intermodal Transport

Autor(en):

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

Titel des Sammelbands:

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

Seiten:

1758-1765

Ort(e):

Cape Town, South Africa

Veröffentlichung:

2016

Sprache:

Englisch

Schlagworte:

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

Digital Object Identifier (DOI):

doi:10.1109/SSCI.2015.245

Zitation:

Download BibTeX

Kurzfassung

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.