Labelled Network Flow Model for Hydro-Electric Generation: 23-Ind-A1 Operations Research, May 2016, Q3

Question 3: Labelled Network Flow Model for Hydro-Electric Generation (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Stations A→B→C along the river; A→B is 10 km, B→C is 20 km, flow speed 10 km/hr ⇒ travel time A→B = 1 hr, B→C = 2 hr. Inflow to A = 100 ML/hr (exogenous, constant). Efficiencies $e_A{=}1.5$, $e_B{=}4.2$, $e_C{=}8.5$ MW/ML; capacities $Cap_A{=}50$, $Cap_B{=}100$, $Cap_C{=}150$ MW; price $\lambda_t$ per hour (not numerically given); horizon $t=1,\dots,8$; each reservoir must return to its starting volume by hour 8.

Given data — station parameters
Station	Travel time to next station	Efficiency $e_i$ (MW/ML)	Capacity (MW)	Implied ML/hr use cap, $Cap_i/e_i$
A	1 hr (→ B)	1.5	50	33.33
B	2 hr (→ C)	4.2	100	23.81
C	— (outflow leaves system)	8.5	150	17.65

Find. A labelled multi-period network flow model (nodes, arcs, capacities, objective) whose optimal solution is the generation/release policy that maximizes 8-hour revenue — formulate and draw only, do not solve.

Fig. 3 — one representative time-expanded cell of the network (repeat for $h=1,\dots,8$ and chain $A(h{+}1)\to A(h{+}2)$, etc.); the $B{\to}C$ arc spans 2 hours because of the longer travel time.

Nodes. One node $(i,t)$ per station $i\in\{A,B,C\}$ and hour $t=1,\dots,8$, plus a source node feeding A and a sink node draining C's final release.
Arcs and their flow variables. At every node $(i,t)$ the inflow splits three ways: a use arc $u_i(t)$ (through the turbines, generating electricity, capacity $u_i(t)\le Cap_i/e_i$ from the table above), a spill arc $sp_i(t)\ge0$ (bypasses the turbines, no capacity limit beyond the physical channel), and a store arc $S_i(t)\ge0$ that carries water forward to node $(i,t{+}1)$ (the reservoir). The use and spill arcs both leave the system downstream after the travel-time lag: 1 hour from A to B, 2 hours from B to C.
Node (flow-conservation) balance. At A, inflow is the fixed 100 ML/hr source plus last hour's stored volume; at B and C, inflow is the lagged release from the upstream station: $$\underbrace{100+S_A(t{-}1)}_{\text{into }A(t)} = u_A(t)+sp_A(t)+S_A(t),$$ $$\underbrace{\big[u_A(t{-}1)+sp_A(t{-}1)\big]+S_B(t{-}1)}_{\text{into }B(t)} = u_B(t)+sp_B(t)+S_B(t),$$ $$\underbrace{\big[u_B(t{-}2)+sp_B(t{-}2)\big]+S_C(t{-}1)}_{\text{into }C(t)} = u_C(t)+sp_C(t)+S_C(t).$$
Terminal (return-to-start) constraint. Policy requires each reservoir back at its opening volume by the end of the horizon: $S_A(8)=S_A(0)$, $S_B(8)=S_B(0)$, $S_C(8)=S_C(0)$ — drawn as a closing "return" arc from each station's hour-8 node back to its hour-0/source node.
Objective. Maximize total revenue over the horizon, where MW produced at a station equals its efficiency times the ML used that hour: $$\text{Maximize } \sum_{t=1}^{8}\lambda_t\Big(e_A\,u_A(t)+e_B\,u_B(t)+e_C\,u_C(t)\Big),$$ subject to the node-balance equations of Step 3, the terminal condition of Step 4, the capacity bounds $0\le u_i(t)\le Cap_i/e_i$, and $sp_i(t),S_i(t)\ge0$ for all $i,t$.

Check: the hourly price $\lambda_t$ is left symbolic because the source text names it but supplies no numeric schedule — consistent with the question asking only that the model be "drawn," not solved. The travel delays are modelled as whole-hour lags (1 hr A→B, 2 hr B→C) since 10 km/10 kph and 20 km/10 kph both divide evenly; a finer time step would be needed if they did not.

Final results — Question 3 (model summary, not solved)
Item	Value
Node set	$(i,t)$ for 3 stations × 8 hours, plus source/sink
Arc types	use $u_i(t)$, spill $sp_i(t)$, store $S_i(t)$, plus terminal return arcs
Objective	maximize $\sum_t\lambda_t\sum_i e_i u_i(t)$
Solved numerically?	No — drawn and formulated only, per instructions

Topic: Multi-period network flow model for a cascaded reservoir system.

Key relations: Conservation of flow at every node: inflow = outflow (use + spill + store); a "return-to-start" arc closes a cyclic reservoir model just as a return-to-depot arc closes a routing network; capacity converts between electrical (MW) and hydraulic (ML) units through the plant efficiency $e_i$.

Why this works: Casting the cascade as a time-expanded network makes the travel-time lag between stations an arc property (which node it lands on) rather than an extra state variable, so the whole 8-hour, 3-station problem is a single generalized network-flow LP whose optimal basis is a spanning tree — the standard reason such problems solve efficiently despite the many periods.

Common pitfall: Balancing water at station B or C using the current-hour release from upstream instead of the correctly lagged one (1 hour late from A, 2 hours late from B) — this silently violates conservation of mass and produces an infeasible or meaningless "optimal" schedule if actually solved.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 9 (network optimization models), reservoir/hydro scheduling extension.

Question 3 of 8: Labelled Network Flow Model for Hydro-Electric Generation

Question 3: Labelled Network Flow Model for Hydro-Electric Generation (20 marks)