無混載校車路線分析模型優(yōu)化實(shí)現(xiàn)方法

高 巍，陳澤穎，李大舟

(沈陽化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 遼寧 沈陽 110142)

隨著中國(guó)社會(huì)經(jīng)濟(jì)不斷發(fā)展，義務(wù)教育的發(fā)展面臨新的任務(wù)和要求，從21世紀(jì)初開始，為降低學(xué)校的運(yùn)營(yíng)成本，優(yōu)化教育資源配置，促進(jìn)教育均衡發(fā)展，我國(guó)進(jìn)行了大規(guī)模的學(xué)校重新布局調(diào)整和撤并.學(xué)校的布局調(diào)整解決了班級(jí)規(guī)模和教育資源浪費(fèi)的問題，但卻引發(fā)了一個(gè)新的問題：學(xué)生入學(xué)距離的增加和上下學(xué)的不便. 近年來，為方便學(xué)生上下學(xué)，對(duì)中小學(xué)生校車服務(wù)的需求日益突出，不少地區(qū)開始逐漸開展校車服務(wù).規(guī)劃一組校車路過學(xué)生人數(shù)已知的站點(diǎn)，早上將學(xué)生從居住地附近送達(dá)學(xué)校，下午接他們送回[1].對(duì)這些車輛的路徑規(guī)劃稱為校車路徑問題(SBRP)[2],校車不僅可以很大程度上提高道路利用率，而且還能節(jié)省大量的能源.

在校車運(yùn)營(yíng)中存在許多不合理的校車路線設(shè)計(jì)及校車運(yùn)營(yíng)方式，缺乏路徑規(guī)劃優(yōu)化的經(jīng)驗(yàn).目前大多數(shù)校車運(yùn)營(yíng)在校車安排上依靠簡(jiǎn)單的人工規(guī)劃路徑，調(diào)度過程困難且調(diào)度結(jié)果缺乏模型理論的支持，造成校車資源浪費(fèi)、校車行駛總路程過長(zhǎng)等問題；學(xué)生乘坐校車的費(fèi)用增加，對(duì)社會(huì)資源亦造成一種浪費(fèi)，且校車乘車服務(wù)質(zhì)量不高[3].

文獻(xiàn)[4-9]針對(duì)單校車問題分別給出了求解算法.Zhang 和 Li使用量子粒子群算法(quantum-behaved particle swarm optimization，QPSO)解決了甘肅民族師范學(xué)院教職工校車路徑問題[4].Euchi和Mraihi結(jié)合蟻群算法(ant colony optimization，ACO) 與 變 鄰 域 搜 索 算 法 (variable neighborhood search，VNS)提出了一種混合算法[5].劉青松采用元啟發(fā)式框架,在校車不超載的約束下,用車輛的行駛距離之和最小作為優(yōu)化目標(biāo),規(guī)劃出校車的數(shù)目[6].張富和朱泰英在學(xué)生乘車站點(diǎn)設(shè)計(jì)方面提出雙目標(biāo)非線性規(guī)劃模型，運(yùn)用了相應(yīng)啟發(fā)式優(yōu)化算法[7].劉青松等將單校校車路徑問題抽象化為開放式車輛路徑問題，以車輛載荷為約束條件的基礎(chǔ)上，實(shí)現(xiàn)車輛行駛距離最短的優(yōu)化目標(biāo)，其求解結(jié)論明顯優(yōu)于Arc GIS[8].呂騰捷[9]主要實(shí)現(xiàn)了最優(yōu)站點(diǎn)的選擇、最優(yōu)路徑的規(guī)劃及成本效益分析.本文以最短路徑為目標(biāo)函數(shù)建立一個(gè)快速有效的無混載校車路線分析模型，求出一條滿足所有約束條件的路徑，達(dá)到降低校車運(yùn)營(yíng)成本的目的.

1 上下學(xué)時(shí)校車的最短行駛路徑問題

1.1 乘降站位置選擇

