The transportation problem with conflicts

Annette M.C. Ficker (Corresponding author), Frits C.R. Spieksma, Gerhard J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

The transportation problem is a fundamental problem in operations research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases we derive constant factor approximation algorithms.

Original languageEnglish
JournalAnnals of Operations Research
VolumeXX
Issue numberXX
DOIs
Publication statusE-pub ahead of print - 2020

Keywords

  • Approximation
  • Computational complexity
  • Conflict graph
  • Transportation problem

Fingerprint Dive into the research topics of 'The transportation problem with conflicts'. Together they form a unique fingerprint.

Cite this