校車路徑優(yōu)化模型及算法研究

郝 忠 娜

( 南京交通職業(yè)技術(shù)學(xué)院 運(yùn)輸管理系，江蘇 南京 211188)

校車路徑優(yōu)化模型及算法研究

郝 忠 娜

( 南京交通職業(yè)技術(shù)學(xué)院 運(yùn)輸管理系，江蘇 南京 211188)

以校車站點(diǎn)選擇、學(xué)生群歸屬站點(diǎn)的劃分以及車輛路徑安排為研究對象，重點(diǎn)考慮了學(xué)生在車上的最大乘車時間、學(xué)生步行到候車站點(diǎn)的最大步行時間等約束條件，以車輛行程時間成本、學(xué)生乘車時間成本以及學(xué)生步行時間成本最小為目標(biāo)建立數(shù)學(xué)規(guī)劃模型。給出了解決這類問題的改進(jìn)遺傳算法，該算法通過啟發(fā)式產(chǎn)生初始種群的優(yōu)良個體，并針對模型特點(diǎn)設(shè)計帶啟發(fā)知識的遺傳算子，提高尋優(yōu)效率。實(shí)例分析表明，該方法可行，并且有比較顯著的效果，能夠有效地解決大規(guī)模的校車路徑優(yōu)化問題。

交通運(yùn)輸工程；校車路徑；優(yōu)化；數(shù)學(xué)規(guī)劃模型；改進(jìn)遺傳算法

0 引 言

校車路徑問題(School Bus Routing Problem, SBRP)主要包括站點(diǎn)選擇、路徑生成、校車時刻表的制定等問題[1]。根據(jù)校車派車車輛數(shù)，可以分為單校車路徑問題和多校車路徑問題。筆者針對單校車接學(xué)生到校的問題進(jìn)行研究，其它更多問題可在此基礎(chǔ)上進(jìn)行擴(kuò)展延伸。

校車路徑問題是NP完全問題，對于小規(guī)模的應(yīng)用問題，可以采用精確算法來解決。J. Riera-Ledesma等[2]針對校車路徑問題，建立了集劃分模型，并設(shè)計了BCP(Branch-and-Cut-and-Price)精確算法對模型進(jìn)行求解。而對于大規(guī)模的問題，精確算法難以在合理的時間內(nèi)得到最優(yōu)解，因此，人們更多地研究采用各種智能算法來快速獲取問題的滿意解。A. Bock等[3]考慮學(xué)生從家到學(xué)校的乘車時間不超過設(shè)定值以及車輛容量限制的約束建立模型，并把學(xué)生和學(xué)校置于固定樹的定點(diǎn)用多項(xiàng)式近似算法進(jìn)行求解。吳耀華等[4]和張麗艷等[5]提出了用改進(jìn)粒子群算法求解車輛路徑問題。P. Díaz等[6]將蟻群算法與大鄰域搜索算法(VNS)進(jìn)行結(jié)合，提出了求解校車路徑問題的混合算法。P. Schittekat等[7]重點(diǎn)考慮校車路線生成和站點(diǎn)選擇問題，并設(shè)計一種數(shù)學(xué)啟發(fā)式算法進(jìn)行求解。劉文[8]采用基于滿意優(yōu)化模型和免疫蟻群算法進(jìn)行模型的建立與求解。B. Kim等[9]考慮到校時間窗建立模型，用精確算法求解特殊情況下的模型，并用啟發(fā)式算法求解一般情況下的模型。目前，國內(nèi)外對校車路徑問題的研究主要針對站點(diǎn)已經(jīng)確定的情況來優(yōu)化行車路線，而同時考慮站點(diǎn)選擇、學(xué)生群歸屬站點(diǎn)的劃分以及行車路線問題的研究很少。由此，筆者給出選擇站點(diǎn)及優(yōu)化行車路線的數(shù)學(xué)模型，并用改進(jìn)的遺傳算法進(jìn)行求解。

1 模型建立

1.1 問題描述

筆者僅針對某區(qū)域需要派一輛校車接學(xué)生到校的問題，送學(xué)生返回的路徑問題按照反向路線行駛即可?？紤]學(xué)生群步行時間、乘車時間以及車輛行駛時間等因素，從所有候選站點(diǎn)中選擇若干個需要停靠的站點(diǎn)，制定車輛行駛路線。校車從學(xué)校出發(fā)，依次到達(dá)各個?？空军c(diǎn)接學(xué)生，最后返回學(xué)校。假設(shè)車輛容量足夠，所有學(xué)生均可在選定的停靠站點(diǎn)上車。