乘降站位置選擇應(yīng)考慮約束條件包括學(xué)生步行距離，學(xué)生上下車方便安全，校車運(yùn)營(yíng)成本等，對(duì)乘車站點(diǎn)的選擇將間接影響校車運(yùn)輸成本控制和服務(wù)質(zhì)量,從而影響對(duì)站點(diǎn)和路徑的決策[10].

考慮到學(xué)生上下車方便，校車停車點(diǎn)與所接學(xué)生家庭住址距離在500 m以內(nèi)，考慮最經(jīng)濟(jì)、最快速的路線和停車點(diǎn)安排.假設(shè)學(xué)校U有S個(gè)學(xué)生，S個(gè)學(xué)生有S個(gè)經(jīng)緯度坐標(biāo).以S個(gè)經(jīng)緯度坐標(biāo)為圓心，500 m為半徑畫圓，有500個(gè)圓，將多個(gè)圓的重疊區(qū)域設(shè)為乘降站選址的可行區(qū)域.有的圓沒有與其他圓相重疊的區(qū)域，將該圓的整個(gè)圓區(qū)域設(shè)為乘降站選址的可行區(qū)域.在乘降站選址的可行區(qū)域內(nèi)根據(jù)實(shí)際周邊環(huán)境選擇停車安全、道路較為寬敞、距離十字路口較近的地點(diǎn)作為乘降站具體地點(diǎn)，如圖1所示.

圖1 乘降站位置選擇Fig.1 Pick up and drop station location selection

使用上述乘降站位置計(jì)算方法，U學(xué)校的S個(gè)學(xué)生需要在m個(gè)乘降站下車回家.m個(gè)乘降站的編號(hào)P1，P2，P3，…，Pi，…，Pm-1，Pm.以U校為例，圖1中共有7個(gè)乘降點(diǎn)，編號(hào)為P1，P2，P3,…，P7.

1.2 上下學(xué)時(shí)校車的最短行駛路徑問題

1.2.1 問題定義

最短路徑問題用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑.上學(xué)時(shí)校車的最短行駛路徑問題就是從出發(fā)點(diǎn)開始，經(jīng)過所有乘降點(diǎn)最終到達(dá)學(xué)校的最短路徑；放學(xué)時(shí)將所有學(xué)生送到對(duì)應(yīng)的乘降點(diǎn)的最短路徑.最短路徑算法是解決在具有拓?fù)潢P(guān)系的連通網(wǎng)絡(luò)中找到兩點(diǎn)之間最優(yōu)路徑問題的有效方法，它除了能夠計(jì)算最短路徑距離外，還能通過給每條邊賦不同的權(quán)重值來滿足不同的搜索條件，如耗時(shí)最少路徑[11-13].

1.2.2 問題描述

分兩種情況描述最優(yōu)路徑問題：極限情況和一般情況.

極限情況：U學(xué)校有S輛校車，要完成送S個(gè)學(xué)生上學(xué).極限情況下每個(gè)學(xué)生都會(huì)獨(dú)自乘坐一輛校車，從家附近的乘降站直接到達(dá)學(xué)校，中途無需經(jīng)過任何其他乘降站，所走的路徑就是學(xué)校到該學(xué)生家之間的最短路徑，使用經(jīng)典最短路徑算法(算法A)就可以求出該路徑.

一般情況：U學(xué)校有n輛校車，要完成送S個(gè)學(xué)生上學(xué).追求在n輛校車中行駛距離最遠(yuǎn)的校車的行駛距離最短.該情況是在充分利用現(xiàn)有校車資源的情況下，追求每個(gè)學(xué)生盡快到達(dá)學(xué)校的校車行駛路線.

一般情況的最優(yōu)解就是極限情況中所描述的答案.每個(gè)學(xué)生自己?jiǎn)为?dú)乘坐一輛校車，不和其他同學(xué)共用校車.此時(shí)需要m輛校車分別從m個(gè)乘降站出發(fā)直接到達(dá)學(xué)校，該方案中行駛距離最遠(yuǎn)的校車的行駛距離等于距離學(xué)校最遠(yuǎn)的乘降站與學(xué)校之間的距離.

