一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法

于海璁，陸 鋒

中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101

一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法

于海璁，陸 鋒

中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101

多標(biāo)準(zhǔn)路徑規(guī)劃是公眾出行信息服務(wù)的研究熱點(diǎn)。然而，多標(biāo)準(zhǔn)路徑規(guī)劃本質(zhì)上是具有NP特性的多標(biāo)準(zhǔn)決策問(wèn)題，且涉及多種交通出行模式。多個(gè)不同標(biāo)準(zhǔn)的權(quán)重設(shè)置將直接影響路徑規(guī)劃結(jié)果。因此，如何科學(xué)合理地設(shè)置不同標(biāo)準(zhǔn)的權(quán)重成為多標(biāo)準(zhǔn)路徑規(guī)劃中的技術(shù)瓶頸。本文提出一種適應(yīng)多模式交通網(wǎng)絡(luò)環(huán)境的多標(biāo)準(zhǔn)路徑規(guī)劃方法，借鑒遺傳算法在求解多標(biāo)準(zhǔn)優(yōu)化問(wèn)題中的優(yōu)勢(shì)，將其擴(kuò)展到多模式多標(biāo)準(zhǔn)路徑規(guī)劃中。該方法避免了不同出行標(biāo)準(zhǔn)權(quán)重設(shè)置中的主觀性和不確定性，能夠?qū)崿F(xiàn)更為靈活的交通出行模式自動(dòng)化組合，為出行者提供滿足個(gè)性化需求的、多標(biāo)準(zhǔn)的出行路徑規(guī)劃服務(wù)。

路徑規(guī)劃；多模式；多標(biāo)準(zhǔn)；遺傳算法

多模式路徑規(guī)劃旨在為出行者提供涉及多種交通模式的出行路徑方案。與單一模式路徑規(guī)劃相比，多模式網(wǎng)絡(luò)環(huán)境下的路徑規(guī)劃更加復(fù)雜，需要考慮多種交通模式的組合方式與換乘耗費(fèi)等問(wèn)題。另一方面，傳統(tǒng)的單一標(biāo)準(zhǔn)路徑查詢，如最短距離、理想最少時(shí)間路徑查詢等，已經(jīng)不能滿足現(xiàn)代城市多模式立體交通體系下公眾出行的現(xiàn)實(shí)需求。從出行者的角度來(lái)看，滿足多種標(biāo)準(zhǔn)的出行路徑方案更適應(yīng)個(gè)體的特殊需要；從出行服務(wù)提供者的角度來(lái)看，在多模式交通環(huán)境中，充分考慮多種個(gè)性化需求、量身定做的多標(biāo)準(zhǔn)出行路徑規(guī)劃服務(wù)，更能夠適應(yīng)市場(chǎng)的需求。

1 多標(biāo)準(zhǔn)路徑問(wèn)題

多標(biāo)準(zhǔn)（或多目標(biāo)）路徑規(guī)劃是同時(shí)考慮多于一種評(píng)價(jià)標(biāo)準(zhǔn)的路徑求解問(wèn)題。其本質(zhì)在于，在大多數(shù)情況下，某一標(biāo)準(zhǔn)（或目標(biāo)）性能的提高可能引起其他標(biāo)準(zhǔn)（或目標(biāo)）性能的降低。同時(shí)使多個(gè)目標(biāo)均達(dá)到最優(yōu)幾乎是不可能的，因此只能在各目標(biāo)之間進(jìn)行協(xié)調(diào)權(quán)衡和折衷處理，使所有目標(biāo)函數(shù)盡可能達(dá)到最優(yōu)。多標(biāo)準(zhǔn)路徑問(wèn)題的結(jié)果不再是單一解，而是一個(gè)Pareto最優(yōu)解集。解集中的解相互間不存在優(yōu)劣關(guān)系。多標(biāo)準(zhǔn)路徑規(guī)劃是具有NP特性的多標(biāo)準(zhǔn)決策問(wèn)題，通常有兩種解決思路，即多標(biāo)準(zhǔn)轉(zhuǎn)化為單標(biāo)準(zhǔn)路徑算法和單標(biāo)準(zhǔn)改造為多標(biāo)準(zhǔn)路徑算法。

多標(biāo)準(zhǔn)轉(zhuǎn)化為單標(biāo)準(zhǔn)路徑算法通過(guò)一定策略將多標(biāo)準(zhǔn)問(wèn)題轉(zhuǎn)化為單標(biāo)準(zhǔn)標(biāo)量值，從而應(yīng)用單標(biāo)準(zhǔn)路徑算法進(jìn)行計(jì)算。又可分為兩類：目標(biāo)加權(quán)法和策略約束法。前者采用線性加權(quán)求和等方法，很難確定科學(xué)合理的權(quán)重值［1-2］，并且不能在非凸的均勻曲面上得到所有最優(yōu)解［3］。后者將k個(gè)標(biāo)準(zhǔn)中的k－1個(gè)標(biāo)準(zhǔn)轉(zhuǎn)換為約束條件，其結(jié)果主要依賴于被確定為目標(biāo)函數(shù)的單標(biāo)準(zhǔn)，可能高估了某一標(biāo)準(zhǔn)的作用，并且可能導(dǎo)致該單標(biāo)準(zhǔn)問(wèn)題無(wú)解［4］。文獻(xiàn)［5］從預(yù)先指定搜索空間的角度進(jìn)行多標(biāo)準(zhǔn)研究，本質(zhì)上還是要預(yù)先確定各標(biāo)準(zhǔn)的權(quán)重。

