PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Service Restoration in Distribution Systems with Uncertain Repair Time and Demand

Anmar Arif, Shanshan Ma, Zhaoyu Wang, Jianhui Wang, Sarah M. Ryan, Chen Chen

arXiv:1806.11076v1math.OC

TL;DR

Extreme-weather outage restoration requires coordinating repair crews with distribution-system operation under uncertain repair times and demand. The paper develops a two-stage stochastic optimization and decomposition approach, and evaluates it on modified IEEE 34- and 8500-bus systems, where the proposed method produces near-extensive-form solutions for small cases and solves the large case within 79 minutes.

  • Problem

    Outage restoration requires integrated repair-crew routing and distribution operation because repair times and customer demand are uncertain, making the stochastic problem computationally challenging.

  • Method

    A two-stage stochastic mixed-integer program routes crews first and models distributed-generation dispatch and network reconfiguration second, using scenario sampling and decomposition with parallel Progressive Hedging.

  • Results

    The proposed method produced solutions with similar quality to the extensive form for small cases and obtained a complete IEEE 8500-bus routing solution in 79 minutes.

  • Takeaways & Limitations

    The decomposition and parallel Progressive Hedging approach supports effective solution of large-scale stochastic distribution repair and restoration problems.

Abstract

from arXiv · show

This paper proposes a novel method to co-optimize distribution system operation and repair crew routing for outage restoration after extreme weather events. A two-stage stochastic mixed integer linear program is developed. The first stage is to dispatch the repair crews to the damaged components. The second stage is distribution system restoration using distributed generators, and reconfiguration. We consider demand uncertainty in terms of a truncated normal forecast error distribution, and model the uncertainty of the repair time using a lognormal distribution. A new decomposition approach, combined with the Progressive Hedging algorithm, is developed for solving large-scale outage management problems in an effective and timely manner. The proposed method is validated on modified IEEE 34- and 8500-bus distribution test systems.

NOMENCLATURE

The nomenclature defines the sets, indices, parameters, and decision variables used to model damaged components, crews, network operation, uncertainty, and restoration.

  • Sets and Indices: The model indexes damaged components, depots, crews, buses, lines, substations, switches, time periods, and scenarios.
  • Parameters: Parameters represent load forecast errors, supplied and generated power, line status, bus voltage, load connection, repair times, line characteristics, crew travel times, load priorities, and restoration timing.
  • Parameters: The formulation includes sufficiently large constants, crew counts and depots, line and distributed-generator limits, demand quantities, electrical parameters, and load-priority weights.
  • Decision Variables: Decision variables encode crew movement, crew arrival times, component criticality, network parent-bus relationships, repair timing, and line or load states.

I. INTRODUCTION

The introduction motivates integrated outage restoration under uncertain repair times and demand, then identifies stochastic routing-restoration modeling and decomposition as the paper’s response.

  • Motivation: Extreme-weather outages make service restoration and coordinated repair-crew dispatch critical utility tasks, while operator experience may not yield optimal outage management.
  • Research Gap: The distribution repair and restoration problem is stochastic because repair times are difficult to predict and customer demand is uncertain.
  • Contributions: The proposed framework uses a two-stage stochastic mixed-integer program: crew routing first, followed by distributed-generation dispatch and network reconfiguration.
  • Contributions: The paper contributes refined routing constraints, stochastic repair-and-demand modeling, a two-stage formulation, and decomposition with parallel Progressive Hedging for large-scale problems.
  • Uncertainty Modeling: Repair-time uncertainty is modeled with a lognormal distribution, while load forecast errors use bounded truncated-normal realizations, such as ±15%.
  • Scenario Construction: The uncertainty representation combines repair times and load forecast errors into scenario matrices whose columns represent scenarios and whose rows represent random variables.

III. MATHEMATICAL FORMULATION

The mathematical formulation integrates crew routing with distribution restoration because the two stages are interdependent, optimizing crew routes alongside distributed-generation and switching decisions.

  • Two-Stage Structure: The first stage routes repair crews among depots and damaged components, while the second stage restores the distribution system using distributed generators and network reconfiguration.
  • Integrated Formulation: A single MILP integrates repair and restoration, maximizing picked-up loads while representing repair progress through repair times.
  • Operational Decisions: During restoration, the utility controls distributed generators and switches to restore power while crews repair damaged components.

A. First Stage: Repair Crew Routing