現(xiàn)在開始削減校車數(shù)量，同時(shí)保證所有校車中行駛距離最遠(yuǎn)的校車的行駛距離最短.校車數(shù)量從m輛減為m-1輛.此情況下，原來到達(dá)某個(gè)乘降站的校車被取消，該校車上的學(xué)生要和到達(dá)其他乘降站的學(xué)生合并乘坐一輛校車.

假設(shè)m輛校車C1，C2，C3，…，Cm中校車Ci被取消，校車Ci中的學(xué)生改為乘坐校車Cj.根據(jù)以下方法在剩余的m-1輛校車中選擇校車Cj：分別把原來校車Ci中的學(xué)生放到剩余的每一輛校車中，獲得m-1輛校車的新的m-1個(gè)行駛路線.選擇新的m-1輛校車行駛路線中變化后行駛距離最小的那輛校車作為校車Cj，讓校車Ci的學(xué)生改乘校車Cj.該方案就是m-1輛校車到達(dá)m乘降站時(shí)，保證行駛距離最遠(yuǎn)的校車的行駛距離最短.

根據(jù)上述方法可以獲得在保證所有校車中行駛距離最遠(yuǎn)的校車的行駛距離最短條件下，m-1輛校車到達(dá)m乘降站的最優(yōu)方案.每削減1輛校車后的最優(yōu)方案都是在當(dāng)前最優(yōu)方案基礎(chǔ)上實(shí)現(xiàn)的，該問題的最優(yōu)解包含了子問題的最優(yōu)解，因此該問題具有最優(yōu)子結(jié)構(gòu).問題的最優(yōu)子結(jié)構(gòu)特征是該問題可以采用上述動(dòng)態(tài)規(guī)化算法(算法B)求解的保證.

1.3 問題的算法設(shè)計(jì)

1.3.1 算法A

算法A用來確定地圖上任意兩點(diǎn)之間的最短路徑，并且該路徑不必經(jīng)過其他特定位置上的點(diǎn).在尋找兩個(gè)乘降站之間的地圖最短路徑，或者尋找一個(gè)乘降站和一所學(xué)校之間的地圖最短路徑時(shí)都會(huì)使用算法A.

算法A基于圖論，乘降站、學(xué)校和地圖上十字路口都被視為一個(gè)圖G的頂點(diǎn)V.連接乘降站、學(xué)校和地圖上十字路口的道路被看成是該圖G的邊E.每條邊無方向但是有權(quán)重W，權(quán)重W就是該路徑的長(zhǎng)度.該圖G上只有相鄰的兩個(gè)頂點(diǎn)V有邊E，地理因素決定不是所有頂點(diǎn)V都是相鄰頂點(diǎn)，例如：不是所有的十字路口之間都有直接道路相連，如圖2所示.

圖2 兩個(gè)乘降站之間的最短路徑Fig.2 Shortest path between two boarding stations

綜上圖G可以看成是一個(gè)無向有權(quán)半連通圖，算法A就是在圖G中找到任意兩定點(diǎn)V之間的最短路徑，該路徑無需經(jīng)過特定頂點(diǎn)[14].該問題有很多經(jīng)典算法可以求解，這里采用Dijkstra算法求解.Dijkstra算法的思想是從起點(diǎn)遍歷與其相鄰的節(jié)點(diǎn)，找到最短距離的點(diǎn)，標(biāo)記該點(diǎn)，然后遍歷新點(diǎn)相鄰且未標(biāo)記的點(diǎn)，重復(fù)之前的搜索計(jì)算步驟，直到目標(biāo)點(diǎn)被標(biāo)記，即從起點(diǎn)到目標(biāo)點(diǎn)的最短路徑[15-16].

1.3.2 算法B

算法B主要解決的問題是在m輛校車中選擇一輛校車Ci作為被取消的校車，校車Ci可能是原來m輛校車中的任何一輛，因此校車Ci的選擇要遍歷所有m輛校車，即把每一輛校車作為Ci來計(jì)算一次，該過程可以以每個(gè)校車都是Ci為對(duì)象.