單標(biāo)準(zhǔn)改造為多標(biāo)準(zhǔn)路徑算法可分為多標(biāo)準(zhǔn)標(biāo)號(hào)算法和進(jìn)化算法。多標(biāo)準(zhǔn)標(biāo)號(hào)算法將圖模型中的節(jié)點(diǎn)或邊的標(biāo)號(hào)由一維擴(kuò)展為多維，多維之間相互獨(dú)立。文獻(xiàn)［6］基于文獻(xiàn)［7］的雙標(biāo)準(zhǔn)標(biāo)號(hào)算法，提出了多標(biāo)號(hào)算法，建立了一種求解連續(xù)線性多目標(biāo)問(wèn)題的方法。此后，出現(xiàn)了多種標(biāo)號(hào)算法求解該問(wèn)題［8-10］。標(biāo)號(hào)算法通過(guò)比較每一步當(dāng)前的最優(yōu)結(jié)果，理論上可以找到最優(yōu)結(jié)果（如果有解），但是，該方法時(shí)間復(fù)雜度高，對(duì)于大規(guī)模真實(shí)網(wǎng)絡(luò)不具可行性。在多模式環(huán)境下，多種出行標(biāo)準(zhǔn)下會(huì)產(chǎn)生不同的交通模式組合情況，使得問(wèn)題變得更加復(fù)雜。

遺傳算法（genetic algorithm，GA）是一類借鑒生物界的進(jìn)化規(guī)律演化而來(lái)的智能優(yōu)化方法，能夠有效避免不同標(biāo)準(zhǔn)權(quán)重人為分配問(wèn)題；由于它固有的并行性，進(jìn)化過(guò)程同時(shí)處理一代種群（解集），結(jié)果不限于單一解，非常適合求解復(fù)雜的多目標(biāo)問(wèn)題。此外，由不同模式下的路徑段組合而成的多模式路徑與遺傳學(xué)中由遺傳基因構(gòu)成的染色體具有結(jié)構(gòu)上的相似性，因此，可以考慮采用遺傳算法解決該問(wèn)題。

GA在路徑規(guī)劃中已有應(yīng)用。在路徑編碼研究方面，編碼方式的改進(jìn)可以提高搜索效率，如基于優(yōu)先權(quán)的路徑編碼方法［11］和基因值順序表示該基因連接的后續(xù)基因位置［12］的編碼方法。但是，這兩種定長(zhǎng)染色體編碼方法的空間復(fù)雜度較高，對(duì)大規(guī)模網(wǎng)絡(luò)缺乏可行性。一些學(xué)者提出了利用遺傳算法解決單標(biāo)準(zhǔn)路徑問(wèn)題的方法，如TSP［13］、k則最短路徑［14］、VRP［15］、最短路徑優(yōu)化［16］、公交線路優(yōu)化［17］等。也有部分學(xué)者研究了單一交通模式下的多標(biāo)準(zhǔn)路徑問(wèn)題，包括針對(duì)開(kāi)放空間的三維環(huán)境路徑規(guī)劃［18］和針對(duì)網(wǎng)絡(luò)受限空間的路徑規(guī)劃［3，19］等。關(guān)于多模式環(huán)境下的多標(biāo)準(zhǔn)路徑規(guī)劃問(wèn)題，文獻(xiàn)［20—21］提出了一種適應(yīng)換乘網(wǎng)絡(luò)的遺傳算法。但該方法限于公共交通或步行換乘網(wǎng)絡(luò)，無(wú)法支持具有復(fù)雜結(jié)構(gòu)的公交模型，并且存在染色體編碼冗余。

本文利用GA求解多標(biāo)準(zhǔn)問(wèn)題的優(yōu)勢(shì)，結(jié)合多模式路徑的特點(diǎn)，提出一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法。

2 多模式多標(biāo)準(zhǔn)路徑方法

2.1 染色體編碼與解碼

染色體編碼，是將待求解的問(wèn)題由表現(xiàn)型空間轉(zhuǎn)換到基因型，以便于進(jìn)行遺傳操作。相對(duì)而言，染色體解碼就是建立從基因型空間到表現(xiàn)的映射。針對(duì)本文研究的道路網(wǎng)絡(luò)而言，一條路徑用所經(jīng)過(guò)的道路ID進(jìn)行個(gè)體編碼可以減小數(shù)據(jù)冗余、實(shí)現(xiàn)精確導(dǎo)航并且易于解碼。

