曾俊豪，鄧連波

(1.中鐵四院集團南寧勘察設計院有限公司，廣西 南寧 530003；2.中南大學 交通運輸工程學院，湖南 長沙 410075)

鐵路工程勘測外業(yè)需要根據(jù)勘測工作量配置負責送接勘測人員(包含勘測設備)的車輛數(shù)量，各車輛從外業(yè)駐地出發(fā)，完成外業(yè)勘測區(qū)域內(nèi)的多個勘測點之間的人員派送和接回任務，并最終返回駐地。隨著鐵路建設工程精細化管理要求的提出[1]，鐵路勘測設計工作時間緊，任務重，要求以較短的勘測時間提交滿足設計要求的勘測數(shù)據(jù)。在勘測過程中，鐵路勘測外業(yè)的送接車輛調(diào)度安排，決定了各個勘測點的開始作業(yè)時間，在一定程度上決定了勘測任務的銜接緊密性，進而影響到整個勘測任務的進度。該問題的研究，對提高勘測作業(yè)效率具有積極意義。

當前關(guān)于鐵路勘測外業(yè)送接問題的研究極少，單玉民[2]認為，鐵路勘測任務需在線路走向方案提出后匯總各專業(yè)勘測工作量確定勘測計劃，進而對勘測用車、勘測里程及偏距(地點)、勘測作業(yè)時間、送接勘測作業(yè)人員的順序、車輛行駛路徑等作出安排。目前，鐵路勘測用車的調(diào)度方式通常為均等或按照遠近順序分配各車勘測點位，司機按照勘測人員完成任務、提出接回需求的先后次序作出響應，完成勘測人員送、接。該方式無法從系統(tǒng)最優(yōu)角度實現(xiàn)人員送、接，產(chǎn)生較多等待時間。

鐵路勘測外業(yè)的送接車輛調(diào)度安排為車輛路徑問題(vehicle routing problem, VRP)中的一個特例。其中，勘測人員是送接車輛的服務對象，決策者關(guān)注勘測任務的完成情況，給各個車輛安排其所負責的勘測點送?接任務，每一車輛的司機用最少行駛里程和等待時間完成任務。二者在雙層決策系統(tǒng)中屬于領導與被領導關(guān)系。決策者只能通過為各車輛分配勘測點來控制勘測進度；而司機通過選定行駛路線反饋給決策者。雙方無法在雙層決策系統(tǒng)中使用1個目標函數(shù)來表示2個相互沖突的目標，故通常用雙層規(guī)劃模型[3-5]研究此類問題，用上層模型表示決策者的任務分配，下層模型表示各車輛的路徑優(yōu)化問題。

鐵路勘測外業(yè)的送?接車輛調(diào)度安排問題本質(zhì)上是一個具有時間窗要求的特殊車輛路徑問題。與一般車輛路徑問題相比，其特殊性主要表現(xiàn)在勘測車輛需要為勘測點先后提供送、接兩種服務，勘測點在送接之間的時間段進行勘測作業(yè)等方面。本文基于送?接車輛調(diào)度安排問題的特點，采用勘測送?接擴展網(wǎng)絡描述問題特征，基于既有VRP問題研究成果[6-7]建立勘測外業(yè)的送?接車輛調(diào)度雙層規(guī)劃模型，并設計嵌套遺傳算法進行求解，最后通過實例驗證模型和算法的有效性，有效提高生產(chǎn)組織效率。

1 問題描述

鐵路勘測日常出工具體流程為所有勘測人員根據(jù)勘測任務分成若干個勘測小組，為每一車輛分配勘測節(jié)點送?接任務，全體勘測人員乘坐一輛或多輛勘測車輛從項目部駐地出發(fā)，各勘測車輛在指定的勘測點之間派送和接回勘測人員，并最終返回駐地的過程。對于任一勘測車輛，須先將各勘測小組送到預定的勘測點，在任務完成后恰當?shù)臅r機返回去將其接回，當日勘測工作量未完成時則前往下一個勘測點，如已完成則可返回駐地。

該問題有如下特點。

1) 每一勘測車輛的送?接路徑，包含駐地和該車輛所承擔送?接任務的勘測點，所配置的勘測車輛應能覆蓋所有勘測點。

2) 各勘測車輛的送?接路徑可視為均從駐地出發(fā)，并在完成所有送?接任務后返回駐地的一個有向、有序閉合路徑。假定每一勘測點的派送和接回任務由同一輛勘測車輛完成，即各車輛的送?接路徑間不存在交叉關(guān)系。

