We derive a number of new results for \(k\)-regular transportation polyhedra (TPs) with a given number of faces: fairly accurate upper bounds for the minimum and lower bounds for the maximum number of vertices; achievable upper and lower bounds on the diameter and the radius. These results incorporate the solution of several important combinatorial problems and conjectures concerning the diameter of \(k\)- regular TPs. We also examine analytical complexity bounds of multicriterion transportation problems with exclusions and establish their nonsolvability in the class of algorithms based on linear scalarization of the criteria.