The first-stage routing model represents crew paths through damaged components, while the restoration model accounts for cold load pickup using a two-block approximation sampled over time.

  • Routing formulation: Crew routes are represented on a graph whose edges indicate whether a crew travels between damaged components in sequence.The routing formulation uses binary x variables for crew movement, with constraints enforcing route continuity and unique component assignment.
  • Routing constraints: Each crew starts and ends at defined locations, flow is conserved through intermediate components, and each damaged component is repaired by only one crew.These requirements are enforced by the route-start, route-end, flow-conservation, and assignment constraints.
  • Cold load pickup: Cold load pickup is modeled as a delayed exponentially decaying load response after restoration, with diversified and undiversified load components.The load returns to normal after a duration represented by λ time steps.
  • Cold load pickup: Two blocks represent undiversified startup consumption and diversified steady-state consumption, reducing nonlinear computational burden while conservatively maintaining supply-load balance.The CLPU curve is sampled using time step ∆t, and λ denotes the number of time steps required to return to normal.
  • Cold load pickup: When a load is restored, the undiversified component is added before the load returns to its normal diversified condition.The model uses a one-hour CLPU decay duration and sets the undiversified component equal to the diversified component at pickup.

3) Distribution Network Optimal Power Flow:

The restoration power-flow model uses linearized Distflow equations to represent active power, reactive power, and voltage while coordinating distributed generation and switching.

  • Power-flow model: Linearized Distflow equations calculate power flows and bus voltages without the nonlinear computational burden of AC optimal power flow.The formulation retains active and reactive power representation while modeling voltage levels.
  • Voltage constraints: Voltage constraints impose allowable deviations around the reference voltage, with ε set to 5%.The voltage range is represented by 1 − ε ≤ V_i,t,s ≤ 1 + ε.
  • Voltage constraints: A disjunctive formulation decouples voltage levels at disconnected buses and uses suitably bounded M values.The paper discusses selecting M to avoid excessive computation time or infeasibility.
  • Restoration operation: Dispatchable distributed generators and automatic switches supply loads and reconfigure the network during restoration.The constraints define generator capacity, line-flow limits, and switching status, including zero flow through damaged lines.
  • Load service: Once a load is served, the formulation keeps it energized in subsequent operation.This persistence is enforced by a dedicated restoration constraint.

4) Radiality Constraints:

Radiality constraints preserve a radial distribution configuration by preventing closed loops or enforcing a spanning-tree structure.

  • Loop-based formulation: The network is dynamically reconfigured with switches, and radiality constraints maintain a radial topology during restoration.The formulation identifies possible loops and constrains their associated lines.
  • Loop-based formulation: Each possible loop must contain at least one disconnected line to prevent the loop from remaining closed.The loop-based constraint uses the number of lines in each loop and guarantees that at least one line is open.
  • Spanning-tree formulation: A spanning-tree alternative limits each bus to one parent, fixes substations as roots, and relates connected lines to tree variables.For a radial network, the number of lines equals the number of non-root buses.

5) Restoration Time:

The restoration-time formulation connects crew routing with network operation by combining travel, arrival, repair, and component-availability timing across scenarios.

  • Arrival timing: Crew arrival at a damaged component combines the preceding location’s arrival time, travel time, and the selected route.Travel-time constraints are activated when a crew moves from component m to n.
  • Arrival timing: Disjunctive constraints decouple arrival times for component pairs that a crew does not traverse.This prevents unused route arcs from affecting the timing calculation.
  • Repair timing: Binary repair variables identify when each damaged component is repaired, with each component assigned a restoration time over the time horizon.A component repaired at t = 3 is represented by a binary sequence whose third entry equals one.
  • Repair timing: Repair time is added to crew arrival time, with integer-time constraints determining the repair period and excluding crews that do not repair the component.The formulation uses a zero arrival-time value for crews not assigned to the component.
  • Component availability: A repaired component becomes available at its repair time and remains available thereafter.If repair occurs at t = 4, the component is usable at t = 4 and in all later periods.
  • Numerical formulation: The big-M value must be chosen carefully because an excessively large value can slow computation, while a small value can create infeasibility.Voltage bounds are used to derive a relevant maximum difference for some constraints.

6) Big M:

The model uses Big M constraints to enforce repair-crew timing and routing relationships, with M bounded by the relevant repair and travel times.

  • Crew arrival must precede repair, so with T = 10 and repair time Tm,s = 1, the crew must arrive by αm,c,s = 9.The time horizon must be long enough for all damaged components to be repaired.
  • The minimum valid M for constraints (25) and (26) equals M27 plus the maximum repair and travel times.
  • The stochastic formulation uses first-stage crew-routing variable xm,n,c and second-stage variables collected in γs after repair times and loads are realized.

IV. SOLUTION ALGORITHM