3) 在每一勘測車輛的送?接路徑上，每一勘測點需要被勘測車輛經(jīng)由兩次，即派送人員至勘測點和從勘測點接回人員的送和接兩個任務分時先后進行。兩個任務之間的時間間隔不少于勘測點的作業(yè)時間。

以圖1(a)所示的勘測送?接網(wǎng)絡為例，由駐地和3個勘測點構(gòu)成該網(wǎng)絡的節(jié)點集合，圖中所示路徑為只有1輛車時的一個單車輛送?接調(diào)度方案。該單車輛調(diào)度方案由派送弧和接回弧兩類弧段組成，是一個送?接任務網(wǎng)絡上的有向、有序閉合路徑，弧上數(shù)字為其先后次序標號。為簡化單車輛送?接調(diào)度方案的表達，可將勘測網(wǎng)絡中每一勘測點按照送?接任務分拆成送點和接點，轉(zhuǎn)化為圖1(b)所示的勘測送?接擴展網(wǎng)絡。在勘測送?接擴展網(wǎng)絡上，單車輛送?接方案可以描述為遍歷所有節(jié)點，每個節(jié)點僅訪問一次的一條有向閉合路徑，且每一勘測點對應的送點和接點之間的時間間隔不少于該點的勘測作業(yè)時間。由于勘測送?接擴展網(wǎng)絡上有向弧的次序可清晰表達，不必在弧段上再增加序號表示其先后關(guān)系。由此，單車輛的送?接調(diào)度，可歸結(jié)為帶送?接約束條件的車輛路徑問題。該問題的優(yōu)化目標可根據(jù)實際情況，設置為勘測人員的總等待時間最短，車輛行駛成本最小等。上述問題可拓展到多車輛情形。在多車模式下，可將其分解為送?接車輛的勘測點任務指派和各車輛送?接路徑優(yōu)化問題，兩者可視為一個雙層規(guī)劃問題。即上層決策點是如何為各車指派勘測點使得工作量均衡分配且用時最短；下層決策點是對各車輛按單車模式下帶送?接約束條件的車輛路徑問題，分別求解最佳送接路徑，并反饋給上層決策以調(diào)整勘測點的指派方案。

圖1 單車送?接擴展網(wǎng)絡示意Figure 1 Send-pick survey network for a single car

2 數(shù)學模型

2.1 模型假設

為簡化問題的建模優(yōu)化，進一步提出如下假設。

1) 送?接車輛數(shù)量已經(jīng)給定，各送?接車輛無能力限制，均能容納所承擔的勘測點的人員和設備運輸裝載要求；

2) 所有勘測點的勘測任務無優(yōu)先等級要求和先后順序要求；

3) 勘測網(wǎng)絡上任意兩節(jié)點間均可相互聯(lián)通，節(jié)點間車輛行駛時間、每個勘測點的作業(yè)時間均已知。

2.2 模型建立

令勘測網(wǎng)絡的節(jié)點集合為N(其中駐地編號為0)，i,j為 勘測點，i,j≠0 。E為派送車輛集合，e∈E為一輛派送車輛，|E|為車輛數(shù)。在勘測網(wǎng)絡中，Ne為車輛e負 責的勘測點集合，滿足wi為勘測網(wǎng)絡節(jié)點i∈N的 作業(yè)時間；sij為勘測網(wǎng)絡節(jié)點i到j的車輛行 駛 里 程；分別為 車 輛e運行到勘測網(wǎng)絡節(jié)點i∈N派送和接回的時刻。決策變量xei，若車輛e負 責勘測點i的派送和接回任務則取1，否則取0。

對于車輛e的擴展送?接網(wǎng)絡，有節(jié)點和分 別表 示中接 回 和派 送節(jié) 點，為勘測網(wǎng)絡N中節(jié)點i,j的 對應節(jié)點。決策變量xe?i?j，若車輛e從擴展送?接網(wǎng)絡節(jié)點運行到節(jié)點則取1，否則取0。

根據(jù)前述分析，將該問題用雙層規(guī)劃模型進行表達。作為上層規(guī)劃的勘測點任務指派模型(U)為

其中，式(1)為各車輛送?接持續(xù)時間最短和最均衡的目標函數(shù)，γ為所有送?接車輛的廣義費用(見式11)的均衡性權(quán)重；式(2)表示任一物理勘測點只由一輛車負責派送和接回；式(3)表示各車輛至少負責1個勘測點。

下層規(guī)劃為各車輛送?接路徑優(yōu)化問題，對各車輛的送?接調(diào)度方案相互獨立求解。對車輛e，其車輛送?接路徑優(yōu)化模型(L)為

