An Integrated Matching and Partitioning Problem with Applications in Intermodal Transport

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.