The solution algorithm applies Progressive Hedging to decompose the two-stage stochastic program into scenario subproblems, iteratively enforcing agreement among first-stage decisions.

  • Progressive Hedging relaxes first-stage non-anticipativity, producing one subproblem per scenario that can be solved in parallel.This decomposition is intended to reduce computational burden for large-scale instances.
  • The general two-stage program separates first-stage variables δ from scenario-specific second-stage variables γs under subproblem feasibility constraints.
  • Each PH iteration aggregates scenario solutions into expected decision δ̄, updates multipliers, and adds a linear multiplier term plus a squared penalty.
  • The algorithm terminates when scenario first-stage decisions converge to a common δ̄, using ε = 0.01 in this paper.

B. Decomposed S-DSRRP

The decomposed S-DSRRP alternates between selecting critical damaged components and routing crews to them, repeating dispatch cycles until all damaged components are repaired.

  • The algorithm iteratively selects groups of damaged components and dispatches crews through two subproblems.
  • Subproblem I: Subproblem I selects C critical components through a two-stage stochastic mixed-integer program that maximizes served load while neglecting routing constraints.The selected-component count is set equal to the number of crews to keep the subsequent problem manageable.
  • Subproblem II: Subproblem II dispatches crews to the selected components in its first stage and operates the distribution network in its second stage.After the first dispatch cycle, each crew starts from its current location rather than the depot.
  • The two subproblems repeat until all damaged components are repaired, with constraint (41) setting um,t,s to zero for damaged components not being repaired.
  • The D-PH algorithm uses ⌊|N\{depot}|/C⌋ dispatch cycles, solves both subproblems with PH, updates crew locations, and removes repaired components.Remaining damages are handled after the regular cycles.

V. SIMULATION AND RESULTS

Simulation studies on modified IEEE feeders evaluate the decomposed algorithm under stochastic repair times and loads, illustrating routing, switching, distributed-generation support, and uncertainty valuation.

  • The test cases are modified IEEE 34- and 8500-bus feeders implemented in PySP with CPLEX, with a 30-minute limit imposed on each subproblem.This yields a one-hour time limit for each dispatch cycle.
  • The IEEE 34-bus case uses three backup DGs, two switches, three crews, seven damaged lines, one-hour time steps, and 1000 equally likely Monte Carlo scenarios.
  • D-PH converges in 10 minutes for the seven-damage IEEE 34-bus case, with dispatch cycles taking 5, 3, and 2 minutes.
  • The routing prioritizes Lines 5-6, 12-13, and 31-32 because they restore substation flow, serve high-priority demand, or supply the lower network portion.
  • In Scenario 1, switching and DG operation restore loads before Lines 7-8 and 9-10 are repaired, while CLPU delays restoration of three loads by one hour.
  • EVPI and VSS are calculated to quantify the value of modeling uncertainty, while EEV fixes the deterministic expected-value routing before stochastic evaluation.
  • D-PH reaches a solution close to the extensive-form solution in 10 minutes, with EENS 21.2 kWh lower and a relative gap of 0.1%.The extensive-form routes required 25 hours, while complete-problem PH required 27 minutes.

B. Case II: IEEE 8500-bus distribution feeder

The IEEE 8500-bus case evaluates scalability and scenario stability for the proposed restoration approach. The method produced a feasible routing solution in 79 minutes, while alternative methods did not converge feasibly within 24 hours.

  • Case setup: The IEEE 8500-bus feeder includes five 500 kW DGs, six crews, and 20 damaged lines for evaluating large-network scalability.Five network loops were identified in 60.72 seconds to form the radiality constraint.
  • Computational performance: 79 minutes produced the complete routing solution, with four dispatch cycles converging after 23, 25, 18, and 13 minutes.The D-PH approach used 1000 Monte Carlo scenarios reduced to 30 with SCENRED2.
  • Computational performance: After 24 hours, EEV, EF, and PH did not converge to a feasible solution for the 8500-bus case.The routing solution obtained using D-PH is reported in Table IV.
  • Restoration performance: 37% of loads were initially served using network topology changes and backup DGs, increasing to 95% after five hours of crew repairs.The reported percentages refer to one sample scenario.
  • Scenario stability: The objective-value variation was very small across scenario counts up to 100, indicating that 30 scenarios represented the uncertainties stably.The sensitivity analysis is shown in Fig. 11.
  • Overall assessment: The proposed decomposition approach balances computational burden and solution quality, matching extensive-form solution quality for small cases while solving large cases when alternatives did not.The conclusion reports similar-quality small-case solutions with significantly reduced computational burden.
Loading 1806.11076v1…