The transportation problem with conflicts

Annette Ficker, Frits Spieksma and Gerhard Woeginger

No 594801, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

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 receive supply from at most one demand node of each conflicting pair. Likewise, each demand node may only send supply to 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: Transportation problem; Conflict graph; Computational complexity; Approximation (search for similar items in EconPapers)
Date: 2017-10
New Economics Papers: this item is included in nep-tre
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1719

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/470764 The transportation problem with conflicts (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:594801

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().