在計(jì)算m-1輛校車因?yàn)槌袚?dān)運(yùn)送校車Ci中學(xué)生而產(chǎn)生行駛路線發(fā)生變化后的最短行駛距離時(shí)，針對(duì)m-1輛校車中每一輛校車使用最短路徑搜索算法.對(duì)于承擔(dān)任務(wù)的m-1輛校車中的任意一輛校車，以學(xué)校為源點(diǎn)，找到途經(jīng)2個(gè)乘降站(該校車原來的目的乘降站、車校Ci的乘降站)的最短路徑，并把該路徑距離作為該校車承擔(dān)運(yùn)送校車Ci中學(xué)生而產(chǎn)生行駛路線發(fā)生變化后的最短行駛距離.

校車Ci可能是任意一輛校車，每一校車都作為Ci進(jìn)行計(jì)算一次，找到結(jié)果Cj和對(duì)應(yīng)的新的Cj最短行駛距離.在m個(gè)方案比較新的Cj最短行駛距離，確定最優(yōu)方案時(shí)Ci的選擇，并將該方案中的Cj作為最終結(jié)果.

綜上，如果想獲得m-2輛校車到達(dá)m乘降站的最優(yōu)方案，可在m-1輛校車到達(dá)m乘降站的最優(yōu)方案基礎(chǔ)上，再次使用上述方法，即可獲得保證所有校車中行駛距離最遠(yuǎn)的校車的行駛距離最短條件下，m-2輛校車到達(dá)m乘降站的最優(yōu)方案.

使用m-n次該算法，直到校車數(shù)量從m被減為n為止.此時(shí)就是保證在n輛校車中行駛距離最遠(yuǎn)的校車的行駛距離最短，安排n輛校車中每輛學(xué)生的人數(shù)，以及確定哪位學(xué)生乘坐哪輛校車的最優(yōu)解.

以此類推，每削減一輛校車后的最優(yōu)方案都是在當(dāng)前最優(yōu)方案基礎(chǔ)上實(shí)現(xiàn)的，該問題的最優(yōu)解包含了子問題的最優(yōu)解，因此該問題具有最優(yōu)子結(jié)構(gòu)，可采用動(dòng)態(tài)規(guī)化算法.算法B因此基于動(dòng)態(tài)規(guī)劃技術(shù).

算法B將m-n輛校車分擔(dān)m個(gè)接送任務(wù)拆分成m-n次，其中第i次是對(duì)m-i由m-i-1的尋優(yōu)，即每一次的尋優(yōu)都是在前一次尋優(yōu)基礎(chǔ)上進(jìn)行的，而且每一次尋優(yōu)的計(jì)算方法都是相同的.

算法B把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，抽象其中單次尋優(yōu)過程.

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)

以SY市某校U為例，該校位于SY市，學(xué)生數(shù)據(jù)為就讀于該校附近的學(xué)生信息.所獲得的數(shù)據(jù)信息整理為Excel數(shù)據(jù)(見表1)，包括10個(gè)屬性，學(xué)生ID(5位數(shù)字)、就讀學(xué)校名稱(U校)、年級(jí)、班級(jí)、性別(0～1)、出行方式、上學(xué)離家時(shí)間、乘校車意愿(0～1)和家庭住址.其中乘校車意愿屬性中0表示不愿意乘坐校車，1表示愿意乘坐校車.家庭住址標(biāo)屬的標(biāo)準(zhǔn)格式為xx區(qū)xx街xx號(hào)，以提供坐標(biāo)軸，獲得精準(zhǔn)的經(jīng)緯度坐標(biāo).

表1 U校學(xué)生信息表Table 1 Student Information of U school

2.2 實(shí)驗(yàn)結(jié)果分析

2.2.1 算法A

算法A以U校為例，選取其中任意一個(gè)愿意乘坐校車的學(xué)生，學(xué)生家為起點(diǎn)，學(xué)校為終點(diǎn)，利用算法A計(jì)算從學(xué)生家到學(xué)校的距離和時(shí)間(見圖3).利用算法A可以計(jì)算各乘降點(diǎn)之間和各乘降點(diǎn)到學(xué)校的距離，為下一步的路徑規(guī)劃提供有效的數(shù)據(jù)幫助.

