Mwlp Storm Repair Eval

mwlp-storm-repair-eval

Post-Disaster Repair Crew Assignment Optimization Using Minimum Latency — Dey et al. (2022) (arXiv:2206.00597, 2022)

What this evaluates

Evaluates an algorithm's ability to optimally partition repair targets among multiple crews and route them to minimize total weighted latency (average wait time) while balancing workload distribution across crews in post-disaster urban scenarios.

Datasets

• Random Environments — total 100; splits: test (100); repo https://github.com/leadcatlab/MWLP-Storm-Repair
• Champaign Case Study — total 25; splits: test (25); repo https://github.com/leadcatlab/MWLP-Storm-Repair

Metrics

• wait (primary) — range: hours
  • wait(π) = wlp_sum(π) / Σ_{i=1}^n w(v_i), where wlp_sum is the total weighted latency (sum of waiting times for every location weighted by population/importance) and w(v_i) is the node weight. Represents the average time a customer waits for service restoration.
• range — range: hours
  • range(π) = max_{φ_i ∈ π}(wlp(φ_i)) - min_{φ_i ∈ π}(wlp(φ_i)), measuring the difference between the highest and lowest crew weighted latencies to assess workload balance.

Input / output format

Input: A graph with node weights representing location importance/population, edge weights representing travel times, a fixed number of crews (m=20), a shared starting location, and a set of target locations (n=201) requiring repair.

Output: A partition of the n target locations into m disjoint sets (one per crew), along with an ordered sequence of locations (routing path) for each crew to visit their assigned targets.

Scoring recipe

def compute_metrics(assignment, graph):
    crew_latencies = []
    total_wlp = 0
    total_weight = 0
    for crew_id, targets in assignment.items():
        crew_wlp = 0
        current_time = 0
        current_loc = graph.start_node
        for target in targets:
            current_time += graph.travel_time(current_loc, target) + graph.repair_time(target)
            crew_wlp += graph.node_weight(target) * current_time
            current_loc = target
        crew_latencies.append(crew_wlp)
        total_wlp += crew_wlp
        total_weight += sum(graph.node_weight(t) for t in targets)
    avg_wait = total_wlp / total_weight
    workload_range = max(crew_latencies) - min(crew_latencies)
    return avg_wait, workload_range

Common pitfalls

• The Champaign case study sets all repair times to zero to isolate travel time effects, which drastically changes the scale and interpretation of the weighted latency metric compared to the random environments.
• The algorithms are heuristic-based with no formal optimality bounds, so performance comparisons are strictly relative to the provided benchmarks rather than absolute optimality.
• Edge weights in the synthetic environments combine travel and repair times, whereas the real-world case study uses only travel times, making direct metric value comparisons across environments invalid.

Evidence (verbatim from paper)

The primary goal of the proposed algorithm is to minimize the total weighted latency incurred by an agent assignment, defined as in ([4]). Recall that ([4]) is a weighted sum of waiting times for every location. Given that in this case the weights indicate population counts, ([4]) induces a natural notion of an average wait time. We define such a time for an assignment π={φ1,…,φm} by wait(π)=wlp_sum(π)/∑_{i=1}^n w(v_i). The value of wait(π) represents the average time a customer waits for their service to be restored, given assignment π.

Citation

@misc{dey2022postdisaster,
  title={Post-Disaster Repair Crew Assignment Optimization Using Minimum Latency},
  author={Dey et al. (2022)},
  year={2022},
  note={arXiv:2206.00597}
}

• arXiv: 2206.00597