城市軌道交通線網檢測車路徑優化

胡政漢

（華東交通大學 軟件學院，南昌 330013）

通過運行大型檢測車輛，如軌道檢查車、鋼軌探傷車等，采集軌面數據進行病害分析是目前實現軌道檢測的主要手段[1-2]。然而，目前手工制定的軌檢車作業路徑主要依靠專家的經驗和知識。人工編排的大型檢測車輛路徑方案無論是里程還是時間均衡性都存在優化空間。如何兼顧一個編排周期內大型檢測車輛的總行駛里程和線網上各條線路的時間均衡性自動編制出更優的大型檢測車輛路徑是目前的研究難點。

地鐵軌道檢測車輛路徑優化問題(urban track inspection vehicle routing problem，UTIVRP)本質上屬于弧路徑優化問題(arc routing problem，ARP)的分支，與目前被廣泛關注的能力受限的弧路徑問題(capacitated arc routing problem，CARP)[3]較為類似。經典的CARP是定義在無向圖上的路徑優化問題，每個弧都有非負的花費和需求，車輛要對有非負需求的弧進行服務，且每輛車提供的服務總量不得超過車輛的能力(能力約束)。目標是尋找最低成本且起始于某一特定車庫的路徑。CARP 理論已被應用于多個領域，如城市垃圾回收[4-5]、灑水車路徑規劃[6]、郵件包裹運送[7]和冬季道路除雪[8]等。小規模的CARP 可以通過精確求解的算法(比如分支定界法)求得最優解[8]。啟發式算法雖不能確保求解結果一定是全局最優，但可以在較短的時間內得到一個滿意的近似解[9-10]，如遺傳算法[11]、蟻群算法[12]等。目前關于CARP 的研究大部分是單目標優化，但是實際問題中除了最小化總路由成本以外，還有很多其他因素需要考慮，如最小化最長行程長度、最小化運用車輛數等。文獻[13]最早提出了多目標CARP 模型。文獻[14]針對同時降低總行駛成本和最長行程的CARP 問題，利用構造性啟發式算法改造非支配排序的遺傳算法進行求解。文獻[15]研究了周期性能力受限的路徑問題(periodic capacitated arc routing problem，PCARP)，將CARP 的服務時間擴展到一段時期內(稱為規劃周期)，用來解決服務任務具有多周期特點的弧路徑問題。但是，根據實際路網和生產需要，UTIVRP 需要另外滿足檢測完整性和作業時長約束。因此，UTIVRP 可視作CARP 的變體，也是NP-hard問題。

目前，CARP 方面的相關探索更多集中在道路網方面[16]，鮮有與城市軌道交通線網的相關研究。本文針對城市軌道交通線網的特點，提出雙層染色體編碼方式，設計文化基因算法進行求解，探索城市軌道交通檢測車路徑方案，并通過算例對比北京地鐵線網檢測車路徑的在用方案，對本文所建模型與設計算法進行驗證。

1 地鐵大型檢測車輛路徑優化模型

1.1 問題描述

地鐵軌道檢測車作業過程如下：編排周期伊始，大型檢測車輛從城市軌道交通線網的固定車庫出發開始作業。由于地鐵線網白天承擔客運任務，因此檢測車只能在夜間規定的時間內執行檢測作業(如02:00 am-04:00 am)。在規定時間結束前，檢測車需要停放在車輛段中。不同線路有不同檢測次數的要求，檢測車輛在完成線網上各條線路規定次數的檢測后需返回到固定車庫。軌道檢測數據分析和管理一般以整條線為單位，這要求大型檢測車輛應盡可能在一天之內完成一個線別的檢測，保證一個線別上檢測數據的完整性。與道路網情況不同，大型檢測車輛在作業過程中若要從某條線路轉到另一條線路必須借助聯絡線。一個編排周期內大型檢測車輛的行駛成本包括消耗的柴油、檢測人員的人工成本和大型檢測車輛的損耗等，即與編排周期內的總行駛里程成正比。因此本文以行駛里程來量化大型檢測車輛的行駛成本，總行駛里程主要包括檢測里程和調車里程，其中檢測線路的里程是大型檢測車輛所必須走行的，不存在優化空間。由此可見，大型檢測車輛的總行駛里程取決于調車里程。同一線路相鄰兩次檢測之間的時間間隔應盡可能保持一致，也就是大型檢測車輛路徑優化需要兼顧總調車里程和時間均衡性。

