劉 霞，李 楠

（江漢大學(xué) 物理與信息工程學(xué)院，湖北 武漢 430056）

0 引言

軌道交通的出現(xiàn)不僅順應(yīng)了城市高速發(fā)展的需要，也逐漸成為了人們出行必不可少的乘車方式之一。我國近年來軌道交通建設(shè)大步向前，軌道線路的數(shù)量和長度都在穩(wěn)步上升，但由于建設(shè)的經(jīng)濟(jì)成本高、耗時(shí)長、技術(shù)難度高和城市地形的復(fù)雜度不同，軌道交通的服務(wù)范圍主要是圍繞著城市中心地帶和一些人流大的地區(qū)，沒能很好地顧及到城市各個(gè)地區(qū)交通出行需求［1］。相比之下，傳統(tǒng)的常規(guī)公交城市覆蓋率非常高，其建設(shè)成本較低，可實(shí)施性也較高，公交系統(tǒng)基本上可以涵蓋城市不同區(qū)域的交通出行，但相較于軌道交通，常規(guī)公交的運(yùn)行效率低，乘客乘車體驗(yàn)感也較差［2］。結(jié)合兩者的不同性質(zhì)，將軌道交通和常規(guī)公交相互協(xié)調(diào)起來工作，可以很好地發(fā)揮它們各自的優(yōu)勢，提高城市交通的效益［3］。

在軌道交通與常規(guī)公交銜接研究方面，國內(nèi)外已經(jīng)有了大量理論基礎(chǔ)，研究的切入點(diǎn)較多集中在以不同的優(yōu)化算法去減少乘客換乘時(shí)間、乘車時(shí)間和公交運(yùn)營成本等［4］。CHOWDHURY等［5］以總費(fèi)用最小為目標(biāo)函數(shù)構(gòu)建模型，以接駁公交線路的開行頻率一致為前提，對常規(guī)公交開行頻率進(jìn)行確定。任芳［6］通過分析和總結(jié)現(xiàn)有城市軌道交通和常規(guī)公交的相關(guān)理論，對公交接駁站點(diǎn)的設(shè)置以及線路優(yōu)化的方法作了具體研究。方曉麗［7］在先定性調(diào)整既有的公交線路去保證線路布局的合理性和新增接駁公交線路去優(yōu)化乘客的成本方面進(jìn)行了研究。在這些問題的研究中，大多數(shù)都是在軌道交通線路不變的情況下，對已有的公交線路進(jìn)行部分的整改優(yōu)化，從而達(dá)到預(yù)期的效果。本文研究的問題是在沒有初始公交線路的基礎(chǔ)上，以一個(gè)軌道交通站點(diǎn)為中心點(diǎn)，在其服務(wù)半徑內(nèi)，結(jié)合周邊乘客出行需求，對接駁軌道交通的公交線路進(jìn)行設(shè)計(jì)，使乘客出行成本和公交公司運(yùn)營成本的總和最低。

1 建立問題求解模型

1.1 問題描述

接駁公交線路是以一定的順序和方向?qū)⒏鱾€(gè)公交站點(diǎn)以及軌道交通站點(diǎn)進(jìn)行彼此之間的聯(lián)通，由軌道交通接駁站點(diǎn)和公交站點(diǎn)組成的一個(gè)城市交通網(wǎng)絡(luò)［8］。本文以魏超［9］提出的接駁公交線路問題為基礎(chǔ)，以單個(gè)的軌道交通站點(diǎn)為圓心，以一定的接駁線路長度為半徑，將區(qū)域范圍內(nèi)的接駁公交站點(diǎn)進(jìn)行連接，從而達(dá)到該區(qū)域的乘客出行成本和公交運(yùn)營成本的總和最小的目的。在該問題中規(guī)定每個(gè)公交站點(diǎn)只出現(xiàn)于一條接駁公交線路上，每條接駁公交線路只連接一個(gè)軌道交通站點(diǎn)，公交車在每個(gè)站點(diǎn)都?？俊?/p>

1.2 變量定義

