鐵路勘測(cè)外業(yè)的送接車輛調(diào)度優(yōu)化問(wèn)題

曾俊豪，鄧連波

(1.中鐵四院集團(tuán)南寧勘察設(shè)計(jì)院有限公司，廣西 南寧 530003；2.中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075)

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

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

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

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

1 問(wèn)題描述

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

該問(wèn)題有如下特點(diǎn)。

1) 每一勘測(cè)車輛的送?接路徑，包含駐地和該車輛所承擔(dān)送?接任務(wù)的勘測(cè)點(diǎn)，所配置的勘測(cè)車輛應(yīng)能覆蓋所有勘測(cè)點(diǎn)。

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

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

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

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

2 數(shù)學(xué)模型

2.1 模型假設(shè)

為簡(jiǎn)化問(wèn)題的建模優(yōu)化，進(jìn)一步提出如下假設(shè)。

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

2) 所有勘測(cè)點(diǎn)的勘測(cè)任務(wù)無(wú)優(yōu)先等級(jí)要求和先后順序要求；

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

2.2 模型建立

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

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

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

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

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

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

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

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

3 嵌套遺傳算法設(shè)計(jì)

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

3.1 染色體設(shè)計(jì)

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

圖2 二進(jìn)制矩陣表示的染色體Figure 2 Chromosome of binary matrix

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

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

3.2 遺傳算子設(shè)計(jì)

1) 外層遺傳算子設(shè)計(jì)。

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

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

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

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

(3) 評(píng)價(jià)。采用上層規(guī)劃問(wèn)題(U)的目標(biāo)函數(shù)來(lái)評(píng)價(jià)各染色體CkO={cen|e=1,···,|E|,n=1,···,|N|}，k=1,···,popSize，染色體的適值函數(shù)為

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

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

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

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

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

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

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

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

3.3 嵌套遺傳算法處理過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例計(jì)算

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

表2 勘測(cè)點(diǎn)數(shù)據(jù)Table 2 Coordinates of survey points

本文利用C#對(duì)提出的送?接車輛調(diào)度優(yōu)化問(wèn)題的嵌套遺傳算法進(jìn)行編程實(shí)現(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é)果與目前的響應(yīng)式車輛送?接調(diào)度方法進(jìn)行對(duì)比，兩種方法對(duì)應(yīng)的路徑為如下。

1) 在拓展網(wǎng)絡(luò)上的優(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)的響應(yī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表示接。響應(yīng)式調(diào)度方法是根據(jù)勘測(cè)點(diǎn)數(shù)量，平分給兩輛車，即車輛1負(fù)責(zé)前9個(gè)勘測(cè)點(diǎn)的送?接任務(wù)，車輛2負(fù)責(zé)后10個(gè)勘測(cè)點(diǎn)的送?接任務(wù)。經(jīng)兩種方法計(jì)算得到的指標(biāo)對(duì)比如表3所示。

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

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

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

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

5 結(jié)論

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

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

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