1.2 模型假設

本文將基于兩個基本假設對UTIVRP 進行研究：大型檢測車輛以恒定的速度運行；大型檢測車輛作業過程中在聯絡線上的時間忽略不計。

1.3 變量與符號定義

模型中涉及的符號定義如下。

V：城市軌道交通線網中的節點集合；

A：城市軌道交通線網中的有向弧集合；

B：車庫節點集合，B?V；

Cs i,j：弧(i，j)在被第s次檢測時所在的天數；

D：完工天數，即軌檢車的實際走行天數；

DP：給定的檢測周期；

DW：檢測車的純工作天數；

depot：軌檢車整條路徑的起終點；

F：車輛每天可經過的最多弧的數量；

Ki,j：弧(i，j)的規定檢測次數；

li,j：弧(i，j)的長度；

r：線路編號；

ti,j：軌檢車在弧(i，j)上的走行時間；

W：檢測車夜間作業時長限制；

1.4 目標函數

由于軌檢車的任務Ki,j是確定的，所以軌檢車的檢測里程是定值。軌檢車的最短走行里程Z1由空走調車里程所決定。

檢測間隔平均偏差Z2，表示需要多次檢測的線路實際檢測間隔與理想檢測間隔差值的平均值。偏差越小說明時間均衡性越好，反之越差。

檢測間隔最大偏差Z3，表示需要多次檢測的線路實際檢測間隔與理想檢測間隔差值的最大值。偏差越小說明時間均衡性越好，反之越差。

1.5 約束條件

各線路的檢測次數要達到工務部門的要求：

2 文化基因算法

2.1 算法流程

文化基因算法(memetic algorithm，MA)是元啟發式算法的一種，該算法在遺傳算法(genetic algorithm，GA)的框架下融合了局部搜索和全局搜索，在車輛路徑優化問題中有著廣泛的應用。該算法的具體操作過程如圖1 所示。首先，隨機初始化種群。結合輪盤賭與精英個體選擇法確定父代個體，通過交叉變異獲得子代。然后，判斷生成的解是否可行，若可行，則計算其適應度函數，并利用Metropolis 準則篩選子代；否則，重復選擇、交叉和變異過程。當迭代滿足終止條件時，終止計算，輸出最佳解。

圖1 算法流程Figure 1 Algorithm flow chart

2.2 染色體編碼方式

染色體的編碼是元啟發式算法的使用前提，良好的編碼方式不僅能夠減少搜索空間，而且能夠有效提高搜索效率。染色體編碼方式如下：第一層為線路序列，第二層為弧序列。線序列染色體上的一個基因代表了軌檢車對某條線路的一次檢測，用整數表示?；〉恼麛敌蛄斜硎疽巹澲芷趦溶墮z車的一條檢測路徑。表1 表示既定的檢測任務，圖2 展示了一個簡化的地鐵線網。在城市軌道交通線網中，各線路之間設有聯絡線，車輛經由聯絡線駛入另一線路，若待檢線路與車輛當前停留的線路間不存在聯絡線，則車輛無法直接駛入目標線路，而需要暫時經由其他線路尋找合適的走行路徑。圖3 給出了簡化地鐵線網(共計5 條線路)的編碼示例，其中相鄰兩條線路之間的路徑由Floyd-Warshall 算法確定。

表1 簡化地鐵線網的一組線路編碼數據Table 1 Line codes for simplified urban rail transit network

圖2 簡化地鐵線網Figure 2 A simplified urban rail transit network

圖3 雙層染色體編碼示意Figure 3 Double-layer chromosome coding method

根據最遠里程約束和車庫約束將染色體解碼為每一天的軌檢車行駛路徑，同時可以得到軌檢車按照該檢測路徑完成規劃周期內所有檢測任務的總天數DW，如圖4 所示。

圖4 染色體解碼示意Figure 4 Chromosome decoding method

2.3 選擇操作與進化算子

