高 巍，陳澤穎，李大舟

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

隨著中國義務(wù)教育水平的不斷提高，為中小學(xué)生提供合理的校車服務(wù)成為對(duì)學(xué)校和教育部門的新要求.對(duì)地方教育局而言，正確規(guī)劃校車路線并盡可能降低校車運(yùn)營成本是一個(gè)難題[1].校車路徑問題主要是為一個(gè)校車車隊(duì)規(guī)劃路線，使校車沿路線將學(xué)生送至學(xué)?；蚍艑W(xué)時(shí)送回乘車站點(diǎn)，并使特定的目標(biāo)達(dá)到最優(yōu).校車不僅可以很大程度上提高道路利用率，而且還能節(jié)省大量的能源.相對(duì)于其他的出行行為，上下學(xué)出行行為在時(shí)間上和空間上都具有一定的確定性，這在一定程度上不僅影響人們的日?；顒?dòng)，而且還對(duì)城市交通有著不可忽視的影響[2].

文獻(xiàn)[3-6]表明通過校車路徑優(yōu)化能夠顯著減少校車數(shù)量或校車行駛距離，從而降低校車運(yùn)營成本.文獻(xiàn)[3]分析紐約市路徑問題的各個(gè)方面，包括在曼哈頓區(qū)建立路線，并提供一種解決方案，方案的校車數(shù)量遠(yuǎn)遠(yuǎn)少于目前使用的校車數(shù)量.文獻(xiàn)[4]開發(fā)了一個(gè)解決方案程序，分別考慮每個(gè)目標(biāo)并搜索一組有效的解決方案，而不是單一的最優(yōu)解決方案.文獻(xiàn)[5]以車輛數(shù)為優(yōu)化目標(biāo)，設(shè)計(jì)了一個(gè)“后啟發(fā)”算法進(jìn)行求解，求解過程中對(duì)不同車型的校車進(jìn)行分配，并不考慮不同車型的固定成本和可變成本的差異.孟凡超等[6]利用禁忌搜索進(jìn)行求解，主要采用插入法和交換法獲取鄰域解.以上算法僅考慮了車輛容量約束，優(yōu)化目標(biāo)是最小化車輛行駛距離，主要利用已有求解VRP(vehicle routing problem)的算法框架，通過引入需求拆分算子進(jìn)行求解.

本文側(cè)重于校車的最少運(yùn)營數(shù)問題，對(duì)校車問題進(jìn)行定義和描述，將問題分為極限情況和一般情況，針對(duì)不同情況設(shè)計(jì)了SBLS(school bus limit situation)算法和SBGS(school bus general situation)算法，并在沈陽市某校進(jìn)行實(shí)驗(yàn)驗(yàn)證，達(dá)到了運(yùn)營成本降低的預(yù)期效果.

1 上下學(xué)時(shí)校車的最少運(yùn)營數(shù)量問題

1.1 問題定義

校車無混載指的是一輛校車只為一所學(xué)校服務(wù)，一輛校車只負(fù)責(zé)一個(gè)學(xué)校學(xué)生的上下學(xué)接送[7].將一所學(xué)校全部乘校車的學(xué)生作為一個(gè)優(yōu)化的目標(biāo)，對(duì)校車乘降站、校車行駛路徑、校車數(shù)量和每輛校車負(fù)責(zé)接送哪些學(xué)生進(jìn)行優(yōu)化.由于高額的運(yùn)營費(fèi)用以及不同于公交客運(yùn)的運(yùn)營模式，因此減少校車的數(shù)量即從源頭上降低了校車的運(yùn)營成本.若只考慮成本而無限減少校車數(shù)量將會(huì)造成行程路徑的增加和時(shí)間的延長，導(dǎo)致學(xué)生可能上學(xué)遲到、家長滿意度下降等問題.解決該問題就是在確保學(xué)生正常上下學(xué)的基礎(chǔ)上，將運(yùn)營成本降到最低.

1.2 問題描述

具體分為兩種情況描述上下學(xué)校車的最少運(yùn)營數(shù)量問題，即極限情況和一般情況.

極限情況：U學(xué)校只有1輛校車，要完成送S個(gè)學(xué)生上學(xué).該情況下校車的數(shù)量最少，校車的利用率最高，空載率最低，校車公司收益最大，但是每個(gè)學(xué)生的到校時(shí)間最晚，最早上車的學(xué)生乘車時(shí)間最長.