多模式路徑要求個(gè)體編碼能夠體現(xiàn)多種交通模式組合，同時(shí)又不產(chǎn)生過(guò)多數(shù)據(jù)冗余；遺傳算法要求個(gè)體編碼易于遺傳算子操作。因此，定義多模式個(gè)體（染色體）編碼為：采用帶模式標(biāo)識(shí)的不定長(zhǎng)表現(xiàn)型編碼，由模式標(biāo)記區(qū)與ID編碼區(qū)組成（如圖1）。模式標(biāo)記可以采用任意類型表示，僅用作區(qū)分不同模式，表示其后至下一模式標(biāo)記前的基因段屬于同一種模式。在圖1中，設(shè)－1、－2、－3、－4分別表示駕車、公交、地鐵、步行等模式，則－1后，－2前的基因段為駕車模式經(jīng)過(guò)的路段ID。

圖1 多模式路徑染色體編碼示意圖Fig．1 Chromosome encoding for multi-modal routes

2.2 適應(yīng)性評(píng)價(jià)

解的適應(yīng)性評(píng)價(jià)在遺傳算法中扮演環(huán)境的角色，根據(jù)個(gè)體的適應(yīng)值進(jìn)行評(píng)定［22］。多標(biāo)準(zhǔn)問(wèn)題中，目標(biāo)函數(shù)可以表達(dá)為

式中，n為目標(biāo)個(gè)數(shù)；fi（x）為某單一目標(biāo)下的目標(biāo)函數(shù)；gi（x）為限制條件。

具體在多模式多標(biāo)準(zhǔn)路徑問(wèn)題上，表現(xiàn)為在不同評(píng)價(jià)標(biāo)準(zhǔn)下的路徑的計(jì)算值，有

式中，n為目標(biāo)個(gè)數(shù)；m為模式個(gè)數(shù)；上標(biāo)k表示不同模式；xkij表示在某一模式中邊（i，j）是否在路徑中；ckij為邊（i，j）的耗費(fèi)，在不同評(píng)價(jià)標(biāo)準(zhǔn)下代表不同的含義。如最短路徑標(biāo)準(zhǔn)下cij表示長(zhǎng)度，最短時(shí)間標(biāo)準(zhǔn)下cij表示時(shí)間等。由此，公式（1）的計(jì)算結(jié)果是一個(gè)p-維向量，每一維度代表一種標(biāo)準(zhǔn)下的路徑評(píng)價(jià)值。因此，根據(jù)p-維向量進(jìn)行比較得到的結(jié)果并非單一解，而是一個(gè)解集，即Pareto優(yōu)化解集。向量間的比較采用“支配”概念進(jìn)行描述。

定義：若解x0支配解x1（記為x0?x1），當(dāng)且僅當(dāng)

對(duì)所有評(píng)價(jià)標(biāo)準(zhǔn)均成立。

在向量比較的基礎(chǔ)上，對(duì)解集中的解進(jìn)行Pareto最優(yōu)排序，并分配適應(yīng)值。可以采用多種排序方法，如Fonseca等的Pareto排序方法［23］，個(gè)體的排序數(shù)等于當(dāng)前種群中支配他的個(gè)體的數(shù)目加1，所有非劣個(gè)體排序值為1，并以此作為個(gè)體適應(yīng)值。

2.3 進(jìn)化算子

由于傳統(tǒng)單模式路徑問(wèn)題中的遺傳算子針對(duì)的個(gè)體編碼是同質(zhì)的，各個(gè)位置的基因性質(zhì)對(duì)等，可以進(jìn)行任意交叉及變異。但是在多模式路徑中，不同模式間的基因段之間是異質(zhì)的，也就是說(shuō)，不同交通模式中的路徑性質(zhì)不對(duì)等，不可實(shí)現(xiàn)任意點(diǎn)任意模式的換乘。因此，要重新定義滿足多模式路徑特征的遺傳算子。遺傳算子通過(guò)對(duì)基因進(jìn)行交叉、變異，生成新個(gè)體，即得到新路徑。因此，定義crossover與mutation算子分別為模式內(nèi)交叉與變異算子，即只在相同模式內(nèi)進(jìn)行遺傳算子操作。定義hypercrossover與hypermutation算子分別為模式間交叉與變異算子，即只在不同模式間進(jìn)行遺傳算子操作。

模式內(nèi)交叉與變異算子的特點(diǎn)是，不引入新的交通模式，即最大化控制換乘次數(shù)的增加。模式間交叉與變異算子的特點(diǎn)是，算子操作會(huì)引起交通模式換乘次數(shù)上的增加，因此在具體操作中要采取一定措施控制其他標(biāo)準(zhǔn)的優(yōu)化。