在該線路設(shè)計(jì)的模型中，公交站點(diǎn)的個(gè)數(shù)為n，站點(diǎn)集合V={1，2，…，n}。軌道交通站點(diǎn)的個(gè)數(shù)為1，設(shè)為站點(diǎn)0，兩者組成的網(wǎng)絡(luò)節(jié)點(diǎn)集合記為N=0?V，任意兩個(gè)站點(diǎn)i和j之間的距離為dij，接駁公交線路的條數(shù)為k，接駁線路集合為K={1，2，…，k}。公交車行駛的平均速度為v，線路k的開行頻率為fk，表示一小時(shí)發(fā)車的次數(shù)。qi表示一小時(shí)內(nèi)i站點(diǎn)的出行量，表示k線路上公交從i站點(diǎn)出發(fā)駛向j站點(diǎn)時(shí)輸送的乘客數(shù)量。采用0-1變量來表示站點(diǎn)與站點(diǎn)關(guān)系，如公式（1）所示；站點(diǎn)與線路的關(guān)系，如公式（2）和公式（3）所示。

1.3 約束條件

1.3.1 接駁線路的完整性 每條接駁線路僅有一個(gè)起始公交站點(diǎn)，即滿足

設(shè)站點(diǎn)i是公交線路k的起點(diǎn)，則站點(diǎn)i只存在后續(xù)站點(diǎn)，沒有前續(xù)站點(diǎn)，即滿足

每條接駁線路均以軌道交通站點(diǎn)為終點(diǎn)，即滿足

除終點(diǎn)外，若站點(diǎn)i在線路k上，則站點(diǎn)i必有一個(gè)后續(xù)站點(diǎn)j，即滿足

1.3.2 站點(diǎn)與線路之間的關(guān)系 每個(gè)公交站點(diǎn)只存在于一條公交線路上，即滿足

為保證公交線路運(yùn)行距離的均衡性，對每條線路經(jīng)過的站點(diǎn)數(shù)量做出約束，即滿足

其中α表示每條線路上站點(diǎn)數(shù)量的波動幅度，Nk表示公交線路k經(jīng)過的站點(diǎn)總數(shù)。

任意一條線路必須是無環(huán)的簡單鏈，即滿足

1.3.3 車上乘客數(shù)量和公交運(yùn)能守恒 線路k上公交駛離站點(diǎn)i后輸送的乘客數(shù)量等于到達(dá)站點(diǎn)i之前輸送的乘客數(shù)量與站點(diǎn)i出行需求之和，即滿足

任意公交線路的運(yùn)能應(yīng)該大于該線路總的客流需求，即滿足

其中pmax為公交車最大載客量。

1.4 系統(tǒng)費(fèi)用

接駁公交線路設(shè)計(jì)考慮的兩個(gè)主體為乘客和公交運(yùn)營商，在保證方案可實(shí)施的前提下，需要整體考慮兩者的利益。因而系統(tǒng)總費(fèi)用由乘客出行成本和公交運(yùn)營成本兩部分組成［10］。

1.4.1 乘客出行成本 乘客的候車時(shí)間成本：乘客候車時(shí)間主要取決于公交車的開行頻率，開行頻率越高則乘客候車時(shí)間越少，反之越多。乘客候車成本可表示為

其中Cw表示單位時(shí)間候車成本。

乘車時(shí)間成本：乘客的乘車時(shí)間主要取決于公交線路的設(shè)計(jì)和公交運(yùn)行速度。乘客的總的乘車時(shí)間成本可以表示為

其中Ct表示單位時(shí)間乘車成本。

1.4.2 公交運(yùn)營成本 公交車輛運(yùn)營成本包括燃油費(fèi)、人工費(fèi)和折舊費(fèi)等，與接駁線路的長度正相關(guān)。此外，公交開行頻率越高，公交運(yùn)營成本也就越高。公交運(yùn)營成本可以表示為

其中C0表示公交車輛單位時(shí)間運(yùn)營成本。

通過上述分析，以乘客出行總成本和公交車輛運(yùn)營成本之和最小為目標(biāo)，建立雙向接駁線路優(yōu)化模型的目標(biāo)函數(shù)為