1.2 參數(shù)及變量設(shè)置

1.3 模型建立

校車路徑優(yōu)化問題要以運(yùn)營單位的效益和學(xué)生的利益最大化為目標(biāo)，運(yùn)營單位的效益以校車行程時間最短來體現(xiàn)，學(xué)生的利益則以學(xué)生步行到站的時間最短以及乘車時間最短來體現(xiàn)。

車輛行程時間最短的目標(biāo)為：

(1)

設(shè)Ωj為車輛到達(dá)站點(diǎn)j時未訪問的站點(diǎn)的集合(不含j)，則所有學(xué)生的乘車時間最短的目標(biāo)為

(2)

學(xué)生步行到候車站點(diǎn)的時間最小的目標(biāo)為

(3)

為將多目標(biāo)轉(zhuǎn)換為單目標(biāo)，各個目標(biāo)函數(shù)值的涵義、范疇要一致。由于目標(biāo)函數(shù)中涉及的時間的數(shù)量范疇具有差異性，不能簡單相加，故把時間轉(zhuǎn)換成時間成本。設(shè)定各個目標(biāo)的成本系數(shù)為：Z表示車輛在行駛過程中的單位時間的行駛成本(含分?jǐn)偟墓潭ǔ杀竞涂勺兂杀?；λ表示學(xué)生在車上的單位時間成本；μ表示學(xué)生步行的單位時間成本。

把多目標(biāo)函數(shù)變?yōu)閱文繕?biāo)函數(shù)，建立模型為

minz=γz1+λz2+μz3

(4)

(5)

(6)

(7)

(8)

Tnjznj≤Tmax, ?n∈N,j∈M

(9)

(10)

xij={0,1}, ?i,j∈M

(11)

yj∈{0,1}, ?j∈M

(12)

znj∈{0,1}, ?n∈N,j∈M

(13)

模型中：式(4)表示總成本最小的目標(biāo)；式(5)表示學(xué)生群必須到且僅到一個站點(diǎn)候車；式(6)表示當(dāng)有學(xué)生群在站點(diǎn)候車時，必須有校車?？吭撜军c(diǎn)；式(7)表示車輛只駛?cè)胄枰？康恼军c(diǎn)；式(8)表示車輛進(jìn)入站點(diǎn)后必須離開且駛?cè)胛ㄒ坏南乱粋€站點(diǎn)；式(9)保證學(xué)生步行到候車站點(diǎn)的時間不能超過最大步行時間的限制；式(10)保證學(xué)生在車上的時間不能超過最大乘車時間的限制；式(11)～式(13)表示決策變量的取值范圍。

2 求解模型的改進(jìn)遺傳算法

2.1 算法選擇

同時考慮站點(diǎn)選擇、學(xué)生歸屬站點(diǎn)及行車路徑的校車路徑問題屬于NP難題。隨著規(guī)模的增大，解空間呈指數(shù)增長，用窮舉法或其精確算法顯然不能在合理的時間內(nèi)得到滿意解。而遺傳算法[10]、粒子群算法[11-12]等智能算法在求解這類問題時通常能獲得較滿意的結(jié)果。遺傳算法[10]以生物進(jìn)化為原型，通過模仿自然界的選擇與遺傳機(jī)理來尋找最優(yōu)解。與傳統(tǒng)的優(yōu)化方法相比，具有較好的收斂性，計算速度快，同時具有較強(qiáng)的魯棒性。但一般遺傳算法容易陷入“早熟”收斂，因此筆者對一般遺傳算法進(jìn)行改進(jìn)，結(jié)合模型特點(diǎn)，在初始群體的產(chǎn)生以及遺傳算子的設(shè)計過程中加入啟發(fā)知識進(jìn)行改進(jìn)，以保證算法的多樣化及尋優(yōu)的速度。

2.2 算法設(shè)計及實(shí)現(xiàn)過程

2.2.1 設(shè) 置

設(shè)置群體規(guī)模R，遺傳操作的交叉概率Pc，變異概率Pm，算法最大迭代次數(shù)T，以及最大連續(xù)相同迭代次數(shù)Tsame。

2.2.2 產(chǎn)生初始群體

1)設(shè)計染色體編碼方式

