Freight trains9 run a regular weekly schedule in both the forward and reverse directions of a railroad’s main line through section boundary points i = 1,

c, 22. Dividing the week into hourly time blocks t = 1,

c, 168 (with t = 1 following t = 168), a train leaving i bound for j 7 i advances through both time and space as it transits sections 1i, i + 12, 1i + 1, i + 22, and so on. Summing requirements for all scheduled trains to pull the anticipated load over grades in the section, engine needs fi, t can be estimated for each forward section 1i, i + 12, and each time t to t + pi, where pi is the number of hours required to transit the section. Reverse requirements ri,t provide the same information for trains moving i at t to i - 1 at t + qi with qi the time to transit segment 1i, i - 12. We assume that all engine units are identical. Those located at any place and time where they are not immediately needed, may be held there, turned around to go the opposite way, or added as extras on a passing train. Cost ci, di, and h reflect the cost of running one unit over segment 1i, i + 12, running one over 1i, i - 12, and holding for an hour at any site, respectively.

Show that the problem of computing a minimum total cost engine schedule can be modeled as a network flow problem over a suitable timeexpanded network, by sketching a representative node and showing all adjacent nodes, arcs, costs, bounds, and node net demands. Some arcs will have nonzero lower bounds.