該問題可以抽象為在m個(gè)乘降站中選擇某一個(gè)特定的乘降站作為起點(diǎn)，將學(xué)校作為終點(diǎn)，選擇一條能夠遍歷所有乘降站的最短的校車行駛路線.考慮到該情況下路線具有雙向性，該情況下上學(xué)的最優(yōu)路線也是放學(xué)送學(xué)生回家的最優(yōu)路線.因此時(shí)這個(gè)問題就是一個(gè)單源點(diǎn)的頂點(diǎn)遍歷最短路徑問題，可以采用本文提出的SBLS算法求解.解題時(shí)將其源點(diǎn)和終點(diǎn)互換，避免m個(gè)乘降站作為源節(jié)點(diǎn)時(shí)的m個(gè)方案之間的比較，使得運(yùn)算時(shí)間降低m倍.

一般情況：U學(xué)校有n輛校車，接送S個(gè)學(xué)生放學(xué)上學(xué)，此時(shí)n

該問題首先需要在m個(gè)乘降站中選擇n個(gè)乘降站作為n輛校車的起始出發(fā)點(diǎn).考慮到每個(gè)乘降站都有可能成為校車的出發(fā)點(diǎn)，這使得計(jì)算復(fù)雜度增加m!/((m-n)!n!).該情況下路線仍然具有雙向性，上學(xué)時(shí)的最優(yōu)解也是放學(xué)時(shí)的最優(yōu)解，可以將上學(xué)問題轉(zhuǎn)化為放學(xué)問題，將學(xué)校作為起點(diǎn)，將m個(gè)乘降站中的n個(gè)乘降站作為終點(diǎn).

此時(shí)該問題可以抽象為：每輛校車都有一個(gè)最遠(yuǎn)的行駛距離，保證最后下車學(xué)生能夠在給定時(shí)間內(nèi)按時(shí)到家；每輛校車最多載學(xué)生30人；第1輛校車選擇運(yùn)送某個(gè)學(xué)生時(shí)，該校車的座位數(shù)量和剩余行駛距離都會(huì)減少，第1輛校車要在保證運(yùn)載人數(shù)和最遠(yuǎn)的行駛距離都不超標(biāo)的條件下，盡可能的多挑選學(xué)生乘坐該校車.此時(shí)問題就變成了一個(gè)0-1的背包問題[8]，下面采用SBGS算法來解決該問題.

第1輛校車采用SBGS算法挑選完其運(yùn)載的學(xué)生之后，第2輛校車從剩余的沒被第一輛校車選走的學(xué)生中再次采用SBGS算法挑選第2輛校車要運(yùn)載的學(xué)生.以此類推，直到第n輛校車挑選完最后一個(gè)學(xué)生為止.此時(shí)n就是所需的最少的校車數(shù)量.

通過SBGS算法可以有效地確定出每輛校車應(yīng)該運(yùn)送的學(xué)生是誰，再根據(jù)這些學(xué)生到達(dá)的乘降站，采用SBLS算法獲得該校車遍歷這些乘降站的最短行駛路徑.

上學(xué)時(shí)校車的最少運(yùn)營數(shù)量問題是放學(xué)校車最少運(yùn)營數(shù)的等價(jià)反問題，其采用放學(xué)校車最少運(yùn)營數(shù)給出的求解方法.

2 算法設(shè)計(jì)

2.1 SBLS算法

SBLS算法用來確定地圖上學(xué)校為起點(diǎn)某個(gè)乘降站為終點(diǎn)的最短路徑，并且該路徑必經(jīng)過特定的其他頂點(diǎn).

SBLS算法解決的問題是基于圖論的，但是并不是圖論中的經(jīng)典問題.乘降站和學(xué)校都被視為一個(gè)圖G的頂點(diǎn)V，連接乘降站和學(xué)校道路被看成是該圖G的邊E.每條邊無方向但是有權(quán)重W，權(quán)重W就是該路徑的長度.該圖G上任意兩個(gè)頂點(diǎn)V有邊E，地理因素決定所有頂點(diǎn)V都是相鄰頂點(diǎn)，例如：所有的乘降站之間、學(xué)校和乘降站之間在地理上都會(huì)有一條可以行使的路線，即地理上任何兩個(gè)地點(diǎn)之間都會(huì)有至少一條道路連通[9].

綜上，圖G可以看成是一個(gè)無向有權(quán)重全連通圖，SBLS算法就是在圖G中找到一條以學(xué)校為起點(diǎn)，能夠遍歷所有其他頂點(diǎn)的最短路徑.

SBLS算法解決的問題就是一個(gè)單源點(diǎn)的遍歷最短路徑問題，求得從學(xué)校途經(jīng)指定的所有乘降站的一條最短的遍歷路徑.

2.2 SBGS算法