模式內(nèi)交叉算子運(yùn)算采用單點(diǎn)交叉策略（圖2），并進(jìn)行環(huán)路檢驗(yàn)與修復(fù)。模式間交叉算子運(yùn)算的基本思想是：首先探測(cè)每個(gè)個(gè)體的模式標(biāo)記，并組合成交叉組合對(duì)，隨機(jī)選擇一個(gè)組合；然后，探測(cè)所有可能的交叉基因?qū)?，隨機(jī)選擇一對(duì)組合進(jìn)行單點(diǎn)交叉運(yùn)算；最后，進(jìn)行環(huán)路檢驗(yàn)與換乘縫隙探測(cè)。模式間交叉算子運(yùn)算后有可能產(chǎn)生連接縫隙，即換乘縫隙（如公交換乘地鐵），通常需要借助其他交通模式（如步行等）進(jìn)行連接，如圖3中采用模式－4。

圖2 模式內(nèi)交叉算子Fig．2 Intra-modal crossover operator

圖3 模式間交叉算子Fig．3 Inter-modal crossover operator

模式內(nèi)變異算子運(yùn)算（圖4）通過(guò)探測(cè)可變基因?qū)?，在該模式下產(chǎn)生新的基因段序列代替原序列中可變基因間的基因段實(shí)現(xiàn)變異。模式間變異算子運(yùn)算（圖5）采用定向變異策略，加速優(yōu)秀個(gè)體產(chǎn)生。其基本思想是首先探測(cè)模式標(biāo)記，根據(jù)定向變異概率確定變異目標(biāo)模式；然后，在該目標(biāo)模式下生成新基因段代替原基因段；最后，合并非必要的連續(xù)模式內(nèi)換乘并進(jìn)行環(huán)路檢驗(yàn)與換乘縫隙探測(cè)。模式間變異算子產(chǎn)生的新個(gè)體同樣可能存在換乘縫隙，可借助其他模式進(jìn)行無(wú)縫連接。

圖4 模式內(nèi)變異算子Fig．4 Intra-modal mutation operator

圖5 模式間變異算子Fig．5 Inter-modal mutation operator

選擇算子運(yùn)算根據(jù)定義種群大小G和新種群當(dāng)前個(gè)體數(shù)G′確定選擇的優(yōu)秀個(gè)體數(shù)量X＝G－G′。G′由交叉與變異算子生成的新個(gè)體組成，優(yōu)秀個(gè)體的選擇方法為：統(tǒng)計(jì)評(píng)價(jià)值為1的非重復(fù)個(gè)體數(shù)目M，若X≤M，則隨機(jī)選擇當(dāng)前評(píng)價(jià)值的非重復(fù)個(gè)體進(jìn)入下一代種群；若X＞M，則當(dāng)前非重復(fù)最優(yōu)個(gè)體進(jìn)入下一代，然后按照二元錦標(biāo)賽方法確定優(yōu)秀個(gè)體進(jìn)入下一代種群，直至達(dá)到選擇數(shù)目。

2.4 計(jì)算流程

本文提出的多模式多標(biāo)準(zhǔn)遺傳算法流程如圖6所示。

圖6 多模式多標(biāo)準(zhǔn)遺傳算法流程Fig．6 GA based multi-modal multi-criteria routing

出行需求參數(shù)包括起點(diǎn)、終點(diǎn)、出行模式、出行標(biāo)準(zhǔn)與出行時(shí)間等。

需要指出的是，該算法流程采用滿足最大進(jìn)化代數(shù)作為進(jìn)化停止標(biāo)志，在實(shí)際應(yīng)用中，也可以以兩代之間適應(yīng)度之差小于某個(gè)固定值，或者以滿足一定更新數(shù)變化為0的連續(xù)進(jìn)化代數(shù)作為結(jié)束條件。

3 試驗(yàn)分析與討論

本文在多模式交通網(wǎng)絡(luò)邏輯一體化模型［24］的基礎(chǔ)上，以北京五環(huán)內(nèi)交通網(wǎng)絡(luò)為試驗(yàn)對(duì)象實(shí)現(xiàn)了該方法。試驗(yàn)數(shù)據(jù)涉及步行、自行車網(wǎng)絡(luò)（包含步行段52 509條）、行車網(wǎng)絡(luò)（包含車行道段54 007條）、公交網(wǎng)絡(luò)（公交線186條，站點(diǎn)4160個(gè)）及地鐵網(wǎng)絡(luò)（軌道段124條，站點(diǎn)113個(gè)）等出行模式。評(píng)價(jià)標(biāo)準(zhǔn)涉及最短時(shí)間、最小費(fèi)用、最少換乘次數(shù)。針對(duì)各種交通模式，在不同評(píng)價(jià)標(biāo)準(zhǔn)下構(gòu)建了相應(yīng)的計(jì)算模型［24］，其中，時(shí)間標(biāo)準(zhǔn)計(jì)算基于浮動(dòng)車系統(tǒng)獲取的道路路況，并考慮各種時(shí)間耗費(fèi)，如路口等待時(shí)間、換乘耗時(shí)等；費(fèi)用標(biāo)準(zhǔn)計(jì)算采用北京市公交、地鐵、出租車通用計(jì)費(fèi)標(biāo)準(zhǔn)；換乘次數(shù)標(biāo)準(zhǔn)中，短距離步行連接不計(jì)入總換乘次數(shù)中。

