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.

  • CreatedSeptember 22, 2015
  • Files Included
Post your question