用十進(jìn)制編碼的方式，用“0”表示學(xué)校，用自然數(shù)表示候選站點(diǎn)，染色體編碼長度為M+2，編碼取值范圍為[0,M]且為整數(shù)。一個染色體中首尾位數(shù)分別表示學(xué)校，即車輛從學(xué)校出發(fā)，經(jīng)過各個站點(diǎn)接收學(xué)生上車后，最后回到學(xué)校，其中各個學(xué)生群到校車?？康淖罱军c(diǎn)上車。不被采用的候選站點(diǎn)則用“0”表示，以保持染色體的長度，同時把染色體中非零數(shù)字中間包含的“0”元素移到所有非零元素之后。如對于一個有8個候選站點(diǎn)的校車路徑問題，染色體長度為10，假設(shè)某染色體為[0,2,3,5,4,1,6,8,0,0]，表示的車輛路徑為：學(xué)校→站點(diǎn)2→站點(diǎn)3→站點(diǎn)5→站點(diǎn)4→站點(diǎn)1→站點(diǎn)6→站點(diǎn)8→學(xué)校，候選站點(diǎn)7不被采用。

2)生成初始群體

接學(xué)生的校車問題，為考慮學(xué)生在車上的乘車時間較短的目標(biāo)，通常先接收較遠(yuǎn)站點(diǎn)的學(xué)生，再到較近的站點(diǎn)。為得到較優(yōu)的初始個體，此考慮產(chǎn)生初始群體的方法為：把所有候選站點(diǎn)按站點(diǎn)到學(xué)校的距離由遠(yuǎn)到近進(jìn)行排序，從學(xué)校出發(fā)以最遠(yuǎn)站點(diǎn)為第1個?？康恼军c(diǎn)，在按照改進(jìn)的C-W節(jié)約算法經(jīng)過剩下的站點(diǎn)，最后回到學(xué)校，得到第1個染色體個體；依次以次遠(yuǎn)站點(diǎn)、第3遠(yuǎn)站點(diǎn)，……，為第1個?？空军c(diǎn)，尋找第2個、第3個染色體，直到產(chǎn)生[M/2]個染色體。若為達(dá)到群體規(guī)模，則按照隨機(jī)順序生成剩下的個體。

針對有些候選站點(diǎn)有可能不被采用的情況，故在初始群體中對部分個體進(jìn)行刪除站點(diǎn)操作：設(shè)群體規(guī)模為R，在生成的群體中隨機(jī)選取R/4個染色體進(jìn)行刪除1個站點(diǎn)的操作，再選取R/4個染色體進(jìn)行刪除2個站點(diǎn)的操作。通過刪除站點(diǎn)的操作，使初始群體中被選擇的站點(diǎn)不限于全部選擇，更趨向多樣化。

2.2.3 評 價

對染色體進(jìn)行適應(yīng)度評價，保存當(dāng)前最優(yōu)染色體。

由于模型的目標(biāo)函數(shù)值恒為正，適應(yīng)度函數(shù)采用目標(biāo)函數(shù)值的倒數(shù)表示。假設(shè)第i個個體的目標(biāo)函數(shù)值為z(i)，則該染色體對應(yīng)的適應(yīng)度值為f(i)=1/z(i)。對于不滿足約束條件的個體，則令其適應(yīng)度值為0。由個體的編碼方式?jīng)Q定了染色體約束條件式(6)～(8)以及式(11)～(13)恒成立，對于式(5)，在每一個染色體實(shí)時進(jìn)行學(xué)生群歸屬站點(diǎn)的劃分，保持該約束條件的成立。對于式(9)～(10)則需要進(jìn)行逐一判斷，當(dāng)有其中一個條件不滿足時，即可令適應(yīng)度值為0。

2.2.4 進(jìn)行遺傳操作

1)選擇操作

在進(jìn)行選擇操作時，采用以下方法選擇染色體進(jìn)入下一步操作：

(a)將當(dāng)前的染色體按照適應(yīng)度值從高到低排序，取前R/4個染色體直接進(jìn)入下一代，保證群體中適應(yīng)度值較高的個體優(yōu)先被選擇；

(b)從當(dāng)前群體中隨機(jī)選擇3R/4個染色體進(jìn)入下一代操作，保持群體的多樣化。

2)交叉操作

將群體中的染色體進(jìn)行隨機(jī)配對，對每一對染色體以Pc概率進(jìn)行交叉操作：逐一考慮每一對染色體，產(chǎn)生隨機(jī)數(shù)ε∈[0,1]，若ε≤Pc，則對該對染色體中表示候選站點(diǎn)的基因座上的基因值進(jìn)行交叉；若ε>Pc，則該對染色體不進(jìn)行交叉操作，直接保留到下一代。在交叉操作過程中，若表示站點(diǎn)的基因座的值為0，則把零元素移到所有非零元素的后面。

