胡政漢

（華東交通大學(xué) 軟件學(xué)院，南昌 330013）

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

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

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

1 地鐵大型檢測車輛路徑優(yōu)化模型

1.1 問題描述

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

1.2 模型假設(shè)

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

1.3 變量與符號定義

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

V：城市軌道交通線網(wǎng)中的節(jié)點集合；

A：城市軌道交通線網(wǎng)中的有向弧集合；

B：車庫節(jié)點集合，B?V；

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

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

DP：給定的檢測周期；

DW：檢測車的純工作天數(shù)；

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

F：車輛每天可經(jīng)過的最多弧的數(shù)量；

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

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

r：線路編號；

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

W：檢測車夜間作業(yè)時長限制；

1.4 目標函數(shù)

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

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

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

1.5 約束條件

各線路的檢測次數(shù)要達到工務(wù)部門的要求：

2 文化基因算法

2.1 算法流程

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

圖1 算法流程Figure 1 Algorithm flow chart

2.2 染色體編碼方式

染色體的編碼是元啟發(fā)式算法的使用前提，良好的編碼方式不僅能夠減少搜索空間，而且能夠有效提高搜索效率。染色體編碼方式如下：第一層為線路序列，第二層為弧序列。線序列染色體上的一個基因代表了軌檢車對某條線路的一次檢測，用整數(shù)表示?；〉恼麛?shù)序列表示規(guī)劃周期內(nèi)軌檢車的一條檢測路徑。表1 表示既定的檢測任務(wù)，圖2 展示了一個簡化的地鐵線網(wǎng)。在城市軌道交通線網(wǎng)中，各線路之間設(shè)有聯(lián)絡(luò)線，車輛經(jīng)由聯(lián)絡(luò)線駛?cè)肓硪痪€路，若待檢線路與車輛當(dāng)前停留的線路間不存在聯(lián)絡(luò)線，則車輛無法直接駛?cè)肽繕司€路，而需要暫時經(jīng)由其他線路尋找合適的走行路徑。圖3 給出了簡化地鐵線網(wǎng)(共計5 條線路)的編碼示例，其中相鄰兩條線路之間的路徑由Floyd-Warshall 算法確定。

表1 簡化地鐵線網(wǎng)的一組線路編碼數(shù)據(jù)Table 1 Line codes for simplified urban rail transit network

圖2 簡化地鐵線網(wǎng)Figure 2 A simplified urban rail transit network

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

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

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

2.3 選擇操作與進化算子

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

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

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

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

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

Metropolis 篩選準則為

3 案例分析

3.1 案例介紹

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

圖7 北京地鐵公司線網(wǎng)示意Figure 7 Network managed by Beijing Metro company

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

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

3.2 參數(shù)設(shè)置與運算結(jié)果

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

表2 參數(shù)設(shè)置Table 2 Parameter settings

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

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

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

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

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

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

4 結(jié)論

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

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