當(dāng)公交線路給定并且忽略公交運(yùn)能約束，則上述優(yōu)化模型將變成無約束優(yōu)化問題。利用函數(shù)最優(yōu)性條件，通過對目標(biāo)函數(shù)求導(dǎo)可以得到無運(yùn)能約束下最優(yōu)公交開行頻率為

因在本文中需要滿足運(yùn)能約束，則最優(yōu)公交開行頻率的計(jì)算如公式（18）所示：

2 基于混合遺傳算法的模型求解

2.1 算法的基本步驟

本文研究的是一個(gè)典型的優(yōu)化組合問題，遺傳算法作為一種啟發(fā)式智能搜索算法在解決此類問題時(shí)效果較好［11］，本文在算法基本框架上做出局部優(yōu)化處理，形成一種混合遺傳算法，使算法收斂性更佳［12］?；静襟E如下［13］：

第一步確定接駁公交線路的總條數(shù)。

第二步種群初始化。隨機(jī)生成含有若干個(gè)初始個(gè)體的種群，并設(shè)置最大的繁衍代數(shù)。

第三步選擇算子。采用錦標(biāo)賽選擇策略將初始種群中適應(yīng)度值較優(yōu)的個(gè)體進(jìn)行保留，形成新的種群。

第四步交叉算子和變異算子。設(shè)置進(jìn)行交叉操作和變異操作的概率，采用順序交叉方式和單點(diǎn)變異方式，形成新的種群。

第五步局部優(yōu)化。采用opt-2和單點(diǎn)插入局部處理方式對種群進(jìn)行優(yōu)化，使種群跳出非最優(yōu)解的局部收斂。

第六步判斷繁衍是否結(jié)束。檢測繁衍的代數(shù)是否到達(dá)上限，若到達(dá)，則輸出當(dāng)前最優(yōu)的值；否則返回第三步。

2.2 解的編碼和初始種群的生成

用數(shù)字1，2，…，n分別代表對應(yīng)的站點(diǎn)編號，數(shù)字0代表軌道交通站點(diǎn)，每條接駁公交線路以軌道交通站點(diǎn)0為結(jié)束標(biāo)志。圖1所示為3線路，分別為1-2-0、7-3-0、6-4-5-0，線路1-2-0是以站點(diǎn)1為起點(diǎn)，接著經(jīng)過站點(diǎn)2，最后到達(dá)軌道交通站點(diǎn)0。

圖1 解的編碼表示Fig.1 Coding representation of solution

初始種群的生成過程為：首先將所有公交站點(diǎn)進(jìn)行隨機(jī)排列，然后根據(jù)預(yù)設(shè)的線路條數(shù)k在公交站點(diǎn)數(shù)列中隨機(jī)插入k個(gè)0，形成一個(gè)完整初始解。重復(fù)該過程生成含有N個(gè)初始解的初始種群。

2.3 選擇策略

在遺傳算法中，可以采用輪盤賭、隨機(jī)遍歷抽樣、最優(yōu)保存、排序選擇和錦標(biāo)賽選擇等選擇策略。為使系統(tǒng)總費(fèi)用最小。本文采用錦標(biāo)賽選擇策略，具體的操作步驟如下：

1）首先確定每次從種群中選擇進(jìn)行優(yōu)劣性比較的個(gè)體數(shù)量n。

2）從種群中隨機(jī)選擇個(gè)體數(shù)量為n的小種群，在小種群中選擇最優(yōu)的個(gè)體進(jìn)入新種群。

3）重復(fù)步驟2），直到構(gòu)成一個(gè)與初始種群個(gè)體規(guī)模相同的新種群。

2.4 交叉策略和變異策略

2.4.1 交叉策略 交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所研究的問題密切相關(guān)，既不能過多地破壞個(gè)體編碼串中表示優(yōu)良性狀的模式，又需要有效地產(chǎn)生一些較好的新個(gè)體模式?？紤]到本文的模型主要是站點(diǎn)之間的匹配順序問題，這里采用順序交叉方式。過程如下：