U學(xué)校需要n輛校車完成學(xué)生放學(xué)后送學(xué)生回家的任務(wù).第一輛校車C1要在U學(xué)校的m個(gè)乘降站選擇e1個(gè)乘降站作為校車C1負(fù)責(zé)到達(dá)的乘降站.校車C1一旦選擇了m個(gè)乘降站中的e1個(gè)乘降站，則選擇的e1個(gè)乘降站分別是：P1，P2，P3，…，Pi，…，Pe1-1，Pe1.

校車C1創(chuàng)造的總的運(yùn)營價(jià)值(下車人數(shù))V1=S1+S2+S3+…+Si+…+Se1-1+Se1.

校車C1消耗的總的運(yùn)營成本(行駛距離)G1=D1+D2+D3+…+Di+…+De1-1+De1.

校車C1要在m個(gè)乘降站選擇e1個(gè)乘降站使校車C1創(chuàng)造的總的運(yùn)營價(jià)值V1盡可能的大.V1越大表示校車C1裝載的學(xué)生人數(shù)越多，即充分利用了每輛校車，但是V1一般要≤20人或者≤30人.

同時(shí)，校車C1要在m個(gè)乘降站選擇e1個(gè)乘降站，使消耗的總的運(yùn)營成本G1≤L.L是一輛校車的一次行駛最大距離，規(guī)定校車一次行駛最大距離L是為了保證家距離學(xué)校很遠(yuǎn)的學(xué)生也能夠在放學(xué)后的1 h內(nèi)到家.L的具體設(shè)定取決于實(shí)際情況，由家長和學(xué)校共同商討確定.

問題簡化：1個(gè)學(xué)校，n輛校車，m個(gè)乘降站.

校車C1要在m個(gè)乘降站選擇e1個(gè)乘降站，使校車C1消耗的總的運(yùn)營成本G1≤L，同時(shí)創(chuàng)造的總的運(yùn)營價(jià)值V1盡可能的大.

校車C2要在m-e1個(gè)乘降站選擇e2個(gè)乘降站，使校車C2消耗的總的運(yùn)營成本G2≤L，同時(shí)創(chuàng)造的總的運(yùn)營價(jià)值V2盡可能的大.

校車C3要在m-e1-e2個(gè)乘降站選擇e3個(gè)乘降站，使校車C3消耗的總的運(yùn)營成本G3≤L，同時(shí)創(chuàng)造的總的運(yùn)營價(jià)值V3盡可能的大.

以此類推，校車Ci要在m-e1-e2-e3-…-ei-1個(gè)乘降站選擇ei個(gè)乘降站，使校車Ci消耗的總的運(yùn)營成本Gi≤L，同時(shí)創(chuàng)造的總的運(yùn)營價(jià)值Vi盡可能的大.

以此類推，校車Cn要在m-e1-e2-e3-…-en-1個(gè)乘降站選擇en個(gè)乘降站，使校車Cn消耗的總的運(yùn)營成本Gn≤L，同時(shí)創(chuàng)造的總的運(yùn)營價(jià)值Vn盡可能的大.

該問題本質(zhì)上屬于0-1背包問題，可以采用動(dòng)態(tài)規(guī)劃的方法求解.

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

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

實(shí)驗(yàn)選取沈陽市某校 U為例，學(xué)生數(shù)據(jù)為該學(xué)校周邊范圍內(nèi)就讀于該校的學(xué)生信息.所獲得的數(shù)據(jù)信息見表1.信息包括10個(gè)屬性:學(xué)生的ID(5位數(shù)字)、學(xué)校名稱(本實(shí)驗(yàn)以U 校為例)、年級(jí)、班級(jí)、性別、上學(xué)出行方式、放學(xué)出行方式，上學(xué)離家時(shí)間、乘校車意愿、家庭住址.其中乘校車意愿中 0 表示不愿意乘坐校車，1 表示愿意乘坐校車，后續(xù)數(shù)據(jù)對(duì)其統(tǒng)計(jì)篩選.

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

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

3.2.1 SBLS算法

如圖1所示，假設(shè)學(xué)校U是圖G的頂點(diǎn)a，4個(gè)乘降站分別是圖G的4個(gè)頂點(diǎn)b、c、d、e.圖G是全連通圖，5個(gè)頂點(diǎn)之間都有連通的路徑，原因是地理上任意兩個(gè)點(diǎn)之間都有道路的連通.

每條路徑都有權(quán)重，例如連接頂點(diǎn)a和頂點(diǎn)b之間的邊Eab的權(quán)值可以通過使用SBLS算法獲得，即SBLS中每條邊的權(quán)值都是通過最短路徑算法計(jì)算出來的，表示兩個(gè)頂點(diǎn)之間的最短路徑的長度.校車從頂點(diǎn)a出發(fā)，遍歷4個(gè)頂點(diǎn)b、c、d、e.

