SQL 實現最優捷運路徑規劃：以換乘次數與站數雙重排序

問題情境

捷運路徑規劃不僅考慮最少站數，有時優先「最少換乘」。需列出所有可行方案，按 換乘次數優先、經過站數次之 排序。

範例資料

lineID  state       orderid
1       廣州東      1
1       體育中心    2
1       體育西      3
1       烈士陵園    4
1       公園前      6
1       西門口      7
2       火車站      1
2       紀念堂      2
2       公園前      3
2       中大        4
2       客村        5
2       琶洲        6
2       萬勝圍      7
3       廣州東      1
3       體育西      2
3       珠江新城    3
3       客村        4
3       市橋        5
4       萬勝圍      1
4       金洲        2

查詢：「廣州東」→「中大」所有最優方案。

T-SQL 遞迴 CTE 解法 (簡化版邏輯)

-- 建立站點資料
DECLARE @tb TABLE (lineID INT, state NVARCHAR(10), orderid INT);
INSERT @tb VALUES
(1,N'廣州東',1),(1,N'體育中心',2),(1,N'體育西',3),(1,N'烈士陵園',4),(1,N'公園前',6),(1,N'西門口',7),
(2,N'火車站',1),(2,N'紀念堂',2),(2,N'公園前',3),(2,N'中大',4),(2,N'客村',5),(2,N'琶洲',6),(2,N'萬勝圍',7),
(3,N'廣州東',1),(3,N'體育西',2),(3,N'珠江新城',3),(3,N'客村',4),(3,N'市橋',5),
(4,N'萬勝圍',1),(4,N'金洲',2);

DECLARE @start NVARCHAR(10) = N'廣州東', @target NVARCHAR(10) = N'中大';

-- 遞迴 CTE 搜尋所有路徑
WITH Paths AS (
    -- 起點
    SELECT
        CAST(lineID AS NVARCHAR(MAX)) + N'{' + CAST(orderid AS NVARCHAR(10)) + N'.' + state AS path,
        0 AS transfers,
        0 AS stations,
        lineID, state, orderid,
        CAST(',' + CAST(lineID AS NVARCHAR(10)) + ',' AS NVARCHAR(MAX)) AS usedLines
    FROM @tb WHERE state = @start

    UNION ALL

    -- 同線路前進 (orderid +1)
    SELECT
        p.path + N'->' + CAST(t.orderid AS NVARCHAR(10)) + N'.' + t.state,
        p.transfers,
        p.stations + 1,
        t.lineID, t.state, t.orderid,
        p.usedLines
    FROM Paths p
    JOIN @tb t ON t.lineID = p.lineID AND t.orderid = p.orderid + 1
    WHERE p.state <> @target

    UNION ALL

    -- 換乘：同站名、不同線路、未用過該線路
    SELECT
        p.path + N')->' + CAST(t.lineID AS NVARCHAR(10)) + N'{' + CAST(t.orderid AS NVARCHAR(10)) + N'.' + t.state,
        p.transfers + 1,
        p.stations + 1,
        t.lineID, t.state, t.orderid,
        p.usedLines + CAST(t.lineID AS NVARCHAR(10)) + N','
    FROM Paths p
    JOIN @tb t ON t.state = p.state AND t.lineID <> p.lineID
    WHERE p.state <> @target
      AND CHARINDEX(',' + CAST(t.lineID AS NVARCHAR(10)) + ',', p.usedLines) = 0
)
SELECT path + N'}', transfers, stations
FROM Paths
WHERE state = @target
ORDER BY transfers, stations;

執行結果 (前兩筆最優)

3{1.廣州東-> 2.體育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大}   換乘:1  站數:5
1{1.廣州東-> 2.體育中心-> 3.體育西)-> 3{2.體育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大}   換乘:2  站數:7

關鍵設計點

• 用 usedLines 字串記錄已使用路線，避免重複換乘同線路造成迴圈。
• 同線路移動不增加換乘計數；跨線路同站換乘 transfers + 1。
• 最終 ORDER BY transfers, stations 滿足雙重排序需求。
• 實際生產環境建議加入最大遞迴深度限制 (OPTION (MAXRECURSION 100)) 並建立站點轉乘關聯表優化效能。