第一步隨機(jī)選擇一個(gè)染色體中兩個(gè)基因作為待交叉片段的起始位置（兩個(gè)父代染色體被選的位置相同），如圖2所示。

圖2 選擇交叉片段Fig.2 Selection of cross section

第二步生成一個(gè)子代，并保證子代中被選中基因的位置與父代相同（其中父代中的軌道站點(diǎn)不參與交叉，即后代中0的位置不變），如圖3所示。

圖3 子一代產(chǎn)生過程（1）Fig.3 Generation process of the first offspring（1）

第三步在另一個(gè)父代中剔除第一步選中的基因，將剩余基因按順序依次放入上一步生成的子代中，如圖4所示。

圖4 子一代產(chǎn)生過程（2）Fig.4 Generation process of the first offspring（2）

在本例中另一個(gè)子代如圖5所示。

圖5 子二代Fig.5 The second offspring

2.4.2 變異策略 遺傳算法中的變異運(yùn)算，是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個(gè)新的個(gè)體。本文采用單點(diǎn)變異，首先隨機(jī)選擇一個(gè)變異點(diǎn)，然后隨機(jī)生成一個(gè)變異基因（這個(gè)基因來自本身存在的編號），最后交換產(chǎn)生的變異基因與該基因的位置，如圖6所示。

圖6 單點(diǎn)變異Fig.6 Single point variation

2.5 局部優(yōu)化

在單純采用傳統(tǒng)遺傳算法的時(shí)候，形成最優(yōu)解的過程收斂速度慢、不穩(wěn)定性也較大，并且容易陷入到局部最優(yōu)解［14］。檢測發(fā)現(xiàn)，由于該問題解結(jié)構(gòu)的特殊性，加上交叉方式的特殊性等一些潛在影響因素，在每次交叉和變異結(jié)束后對較優(yōu)的后代進(jìn)行局部優(yōu)化。本文采用2-opt法和隨機(jī)插入法進(jìn)行局部優(yōu)化。

2.5.1 2-opt法 2-opt是一種隨機(jī)性局部優(yōu)化的方法，是解決優(yōu)化組合問題的有效工具，這里以問題的子線路來說明（設(shè)最大循環(huán)次數(shù)為n，單次循環(huán)次數(shù)為c）：

第一步隨機(jī)選擇1條子線路（如1-2-3-4-5-6-0），計(jì)算出該條子線路的總費(fèi)用為mincost。

第二步隨機(jī)選擇該條子線路中的兩個(gè)站點(diǎn)，依次對調(diào)兩個(gè)站點(diǎn)形成新的子線路，如選擇站點(diǎn)3和站點(diǎn)6，則新的子線路為1-2-6-5-4-3-0。

第三步若新的子線路總費(fèi)用比mincost要小，更新最優(yōu)子線路為當(dāng)前子線路，并更新mincost的值，將c的值改為0，回到第二步，否則將c的值加1，回到第二步，當(dāng)c的值大于n時(shí)，結(jié)束算法。

2.5.2 隨機(jī)插入法 隨機(jī)插入法是針對該問題所衍生出來的一種局部處理當(dāng)前解方法。具體步驟如下：

第一步隨機(jī)選擇一條子線路和該線路上的一個(gè)站點(diǎn)。如圖7所示，選擇子線路8-9-10-0中的站點(diǎn)9。

圖7 站點(diǎn)選擇Fig.7 Site selection

第二步將該站點(diǎn)隨機(jī)插入到另一條子線路中，并在原始的子線路中刪除該站點(diǎn)。如圖8所示，將站點(diǎn)9插入到子線路1-2-3-0的站點(diǎn)2和站點(diǎn)3之間。

3 算例

魏超［9］提出的接駁公交線路問題的算例中使用了遺傳算法進(jìn)行求解，本文采用混合遺傳算法來求解相同算例，并在算法的收斂速度上對遺傳算法和混合遺傳算法進(jìn)行比較。

3.1 基于混合遺傳算法的算例求解

