# Question: One track of the Eura Railroad system runs from the

One track of the Eura Railroad system runs from the major industrial city of Faireparc to the major port city of Portstown. This track is heavily used by both express passenger and freight trains. The passenger trains are carefully scheduled and have priority over the slow freight trains (this is a European railroad), so that the freight trains must pull over onto a siding whenever a passenger train is scheduled to pass them soon. It is now necessary to increase the freight service, so the problem is to schedule the freight trains so as to maximize the number that can be sent each day without interfering with the fixed schedule for passenger trains.

Consecutive freight trains must maintain a schedule differential of at least 0.1 hour, and this is the time unit used for scheduling them (so that the daily schedule indicates the status of each freight train at times 0.0, 0.1, 0.2, . . . , 23.9). There are S sidings between Faireparc and Portstown, where siding i is long enough to hold ni freight trains (i = 1, . . . ,S). It requires ti time units (rounded up to an integer) for a freight train to travel from siding i to siding i + 1 (where t0 is the time from the Faireparc station to siding 1 and ts is the time from siding S to the Portstown station). A freight train is allowed to pass or leave siding i (i = 0, 1, . . . ,S) at time j (j = 0.0, 0.1, . . . , 23.9) only if it would not be overtaken by a scheduled passenger train before reaching siding i = 1 (let δij = 1 if it would not be overtaken, and let δij = 0 if it would be). A freight train also is required to stop at a siding if there will not be room for it at all subsequent sidings that it would reach before being overtaken by a passenger train.

Formulate this problem as a maximum flow problem by identifying each node (including the supply node and the demand node) as well as each arc and its arc capacity for the network representation of the problem.

Consecutive freight trains must maintain a schedule differential of at least 0.1 hour, and this is the time unit used for scheduling them (so that the daily schedule indicates the status of each freight train at times 0.0, 0.1, 0.2, . . . , 23.9). There are S sidings between Faireparc and Portstown, where siding i is long enough to hold ni freight trains (i = 1, . . . ,S). It requires ti time units (rounded up to an integer) for a freight train to travel from siding i to siding i + 1 (where t0 is the time from the Faireparc station to siding 1 and ts is the time from siding S to the Portstown station). A freight train is allowed to pass or leave siding i (i = 0, 1, . . . ,S) at time j (j = 0.0, 0.1, . . . , 23.9) only if it would not be overtaken by a scheduled passenger train before reaching siding i = 1 (let δij = 1 if it would not be overtaken, and let δij = 0 if it would be). A freight train also is required to stop at a siding if there will not be room for it at all subsequent sidings that it would reach before being overtaken by a passenger train.

Formulate this problem as a maximum flow problem by identifying each node (including the supply node and the demand node) as well as each arc and its arc capacity for the network representation of the problem.

**View Solution:**## Answer to relevant Questions

Consider the maximum flow problem shown below, where the source is node A, the sink is node F, and the arc capacities are the numbers shown next to these directed arcs. (a) Use the augmenting path algorithm described in Sec. ...Reconsider Prob. 10.3-3. Now formulate this problem as a minimum cost flow problem by showing the appropriate network representation. For the P & T Co. transportation problem given in Table 9.2, consider its network representation as a minimum cost flow problem presented in Fig. 9.2. Use the northwest corner rule to obtain an initial BF solution from Table ...The Lockhead Aircraft Co. is ready to begin a project to develop a new fighter airplane for the U.S. Air Force. The company’s contract with the Department of Defense calls for project completion within 92 weeks, with ...Reconsider the networks shown in Prob. 10.3-4. Use the algorithm described in Sec. 10.4 to find the minimum spanning tree for each of these networks. In problem (a) (b)Post your question