城市軌道交通線網(wǎng)檢測(cè)車路徑優(yōu)化

胡政漢

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

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

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

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

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

1.1 問(wèn)題描述

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

1.2 模型假設(shè)

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

1.3 變量與符號(hào)定義

模型中涉及的符號(hào)定義如下。

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

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

B：車庫(kù)節(jié)點(diǎn)集合，B?V；

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

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

DP：給定的檢測(cè)周期；

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

depot：軌檢車整條路徑的起終點(diǎn)；

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

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

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

r：線路編號(hào)；

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

W：檢測(cè)車夜間作業(yè)時(shí)長(zhǎng)限制；

1.4 目標(biāo)函數(shù)

由于軌檢車的任務(wù)Ki,j是確定的，所以軌檢車的檢測(cè)里程是定值。軌檢車的最短走行里程Z1由空走調(diào)車?yán)锍趟鶝Q定。

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

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

1.5 約束條件

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

2 文化基因算法

2.1 算法流程

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

圖1 算法流程Figure 1 Algorithm flow chart

2.2 染色體編碼方式

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

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

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

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

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

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

2.3 選擇操作與進(jìn)化算子

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

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

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

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

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

Metropolis 篩選準(zhǔn)則為

3 案例分析

3.1 案例介紹

以北京市地鐵線網(wǎng)為例對(duì)軌檢車的運(yùn)行路徑展開研究，其地鐵線網(wǎng)如圖7 所示。實(shí)驗(yàn)環(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 的迭代過(guò)程示意Figure 8 Parameters Z 1min and Z 1max iterative process

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

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

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

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

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

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

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

由表3 可以看出，人工安排的軌檢車空走調(diào)車?yán)锍虨?03.530 km，完成所有檢測(cè)任務(wù)共需要43 d，檢測(cè)間隔平均偏差日為10.38 d，檢測(cè)間隔最大偏差日為14.99 d。而經(jīng)過(guò)本文優(yōu)化所得到的空走調(diào)車?yán)锍虨?08.514 km，完成所有檢測(cè)任務(wù)的純工作時(shí)間為29 d，檢測(cè)間隔平均偏差日為1.00 d，檢測(cè)間隔最大偏差日為1.00 d。調(diào)車?yán)锍探档图s48.88%，檢測(cè)間隔平均偏差率降低約90.37%，最大偏差率降低約93.33%。

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

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

4 結(jié)論

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

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