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)
16 Downloads (Pure)

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
Pages (from-to)207-227
Number of pages21
JournalAnnals of Operations Research
Volume298
Issue number1-2
Early online date2020
DOIs
Publication statusPublished - Mar 2021

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