如圖2所示，全連通圖G中有5個(gè)頂點(diǎn)，因此圖G中有10條邊.抽象圖G中邊的幾何長度不表示權(quán)重，每條邊的權(quán)重可以通過前面的SBLS算法求出，結(jié)果如表2所示，例如邊Eba的權(quán)重為1.1 km.

圖2 U學(xué)校和4個(gè)乘降站在圖G中抽象位置關(guān)系Fig.2 Abstract positional relationship in figure G of U school and 4 boarding and landing stations

表2 全連通圖G中每條邊的權(quán)重Table 2 Weights of each edge in the fully connected graph G km

圖G中以頂點(diǎn)a為源點(diǎn)，遍歷頂點(diǎn)b、c、d、e的路徑共有(5-1)!=24條(見圖3).

SBLS算法基于Branch Bounding思想以廣度優(yōu)先的方式搜索圖3中的樹，找到最優(yōu)路徑所在的分支，即權(quán)重之和最小的分支[10].在實(shí)現(xiàn)SBLS的過程中可以引入堆棧存儲(chǔ)的方式來增加SBLS的運(yùn)行效率.把搜索過程看作是對(duì)一棵樹的遍歷，那么剪枝就是將樹中不能得到最優(yōu)解的結(jié)點(diǎn)剪掉[11].

SBLS算法從G的源點(diǎn)a和空隊(duì)列開始.結(jié)點(diǎn)a被擴(kuò)展之后，其子結(jié)點(diǎn)b、c、d、e被依次插入隊(duì)列當(dāng)中；然后取出隊(duì)頭元素，進(jìn)行下一步擴(kuò)展，保證每一次擴(kuò)展時(shí)，源點(diǎn)a到當(dāng)前節(jié)點(diǎn)的和都是最小.具體的解空間圖如圖3所示.

SBLS算法過程：SBLS算法先從源節(jié)點(diǎn)a開始擴(kuò)展，4個(gè)子結(jié)點(diǎn)b、c、d、e被插入到隊(duì)列當(dāng)中，如表3所示.

表3 SBLS算法的活節(jié)點(diǎn)隊(duì)列Table 3 Live node queue of SBLS algorithm

取出結(jié)點(diǎn)a-b，它有3個(gè)子樹.因?yàn)镋cb=1 km Eea=9.5 km，所以結(jié)點(diǎn)a-b的子樹b-e沒有得到優(yōu)化，該子樹被刪除.結(jié)點(diǎn)a-b沿邊Ecb和Edb擴(kuò)展到頂點(diǎn)c和d時(shí)，將他們加入優(yōu)先隊(duì)列，如表4所示.

表4 SBLS算法的活節(jié)點(diǎn)隊(duì)列Table 4 Live node queue of SBLS algorithm

取出頭結(jié)點(diǎn)a-c，它有3個(gè)子樹.因?yàn)镋cb=1 kmEea=9.5 km，所以結(jié)點(diǎn)a-c的子樹c-e沒有得到優(yōu)化，該子樹被刪除.結(jié)點(diǎn)a-c沿邊Ecb和Edc擴(kuò)展到頂點(diǎn)b和d時(shí)，將他們加入優(yōu)先隊(duì)列，如表5所示

表5 SBLS算法的活節(jié)點(diǎn)隊(duì)列Table 5 Live node queue of SBLS algorithm

重復(fù)上面操作直到隊(duì)列為空.

3.2.2 SBGS算法

下面以校車C1為例，給出校車C1在m個(gè)乘降站里選擇e1個(gè)乘降站的具體計(jì)算方法.

V1(Pi,G1)=

(1)

(2)

Pi表示C1可選的乘降站為Pi，…，Pe1-1，Pe1;G1表示校車C1消耗的總的運(yùn)營成本(行駛距離);V1(Pi,G1)表示乘降站為Pi、運(yùn)營成本為G1時(shí)校車C1創(chuàng)造的總的運(yùn)營價(jià)值(下車人數(shù)).

以學(xué)校U為例，學(xué)校U有7名學(xué)生乘坐校車C1回家，該7名學(xué)生的乘降站位置選擇方法如前文所述，共有7個(gè)乘降站，如圖4所示.7個(gè)乘降站的地理位置、運(yùn)營價(jià)值、運(yùn)營成本見表6.

圖4 U學(xué)校和7個(gè)乘降站的位置Fig.4 Location of U school and 7 boarding and landing stations

