The partitioning approach to the solution of a class of routing problems

In this paper, the authors study a partitioning approach to the solution of a class of routing problems on networks. These problems involve transportation of commodities on networks, with sorting operations at nodes on groups of commodities. As an example of the class of routing problems involving sorting, the authors have considered the problem of rail freight transportation. Other areas where similar problems arise are mail operations, packet switching in computer networks, etc. They show that for the class of problems being studied, the authors need to obtain arc partitions which minimize the error inherent in the partitioning approach. In order to do this, they consider the Principal Lattice of Partitions of an appropriate supermodular set function defined on the left vertex set of a bipartite graph.