An all Zero-One Algorithm for a Certain Class of Transportation Problems

Abstract

This paper considers a special class of transportation problems. There is a set of sources producing the same material with a fixed maximum capacity, and a set of users whose demands for the material are known. A cost is associated with the transportation of the material from each source to each user. Each user is to be supplied by one source only. The problem consists of finding the flow of the material from the sources to the users that satisfies their demands and minimizes the total transportation cost. The formulation of the problem is the same as the well-known Hitchcock problem with the further constraint that all the variables are binary. The paper proposes a search method, roughly resembling Balas's filter method, for the solution of the problem, and discusses it from a computational point of view. Finally, it describes an application of the model to a real industrial problem.