試驗(yàn)中隨機(jī)選取了839個(gè)點(diǎn)作為起止點(diǎn)。由于本研究中所采用數(shù)據(jù)在各種單一出行模式下ID編碼非負(fù)唯一，因此，可以采用負(fù)值區(qū)分各種模式（如圖1中－1、－2、－3、－4）。在ID編碼中，既可以采用弧段ID也可以采用節(jié)點(diǎn)ID，本研究中對(duì)行車網(wǎng)絡(luò)和步行網(wǎng)絡(luò)采用弧段ID，對(duì)公交網(wǎng)絡(luò)和地鐵網(wǎng)絡(luò)采用節(jié)點(diǎn)ID。

在設(shè)定起止點(diǎn)和遺傳算法參數(shù)后，首先，在各單模式環(huán)境下，分別在起止點(diǎn)一定范圍內(nèi)，生成一定數(shù)量的初始個(gè)體，此時(shí)生成的個(gè)體可能不完全覆蓋起止點(diǎn)路徑（如：地鐵模式不能連接任意兩個(gè)起止點(diǎn)），稱之為不完全個(gè)體；對(duì)該群體進(jìn)行模式間交叉算子運(yùn)算，補(bǔ)充不完全個(gè)體為完全個(gè)體（覆蓋起止點(diǎn)的路徑）；然后按照計(jì)算流程進(jìn)行計(jì)算，直至滿足終止條件，本試驗(yàn)中采用固定最大進(jìn)化代數(shù)。對(duì)于個(gè)體的生成算法，可以采用成熟的單標(biāo)準(zhǔn)路徑規(guī)劃算法。

業(yè)界對(duì)遺傳初始種群個(gè)數(shù)對(duì)算法的影響存在一定爭(zhēng)議［25］，但是普遍認(rèn)可其對(duì)算法的空間復(fù)雜度的影響；對(duì)進(jìn)化參數(shù)迄今沒(méi)有公認(rèn)的確定方法，但存在一些普遍的指導(dǎo)思想，對(duì)交叉和變異算子在進(jìn)化前期與后期的作用有相應(yīng)研究；針對(duì)不同的目的，參數(shù)設(shè)置也會(huì)出現(xiàn)不同。

針對(duì)本文提出的方法，初始個(gè)體在各種交通模式中均有體現(xiàn)，一方面可以增加進(jìn)化開(kāi)始階段的種群多樣性，確保各種交通模式參與到進(jìn)化過(guò)程中；另一方面，不定長(zhǎng)的編碼方式在多模式交通環(huán)境能夠有效控制空間耗費(fèi)。進(jìn)化代數(shù)是給定的算法結(jié)束標(biāo)志，其合理取值通常需要通過(guò)試驗(yàn)獲取。交叉、變異算子都是為了產(chǎn)生新個(gè)體，其運(yùn)算概率直接影響路徑結(jié)果。由于本方法中變異算子突破了傳統(tǒng)遺傳算法中的含義，作為一種有效的模式轉(zhuǎn)換手段，變異與交叉重要程度相近；另外，由于模式間變異一定會(huì)產(chǎn)生換乘次數(shù)的增加（采用定向變異策略可消除部分影響），因此，其變異概率可略小于交叉概率。選擇算子保留一定數(shù)量的優(yōu)秀個(gè)體直接進(jìn)入下一代，過(guò)大會(huì)導(dǎo)致過(guò)早陷入局部解；過(guò)小，體現(xiàn)不出算子意義。通常情況下保留10%～20%的精英個(gè)體。

為了確定進(jìn)化參數(shù)的影響，分別采用了5種參數(shù)分配案例進(jìn)行試驗(yàn)，各案例參數(shù)取值見(jiàn)表1，種群大小設(shè)為100，進(jìn)化代數(shù)4000。定義從父代到子代產(chǎn)生新最優(yōu)個(gè)體的數(shù)目為更新數(shù)。更新數(shù)表明遺傳進(jìn)化是否有新最優(yōu)個(gè)體產(chǎn)生。如果更新數(shù)為0，最優(yōu)個(gè)體表現(xiàn)值未發(fā)生變化，若持續(xù)多代均保持該數(shù)值，則認(rèn)為進(jìn)化趨于穩(wěn)定；若不為0，則表示產(chǎn)生新的最優(yōu)個(gè)體。對(duì)位于試驗(yàn)區(qū)對(duì)角域內(nèi)的直線距離10 km以上的某一隨機(jī)O-D對(duì)進(jìn)行遺傳算法運(yùn)算，得到更新數(shù)變化圖（如圖7）。

表1 試驗(yàn)案例參數(shù)Tab.1 Experiment scenario parameters

