郝 忠 娜

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

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

郝 忠 娜

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

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

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

0 引 言

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

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

1 模型建立

1.1 問(wèn)題描述

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

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

1.3 模型建立

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

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

(1)

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

(2)

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

(3)

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

把多目標(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é)生群必須到且僅到一個(gè)站點(diǎn)候車；式(6)表示當(dāng)有學(xué)生群在站點(diǎn)候車時(shí)，必須有校車?？吭撜军c(diǎn)；式(7)表示車輛只駛?cè)胄枰？康恼军c(diǎn)；式(8)表示車輛進(jìn)入站點(diǎn)后必須離開(kāi)且駛?cè)胛ㄒ坏南乱粋€(gè)站點(diǎn)；式(9)保證學(xué)生步行到候車站點(diǎn)的時(shí)間不能超過(guò)最大步行時(shí)間的限制；式(10)保證學(xué)生在車上的時(shí)間不能超過(guò)最大乘車時(shí)間的限制；式(11)～式(13)表示決策變量的取值范圍。

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

2.1 算法選擇

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

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

2.2.1 設(shè) 置

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

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

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

用十進(jìn)制編碼的方式，用“0”表示學(xué)校，用自然數(shù)表示候選站點(diǎn)，染色體編碼長(zhǎng)度為M+2，編碼取值范圍為[0,M]且為整數(shù)。一個(gè)染色體中首尾位數(shù)分別表示學(xué)校，即車輛從學(xué)校出發(fā)，經(jīng)過(guò)各個(gè)站點(diǎn)接收學(xué)生上車后，最后回到學(xué)校，其中各個(gè)學(xué)生群到校車?？康淖罱军c(diǎn)上車。不被采用的候選站點(diǎn)則用“0”表示，以保持染色體的長(zhǎng)度，同時(shí)把染色體中非零數(shù)字中間包含的“0”元素移到所有非零元素之后。如對(duì)于一個(gè)有8個(gè)候選站點(diǎn)的校車路徑問(wèn)題，染色體長(zhǎng)度為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é)生的校車問(wèn)題，為考慮學(xué)生在車上的乘車時(shí)間較短的目標(biāo)，通常先接收較遠(yuǎn)站點(diǎn)的學(xué)生，再到較近的站點(diǎn)。為得到較優(yōu)的初始個(gè)體，此考慮產(chǎn)生初始群體的方法為：把所有候選站點(diǎn)按站點(diǎn)到學(xué)校的距離由遠(yuǎn)到近進(jìn)行排序，從學(xué)校出發(fā)以最遠(yuǎn)站點(diǎn)為第1個(gè)?？康恼军c(diǎn)，在按照改進(jìn)的C-W節(jié)約算法經(jīng)過(guò)剩下的站點(diǎn)，最后回到學(xué)校，得到第1個(gè)染色體個(gè)體；依次以次遠(yuǎn)站點(diǎn)、第3遠(yuǎn)站點(diǎn)，……，為第1個(gè)?？空军c(diǎn)，尋找第2個(gè)、第3個(gè)染色體，直到產(chǎn)生[M/2]個(gè)染色體。若為達(dá)到群體規(guī)模，則按照隨機(jī)順序生成剩下的個(gè)體。

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

2.2.3 評(píng) 價(jià)

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

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

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

1)選擇操作

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

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

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

2)交叉操作

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

3)變異操作

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

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

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

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

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

2.2.5 重新評(píng)價(jià)及判斷

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

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

3 算 例

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

某學(xué)校在一個(gè)區(qū)域內(nèi)需要派一輛校車接學(xué)生上學(xué)，共有79個(gè)學(xué)生，根據(jù)住所的集聚性，所有學(xué)生可分為33個(gè)學(xué)生群體，根據(jù)學(xué)生住所及道路狀況，有7個(gè)候選站點(diǎn)可供選擇。以學(xué)校為坐標(biāo)原點(diǎn)(0,0)，各個(gè)候選站點(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é)生群的序號(hào)續(xù)候選站點(diǎn)的編號(hào)

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

對(duì)本例采用改進(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)用粒子群算法求解車輛路徑問(wèn)題具有快速收斂的特點(diǎn)。為了更進(jìn)一步地驗(yàn)證本文改進(jìn)遺傳算法的有效性，將改進(jìn)遺傳算法與基本遺傳算法(GA)、基本粒子群算法(PSO)以及改進(jìn)的粒子群算法各隨機(jī)運(yùn)算50次，進(jìn)行對(duì)比分析。集中算法的最大迭代次數(shù)均為200，最大相同迭代次數(shù)均為50，對(duì)比結(jié)果如表4。分別選取4種算法中收斂最快的最優(yōu)運(yùn)行結(jié)果進(jìn)行對(duì)比，如圖2。

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

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

圖2 4種算法最優(yōu)解收斂對(duì)比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算法?？梢?jiàn)，改進(jìn)的GA算法明顯優(yōu)于其它3種方法，是解決這類問(wèn)題的有效方法。

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

4 結(jié) 語(yǔ)

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

[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] 吳耀華，張念志.帶時(shí)間窗車輛路徑問(wèn)題的改進(jìn)粒子群算法研究[J].計(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] 張麗艷,龐小紅,夏蔚軍,等.帶時(shí)間窗車輛路徑問(wèn)題的混合粒子群算法[J].上海交通大學(xué)學(xué)報(bào),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é)報(bào)(自然科學(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] 吳天羿,許繼恒,劉建永,等.求解有硬時(shí)間窗車輛路徑問(wèn)題的改進(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] 李毅,陸百川,劉春旭.車輛路徑問(wèn)題的混沌粒子群算法研究 [J].重慶交通大學(xué)學(xué)報(bào)(自然科學(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í)變單車路徑問(wèn)題建模及算法設(shè)計(jì)[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(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)的粒子群算法及其在帶軟時(shí)間窗車輛調(diào)度問(wèn)題中的應(yīng)用[J].華東理工大學(xué)學(xué)報(bào)(自然科學(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é)社會(huì)科學(xué)研究項(xiàng)目(2013SJB6300048)；南京交通職業(yè)技術(shù)學(xué)院校級(jí)課題(JR1210)

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

U121

A

1674-0696(2016)02-126-05