3)變異操作

由于規(guī)劃問題中候選站點(diǎn)存在被采用與不被采用的情況，因此，在變異算子的設(shè)計中除改變?nèi)旧w中的站點(diǎn)順序的操作，還要增加給染色體增加站點(diǎn)與刪除站點(diǎn)的變異操作。依次考慮群體中的個體，產(chǎn)生隨機(jī)數(shù)ξ∈[0,1]，把變異概率Pm分成3部分考慮變異操作：

(a)若ξ≤Pm/3，對染色體的基因值進(jìn)行改變順序的操作，產(chǎn)生[2,M+1]范圍內(nèi)的兩個不相等隨機(jī)整數(shù)P1，P2，交換染色體中基因座P1，P2位置上的基因值；

(b)若Pm/3<ξ≤2Pm/3，則判斷染色體中是否有缺失的候選站點(diǎn)，若有，則以[2,M+1]范圍內(nèi)的一個隨機(jī)整數(shù)作為插入位置，從缺失的候選站點(diǎn)中隨機(jī)選擇一個插入該位置，再把除了染色體首末位之外的一個“0”元素刪除，保持染色體的長度不變；

(c)若2Pm/3<ξ≤Pm，則進(jìn)一步判斷染色體中非零元素的個數(shù)是否大于2，若是，則隨機(jī)選擇染色體中的非零元素進(jìn)行刪除，再在末位補(bǔ)“0”；

若不滿足以上條件，則保留原來的染色體，不進(jìn)行變異操作。

2.2.5 重新評價及判斷

1)重新評價當(dāng)前染色體適應(yīng)值，更新當(dāng)前最優(yōu)染色體。

2)判斷是否滿足終止條件:(a)算法迭代到最大迭代次數(shù)T；(b)有連續(xù)Tsame代的最佳染色體相同。若滿足終止條件，輸出歷史最優(yōu)值的首次出現(xiàn)的代數(shù)，最優(yōu)適應(yīng)度值以及最佳個體，算法終止；否則，返回步驟2.2.4節(jié)。

3 算 例

3.1 基本數(shù)據(jù)

某學(xué)校在一個區(qū)域內(nèi)需要派一輛校車接學(xué)生上學(xué)，共有79個學(xué)生，根據(jù)住所的集聚性，所有學(xué)生可分為33個學(xué)生群體，根據(jù)學(xué)生住所及道路狀況，有7個候選站點(diǎn)可供選擇。以學(xué)校為坐標(biāo)原點(diǎn)(0,0)，各個候選站點(diǎn)的坐標(biāo)位置如表1，各學(xué)生群的坐標(biāo)位置及人數(shù)如表2。

表1 候選站點(diǎn)的坐標(biāo)位置Table 1 Coordinates of the candidate station location /km

表2 學(xué)生群的位置坐標(biāo)及人數(shù)Table 2 Coordinates and the number of student of each student group

注：表中學(xué)生群的序號續(xù)候選站點(diǎn)的編號

設(shè)兩點(diǎn)之間的距離系數(shù)α=1，校車行駛速度v1=30 km/h，學(xué)生步行速度v2=5 km/h，車輛?？空军c(diǎn)消耗的最短時間t1=2 min，每個學(xué)生上車消耗的時間t2=3 s，學(xué)生最大步行時間Tmax=15 min，學(xué)生在車上的最長乘車時間tmax=50 min，車輛單位時間的行駛成本γ=200 元/h，學(xué)生在車上的單位時間成本λ=2.5 元/h，學(xué)生步行的單位時間成本μ=3.0 元/h，求出校車的路徑優(yōu)化方案。

對本例采用改進(jìn)的遺傳算法求解，設(shè)定算法的參數(shù)如下：種群規(guī)模R=50，交叉概率Pc=0.6，變異概率Pm=0.1，最大迭代終止代數(shù)T=200，最大相同最佳迭代次數(shù)Tsame=50。

3.2 結(jié)果分析

3.2.1 最優(yōu)解

應(yīng)用改進(jìn)的遺傳算法，用matlab編程運(yùn)算。經(jīng)50次運(yùn)算，有49次得到相同的最優(yōu)解。其中最快得到最優(yōu)解的是第3次運(yùn)算第29次迭代得到最優(yōu)解的適應(yīng)度值為f=3.466×10-3，總成本函數(shù)值為z=288.501(元)，表3為所求得的最優(yōu)解。