圖7中，橫軸為進(jìn)化代數(shù)（每20代一統(tǒng)計(jì)），縱軸為更新數(shù)目。從進(jìn)化更新數(shù)變化可以看出，案例1、2、3進(jìn)化趨于穩(wěn)定，案例4、5仍在進(jìn)化。進(jìn)一步對(duì)同一O-D的4000代進(jìn)化后的結(jié)果進(jìn)行比較發(fā)現(xiàn)，在案例1得到的5個(gè)最優(yōu)個(gè)體中有3個(gè)個(gè)體在所有最優(yōu)結(jié)果個(gè)體中占優(yōu)；案例4的4個(gè)最優(yōu)個(gè)體中有兩個(gè)在所有個(gè)體中占優(yōu)；其他案例結(jié)果均未得到最優(yōu)結(jié)果。在對(duì)試驗(yàn)區(qū)內(nèi)其他隨機(jī)O-D進(jìn)行的試驗(yàn)中發(fā)現(xiàn)，不同O-D對(duì)于概率參數(shù)的敏感程度不同，除案例2達(dá)到穩(wěn)定的代數(shù)較早（1500代以內(nèi)）外，其他案例并無(wú)明確先后順序，但對(duì)其結(jié)果進(jìn)行比較發(fā)現(xiàn)，案例1和案例4的參數(shù)得到的結(jié)果相對(duì)而言更易于在對(duì)比結(jié)果中取得最優(yōu)。

以上試驗(yàn)結(jié)果基本上驗(yàn)證了先前的分析，因此，對(duì)于本文提出的方法，交叉概率等于或略高于變異概率時(shí)容易獲得較好解。對(duì)于進(jìn)化代數(shù)的確定，可以在設(shè)置最大進(jìn)化代數(shù)基礎(chǔ)上，通過(guò)本方法中的更新數(shù)以一定代數(shù)不變化作為結(jié)束標(biāo)志。根據(jù)該算法的設(shè)計(jì)，進(jìn)化過(guò)程中每個(gè)個(gè)體都是完整的一個(gè)路徑結(jié)果，因此，無(wú)論采用哪種概率方案，均可得到可用解。

圖7 更新數(shù)變化對(duì)比Fig．7 Scenarios with new generated number

按照案例1的參數(shù)進(jìn)行計(jì)算，經(jīng)過(guò)4000代進(jìn)化達(dá)到穩(wěn)定后結(jié)果見(jiàn)表2。

表2所示為達(dá)到最大進(jìn)化代數(shù)后的Pareto最優(yōu)解統(tǒng)計(jì)結(jié)果。其中，T、W、B與S分別代表出租車、步行、公交與地鐵模式。該結(jié)果集涉及單模式路徑結(jié)果，如出租車、步行、自行車等；傳統(tǒng)換乘模式組合，如公交換乘組合等；對(duì)于時(shí)間耗費(fèi)較少的組合，顯示了較強(qiáng)的實(shí)用性方案，如出租車-地鐵-出租車、地鐵-出租車、地鐵-公交等；對(duì)于地鐵-出租車-公交模式在預(yù)算控制和時(shí)間控制的平衡上表現(xiàn)較好。從各標(biāo)準(zhǔn)的滿足上，能夠體現(xiàn)不同需求，用戶可根據(jù)自身需要選擇合適的路徑方案出行。部分結(jié)果可視化如圖8所示，8（a）為地鐵換乘出租帶有步行連接，8（b）為地鐵換乘公交帶有步行連接，8（c）為公交換乘帶有步行連接。

表2 試驗(yàn)結(jié)果統(tǒng)計(jì)Tab.2 Experiment results

圖8 結(jié)果顯示Fig．8 Results visualizations

在實(shí)用性方面，無(wú)論是在多模式組合情況，還是各種特殊評(píng)價(jià)標(biāo)準(zhǔn)權(quán)衡要求的情況下，該方法均能給出較為實(shí)用的出行方案，為出行信息服務(wù)從大眾服務(wù)到個(gè)性化服務(wù)提供借鑒，并且適用于各種路徑生成算法和方法改造。在效率方面，由于遺傳算法具有很強(qiáng)的并行性，可以同時(shí)處理一個(gè)種群，即多個(gè)個(gè)體，可以采用諸如并行計(jì)算、分布式處理等方式提高效率。除了采用算法自身加速改造，如算法終止條件、路徑生成加速算法、加速進(jìn)化策略等，還可以采用并行遺傳算法（parallel GA）提高效率。通過(guò)將串行算法并行化，采用一定的信息交互模型，如主從式模型、粗粒度模型、細(xì)粒度模型和混合模型等，實(shí)現(xiàn)本文方法的并行遺傳算法改造，這在互聯(lián)網(wǎng)地圖服務(wù)大用戶并發(fā)、分布式數(shù)據(jù)存儲(chǔ)的情況下尤其適用。

4 結(jié) 論

