The Red-Blue transportation problem

W. Vancroonenburg, F. Della Croce, D.R. Goossens, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)

Abstract

This paper considers the Red–Blue Transportation Problem (Red–Blue TP), a generalization of the transportation problem where supply nodes are partitioned into two sets and so-called exclusionary constraints are imposed. We encountered a special case of this problem in a hospital context, where patients need to be assigned to rooms. We establish the problem’s complexity, and we compare two integer programming formulations. Furthermore, a maximization variant of Red–Blue TP is presented, for which we propose a constant-factor approximation algorithm. We conclude with a computational study on the performance of the integer programming formulations and the approximation algorithms, by varying the problem size, the partitioning of the supply nodes, and the density of the problem.
Original languageEnglish
Pages (from-to)814-823
JournalEuropean Journal of Operational Research
Volume237
Issue number3
DOIs
Publication statusPublished - 16 Sept 2014
Externally publishedYes

Keywords

  • Transportation problem
  • Exclusionary constraints
  • Complexity
  • Approximation
  • Integer programming

Fingerprint

Dive into the research topics of 'The Red-Blue transportation problem'. Together they form a unique fingerprint.

Cite this