表3 改進(jìn)遺傳算法得到的最優(yōu)解Table 3 The optimal solution by improved genetic algorithm

最優(yōu)解路徑網(wǎng)絡(luò)如圖1，圖中帶箭頭的實(shí)線表示校車行車路徑，虛線表示學(xué)生群所歸屬的候車站點(diǎn)。

圖1 校車行駛的最優(yōu)路徑網(wǎng)絡(luò)Fig.1 The optimal routing network of school bus

3.2.2 不同算法結(jié)果比較分析

吳耀華等[4]，張麗艷等[5]和張海剛等[13]提到了改進(jìn)用粒子群算法求解車輛路徑問題具有快速收斂的特點(diǎn)。為了更進(jìn)一步地驗(yàn)證本文改進(jìn)遺傳算法的有效性，將改進(jìn)遺傳算法與基本遺傳算法(GA)、基本粒子群算法(PSO)以及改進(jìn)的粒子群算法各隨機(jī)運(yùn)算50次，進(jìn)行對比分析。集中算法的最大迭代次數(shù)均為200，最大相同迭代次數(shù)均為50，對比結(jié)果如表4。分別選取4種算法中收斂最快的最優(yōu)運(yùn)行結(jié)果進(jìn)行對比，如圖2。

表4 4種算法運(yùn)行結(jié)果對比Table 4 The comparison of running results by four kinds of algorithms

由表4可見，改進(jìn)的GA算法的搜索成功率比改進(jìn)PSO高出8個百分點(diǎn)，同時迭代次數(shù)和運(yùn)行時間均較少；比基本PSO算法和基本GA算法的搜索成功率高出超過20個百分點(diǎn)，同時迭代次數(shù)和運(yùn)行時間明顯小于PSO算法和基本GA算法。

圖2 4種算法最優(yōu)解收斂對比Fig.2 The comparison of convergence of the optimal solutions by the four kinds of algorithms

從圖2可以看出，改進(jìn)GA算法的收斂速度略高于改進(jìn)的PSO算法，而明顯高于基本GA算法和基本PSO算法?？梢?，改進(jìn)的GA算法明顯優(yōu)于其它3種方法，是解決這類問題的有效方法。

3.2.3 最優(yōu)解敏感性分析

根據(jù)所得的最優(yōu)路徑，把未被選中的站點(diǎn)按照最近原則插入最優(yōu)路徑中進(jìn)行敏感性分析如表5。

表5 最優(yōu)方案的敏感性分析Table 5 Sensitivity analysis of the optimal solutions

從表4可見，幾個方案均滿足約束條件，而方案4與最優(yōu)方案1相比，最長步行時間縮短了2.093 min，付出的代價是學(xué)生在車上的最長乘車時間增加了5.975 min，同時目標(biāo)函數(shù)的總成本值增加22.23元。同樣，方案2和方案3與最優(yōu)方案1相比也顯然處于劣勢。由此，可以看出方案1明顯優(yōu)于其它方案。

4 結(jié) 語

筆者綜合考慮校車路徑問題中站點(diǎn)選擇、學(xué)生群歸屬站點(diǎn)劃分以及車輛行程線路問題，考慮車輛行駛成本、學(xué)生在車上的乘車成本以及學(xué)生的步行成本問題建立了數(shù)學(xué)規(guī)劃模型。根據(jù)模型特點(diǎn)設(shè)計了改進(jìn)的遺傳算法進(jìn)行求解，有效降低問題的復(fù)雜度，提高搜索效率。通過實(shí)例進(jìn)行分析，表明該算法具有較強(qiáng)的尋優(yōu)能力，為校車路徑問題提供有效的解決方法。

[1] KINABLE J,SPIEKSMA F C R,VANDEN B G.School bus routing—a column generation approach [J].InternationalTransactionsinOperationalResearch,2014,21(3):453-478.

[2] RIERA-LEDESMA J,SALAZAR-GONZALEZ J J.A column generation approach for a school bus routing problem with resource con-straints[J].Computers&OperationsResearch,2013,40(2):566-583.

[3] BOCK A,GRANT E,KOENEMANN J.The school bus problem on trees[J].Algorithmica,2013,67(1):518-528.