本文提出了一種適宜多模式交通網(wǎng)絡(luò)環(huán)境下的多標(biāo)準(zhǔn)路徑搜索方法。該方法結(jié)合遺傳算法與最優(yōu)化理論，采用不定長(zhǎng)表現(xiàn)型基因編碼，使用模式標(biāo)識(shí)表示不同模式下的路徑。為了適應(yīng)多模式交通網(wǎng)絡(luò)環(huán)境，定義模式內(nèi)交叉與變異算子和模式間交叉與變異算子，使遺傳進(jìn)化能夠同時(shí)兼顧模式內(nèi)與模式間不同的進(jìn)化方向。采用多維權(quán)值向量表示多種評(píng)價(jià)標(biāo)準(zhǔn)，涉及時(shí)間最短、換乘最少和費(fèi)用最低等標(biāo)準(zhǔn)。通過(guò)應(yīng)用Pareto排序方法進(jìn)行適應(yīng)度值的分配。該方法能夠有效避免人為設(shè)置權(quán)重值導(dǎo)致的多標(biāo)準(zhǔn)權(quán)衡偏差。通過(guò)對(duì)比試驗(yàn)確定了遺傳算法進(jìn)化參數(shù)的分配方案。試驗(yàn)結(jié)果顯示，該方法能夠?qū)崿F(xiàn)更為多樣的模式組合方式，同時(shí)兼顧不同程度的用戶需求，為出行者提供滿足個(gè)性化需求的、優(yōu)化可替換的、無(wú)縫全程無(wú)障礙出行服務(wù)。在后續(xù)的研究中，需要進(jìn)一步考慮該方法的效率改進(jìn)方法以及實(shí)時(shí)路況對(duì)路徑計(jì)算的影響，以提供更加符合用戶出行需求的出行服務(wù)。

［1］ MOONEY P，WINSTANLEY A．An Evolutionary Algorithm for Multicriteria Path Optimization Problems［J］．International Journal of Geographical Information Science，2006，20（4）：401-423．

［2］ PEREIRA C M N A．Evolutionary Multicriteria Optimization in Core Designs：Basic Investigations and Case Study［J］．Annals of Nuclear Energy，2004，31（11）：1251-1264．

［3］ LI R，LEUNG Y．Multi-Objective Route Planning for Dangerous Goods Using Compromise Programming［J］．Journal of Geographical Systems，2011，13（3）：249-271．

［4］ CHAKRABORTY B．GA-based Multiple Route Selection for Car Navigation［M］．Berlin：Springer-Verlag，2004：76-83．

［5］ HUANG B，F(xiàn)ERY P，XUE L，et al．Seeking the Pareto Front for Multiobjective Spatial Optimization Problems［J］．International Journal of Geographical Information Science，2008，22（5）：507-526．

［6］ MARTINS E Q V．On a Multicriteria Shortest Path Problem［J］．European Journal of Operational Research，1984，16（2）：236-245．

［7］ HANSEN P．Bicriterion Path Problems［C］∥Multiple Criteria Decision Making：Theory and Application．［S．l．］：Springer-Verlag，1980：109．

［8］ BRUMBAUGH S J，SHIER D．An Empirical Investigation of Some Bicriterion Shortest Path Algorithms［J］．European Journal of Operational Research，1989，43（2）：216-224．

［9］ SKRIVER A J V，ANDERSEN K A．A Label Correcting Approach for Solving Bicriterion Shortest-path Problems［J］．Computers and Operations Research，2000，27（6）：507-524．

［10］ LOZANO A，STORCHI G．Shortest Viable Path Algorithm in Multimodal Networks［J］．Transportation Research Part A：Policy and Practice，2001，35（3）：225-241．

［11］ GEN M，CHENG R，WANG D．Genetic Algorithms for Solving Shortest Path Problems［C］∥Proceedings of IEEE International Conference on Evolutionary Computation．Indianapolis：IEEE Press，1997：401-406．

［12］ INAGAKI J，HASEYAMA M，KITAJIMA H．A Genetic Algorithm for Determining Multiple Routes and Its Applications［C］∥Proceedings of the 1999 IEEE International Symposium on Circuits and Systems．［S．l．］：IEEE，1999：137-140．

［13］ SUN Huiwen．A Genetic Algorithm for Travelling Salesman Problems［J］．Journal of Southwest Jiaotong University，1996，31（5）：550-554．（孫惠文．遺傳算法求解旅行商問(wèn)題［J］．西南交通大學(xué)學(xué)報(bào)，1996，31（5）：550-554．）

［14］ MA Xuan．A Genetic Algorithm for k Optimal Paths Problem［J］．Computer Engineering and Applications，2006（12）：100-101．（馬炫．求解k條最優(yōu)路徑問(wèn)題的遺傳算法［J］．計(jì)算機(jī)工程與應(yīng)用，2006（12）：100-101．）

［15］ JIANG Bo．Study of Vehicle Routing Problem with Time Windows Based on Genetic Algorithm［D］．Beijing：Beijing Jiaotong University，2010．（蔣波．基于遺傳算法的帶時(shí)間窗車輛路徑優(yōu)化問(wèn)題研究［D］．北京：北京交通大學(xué)，2010．）