其中，式(4)表示車輛e勘測總等待時間最短，包括人等車和車等人兩種情況；式(5)表示車輛固定成本加行駛成本最小；對于車輛e，式(6)、(7)表示擴展送?接網(wǎng)絡中任一頂點都要被訪問一次；式(8)、(9)保證從駐地出發(fā)的車輛必須返回駐地；式(10)表示接人時間不早于送人時間。 為便于多目標優(yōu)化問題求解，采用線性加權(quán)組合法將式(4)和式(5)組合作為送接路徑的廣義費用。

其中，α為勘測地區(qū)單位時間內(nèi)工資成本，采用α 作 為Z2e的權(quán)重系數(shù)。

由上層規(guī)劃的勘測點任務指派模型(U)和下層規(guī)劃的車輛送?接路徑優(yōu)化模型(L)構(gòu)成送?接車輛調(diào)度優(yōu)化問題的一對多雙層規(guī)劃模型。

3 嵌套遺傳算法設計

下層規(guī)劃(L)中的車輛送?接路徑問題屬于典型的組合優(yōu)化問題，目前無多項式時間算法，在算法復雜性上為NP難題[8]，本文的雙層規(guī)劃模型難以用精確算法求解。20世紀90年代以來，遺傳算法由于具有多點并行搜索、基于采樣隨機搜索和基于概率搜索等優(yōu)良特性，在解決組合優(yōu)化問題上顯示出強大功能[9-10]。為求解本文雙層規(guī)劃模型，設計嵌套遺傳算法，外層遺傳算法求解上層規(guī)劃，內(nèi)層遺傳算法求解下層規(guī)劃，實現(xiàn)雙層規(guī)劃一體優(yōu)化。

3.1 染色體設計

1) 外層遺傳算法編碼設計。根據(jù)上層規(guī)劃模型(U)的特征，以二進制矩陣來表示決策變量，即車輛e負責勘測點i的送接任務則用1表示，否則用0表示。該編碼方式形成的編碼空間中的所有點與可行解空間中的所有點一一對應。考慮式(2)，同一染色體等位基因上具有成組關(guān)聯(lián)的特征。假設模型中共有n輛車，m個勘測點，圖2所示為二進制矩陣表示的染色體，1列為1個基因組，同一基因組中所有基因之和為1，確保模型解的可行性。在遺傳操作中，為避免單基因變換對染色體的可行性造成破壞，以基因組為單位進行交叉和變異操作。

圖2 二進制矩陣表示的染色體Figure 2 Chromosome of binary matrix

2) 內(nèi)層遺傳算法染色體設計。對任一車輛e，其負責送?接范圍內(nèi)的每一個勘測點都要訪問兩次，即送、接各一次。對應到送?接擴展網(wǎng)絡上，下層規(guī)劃染色體設計需要區(qū)分每一個勘測點的勘測接點、勘測送點兩種擴展網(wǎng)絡節(jié)點。本文提出勘測點i∈N及其擴展節(jié)點的編、解碼方法，如表1所示。

表1 送-接擴展網(wǎng)絡編、解碼設計Table 1 Coding and decoding design of extended send-pick network

3.2 遺傳算子設計

1) 外層遺傳算子設計。

(1) 變異操作。外層遺傳算子運算操作基于二進制矩陣表示的染色體，其中變異操作采用基因組反轉(zhuǎn)變異，即以一定的概率pOm選 擇一個染色體C1O。先隨機選擇一個變異組x，再隨機選擇基因組中異于原值為1的位置，調(diào)換二者基因，其余位置的基因不變，如圖3所示。

圖3 外層染色體成組反轉(zhuǎn)變異Figure 3 Group inverting mutation of outer chromosome

(2) 交叉操作。交叉操作采用單基因位的成組交叉，確保染色體在交叉過程中的可行性，有效改進遺傳編碼，即以一定的概率選擇兩個染色體C1O和C2O，隨機生成一個交叉點位x，則C和C2O交叉點位x之前的基因組不變，將包括x在內(nèi)的之后的基因組相互交換，生成兩個子代染色體和，如圖4所示。

圖4 外層染色體成組交叉Figure 4 Group crossover of outer chromosomes

(3) 評價。采用上層規(guī)劃問題(U)的目標函數(shù)來評價各染色體CkO={cen|e=1,···,|E|,n=1,···,|N|}，k=1,···,popSize，染色體的適值函數(shù)為

其中，根據(jù)問題特征Z1>0。

