Paper Info
Title
Solving Two-Commodity Transportation Problems with Coupling Constraints
Abstract
The two-commodity transportation problem with coupling constraints occurs in the formulation of a variety of plant-location models, including those for locating power plants and distributing electrical power The constraint matrix of the problem has a structure resembhng the structure of MCTP(M, N, 2) However, the structure of the coupling constraints is unique to this kind of problem. An effic,ent pr,mal algorithm that explo,ts both the underlying network formulation, as well as the structure of the couphng constraints, is developed The derivation of the algorithm ts based on three basic results" (i) defining for the problem a class of bases which can be represented as spanning trees of the underlying network, (u) establishing the existence of an opt,mal basis that is both primal and dual feasible, which belongs to this class; and 0Ii) specializing the simplex method so that only bases belonging to this class are examined dunng the execution of the algorithm It ts shown that this algorithm is similar to the algorithm for solving a pure transportation problem in one commodity from a computational complexity viewpoint Computational experiments suggest that the algorithm is two orders of magnitude faster than the MPSX on the IBM 3(60,/67. The algorithm involves only operations of addition and subtraction during the lteratlve part and can be implemented in mteger arithmetic, resultmg In a numerically stable code
Year
DOI
Venue
1980
10.1145/322217.322227
J. ACM
Keywords
DocType
Volume
Two-Commodity Transportation Problems,bipartite graph,spanning tree basis,coupling constraints,network simplex method,. multicommodtty transportation problem,Coupling Constraints,t-basts
Journal
27
Issue
ISSN
Citations 
4
0004-5411
1
PageRank 
References 
Authors
0.37
3
1
Name
Order
Citations
PageRank
K. G. Ramakrishnan158798.53