表6 7個(gè)乘降站的地理位置、運(yùn)營價(jià)值和運(yùn)營成本Table 6 Geographical location,operational value and operating costs of the seven boarding and landing stations

每個(gè)乘降站有1名學(xué)生下車，因此校車C1途經(jīng)每個(gè)乘降站的運(yùn)營價(jià)值都是1.校車C1為了到達(dá)某個(gè)乘降站Pi而行駛的距離Di取決于校車C1的前一個(gè)途經(jīng)的乘降站Pi-1.因此,校車C1到達(dá)乘降站Pi的運(yùn)營成本(行駛距離)Di是一個(gè)動(dòng)態(tài)變量，取決于出發(fā)點(diǎn)，如表7所示.

表7 不同起始點(diǎn)的7個(gè)乘降站的動(dòng)態(tài)運(yùn)營成本Table 7 Dynamic operating costs of 7 boarding and landing stations with different starting points

校車C1沿著不同順序到達(dá)7個(gè)乘降站時(shí)，所消耗運(yùn)營成本將會(huì)發(fā)生動(dòng)態(tài)變化.到達(dá)同一個(gè)乘降站也會(huì)隨著起始點(diǎn)的不同而產(chǎn)生不同的成本.表8給出了7種順序得到的全部成本.

表8 校車C1搜索7次的每一次運(yùn)營成本Table 8 Each operating cost of the school bus C1 search 7 times

通過上述SBGS算法,可以得出校車C1到達(dá)哪些乘降站，這些乘降站的數(shù)量是e1，以及到達(dá)上述e1個(gè)乘降站的順序.然后再次使用SBGS算法在剩余的m-e1個(gè)乘降站中選擇出e2個(gè)乘降站作為校車C2的到達(dá)目的地，同時(shí)也獲得最短行駛路徑下的到達(dá)上述e2個(gè)乘降站的順序.

依次反復(fù)使用SBGS算法，直到所有的乘降站都被選擇完畢，則此時(shí)所需的校車數(shù)量、每輛校車負(fù)責(zé)的乘降站集合、每輛校車到達(dá)各自負(fù)責(zé)的多個(gè)乘降站的最短路徑都可以被依次求出.

4 總 結(jié)

針對(duì)無混載校車路徑規(guī)劃問題，查詢部分中小學(xué)校的上下學(xué)時(shí)間、學(xué)生的家庭住址和學(xué)校地址，充分調(diào)研沈陽市交通情況，綜合考慮校車運(yùn)營方式和盈利方法，對(duì)實(shí)際的校車運(yùn)營問題進(jìn)行分析，把經(jīng)典的校車路徑規(guī)劃問題拆分為校車最短路徑與最少運(yùn)營數(shù).重點(diǎn)關(guān)注校車數(shù)量，提出了SBLS算法和SBGS算法.實(shí)驗(yàn)結(jié)果表明：運(yùn)用算法后的行車距離更短，校車數(shù)量減少，達(dá)到了降低運(yùn)營成本的預(yù)期效果.

采用圖論的方法，推導(dǎo)了不同情況下校車數(shù)量與校車路徑之間的計(jì)算關(guān)系，闡述了不同運(yùn)營方式所產(chǎn)生的行駛距離不同的情況.對(duì)校車數(shù)量問題設(shè)定兩種情況，不同情況給出不同的算法.極限情況作為一般情況的支撐，一般情況的SBGS算法加上極限情況SBLS算法為無混載校車路徑問題、校車運(yùn)營數(shù)量問題提供了解決方案.

文中在構(gòu)建校車路線優(yōu)化模型時(shí)沒有考慮城市交通的情況.事實(shí)上，由于校車運(yùn)營時(shí)間集中在早晚的城市交通高峰期，不可避免地出現(xiàn)交通擁堵現(xiàn)象，導(dǎo)致校車到達(dá)不及時(shí). 在這種情況下，一些學(xué)校調(diào)整了學(xué)校的上下學(xué)時(shí)間，在設(shè)計(jì)校車路線時(shí)做到基于學(xué)校上下學(xué)時(shí)間調(diào)整校車調(diào)度方案[12].后續(xù)將會(huì)在本研究的基礎(chǔ)上，考慮學(xué)校時(shí)間窗的調(diào)整，服務(wù)于錯(cuò)峰上學(xué)背景下的校車路徑問題；考慮實(shí)時(shí)交通情況，做出基于實(shí)時(shí)城市交通的校車路徑規(guī)劃；結(jié)合兩種情況的有混載校車路徑規(guī)劃，進(jìn)一步完善校車路徑問題在生活實(shí)際中的運(yùn)用.