假設(shè)有一個(gè)軌道交通站點(diǎn)，在這個(gè)站點(diǎn)的接駁半徑內(nèi)有25個(gè)公交站點(diǎn)。并且設(shè)置求解模型的其他參數(shù)為α=2，v=20 km/h，pmax=80人/車，C0=100元/（車·小時(shí)），Ct=10元/（人·小時(shí)），Cw=20元/（人·小時(shí)）。各公交站點(diǎn)的乘客出行需求和坐標(biāo)分別如表1和表2所示。這里設(shè)初始種群規(guī)模為50，交叉概率為0.9，變異概率為0.1。2-opt法和隨機(jī)插入法的內(nèi)部循環(huán)的次數(shù)為10，種群遺傳的代數(shù)為100。

本文采用Python語言在PyCharm編譯環(huán)境下編寫的仿真程序來生成最優(yōu)公交接駁線路。在程序模擬求解過程中，首先設(shè)定接駁線路條數(shù)為4，接著實(shí)現(xiàn)混合遺傳算法的仿真運(yùn)算，在遺傳至70代左右時(shí)可得到最優(yōu)解。并且每次模擬結(jié)果穩(wěn)定，程序運(yùn)行時(shí)間較快。如圖9所示，給出了3次混合遺傳算法求解過程中系統(tǒng)總費(fèi)用隨遺傳代數(shù)增加的趨勢圖。

表1 站點(diǎn)乘客出行人數(shù)需求Tab.1 Site passenger travelling demand

表2 站點(diǎn)坐標(biāo)Tab.2 Site coordinates

圖9 系統(tǒng)費(fèi)用走勢圖（1）Fig.9 System cost chart（1）

得出最優(yōu)的4條接駁線路分別為：1-5-10-14-18-22-0、2-6-9-13-17-21-0、3-8-12-16-20-23-25-0、4-7-11-15-19-24-0，系統(tǒng)的總費(fèi)用為10 834.26元。形成4條最優(yōu)接駁線路如圖10所示。

3.2 與遺傳算法求解的對比

保持兩個(gè)算法的選擇策略、交叉算子、變異算子均相同，去掉混合遺傳算法中局部優(yōu)化處理的操作，其他參數(shù)不變，單純采用遺傳算法求解。結(jié)果如圖11所示，給出了3次遺傳算法求解過程中系統(tǒng)總費(fèi)用隨遺傳代數(shù)增加的趨勢圖。

圖10 最優(yōu)線路圖Fig.10 Diagram of optimal routes

圖11 系統(tǒng)費(fèi)用走勢圖（2）Fig.11 System cost chart（2）

比較圖9和圖11可看出，當(dāng)遺傳代數(shù)到達(dá)100時(shí)，遺傳算法還未收斂到最優(yōu)值，并且從圖11中也可以看出隨著遺傳代數(shù)的增加，收斂的速度也在變慢，而混合遺傳算法在100代之前已經(jīng)收斂于最優(yōu)值。所以，采用混合遺傳算法可在一定程度上提升收斂的速度。

4 結(jié)語

本文研究的對象是城市軌道交通與常規(guī)公交接駁的線路優(yōu)化問題。首先提出如何將軌道交通站點(diǎn)和常規(guī)公交站點(diǎn)有效銜接的問題，接著建立問題的求解數(shù)學(xué)模型，并描述了采用混合遺傳算法求解該問題的具體步驟，最后用該算法求解了一個(gè)具體算例，并在收斂速度上與遺傳算法進(jìn)行對比，可看出混合遺傳算法收斂效果更好。此外，由于算例中所需的數(shù)據(jù)是參考實(shí)際情況而設(shè)定的，也表明了混合遺傳算法在解決該問題上的可行性。由于本文約束條件的理想化，對于一些實(shí)際問題的考慮不足，還有很大的改善余地。并且，算例中的軌道交通站點(diǎn)數(shù)量和公交站點(diǎn)的數(shù)量不多，對于多個(gè)軌道站點(diǎn)接駁多個(gè)公交站點(diǎn)的研究也有待進(jìn)一步探討。