A substantial part of United Parcel Service’s10 freight traffic moves as trailer-on-flatcars

(i.e., with truck trailers traveling most of the way on railroad flatcars). The required number of truckloads di,j to be shipped between points i, j = 1,

c, n in this way is known, but UPS can use either its own trailers at unit cost ci,j or rent trailers from the railroad at unit cost ri,j. Rented trailers can be left anywhere, but UPS wishes to balance the number of its own trailers available at every point. That is, the number of company trailers inbound at any point should equal the number outbound. If necessary, trailers may be returned empty from i to j at unit cost ei,j to meet this requirement. Show that the problem of finding a minimum total cost shipping plan can be modeled as a (single-commodity) network flow problem by detailing the arcs that would join each node i to another j, including both their cost and any applicable capacity. Also indicate the net flow demand at each node. (Hint: Represent rented trailer flows indirectly from flows of loaded company-owned trailers with capacity di,j.)