圖3 算法A計(jì)算兩點(diǎn)的最短距離Fig.3 Algorithm A calculates the shortest distance between two points

2.2.2 算法B

U學(xué)校有7個(gè)學(xué)生通過校車上學(xué)和放學(xué)，該7位學(xué)生住的比較分散，每個(gè)學(xué)生都有一個(gè)獨(dú)立的乘降站.在圖4中給出了U學(xué)校的位置和7個(gè)乘降站的位置P1，P2，P3，P4，P5，P6，P7.

圖4 U學(xué)校的7個(gè)乘降站分布Fig.4 Distribution of 7 boarding stations in U school

下面以放學(xué)為例，上學(xué)問題是放學(xué)問題的等價(jià)反問題，因此可以采用相同的解法.為讓每一個(gè)學(xué)生都能盡快回家，極限情況下是每個(gè)乘降站都有一個(gè)校車直接到達(dá).因此最優(yōu)情況是7輛校車C1，C2，C3，C4，C5，C6，C7分別從學(xué)校直接到達(dá)7個(gè)乘降站P1，P2，P3，P4，P5，P6，P7.為了節(jié)約校車運(yùn)營(yíng)成本，增加校車的運(yùn)載率，假設(shè)學(xué)校希望從7輛校車減少為4輛校車，則需要通過算法B運(yùn)算3次，每一次都選擇出取消哪輛校車Ci是最優(yōu)的，同時(shí)從剩下的校車選擇出最優(yōu)的校車Cj來完成被取消的校車Ci的任務(wù).

下面以第1次執(zhí)行算法B為例，校車數(shù)量從7輛削減到6輛，算法執(zhí)行完后能夠判斷出被取消的校車Ci和代替Ci完成到達(dá)乘降站Pi任務(wù)的校車Cj.

首先，列出U學(xué)校以及7個(gè)乘降站相互之間的最短距離，可以采用算法A來實(shí)現(xiàn)表中每項(xiàng)數(shù)值的獲得，如表2所示.

表2 U學(xué)校以及7個(gè)乘降站相互之間的最短距離Table 2 The shortest distance between U school and 7 boarding stations km

分別將每個(gè)校車都作為Ci和Cj進(jìn)行考慮，計(jì)算出每種情況下，行駛最遠(yuǎn)的校車的行駛距離.例如：當(dāng)C1=Ci，C2=Cj時(shí)，校車C2除了要到乘降站P2之外，還要到乘降站P1.校車C2新的最短行駛路線長(zhǎng)度和最短行駛路線可以根據(jù)下面提到的算法獲得，路線是U學(xué)?！鶳2→P1，最短長(zhǎng)度是1.7+12.3=14 km.該情況下，6輛校車中行駛最遠(yuǎn)的校車就是校車C2，其最遠(yuǎn)行駛距離是14 km.當(dāng)Cx=Ci，Cy=Cj時(shí)，方案中最短行駛距離Px到Py的最短距離+Min{U學(xué)校到Px的最短距離，U學(xué)校到Py的最短距離}.

根據(jù)此算法得出表3中每一個(gè)表項(xiàng)數(shù)值.該表中每一數(shù)值表示校車Cj由于接替了Ci的任務(wù)而生成的新的最短路徑長(zhǎng)度.

表3 校車Cj由于接替了Ci的任務(wù)而生成的新的最短路徑的長(zhǎng)度Table 3 Length of the new shortest path generated by the school bus Cj to take over the task of Ci km

新方案共有42種，每種新方案都會(huì)刪除校車Ci的原有行駛距離，增加校車Cj的原有行駛距離.

綜合考慮42種新方案中每一種方案行駛最遠(yuǎn)的校車的行駛距離是多少.例如：當(dāng)C1=Ci，C2=Cj時(shí)， 該新方案行駛最遠(yuǎn)的校車的行駛距離可以根據(jù)表4直接找出.