［16］ LI Qing，ZHANG Wei，YIN Yixin，et al．An Improved Genetic Algorithm for Optimal Path Planning［J］．Information and Control，2006，35（4）：444-447．（李擎，張偉，尹怡欣，等．一種用于最優(yōu)路徑規(guī)劃的改進(jìn)遺傳算法［J］．信息與控制，2006，35（4）：444-447．）

［17］ HUANG Z D，LIU X J，HUANG C C，et al．A GIS-based Framework for Bus Network Optimization Using Genetic Algorithm［J］．Annals of GIS，2010，16（3）：185-194．

［18］ LIU Xuhong，ZHANG Guoying，LIU Yushu，et al．Path Planning Based on Multi-objective Genetic Algorithm［J］．Transactions of Beijing Institute of Technology，2005，25（7）：613-616．（劉旭紅，張國(guó)英，劉玉樹(shù)，等．基于多目標(biāo)遺傳算法的路徑規(guī)劃［J］．北京理工大學(xué)學(xué)報(bào)，2005，25（7）：613-616．）

［19］ ABDELGAWAD H，ABDULHAI B，WAHBA M．Multiobjective Optimization for Multimodal Evacuation［J］．Transportation Research Record：Journal of the Transportation Research Board，2010，2196：21-33．

［20］ ABBASPOUR R A，SAMADZADEGAN F．A Solution for Time-dependent Multimodal Shortest Path Problem［J］．Journal of Applied Sciences，2009，9（21）：3804-3812．

［21］ ABBASPOUR R A，SAMADZADEGAN F．An Evolutionary Solution for Multimodal Shortest Path Problem in Metropolises［J］．Computer Science and Information Systems，2010，7（4）：789-811．

［22］ MICHALEWICZ Z．Genetic Algorithms＋Data Structures＝Evolution Programs［M］．Berlin：Springer-Verlag，1996．

［23］ FONSECA C M，F(xiàn)LEMING P J．Genetic Algorithms for Multiobjective Optimization：Formulation，Discussion and Generalization［C］∥Proceedings of the Fifth International Conference on Genetic Algorithms，University of Illinois at Urbana-Champaign．San Mateo：［s．n．］，1993：416-423．

［24］ YU Haicong，LU Feng．A Multi-criteria Route Planning Approach Considering Walking Guidance［J］．Journal of Image and Graphics，2010，15（4）：677-683．（于海璁，陸鋒．一種顧及步行引導(dǎo)的多標(biāo)準(zhǔn)路徑規(guī)劃方法［J］．中國(guó)圖象圖形學(xué)報(bào)，2010，15（4）：677-683．）

［25］ ZITZLER E，DEB K，THIELE L．Comparison of Multiobjective Evolutionary Algorithms：Empirical Results［J］．Evolutionary Computation，2000，8（2）：173-195．

（責(zé)任編輯：宋啟凡）

A Multi-modal Multi-criteria Route Planning Method Based on Genetic Algorithm

YU Haicong，LU Feng
lnstitute of Geographic Sciences and Natural Resources Research，Chinese Academy of Sciences，Beijing 100101，China

How to provide multi-criteria routing service has been a hot topic for advanced travel information systems．Basically，the multi-criteria routing is a complex NP problem，and involves different transportation modes．Arbitrary weight assignment for various criteria will remarkably affect the routing results．Thus，the challenge is to determine the appropriate relationship among multiple criteria．A multi-criteria route planning method for multi-modal transportation system was proposed．lt took the advantage of genetic algorithm for solving optimization problems and extended it to multi-modal routing environment．Various length of chromosome with mode tags was used to encode individuals．Both intra-and inter-mode evolution operators were defined to guarantee the diversity．Pareto ranking method with a p-dimensional vector representing multiple criteria was used for fitness calculation．The presented method avoids subjective weight setting procedure，and can obtain various modes combination results for route planning to meet personalized requirements．

route planning；multi-modal；multi-criteria；genetic algorithms

YU Haicong（1984—），male，PhD，interested in multi-modal transportation network，route planning，multi-creteria optimization，and GlS for transportation．

LU Feng

P208

A

1001-1595（2014）01-0089-08

國(guó)家863計(jì)劃（2012AA12A211）；國(guó)家自然科學(xué)基金（41271408）

2012-10-31

于海璁（1984—），男，博士，主要從事多模式交通網(wǎng)絡(luò)、路徑規(guī)劃、多標(biāo)準(zhǔn)優(yōu)化、交通地理信息系統(tǒng)方向等研究。

E-mail：yuhc＠lreis．a(chǎn)c．cn

陸鋒

E-mail：luf＠lreis．a(chǎn)c．cn

YU Haicong，LU Feng．A Multi-modal Multi-criteria Route Planning Method Based on Genetic Algorithm［J］．Acta Geodaetica et Cartographica Sinica，2014，43（1）：89-96．（于海璁，陸鋒．一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法［J］．測(cè)繪學(xué)報(bào)，2014，43（1）：89-96．）

10．13485／j．cnki．11-2089．2014．0013

修回日期：2013-06-26