綜合考慮輪盤賭和精英個體選擇兩種方式的優缺點，本文將這2 種選擇方式進行結合：將父代優良個體按照一定比例直接放入子代，同時從父代的所有個體中以輪盤賭的方式選擇剩余名額的個體進入子代。

MA 所采用的交叉算子如下：隨機選取P1 染色體中的基因段復制到C1 的相同位置處，再將P2 染色體中與之相同的基因段刪除，之后將剩余的基因按照從左到右的順序復制到C1 中，C2 的染色體操作方式相同，具體過程見圖5。

圖5 交叉算子示意Figure 5 Example of crossover operator

本文所采用的線染色體變異算子包括挪位和換位，如圖6 所示。挪位是選取線序列中任意連續的q個基因(q取小于線序列長度的隨機整數)插入某位基因之前(后)；換位是選取線序列中任意p對基因(p是不大于線序列長度的隨機整數)交換位置。

圖6 線染色體變異Figure 6 Line-chromosome mutation

Metropolis 篩選準則為

3 案例分析

3.1 案例介紹

以北京市地鐵線網為例對軌檢車的運行路徑展開研究，其地鐵線網如圖7 所示。實驗環境配置為2.60GHz CPU、8.00 GB 內存。

圖7 北京地鐵公司線網示意Figure 7 Network managed by Beijing Metro company

圖8 參數 Z 1min 和 Z 1max 的迭代過程示意Figure 8 Parameters Z 1min and Z 1max iterative process

圖9 參數 Z 2min 和 Z 3min 的迭代過程示意Figure 9 Parameters Z 2min and Z 3min iterative process

3.2 參數設置與運算結果

綜上，文化基因算法在處理單目標問題時，收斂值及解的質量均能令人滿意。為進一步評價文化基因算法的有效性，在計算Z時，對文化基因算法中的各輸入參數選取不同的值，參數設置及計算結果見表2，迭代過程見圖10。

表2 參數設置Table 2 Parameter settings

圖10 求解Z 的迭代過程示意Figure 10 Schematic diagram of the Z iterative process

計算結果的標準差s=0.0048，變異系數cv=3.299%，分布較為集中。本節從相同參數多次運算和多種參數獨立運算的兩種角度對算法進行評估，結果表明，針對UTIVRP 所設計的MA 算法有較高的精度。

表3 列舉出曲線5 對應的軌檢車路徑編制方案與目前在用方案的對比結果。

由表3 可以看出，人工安排的軌檢車空走調車里程為603.530 km，完成所有檢測任務共需要43 d，檢測間隔平均偏差日為10.38 d，檢測間隔最大偏差日為14.99 d。而經過本文優化所得到的空走調車里程為308.514 km，完成所有檢測任務的純工作時間為29 d，檢測間隔平均偏差日為1.00 d，檢測間隔最大偏差日為1.00 d。調車里程降低約48.88%，檢測間隔平均偏差率降低約90.37%，最大偏差率降低約93.33%。

本文所規劃的軌檢車作業路線如圖11 所示，其中車輛走行而不開啟檢測模式的路徑被標記為黃色；在兩站點之間的檢測路徑被標記為綠色。

圖11 檢測車作業路線Figure 11 Routes of the track inspection vehicle

4 結論

針對城市軌道交通線網的特點，建立了復雜約束條件下的多目標UTIVRP 模型，提出了雙層染色體結構及編碼方式，設計出MA 算法。將模型應用于北京市軌道交通線網，并將求解結果與目前北京市地鐵工務部門在用的軌檢車檢測路徑進行對比。結果表明：相比于手工方案，優化后的檢測路徑降低了48.88%的空走調車里程，減少了14 d 的作業天數；極大地提高了各線路的檢測效果，優化后的車輛調度計劃的檢測間隔平均偏差率降低約90.37%，最大偏差率降低約93.33%。

UTIVRP 仍存在進一步改進的空間。本文只考慮了單輛城市軌道檢測車的路徑優化過程。下一步將針對在城市軌道交通線網上同時優化兩輛及以上大型檢測車輛的路徑展開討論，為未來城市軌道檢測車路徑規劃的應用奠定基礎。