10.2 工業界的NP-hard問題案例#

概念說明#

NP-hard 不是學術標籤，而是每天發生在工業界的現實。以下挑選五個代表案例，說明它們各自對應哪個經典問題、業界用什麼策略應對。

1. 物流路線規劃（VRP, Vehicle Routing Problem）：快遞公司要為數百台貨車規劃路線，每台有載重限制、每個客戶有時限窗。VRP 是 TSP 加上容量與多車限制，自然是 NP-hard。業界解法：先以掃描法/凝聚法分群，再對每群跑 2-opt/OR-opt 局部搜尋；大型企業用集體智慧（螞蟻演算法、大型鄰域搜尋 LNS）與整數規劃混合。亞馬遜、UPS 的路線系統每天解的是數十萬節點的 VRP。

2. 考試/課表排程：把考試排進時段，同一學生的兩科不能同時段、教室容量夠用——本質是圖著色加資源約束。學術界每年舉辦 ITC 排程競賽，頂尖解法全是超啟發式（模擬退火、基因演算法）與局部搜尋的變體。

3. 半導體晶片設計：晶片上的暫存器分配是圖著色；電路布局繞線、測試點選擇是集合覆蓋；FPGA 映射則涉及多層 NP-hard 子問題。EDA 工具長期投入精確演算法（分支限界、SAT/ILP）與啟發式的分層混合。

4. 航空業機組員排班（Crew Scheduling）：把班次組成「勤務鏈」再分配給組員，成本最小化且符合工時法規。這是集合分割（set partitioning）問題——NP-hard，但結構特殊：業界標準做法是「列生成（column generation）+ 分支定價（branch-and-price）」，能處理數千萬候選勤務鏈，是 OR 界最成功的工業級精確求解技術之一。

5. 廣告與投資組合分配：在預算內選一組廣告位/資產使期望收益最大——0/1 背包的多維版本（多重背包）。線上廣告系統以毫秒級反應，用貪婪 + LP 鬆弛 + 對偶價格做即時決策。

跨案例的共同模式：分解（把大問題拆成 NP-hard 小塊與多項式小塊）、混合（精確方法在核心、啟發式在外圍）、妥協（用近似保證或即時可行解取代最佳解）。

演算法步驟（以 VRP 的節約演算法為例）#

每個客戶先各自一條來回路線（成本 2·d(0, i)）。
對每對客戶 (i, j) 計算節約值 s(i, j) = d(0, i) + d(0, j) − d(i, j)。
依 s 遞減排序所有配對。
依序嘗試合併 i、j 所在的兩條路線，須滿足：兩者不共享其他點、合併後載重不超限、i 為其路線末端且 j 為另一條起端。
合併直到無法再併，輸出路線集合。

Python 程式碼範例#

import math

def clarke_wright(depot, customers, demand, capacity):
    """Clarke-Wright 節約演算法（容量限制 VRP）"""
    d = lambda a, b: math.dist(a, b)
    routes = {i: [i] for i in customers}
    load = {i: demand[i] for i in customers}
    savings = sorted(
        ((d(depot, i) + d(depot, j) - d(i, j), i, j)
         for i, j in combinations(customers, 2)),
        reverse=True)

    def find(i):
        while i not in routes:
            i = next(k for k in routes if i in routes[k])
        return i

    for s, i, j in savings:
        ri, rj = find(i), find(j)
        if ri == rj or load.get(ri, 0) + load.get(rj, 0) \
           > capacity:
            continue
        if routes[ri][-1] == i and routes[rj][0] == j:
            routes[ri] = routes[ri] + routes.pop(rj)
            load[ri] = load.pop(rj)
        elif routes[rj][-1] == j and routes[ri][0] == i:
            routes[rj] = routes[rj] + routes.pop(ri)
            load[rj] = load.pop(ri)
    return list(routes.values())

from itertools import combinations
depot = (0, 0)
customers = list(range(1, 8))
pts = {i: (math.cos(i) * 10, math.sin(i) * 10)
       for i in customers}
demand = {i: 2 + (i % 3) for i in customers}
for r in clarke_wright(depot, customers, demand, 10):
    print("路線:", r, "載重:", sum(demand[i] for i in r))

複雜度分析#

Clarke-Wright：排序 O(n² log n)，合併 O(n²)，n = 5000 客戶秒級可解；品質通常在最佳解 5~10% 內。
列生成 + 分支定價：主問題是 LP，子問題生成可行勤務鏈（多項式 DP）；單輪多項式，整體最壞仍指數但工業實例極有效。
實務量級參考：精確法（ILP/B&B）約 n ≤ 數百；近似/局部搜尋 n ≤ 數十萬；貪婪線上決策 n 無上限但品質最低。

練習#

為 clarke_wright 的輸出路線加上 2-opt 改良，量測 50 個隨機實例的總里程改善幅度。
查一個你感興趣的行業（外送、電力、醫療班表），辨認其核心問題對應的經典 NP-complete 問題，寫一頁分析。
實作多維背包的簡化版（兩種資源：預算與版位），比較貪婪（收益/資源比）與 DP 的差距。