[4] 吳耀華，張念志.帶時間窗車輛路徑問題的改進(jìn)粒子群算法研究[J].計算機(jī)工程與應(yīng)用,2010,46(15):230-234. WU Yaohua,ZHANG Nianzhi.Modified particle swarm optimization algorithm for vehicle routing problem with time windows[J].ComputerEngineeringandApplications,2010,46(15):230-234.

[5] 張麗艷,龐小紅,夏蔚軍,等.帶時間窗車輛路徑問題的混合粒子群算法[J].上海交通大學(xué)學(xué)報,2006,40(11):1890-1894. ZHANG Liyan,PANG Xiaohong,XIA Weijun,et al.A hybrid particle swarm optimization algorithm for vehicle routing problem with time windows[J].JournalofShanghaiJiaotongUniversity,2006,40(11):1890-1894.

[7] SCHITTEKAT P,KINABLE J,SORENSEN K.A metaheuristic forthe school bus routing problem with bus stop selection[J].EuropenJournalofOperationalResearch,2013(2):518-528.

[8] 劉文.校車優(yōu)化調(diào)度算法及模型研究[J].清華大學(xué)學(xué)報(自然科學(xué)版),2013,53(2):247-251. LIU Wen.An optimization model and algorithms for school bus dispatching[J].JournalofTsinghuaUniversity(ScienceandTechnology),2013,53(2):247-251.

[9] KIM B,KIM S,PARK J.A school bus scheduling problem[J].EuropeanJournalofOperationalResearch,2012,218(2):577-585.

[10] 吳天羿,許繼恒,劉建永,等.求解有硬時間窗車輛路徑問題的改進(jìn)遺傳算法[J].系統(tǒng)工程與電子技術(shù)，2014，36(4):708-713. WU Tianyi,XU Jiheng,LIU Jianyong,et al.Improved genetic algorithm for vehicle routing problem with hard time windows[J].SystemsEngineeringandElectronics,2014,36(4):708-713.

[11] 李毅,陸百川,劉春旭.車輛路徑問題的混沌粒子群算法研究 [J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2012,31(4):842-845. LI Yi,LU Baichuan,LIU Chunxu.Research on chaos particle swarm optimization algorithm for vehicle routing problem[J].JournalofChongqingJiaotongUniversity(NaturalScience),2012,31(4):842- 845.

[12] 彭勇,謝祿江,劉松.時變單車路徑問題建模及算法設(shè)計[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2013,32(2):263-266. PENG Yong,XIE Lujiang,LIU Song.Route modeling and algorithm designing of time-dependent single vehicle[J].JournalofChongqingJiaotongUniversity(NaturalScience),2013,32(2):263-266.

[13] 張海剛，顧幸生，吳燕翔.改進(jìn)的粒子群算法及其在帶軟時間窗車輛調(diào)度問題中的應(yīng)用[J].華東理工大學(xué)學(xué)報(自然科學(xué)版),2009,35( 5):774-778 . ZHANG Haigang,GU Xingsheng,WU Yanxiang.Vehicle scheduling problem with soft time windows based on improved particle swarm optimization[J].JournalofEastChinaUniversityofScienceandTechnology(NaturalScienceEdition),2009 ,35(5):774-778.

An Optimization Model and Algorithm for School Bus Routing

HAO Zhongna

(College of Transportation Management, Nanjing Communications Institute of Technology, Nanjing 211188, Jiangsu, P. R. China)

To facilitate selection of school bus stations, allocating student groups to stations and developing vehicle routings, the mathematical programming model was established to minimize the cost of the vehicle travel time, the students journey time, and the students walking time to the station by considering the key constraint conditions such as the longest riding time in the school bus and the longest walking time of students to the station. Then the improved genetic algorithm was put forward to for above purpose and by this algorithm, the excellent individual of initial population was produced by heuristic method, and the operators with heuristic knowledge were designed to improve the excellent searching efficiency. The example analysis results show that the proposed method is feasible with significant results, which can effectively provide optimal route for school bus of large number.

traffic and transportation engineering; school bus routing; optimization; mathematical programming model; improved genetic algorithm

10.3969/j.issn.1674-0696.2016.02.26

2014-11-06；

2015-12-13

江蘇省教育廳高校哲學(xué)社會科學(xué)研究項(xiàng)目(2013SJB6300048)；南京交通職業(yè)技術(shù)學(xué)院校級課題(JR1210)

郝忠娜(1978—)，女，山東煙臺人，副教授，碩士，主要從事交通運(yùn)輸規(guī)劃與管理方面的研究。E-mail：haozn1978@163.com。

U121

A

1674-0696(2016)02-126-05