郝 忠 娜

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

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

郝 忠 娜

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

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

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

0 引 言

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

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

1 模型建立

1.1 問題描述

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

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

1.3 模型建立

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

車輛行程時間最短的目標為：

(1)

設Ωj為車輛到達站點j時未訪問的站點的集合(不含j)，則所有學生的乘車時間最短的目標為

(2)

學生步行到候車站點的時間最小的目標為

(3)

為將多目標轉換為單目標，各個目標函數(shù)值的涵義、范疇要一致。由于目標函數(shù)中涉及的時間的數(shù)量范疇具有差異性，不能簡單相加，故把時間轉換成時間成本。設定各個目標的成本系數(shù)為：Z表示車輛在行駛過程中的單位時間的行駛成本(含分攤的固定成本和可變成本)；λ表示學生在車上的單位時間成本；μ表示學生步行的單位時間成本。

把多目標函數(shù)變?yōu)閱文繕撕瘮?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)表示總成本最小的目標；式(5)表示學生群必須到且僅到一個站點候車；式(6)表示當有學生群在站點候車時，必須有校車停靠該站點；式(7)表示車輛只駛入需要?？康恼军c；式(8)表示車輛進入站點后必須離開且駛入唯一的下一個站點；式(9)保證學生步行到候車站點的時間不能超過最大步行時間的限制；式(10)保證學生在車上的時間不能超過最大乘車時間的限制；式(11)～式(13)表示決策變量的取值范圍。

2 求解模型的改進遺傳算法

2.1 算法選擇

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

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

2.2.1 設 置

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

2.2.2 產生初始群體

1)設計染色體編碼方式

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

2)生成初始群體

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

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

2.2.3 評 價

對染色體進行適應度評價，保存當前最優(yōu)染色體。

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

2.2.4 進行遺傳操作

1)選擇操作

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

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

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

2)交叉操作

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

3)變異操作

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

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

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

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

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

2.2.5 重新評價及判斷

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

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

3 算 例

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

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

表1 候選站點的坐標位置Table 1 Coordinates of the candidate station location /km

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

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

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

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

3.2 結果分析

3.2.1 最優(yōu)解

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

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

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

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

3.2.2 不同算法結果比較分析

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

表4 4種算法運行結果對比Table 4 The comparison of running results by four kinds of algorithms

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

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

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

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

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

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

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

4 結 語

筆者綜合考慮校車路徑問題中站點選擇、學生群歸屬站點劃分以及車輛行程線路問題，考慮車輛行駛成本、學生在車上的乘車成本以及學生的步行成本問題建立了數(shù)學規(guī)劃模型。根據(jù)模型特點設計了改進的遺傳算法進行求解，有效降低問題的復雜度，提高搜索效率。通過實例進行分析，表明該算法具有較強的尋優(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].計算機工程與應用,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].上海交通大學學報,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)化調度算法及模型研究[J].清華大學學報(自然科學版),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].系統(tǒng)工程與電子技術，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].重慶交通大學學報(自然科學版),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] 彭勇,謝祿江,劉松.時變單車路徑問題建模及算法設計[J].重慶交通大學學報(自然科學版),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].華東理工大學學報(自然科學版),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

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

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

U121

A

1674-0696(2016)02-126-05