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
DOIs
Publication statusE-pub ahead of print - 2020

Fingerprint

Transportation problem
Node
Graph
Approximation algorithms
Factors
Operations research
NP-hard

Keywords

  • Approximation
  • Computational complexity
  • Conflict graph
  • Transportation problem

Cite this

@article{ce18fcbfa38c4f69aca0822da5b04e2e,
title = "The transportation problem with conflicts",
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.",
keywords = "Approximation, Computational complexity, Conflict graph, Transportation problem",
author = "Ficker, {Annette M.C.} and Spieksma, {Frits C.R.} and Woeginger, {Gerhard J.}",
year = "2020",
doi = "10.1007/s10479-018-3004-y",
language = "English",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",

}

The transportation problem with conflicts. / Ficker, Annette M.C. (Corresponding author); Spieksma, Frits C.R.; Woeginger, Gerhard J.

In: Annals of Operations Research, 2020.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The transportation problem with conflicts

AU - Ficker, Annette M.C.

AU - Spieksma, Frits C.R.

AU - Woeginger, Gerhard J.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Approximation

KW - Computational complexity

KW - Conflict graph

KW - Transportation problem

UR - http://www.scopus.com/inward/record.url?scp=85052499483&partnerID=8YFLogxK

U2 - 10.1007/s10479-018-3004-y

DO - 10.1007/s10479-018-3004-y

M3 - Article

AN - SCOPUS:85052499483

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

ER -