校巴路線規劃 — Kenneth Cheng

校巴路線是一個真實而常見的最佳化問題。學生可能住得離學校很遠，車隊數量、司機工時、容量、到校時間及學生在車時間都有限。任務不只是縮短總距離，而是在成本與不同學生的服務質素之間取得平衡。

問題背景

考慮一個主要服務鄉郊學生的學區。巴士可以先接載小學生到小學，再繼續接載中學生；另一方案是每所學校使用獨立巴士，即使部分道路重複。題目要求：

在預算、司機、車輛與時間限制下設計路線；
任何學生乘車不超過一小時；
平衡不同學校群體的乘車時間；
說明模型假設、測試方法與結果。

這是 Vehicle Routing Problem（VRP）的變體。若還有到校時窗、每名學生 ride-time 限制與多學校，它接近 multi-depot／school-bus routing with time windows。

模型元素

目標

可使用多目標成本：

\min\; c_f B +c_d\sum_r D_r +c_t\sum_s n_sT_s +c_{\max}\max_sT_s,

其中 $B$ 是巴士數， $D_r$ 是路線距離， $n_s$ 是站點學生數， $T_s$ 是該站學生乘車時間。最後一項防止只改善平均值，卻讓一小群學生承受極長行程。

決策

哪些站分配到哪一輛巴士；
每條路線的站點次序；
每條路線服務哪一所學校；
出發與到校時間。

約束

每個站只被服務一次；
同一路線所有學生到達正確學校；
載客量不超過巴士容量；
到校時間位於指定窗口；
每名學生由上車至到校不超過上限；
司機工時、巴士可用性及道路限制成立。

Clarke–Wright Savings

對一所學校 $S$ ，初始時每個站各有一條往返路線 $S\to i\to S$ 。若合併成 $S\to i\to j\to S$ ，距離節省為

s_{ij}=d(S,i)+d(S,j)-d(i,j).

演算法：

每個站建立一條獨立路線；
為同一學校站點計算 $s_{ij}$ ；
由大至小排序；
只有當 $i,j$ 位於兩條不同路線的端點，而且合併後所有約束成立，才合併；
直至再沒有可行正 savings。

這個「端點」條件很重要。若只檢查 i in route，演算法可以在路線中間接合，產生實際次序與 savings 計算不一致的路線。

合成資料

原示例使用 150 個站、4 所學校、每車 40 人，並固定種子：

import random
import math

random.seed(23)

num_stops = 150
num_schools = 4
bus_capacity = 40

stops = list(range(num_stops))
schools = list(
    range(num_stops, num_stops + num_schools)
)
all_nodes = stops + schools

coordinates = {
    node: (
        random.uniform(0, 800),
        random.uniform(0, 800)
    )
    for node in all_nodes
}
students_at_stop = {
    stop: random.randint(1, 10)
    for stop in stops
}
school_assignments = {
    stop: random.choice(schools)
    for stop in stops
}

原文使用 Manhattan distance，作為網格城市的粗略代理：

def distance(a, b):
    x1, y1 = coordinates[a]
    x2, y2 = coordinates[b]
    return abs(x1 - x2) + abs(y1 - y2)

直線 Manhattan distance 並不等於真實道路最短時間；橋樑、單程路、交通燈與擠塞均被省略。部署前應使用道路網絡的 travel-time matrix。

可檢查的 savings 實作

每條路線只保存站點；學校作共同 depot。以下版本要求同校、端點接合及容量可行：

from collections import defaultdict

def route_load(route):
    return sum(students_at_stop[s] for s in route)

def route_distance(route, school):
    if not route:
        return 0.0
    nodes = [school] + route + [school]
    return sum(
        distance(nodes[k], nodes[k + 1])
        for k in range(len(nodes) - 1)
    )

def orient_for_merge(route_i, i, route_j, j):
    # Return route_i ending in i and route_j starting in j.
    if route_i[-1] != i:
        route_i = list(reversed(route_i))
    if route_j[0] != j:
        route_j = list(reversed(route_j))
    if route_i[-1] != i or route_j[0] != j:
        return None
    return route_i + route_j