表4 C1=Ci，C2=Cj時(shí)，該新方案行駛最遠(yuǎn)的 校車的行駛距離Table 4 When C1=Ci,C2=Cj,the travel distance of the school bus with the farthest travel of the new scheme

結(jié)果是C1=Ci，C2=Cj時(shí)，該新方案行駛最遠(yuǎn)的校車的行駛距離等于14 km.

當(dāng)Cx=Ci，Cy=Cj時(shí)，方案中行駛最遠(yuǎn)的校車的行駛距離=Max{Px到Py的最短距離+Min{U學(xué)校到Px的最短距離，U學(xué)校到Py的最短距離}，Max{7個(gè)乘降站之間的相互距離}}.

根據(jù)此算法得出表5中每一個(gè)表項(xiàng)數(shù)值.該表中每一數(shù)值表示該新方案行駛最遠(yuǎn)的校車的行駛距離.

由表5可知：新方案行駛最遠(yuǎn)的校車的行駛距離在表中的每一項(xiàng)里給出，其中數(shù)值最小的是12.2 km.因此，取消校車C5，讓校車C7代替C5到達(dá)乘降站P5是最優(yōu)的從7輛校車減為6輛校車的方案.

采用同樣的方法，可以計(jì)算出從6輛校車減為5輛校車的最優(yōu)方案.依次類推，反復(fù)使用算法B，最終可以得到U學(xué)校具有4輛校車時(shí)，最優(yōu)的學(xué)生乘坐分配方案.

需要注意的一點(diǎn)是如果方案中最優(yōu)的方案不止一種時(shí)，要根據(jù)前一個(gè)表，選擇校車Cj由于接替了Ci的任務(wù)而生成的新的最短路徑長(zhǎng)度最小的方案.該方案表明在行駛最遠(yuǎn)的校車的行駛距離最小的條件下，原來乘坐Ci和Cj到達(dá)乘降站Pi和Pj的學(xué)生所受到的影響也被降為最低.

3 總 結(jié)

本文就校車路徑規(guī)劃問題，查閱相關(guān)學(xué)校的上學(xué)放學(xué)時(shí)間，充分調(diào)研各個(gè)學(xué)生的家庭住址和SY市交通情況，綜合考慮校車運(yùn)營(yíng)方式和盈利方法，對(duì)實(shí)際的校車運(yùn)營(yíng)問題進(jìn)行分析，提出了算法，實(shí)驗(yàn)結(jié)果表明運(yùn)用算法后的行車距離更短，校車數(shù)量減少，運(yùn)營(yíng)成本降低，達(dá)到預(yù)期效果.

本次建模以完成接送每個(gè)學(xué)生上學(xué)放學(xué)為要求，以盈利最大化為最終約束，提出算法.首先，通過對(duì)每個(gè)學(xué)生家庭住址的研究，利用網(wǎng)絡(luò)地圖對(duì)他們的地址進(jìn)行精確定位.之后將所有的地址信息抽象成乘降站，充分利用算法A計(jì)算各乘降點(diǎn)之間和各乘降點(diǎn)與學(xué)校的距離，然后利用算法B進(jìn)行一系列復(fù)雜的計(jì)算，并最終獲得了單校校車情況下最佳的校車路線、最佳數(shù)量.

本文在建立校車線路優(yōu)化模型時(shí)沒有考慮城市交通情況. 實(shí)際上，校車的運(yùn)行時(shí)間集中在早晚的城市交通高峰期，不可避免地導(dǎo)致交通擁堵和校車不及時(shí)現(xiàn)象. 在這個(gè)階段，由于這種情況，部分學(xué)校提前或推遲上下學(xué)時(shí)間，學(xué)校在設(shè)計(jì)校車路線時(shí)應(yīng)考慮這個(gè)因素，這時(shí)路徑最短便不是最優(yōu)結(jié)果. 因此，如何設(shè)計(jì)規(guī)劃校車線路和乘降站，如何合理運(yùn)營(yíng)校車實(shí)現(xiàn)最大經(jīng)濟(jì)效益是目前研究的重點(diǎn)[17].