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

VL - XX

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - XX

ER -