def savings_algorithm():
    by_school = defaultdict(list)
    for stop in stops:
        by_school[school_assignments[stop]].append(stop)

    final_routes = []
    for school, school_stops in by_school.items():
        routes = [[s] for s in school_stops]
        savings = []
        for index, i in enumerate(school_stops):
            for j in school_stops[index + 1:]:
                value = (
                    distance(school, i)
                    + distance(school, j)
                    - distance(i, j)
                )
                savings.append((value, i, j))
        savings.sort(reverse=True)

        for value, i, j in savings:
            if value <= 0:
                continue
            route_i = next(
                (r for r in routes if i in r), None
            )
            route_j = next(
                (r for r in routes if j in r), None
            )
            if route_i is None or route_j is None:
                continue
            if route_i is route_j:
                continue
            if i not in (route_i[0], route_i[-1]):
                continue
            if j not in (route_j[0], route_j[-1]):
                continue

            merged = orient_for_merge(
                route_i, i, route_j, j
            )
            if merged is None:
                merged = orient_for_merge(
                    route_j, j, route_i, i
                )
            if merged is None:
                continue
            if route_load(merged) > bus_capacity:
                continue

            routes.remove(route_i)
            routes.remove(route_j)
            routes.append(merged)

        final_routes.extend(
            (school, route) for route in routes
        )

    return final_routes

要真正實施一小時限制，還需用道路行車時間逐站計算：最早上車學生的 remaining route time、停站服務時間及到校時窗。這部分不能以 len(merged_route) <= bus_capacity 代替。

成本與輸出

routes = savings_algorithm()

total_distance = sum(
    route_distance(route, school)
    for school, route in routes
)
fixed_bus_cost = 100
total_cost = (
    len(routes) * fixed_bus_cost + total_distance
)

print(f"Number of routes: {len(routes)}")
print(f"Total distance: {total_distance:.2f}")
print(f"Total cost: {total_cost:.2f}")

原始程式報告：

Number of routes: 22
Total distance: 39013.64
Total cost: 41213.64

並列出 22 條路線，載客量由 4 至 40 人。這些數值來自舊實作：距離只累計站點至學校，沒有計算學校至首站的一段，合併亦不限制端點。因此，數字只屬原程式輸出，不能作為已驗證最佳化結果。修正版需重新運行後另行報告。

視覺化可以檢查路線是否交叉或跨度不合理，卻不能單靠圖證明最優、準時或公平。

原結論為何過強

原文聲稱路線「最小化總成本並確保所有學生準時接送」，但程式沒有：

最優性下界或與精確解比較；
時間窗；
站點服務時間；
每名學生乘車時間；
道路速度或擠塞；
巴士由 depot 前往首站的成本；
多輪次及小學／中學串接；
對隨機座標以外資料的測試。

Savings 是一個構造式啟發法，能快速得到可行起點，不提供普遍最優保證。更誠實的主張是：在合成資料上，它把單站路線合併成容量可行的候選路線；成本與服務質素仍須與其他方法及下界比較。

實施前的驗證

一個學區應至少進行：

在小實例以 MILP／constraint programming 求最優解，量度 heuristic gap；
與現有人工路線、nearest-neighbour、local search 及 OR-Tools 基準比較；
使用真實道路 travel times，於上課時段作情境測試；
模擬學生缺席、道路封閉、巴士故障及交通延誤；
報告平均及 95th-percentile ride time、最差學生、準時率、巴士數與成本；
由司機、學校及家長檢查安全站點與公平性；
先小規模 shadow run，再逐步部署。

結語

校巴路線是 VRP 的實際變體。Clarke–Wright savings 提供快速、透明的初始解，但真正問題由容量、時間窗、個人乘車上限、道路網絡及公平目標共同定義。

一張看起來整齊的路線圖，不代表學生已準時或不超過一小時。可靠模型必須把這些要求寫入約束，再以真實行車時間及獨立日子測試。