2) 內(nèi)層遺傳算子設計。

(1) 交叉操作。內(nèi)層遺傳算法的編碼方式?jīng)Q定了內(nèi)層染色體的基因組成為送?接擴展網(wǎng)絡的車輛送、接順序，故其交叉操作是以一定的概率選擇兩個染色體和，對其采用部分一致交叉法(partial-mapped crossover, PMX)[10]，交叉過程如圖5所示。

圖5 部分一致交叉法示例Figure 5 Illustration of PMX

(2) 變異操作。內(nèi)層遺傳算法的變異操作是從父代以一定的概率隨機選擇一個染色體，隨機生成2個變異位置x和y，交換這2個點的基因得到子代染色體，如圖6所示。

圖6 變異算子示例Figure 6 Illustration of mutation operator

(3) 評價。下層規(guī)劃模型(L)通過計算送?接路徑廣義費評價各染色體|N|}，k=1,···,popSize ，染色體的適值函數(shù)如式(13)所示。

其中，M為較大的正整數(shù)，是對染色體所產(chǎn)生的解不滿足約束條件而進行的懲罰；根據(jù)問題特征，Z4e＞0。

3.3 嵌套遺傳算法處理過程

采用嵌套遺傳算法求解本文雙層規(guī)劃模型。計算步驟如下。

步驟 0設定內(nèi)、外層種群的大小分別為popSizeI和 p opSizeO，交叉率分別為pIc和pOc，變異率分別為和pOm，最大代數(shù)m ax GenI和m ax GenO，初始評價函數(shù)值min EvalI和min EvalO。

步驟 1外層算法開始，生成滿足上層規(guī)劃模型(U)約束條件的初始解的二進制染色體(編碼)。

步驟 2根據(jù)染色體，計算適值函數(shù)(解碼)，解碼染色體后逐一將每輛車e∈E負責送?接的勘測點集傳入內(nèi)層算法作為輸入。

1) 內(nèi)層算法開始，隨機生成當前車輛e下層規(guī)劃模型(L)初始解的染色體(編碼)。

3) 代數(shù)g en=gen+1，進行如下操作。

(1) 部分一致交叉(內(nèi)層)。交叉生成的新染色體數(shù)用 cCntI表示，令 cCntI=0，生成 (0,1)區(qū)間內(nèi)的隨機數(shù)。選擇滿足rk＜pIc的 染色體，并對被選染色體進行配對，令 cCntI=cCntI+2，按圖5所示方法進行交叉操作，得到的新染色體分別定義為

(2) 變異(內(nèi)層)。令變異生成的染色體數(shù)mCntI=0。 生成 (0,1)區(qū) 間內(nèi)的隨機數(shù)選擇滿足的染色體，按圖6所示方法進行變異，令 mCntI=mCntI+1，生成新的染色體

(3) 輪盤賭選擇(內(nèi)層)。按式(13)計算染色體的適值，按適值大小進行排序，用輪盤賭模型[11]選擇適值較高的 p opSizeI數(shù)目的染色體作為子代染色體。

4) 若 gen＜max GenI，返回2)；否則循環(huán)結(jié)束，返回當前最佳送?接路徑及其廣義費用。

步驟 3代數(shù)g en=gen+1，進行如下操作。

1) 基因組交叉(外層)。交叉生成的新染色體數(shù)用 c CntO表 示，令 c CntO=0。 生成 (0,1)區(qū)間內(nèi)的隨機數(shù)。選擇滿足的染色體，并對被選染色體進行配對，令c CntO=cCntO+2，按圖4所示方法進行單點位基因組交叉，得到的新染色體分別定義為

2) 基因組變異(外層)。令用來變異生成的染色體數(shù) mCntO=0 。生成 (0,1)區(qū) 間內(nèi)的隨機數(shù)。選擇滿足的染色體CkO，按圖3所示方法進行成組反轉(zhuǎn)變異，令 m CntO=mCntO+1，生成新的染色體

3) 輪盤賭選擇(外層)。按式(12)計算染色體的適值按適值大小進行排序，用輪盤賭模型選擇適值較高的popSizeO數(shù)目的染色體作為子代染色體。

步驟 4若g en＜max GenO，返回步驟 2；否則循環(huán)結(jié)束，輸出每輛車負責的勘測點及其最佳送?接路徑。

4 實例計算

