×

The transportation problem with conflicts. (English) Zbl 1462.90017

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja, RK; Magnanti, TL; Orlin, JB, Network flows: Theory, algorithms, and applications (1993), Englewood Cliffs: Prentice Hall, Englewood Cliffs · Zbl 1201.90001
[2] Bar-Noy, A.; Kortsarz, G., Minimum color sum of bipartite graphs, Journal of Algorithms, 28, 2, 339-365 (1998) · Zbl 0936.68076 · doi:10.1006/jagm.1998.0938
[3] Bender, M.; Thielen, C.; Westphal, S., Packing items into several bins facilitates approximating the separable assignment problem, Information Processing Letters, 115, 6-8, 570-575 (2015) · Zbl 1328.68296 · doi:10.1016/j.ipl.2015.02.001
[4] Cao, B., Transportation problem with nonlinear side constraints a branch and bound approach, Zeitschrift für Operations Research, 36, 2, 185-197 (1992) · Zbl 0764.90055
[5] Cao, B.; Uebe, G., Solving transportation problems with nonlinear side constraints with tabu search, Computers & Operations Research, 22, 6, 593-603 (1995) · Zbl 0827.90112 · doi:10.1016/0305-0548(94)00055-D
[6] Chen, C.; Zheng, L.; Srinivasan, V.; Thomo, A.; Wu, K.; Sukow, A., Conflict-aware weighted bipartite B-matching and its application to E-commerce, IEEE Transactions on Knowledge and Data Engineering, 28, 6, 1475-1488 (2016) · doi:10.1109/TKDE.2016.2527003
[7] Darmann, A., Pferschy, U., Schauer, J., & Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics. 8th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009), 159(16), 1726 - 1735. · Zbl 1228.05186
[8] Fleischer, L.; Goemans, MX; Mirrokni, VS; Sviridenko, M., Tight approximation algorithms for maximum separable assignment problems, Mathematics of Operations Research, 36, 3, 416-431 (2011) · Zbl 1238.68187 · doi:10.1287/moor.1110.0499
[9] Garey, MR; Johnson, DS, Computers and intractability: A guide to the theory of NP-completeness (1979), New York: W. H. Freeman & Co., New York · Zbl 0411.68039
[10] Goossens, D.; Polyakovskiy, S.; Spieksma, FCR; Woeginger, GJ, Between a rock and a hard place: The two-to-one assignment problem, Mathematical Methods of Operations Research, 76, 2, 223-237 (2012) · Zbl 1261.90023 · doi:10.1007/s00186-012-0397-2
[11] Goossens, D. R.; Spieksma, FC R., The transportation problem with exclusionary side constraints, 4OR, 7, 1, 51-60 (2009) · Zbl 1179.90233 · doi:10.1007/s10288-007-0067-z
[12] Håstad, J. (1996). Clique is hard to approximate within \(n^{1-\epsilon }\). Proceedings of 37th Conference on Foundations of Computer Science, pp. 627-636.
[13] Kalra, T., Mathew, R., Pal, S. P., & Pandey, V. (2017). Maximum weighted independent sets with a budget. In D. Gaur & N. Narayanaswamy (Eds.), CALDAM 2017, LNCS 10156, pp. 254-266, Cham, Springer. · Zbl 1485.68187
[14] Khot, S. (2001). Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, pp. 600-609.
[15] Marx, D., A short proof of the NP-completeness of minimum sum interval coloring, Operations Research Letters, 33, 4, 382-384 (2005) · Zbl 1067.05027 · doi:10.1016/j.orl.2004.07.006
[16] Pferschy, U.; Schauer, J., The maximum flow problem with disjunctive constraints, Journal of Combinatorial Optimization, 26, 1, 109-119 (2013) · Zbl 1275.90120 · doi:10.1007/s10878-011-9438-7
[17] Ratner, D.; Warmuth, M., The \((n^2-1)\)-puzzle and related relocation problems, Journal of Symbolic Computation, 10, 2, 111-137 (1990) · Zbl 0704.68057 · doi:10.1016/S0747-7171(08)80001-6
[18] Salavatipour, M. (2000). On sum coloring of graphs. Master’s Thesis, Department of Computer Science, University of Toronto. · Zbl 1018.05035
[19] Sun, M., A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints, Journal of Heuristics, 3, 4, 305-326 (1998) · Zbl 0903.90120 · doi:10.1023/A:1009630528341
[20] Sun, M., The transportation problem with exclusionary side constraints and two branch-and-bound algorithms, European Journal of Operational Research, 140, 3, 629-647 (2002) · Zbl 0998.90007 · doi:10.1016/S0377-2217(01)00239-9
[21] Syarif, A.; Gen, M., Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm, Journal of Intelligent Manufacturing, 14, 3-4, 389-399 (2003) · doi:10.1023/A:1024610128238
[22] Szkaliczki, T., Routing with minimum wire length in the dogleg-free manhattan model is NP-complete, SIAM Journal on Computing, 29, 1, 274-287 (1999) · Zbl 0937.68055 · doi:10.1137/S0097539796303123
[23] Vancroonenburg, W.; Della Croce, F.; Goossens, D.; Spieksma, FCR, The red-blue transportation problem, European Journal of Operational Research, 237, 3, 814-823 (2014) · Zbl 1338.90256 · doi:10.1016/j.ejor.2014.02.055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.