為驗證本文模型和算法的有效性，以我國中南地區(qū)某新建高速鐵路的現(xiàn)場勘測數(shù)據(jù)為例進行鐵路勘測車輛調(diào)度優(yōu)化。某日出工計劃兩輛勘測用車負責沿線位附近19個勘測點，詳細數(shù)據(jù)如表2所示，其中駐地編號為0，其余按編號升序依次遠離駐地。車輛行駛速度v=0.6 km/min，單位里程行駛費用f=0.8 元/km，車輛的固定使用費用F=150 元，勘測所在地區(qū)單位時間內(nèi)工資成本α=0.5 元/min。

表2 勘測點數(shù)據(jù)Table 2 Coordinates of survey points

本文利用C#對提出的送?接車輛調(diào)度優(yōu)化問題的嵌套遺傳算法進行編程實現(xiàn)。外層遺傳算法參數(shù)：迭代次數(shù) max GenO= 4 000，種群規(guī)模 popSizeO=10，交叉率=0.6，變異率為pOm=0.2；內(nèi)層遺傳算法參數(shù)：迭代次數(shù)m ax GenI= 2 000，種群規(guī)模 p opSizeI=10，交叉率= 0.4, 變異率為=0.6。將基于本文雙層規(guī)劃模型與算法的優(yōu)化結(jié)果與目前的響應式車輛送?接調(diào)度方法進行對比，兩種方法對應的路徑為如下。

1) 在拓展網(wǎng)絡上的優(yōu)化送?接路徑。車輛1：0-19S-17S-8S-18S-17P-5S-7S-13S-5P-8P-13P-7P-18P-19P-0；車 輛2：0-15S-14S-12S-6S-1S-2S-11S-14P-16S-9S-4S-15P-11P-2P- 3S-6P-10S-10P-16P-9P-1P-3P-4P-12P-0。

2) 按傳統(tǒng)的響應式思想編制的送?接路徑。車輛1：0-1S-2S-3S-4S-5S-6S-7S-8S-5P-2P-7P-3P-6P-9P-1P-4P-8P-0；車輛2：0-10S-11S-12S-13S-14S-15S-16S-17S-18S-19S-10P-14P-11P-13P-15P-17P-16P-18P-12P-19P-0。

其中，S表示送，P表示接。響應式調(diào)度方法是根據(jù)勘測點數(shù)量，平分給兩輛車，即車輛1負責前9個勘測點的送?接任務，車輛2負責后10個勘測點的送?接任務。經(jīng)兩種方法計算得到的指標對比如表3所示。

由表3可看出，調(diào)度優(yōu)化算法的總廣義費用相較于響應式調(diào)度減少18.0%。二者差距在于調(diào)度優(yōu)化算法求解的雙層規(guī)劃模型中體現(xiàn)了對送?接調(diào)度方案的總廣義費用的優(yōu)化，故兩輛車的各個指標都較均衡，任務分配更加合理，等待時間也遠小于響應式調(diào)度方式。通過送、接次序的優(yōu)化提高了勘測進度緊湊性，其中人等車的時間僅占總等待時間的20%，各指標都優(yōu)于目前的響應式調(diào)度方法。

表3 優(yōu)化算法結(jié)果與響應式調(diào)度結(jié)果比較Table 3 Comparison of results between optimization and responsive scheduling

調(diào)度優(yōu)化算法求得的最優(yōu)送?接方案調(diào)度方案，如圖7所示?？梢?，各車在大部分勘測點接人時產(chǎn)生的等待時間較小，對從送?接車輛組織環(huán)節(jié)上加快勘測進度，提高勘測效率具有積極意義。

圖7 優(yōu)化方案勘測車輛調(diào)度運行圖Figure 7 Survey vehicle dispatching diagram of optimal scheme

5 結(jié)論

本文基于鐵路工程勘測中送?接車輛的調(diào)度問題，以多車指派問題和單車帶作業(yè)時間窗和送?接約束VRP問題為切入點，建立雙層規(guī)劃模型將二者有機結(jié)合進行研究。該模型為NP難問題，針對該模型的特點提出了內(nèi)外層嵌套的遺傳算法用以求解該模型，專門設計了嵌套遺傳算法的遺傳算子。

求解實例表明，本文提出的模型與算法求解得到的廣義勘測費用相較于響應式調(diào)度方式減少了18.0%，成本、里程和等待時間等指標更加均衡，車輛任務分配更加合理，可有效提高勘測效率和勘測進度的銜接程度。

本文所提出的模型與算法不僅為解決多車送?接的車輛路徑問題提供了一種有效的工具和手段，也可為鐵路工程勘測送?接車輛調(diào)度優(yōu)化提供可行方法，在理論研究和實踐應用上具有一定意義。