李開(kāi)雷　白翰　燕翔　朱漫兮　王修光

摘要 為解決農(nóng)村地區(qū)校車路網(wǎng)布局中校方運(yùn)營(yíng)成本過(guò)高，以及乘車站點(diǎn)分布散亂導(dǎo)致校車服務(wù)質(zhì)量差的問(wèn)題，建立混載與不混載場(chǎng)景下多目標(biāo)校車路徑規(guī)劃問(wèn)題（SBRP）模型．在不混載情景下，構(gòu)建以學(xué)生出行成本和校方運(yùn)營(yíng)成本為優(yōu)化目標(biāo)的融合校車服務(wù)水平的SBRP數(shù)學(xué)模型;在混載情景下，構(gòu)建考慮校車投入成本與運(yùn)營(yíng)成本的SBRP數(shù)學(xué)模型．通過(guò)對(duì)比多個(gè)啟發(fā)式算法，確定基于模擬退火算法的求解流程和基于遺傳算法求解結(jié)果的橫向比對(duì)．最后，在國(guó)際基準(zhǔn)案例上進(jìn)行了測(cè)試，基于模擬退火算法引入不同搜索算子求解不同場(chǎng)景下構(gòu)建的SBRP數(shù)學(xué)模型，應(yīng)用于山東日照五蓮縣校車路徑優(yōu)化設(shè)計(jì)，結(jié)果表明不混載SBRP情景下，提出的方法較原校車運(yùn)營(yíng)方式，校車投入量、行駛里程、行程成本分別減少28.6％、37.8％、35.6％，考慮到學(xué)生的校車服務(wù)感知度，學(xué)生出行成本降低4.3％;由于混載情景的復(fù)雜性，難以有效兼顧出行成本，提出的方法較原校車運(yùn)營(yíng)方式的學(xué)生出行成本增加了0.5％，但校車投入量、行駛里程、行程成本分別減少37.5％、42.0％、35.8％，更好地驗(yàn)證了構(gòu)建模型的有效性及模擬退火算法相較于遺傳算法，能夠更大程度提高農(nóng)村地區(qū)校車服務(wù)質(zhì)量和降低校方運(yùn)營(yíng)成本．關(guān)鍵詞 公路運(yùn)輸管理;校車路徑問(wèn)題;混載;模擬退火算法;多目標(biāo);出行成本

中圖分類號(hào)U492.4

文獻(xiàn)標(biāo)志碼A

0 引言

目前，我國(guó)農(nóng)村交通發(fā)展總體上比較落后，校車服務(wù)在農(nóng)村地區(qū)并不完善．與城市校車站點(diǎn)的短距離線路長(zhǎng)度、高密度站點(diǎn)覆蓋模式不同的是，農(nóng)村校車站點(diǎn)多呈現(xiàn)為縱向延伸、分散布點(diǎn)的需求模式，農(nóng)村校車路徑規(guī)劃有待改善．校車路徑問(wèn)題（School Bus Routing Problem，SBRP）是在滿足校車容量、時(shí)間窗等約束條件下，合理地規(guī)劃校車線路將學(xué)生從乘車站點(diǎn)送到學(xué)校（或從學(xué)校返回乘車站點(diǎn)），并達(dá)到特定目標(biāo)的組合優(yōu)化問(wèn)題．自多校SBRP問(wèn)題的提出者Newton等［1］基于啟發(fā)式算法的生成校車路線和時(shí)刻表，使用二次規(guī)劃的方法規(guī)劃校車路網(wǎng)以來(lái)，眾多學(xué)者一直在探索相關(guān)的數(shù)學(xué)模型、優(yōu)化算法及其應(yīng)用．為解決校車路徑問(wèn)題，Jaradat等［2］以校車容量、最大乘車時(shí)間和學(xué)校時(shí)間窗為目標(biāo)，采用智能水滴算法（Intelligent Water Drops，IWD）優(yōu)化求解．Calvete等［3］提出一種局部分配局部搜索算法，求解帶有停車位選擇的校車路徑問(wèn)題．高巍等［4］側(cè)重于校車的最少運(yùn)營(yíng)數(shù)問(wèn)題，對(duì)校車問(wèn)題進(jìn)行定義和描述，將問(wèn)題分為極限情況和一般情況，針對(duì)不同情況設(shè)計(jì)了SBLS（School Bus Limit Situation）算法和SBGS（School Bus General Situation）算法．關(guān)于混載SBRP，Hargroves等［5］指明了研究方向，但未構(gòu)建相關(guān)模型與算法進(jìn)行求解．Hou等［6］構(gòu)建了一種混合迭代局部搜索 （ILS） 元啟發(fā)式算法，可用于具有多種規(guī)劃場(chǎng)景的 SBRP，包括同質(zhì)或異構(gòu)車隊(duì)、單載或混載運(yùn)行模式．Park等［7］提出一種將多校SBRP問(wèn)題分解為單校SBRP問(wèn)題，使用掃描算法優(yōu)化單校路線，再合并優(yōu)化的單校線路結(jié)果的新型混載改進(jìn)算法．Semba等［8］運(yùn)用模擬退火（Simulated Annealing，SA）、禁忌搜索（Tabu Search，TS）和蟻群優(yōu)化（Ant Colony Optimization，ACO）三種元啟發(fā)式算法求解多校SBRP問(wèn)題的模型，對(duì)三種算法性能進(jìn)行了實(shí)證比較．

上述文獻(xiàn)對(duì)多校SBRP進(jìn)行了研究，但對(duì)農(nóng)村地區(qū)校車服務(wù)過(guò)于重視校車運(yùn)營(yíng)方成本，而服務(wù)質(zhì)量問(wèn)題未能深度探討．本文針對(duì)學(xué)生出行成本，即學(xué)生對(duì)校車服務(wù)的感知度，建立一種基于學(xué)生出行成本和服務(wù)協(xié)調(diào)的不混載校車路網(wǎng)布局模型，在保證校車服務(wù)質(zhì)量的條件下，優(yōu)化校車路徑減少校車運(yùn)營(yíng)里程從而降低校方運(yùn)營(yíng)成本;混載情景下，則是從校車購(gòu)置和運(yùn)營(yíng)成本兩方面出發(fā)，建立混載優(yōu)化模型．引入不同搜索算子的模擬退火算法（SA）和遺傳算法（Genetic Algorithm，GA）在國(guó)際基準(zhǔn)案例上的測(cè)試結(jié)果表明，SA算法具有良好的適用性，兩種情景下構(gòu)建的模型能夠提高農(nóng)村地區(qū)校車服務(wù)質(zhì)量、降低校方運(yùn)營(yíng)成本．

1 問(wèn)題描述與數(shù)據(jù)介紹

1.1 問(wèn)題描述

某學(xué)區(qū)內(nèi)有若干學(xué)校，每所學(xué)校擁有一輛或多輛校車，學(xué)生只允許在本校站點(diǎn)上下車．學(xué)校、乘車站點(diǎn)、場(chǎng)站的數(shù)量與坐標(biāo)已知，每個(gè)站點(diǎn)學(xué)生數(shù)量及該站點(diǎn)學(xué)生的目標(biāo)學(xué)校已知，校車數(shù)量和校車容量已知．每個(gè)站點(diǎn)僅能由一輛校車進(jìn)行服務(wù)且至少一名學(xué)生候車．在不混載情景下，同一校車上不能同時(shí)乘坐去往不同學(xué)校的學(xué)生，需要考慮校車到站點(diǎn)的上下車服務(wù)時(shí)間，以及所有學(xué)生在學(xué)校規(guī)定的時(shí)間窗內(nèi)到達(dá)，保證學(xué)生出行成本最小，降低校方運(yùn)營(yíng)成本;在混載情景下，每輛校車為不同的學(xué)校提供服務(wù)，同樣需要考慮上下車服務(wù)時(shí)間，設(shè)置學(xué)生的最大乘車時(shí)間．

1.2 數(shù)據(jù)介紹

Park等［7］于2012年提出了校車路網(wǎng)布局問(wèn)題的通用數(shù)據(jù)測(cè)試集，并將校車站點(diǎn)與學(xué)校布局的共性總結(jié)為RSRB與CSCB兩種類型，其中“R”與“C”分別意為隨機(jī)和聚集，“S”與“B”分別表示學(xué)校與站點(diǎn)，即RSRB的學(xué)校與站點(diǎn)坐標(biāo)的分布是隨機(jī)的，而CSCB將去往不同學(xué)校的學(xué)生站點(diǎn)進(jìn)行站點(diǎn)布置時(shí)，形成數(shù)個(gè)集群中心，且不同的學(xué)校也集中在同一區(qū)域中．

山東省日照市五蓮縣位于山東半島中南部，總面積為1 497 km²，常住人口49.98 萬(wàn)．本文選取五蓮縣城區(qū)進(jìn)行校車路網(wǎng)的布局實(shí)例研究．研究區(qū)道路眾多，但部分道路過(guò)窄、路面質(zhì)量不佳．研究區(qū)實(shí)例學(xué)校6 所，在讀學(xué)生共4 522人，其中乘坐校車的學(xué)生795 名．由圖1可知，實(shí)例學(xué)區(qū)屬于學(xué)校分散站點(diǎn)分散型案例，即RSRB．

2 建立數(shù)學(xué)模型

2.1 參數(shù)和決策變量

2.2 構(gòu)建模型

2.2.1 不混載情景下線性規(guī)劃數(shù)學(xué)模型

2.2.2 混載情景下線性規(guī)劃數(shù)學(xué)模型

3 求解算法

3.1 算法框架選取

遺傳算法是校車問(wèn)題中最常用的，因?yàn)檫z傳算法將目標(biāo)函數(shù)定為搜索信息，故求解多目標(biāo)函數(shù)具有優(yōu)勢(shì)．遺傳算法在搜索時(shí)遵循概率，全局性較強(qiáng)，具有一定的隨機(jī)性和靈活性，能大大減少參數(shù)對(duì)結(jié)果的干擾，但存在容易陷入過(guò)早收斂、對(duì)約束條件的表達(dá)不全面、對(duì)初始種群依賴性較強(qiáng)等缺點(diǎn)，影響多校問(wèn)題結(jié)果的準(zhǔn)確性［13-14］．蟻群算法（ACO）雖然在使用上更加靈活，還可通過(guò)和其他啟發(fā)式算法結(jié)合提升算法的求解能力，但是計(jì)算量大、求解時(shí)間長(zhǎng)，無(wú)法適應(yīng)大規(guī)模問(wèn)題，而且在進(jìn)行搜索時(shí)，容易因所有個(gè)體得出的解一致性造成運(yùn)算終止，不利于得出最優(yōu)解［15］．模擬退火算法相較于上述兩種算法具有更高的運(yùn)算效率、更短的運(yùn)算時(shí)間，且不受初始解的影響，并且該算法可以使模型中復(fù)雜的約束直觀明了地展示在算法結(jié)構(gòu)中［16-18］．當(dāng)然，模擬退火算法在搜索過(guò)程中容易陷入局部最優(yōu)，很難保證一次輸出最優(yōu)解，但可以通過(guò)多次代入求解取最優(yōu)解決這一問(wèn)題．綜合考慮研究數(shù)據(jù)量大、模型約束條件多、計(jì)算復(fù)雜等因素，故不混載與混載情景下構(gòu)建的模型均以基于模擬退火算法為框架，并引入不同鄰域搜索算子求解模型．為了更好地驗(yàn)證文中構(gòu)建模型采用模擬退火算法的優(yōu)越性，將求解結(jié)果與遺傳算法求解模型結(jié)果進(jìn)行橫向?qū)Ρ龋?/p>

3.2 鄰域搜索算子

不混載情景下采用shift、swap、2-opt三種常規(guī)搜索算子，而混載情景下算法求解時(shí)路徑間以及路徑內(nèi)的鄰域搜索算子都是成對(duì)移動(dòng)的．因此，結(jié)合問(wèn)題特性引入PD-Shift、PD-Exchange、PD-Rearrange三種鄰域算子［19］，其主要描述如下：

1） PD-Shift：將一對(duì)點(diǎn)“P”與“D”從路線1移動(dòng)至路線2，在移動(dòng)時(shí)需要受到優(yōu)化目標(biāo)模型中所有約束的限制，并禁止不可行的移動(dòng)，其操作示意如圖2所示．

2） PD-Exchange：交換兩條線路中的“P”與“D”點(diǎn)對(duì)．如圖3所示，“P1”與“D1”是線路1中的點(diǎn)對(duì)，“P2”與“D2”是線路2中的點(diǎn)對(duì)，首先從線路1與線路2中將這兩組點(diǎn)對(duì)刪除，繼而將“P1”與“D1”插入線路2中的可行位置，“P2”與“D2”插入線路1的可行位置．

3） PD-Rearrange：在相同的路徑中，通過(guò)重新排列，將“P”與“D”點(diǎn)對(duì)放置到最佳位置，從而最大限度地降低目標(biāo)函數(shù)的值．如圖4所示，“P”與“D”是某線路的一組點(diǎn)對(duì)，通過(guò)PD-Rearrange操作，將其在線路中刪除，然后將它們插入到同一線路中新的可行位置．

鄰域搜索的最終結(jié)果往往過(guò)度關(guān)注總里程［20］，與校車行駛路徑優(yōu)化相比，校車的投入數(shù)目才是影響校方運(yùn)營(yíng)成本的首要因素．因此每個(gè)局部搜索算子完成搜索產(chǎn)生新的鄰域解后，實(shí)現(xiàn)Metropolis判斷準(zhǔn)則［21］，評(píng)價(jià)函數(shù)為

4 實(shí)驗(yàn)驗(yàn)證及數(shù)據(jù)測(cè)試

4.1 測(cè)試案例及參數(shù)設(shè)定

參數(shù)設(shè)置為校車容量Q為66 人，校車平均行駛速度v約32 km／h，考慮到服務(wù)水平，規(guī)定學(xué)生在校車上允許的最大乘車時(shí)間為2 700 s，最后設(shè)置一個(gè)位于中心位置的校車場(chǎng)站0．?dāng)?shù)據(jù)集提供學(xué)校坐標(biāo)、站點(diǎn)坐標(biāo)以及站點(diǎn)需求等，如表2所示．

4.2 不混載情景下實(shí)驗(yàn)結(jié)果分析

由于現(xiàn)有文獻(xiàn)無(wú)同情景下不混載、站點(diǎn)需求不拆分的閉合回路服務(wù)模式使用測(cè)試集計(jì)算的數(shù)據(jù)，因此構(gòu)建模型的求解結(jié)果對(duì)比數(shù)據(jù)為不混載情景下僅選取運(yùn)營(yíng)里程為優(yōu)化目標(biāo)的一般模型所得出的結(jié)果，如表3所示．其中N1，Dm1，Dc1，Tc1分別表示一般模型求解結(jié)果的校車數(shù)量、行駛里程、行駛和學(xué)生出行成本，N2，Dm2，Dc2，Tc2分別表示構(gòu)建模型求解結(jié)果的校車數(shù)量、行駛里程、行駛和學(xué)生出行成本．由表3可知，構(gòu)建的模型綜合考慮了校車運(yùn)營(yíng)時(shí)的行駛成本與學(xué)生出行成本情況，校車的投入數(shù)量平均減少14.1％，行駛里程平均降低14.4％，行駛成本平均降低14.2％，校方運(yùn)營(yíng)成本大部分來(lái)源于校車的購(gòu)入，因此校車投入量的減少也從根本上降低了校方的投入成本．考慮使學(xué)生出行成本盡可能地達(dá)到最優(yōu)，但到校模式下每輛校車服務(wù)具有很強(qiáng)的針對(duì)性，故學(xué)生出行成本平均降低0.26％．

4.3 混載情景下模型實(shí)驗(yàn)結(jié)果分析

多?；燧d情景下構(gòu)建模型求解結(jié)果的對(duì)比數(shù)據(jù)選擇測(cè)試集在同情景下單一模型求解結(jié)果，如表4所示．其中Ni，Dmi，Dci，Tci（i=1，2）含義同上．從表4可知，以校車數(shù)量與運(yùn)行里程為目標(biāo)優(yōu)化后的模型比單一目標(biāo)模型總體上更具有優(yōu)勢(shì)，以及PD三種搜索算子的加入使站點(diǎn)之間實(shí)現(xiàn)更多的可行交換，對(duì)路線的優(yōu)化明顯提升，因此校車的平均投入量減少7.9％，校車行駛里程平均下降7.6％，行程成本平均下降7.5％，學(xué)生出行成本平均上升0.11％．

4.4 實(shí)例驗(yàn)證：五蓮縣校車路徑優(yōu)化設(shè)計(jì)

4.4.1 橫向?qū)Ρ冉Y(jié)果

不混載情景下遺傳算法和模擬退火算法求解規(guī)劃結(jié)果如表6所示，混載情景下遺傳算法和模擬退火算法求解規(guī)劃結(jié)果如表7所示．將模擬退火算法求解模型結(jié)果和求解結(jié)果橫向?qū)Ρ龋换燧d情景下，模擬退火算法比遺傳算法的校車數(shù)量、行駛里程、行駛成本、出行成本分別平均下降14.28％、19.67％、20.96％、3.60％;混載情景下，模擬退火算法比遺傳算法的校車數(shù)量、行駛里程、行駛成本、出行成本分別平均下降7.14％、15.17％、17.14％、2.72％．雖然遺傳算法相對(duì)于原校車服務(wù)模式不論是混載和不混載情景下校車數(shù)量、行駛里程、行駛成本均有所改善，但是相較于模擬退火算法求解結(jié)果的優(yōu)勢(shì)略顯不足．

4.4.2 縱向?qū)Ρ冉Y(jié)果

不混載和混載情景下校車路網(wǎng)布局結(jié)果分別如圖5和圖6所示，輸出的路網(wǎng)布局站點(diǎn)與站點(diǎn)之間為直線連接，需要與實(shí)例區(qū)域的現(xiàn)狀可通行路網(wǎng)相結(jié)合，在輸出的路網(wǎng)布局結(jié)果為基礎(chǔ)進(jìn)行調(diào)整，排除無(wú)法通行的站點(diǎn)連接路段．

不混載情景下的校車路網(wǎng)布局較原校車服務(wù)模式縱向?qū)Ρ?，校車的投入?shù)量減少28.6％，而校車運(yùn)營(yíng)的成本很大部分都來(lái)源于校車的購(gòu)入，因此校車投入量的減少也從根本上降低了校車投入成本．在運(yùn)營(yíng)里程上，不混載情景下優(yōu)化不同學(xué)校服務(wù)路徑之間的銜接，使校車行駛里程降低37.8％，行駛成本降低35.6％．考慮使學(xué)生出行成本盡可能達(dá)到最優(yōu)，使學(xué)生獲得更好的乘車體驗(yàn)，但到校模式下每輛校車服務(wù)具有很強(qiáng)的針對(duì)性，故學(xué)生出行成本降低4.3％．

混載情景下的校車路網(wǎng)布局較原校車服務(wù)模式縱向?qū)Ρ?，無(wú)論是校車的投入還是校車運(yùn)營(yíng)過(guò)程中的資金投入都具有較大優(yōu)勢(shì)，校車的投入數(shù)量和行駛里程分別減少37.5％、42.0％．而且此情景下校車調(diào)用更加靈活，路徑方案之間的交替變換也產(chǎn)生更多的可能，行駛成本下降35.8％．但由于混載情景的復(fù)雜性，難以同時(shí)兼顧出行成本，也產(chǎn)生了最多的出行時(shí)間，在一定程度上降低了校車的服務(wù)水平，因此學(xué)生出行成本上略微高于原校車服務(wù)模式，增加了0.5％．

在不混載與混載兩種情景下，基于模擬退火算法和遺傳算法的校車路網(wǎng)布局結(jié)果與原校車服務(wù)模式縱橫向差異性對(duì)比，如圖7所示．

5 結(jié)論

文中以農(nóng)村地區(qū)多校SBRP為研究對(duì)象，考慮不同情景和優(yōu)化目標(biāo)，建立了基于校方運(yùn)營(yíng)成本和學(xué)生出行成本的不混載SBRP數(shù)學(xué)模型;考慮校方運(yùn)營(yíng)成本，建立了以校方運(yùn)營(yíng)成本和投入成本最低為目標(biāo)的混載SBRP數(shù)學(xué)模型．利用模擬退火算法和遺傳算法在國(guó)際基準(zhǔn)測(cè)試案例和國(guó)內(nèi)實(shí)例進(jìn)行分析，得出以下結(jié)論：

1） 橫向?qū)Ρ确治?，無(wú)論是不混載情景還是混載情景下，模擬退火算法比遺傳算法的校車數(shù)量、行駛里程、行駛成本、出行成本均有所下降，引入不同搜索算子的模擬退火算法求解構(gòu)建模型的結(jié)果較遺傳算法求解結(jié)果更具有優(yōu)勢(shì)，對(duì)文中構(gòu)建考慮多種優(yōu)化目標(biāo)的模型具有更強(qiáng)的針對(duì)性．

2） 縱向?qū)Ρ确治?，文中建立的不混載SBRP模型在兼容降低運(yùn)營(yíng)成本的同時(shí)可以有效提高農(nóng)村校車的服務(wù)水平，保證優(yōu)化校車的投入和總里程，平均降低行駛里程37.8％，降低校方運(yùn)營(yíng)成本分別為28.6％、35.6％，同時(shí)考慮學(xué)生的出行感知度，減少學(xué)生出行成本為4.3％，學(xué)生獲得更好的乘車體驗(yàn)．建立的混載SBRP模型能夠最大程度縮減運(yùn)營(yíng)成本分別為37.5％、35.8％，行駛里程降低了42.0％，且校車調(diào)用更加靈活，路徑方案之間的交替變換產(chǎn)生更多的可能，更有利于校方運(yùn)營(yíng)．

3） 值得指出的是，對(duì)于站點(diǎn)需求拆分及校車多車型的情景、求解模型的算法的進(jìn)一步改進(jìn)，以及混載情景下，不同的校車路網(wǎng)布局對(duì)學(xué)生等車時(shí)間的影響等，這將是下一步的研究方向．

參考文獻(xiàn) References

［1］Newton R M，Thomas W H.Bus routing in a multi-school system［J］.Computers ＆ Operations Research，1974，1（2）：213-222

［2］ Jaradat A S，Shatnawi M Q.Solving school bus routing problem by intelligent water drops algorithm［J］.Journal of Computer Science，2020，16（1）：25-34

［3］ Calvete H I，Galé C，Iranzo J A，et al.A partial allocation local search matheuristic for solving the school bus routing problem with bus stop selection［J］.Mathematics，2020，8（8）：1214

［4］ 高巍，陳澤穎，李大舟.基于校車數(shù)量的無(wú)混載校車路線問(wèn)題模型優(yōu)化實(shí)現(xiàn)［J］.沈陽(yáng)化工大學(xué)學(xué)報(bào)，2021，35（1）：82-89GAO Wei，CHEN Zeying，LI Dazhou.Optimization of the model of unmixed school bus route based on the number of school bus［J］.Journal of Shenyang University of Chemical Technology，2021，35（1）：82-89

［5］ Hargroves B T，Demetsky M J.A computer assisted school bus routing strategy：a case study［J］.Socio-Economic Planning Sciences，1981，15（6）：341-345

［6］ Hou Y，Zhao N，Dang L，et al.A hybrid metaheuristic algorithm for the school bus routing problem with multi-school planning scenarios［J］.Engineering Letters，2021，29（4）：1-10

［7］ Park J，Tae H，Kim B I.A post-improvement procedure for the mixed load school bus routing problem［J］.European Journal of Operational Research，2012，217（1）：204-213

［8］ Semba S，Mujuni E.An empirical performance comparison of meta-heuristic algorithms for school bus routing problem［J］.Tanzania Journal of Science，2019，45（1）：81-92

［9］ Braca J，Bramel J，Posner B，et al.A computerized approach to the New York City school bus routing problem［J］.IIE Transactions，1997，29（8）：693-702

［10］ 劉夢(mèng)琪，瞿何舟.基于軌道交通與常規(guī)公交組合的出行路徑選擇研究［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，2018，16（4）：63-68LIU Mengqi，QU Hezhou.Study on the route choice using the combination of rail and bus transit［J］.Journal of Transportation Engineering and Information，2018，16（4）：63-68

［11］ 馮煥煥，鄧建華.基于前景值和乘客最優(yōu)理論的居民公交出行選擇模型［J］.科學(xué)技術(shù)與工程，2019，19（5）：307-311

FENG Huanhuan，DENG Jianhua.Model of public transport choice based on prospect value and passenger optimal theory［J］.Science Technology and Engineering，2019，19（5）：307-311

［12］ Levin M W，Boyles S D.Practice summary：improving bus routing for KIPP charter schools［J］.Interfaces，2016，46（2）：196-199

［13］ 洪越，殷利平.基于遺傳算法的非高斯系統(tǒng)隨機(jī)分布控制［J］.南京信息工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，12（4）：504-509HONG Yue，YIN Liping.Genetic algorithm-based stochastic distribution control for non-Gaussian systems［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2020，12（4）：504-509

［14］ Minocha B，Tripathi S.Solving school bus routing problem using hybrid genetic algorithm：a case study［M］／／Advances in Intelligent Systems and Computing.New Delhi：Springer India，2014：93-103

［15］ 李燕，季建楠，沈葭櫟，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法［J］.南京信息工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，13（3）：298-303LI Yan，JI Jiannan，SHEN Jiali，et al.Mobile robot path planning based on improved ant colony algorithm［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2021，13（3）：298-303

［16］ 鄧紹強(qiáng)，郭宗建，李芳，等.基于Metropolis準(zhǔn)則的自適應(yīng)模擬退火粒子群優(yōu)化［J］.軟件導(dǎo)刊，2022，21（6）：85-91DENG Shaoqiang，GUO Zongjian，LI Fang，et al.Adaptive simulated annealing particle swarm optimization algorithm based on metropolis［J］.Software Guide，2022，21（6）：85-91

［17］ 李朝遷，裴建朝.新型模擬退火遺傳算法在路徑優(yōu)化的應(yīng)用［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2022（3）：52-55LI Chaoqian，PEI Jianchao.Application of new simulated annealing genetic algorithm in path optimization［J］.Modular Machine Tool ＆ Automatic Manufacturing Technique，2022（3）：52-55

［18］ Yu V F，Jewpanya P，Redi A A N P，et al.Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks［J］.Computers ＆ Operations Research，2021，129：105205

［19］ Li H B，Lim A.A metaheuristic for the pickup and delivery problem with time windows［J］.Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence （ICTAI 2001）.November 7-9，2001，Dallas，TX，USA.IEEE，2001：160-167

［20］ Bent R，Hentenryck P V.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows［J］.Computers ＆ Operations Research，2006，33（4）：875-893

［21］ Liu W W，Li X，Qin X N，et al.A metropolis criterion based fuzzy Q-learning flow controller for high-speed networks［J］.Applied Mechanics and Materials，2012，241／242／243／244：2327-2330

School bus routing considering operation and travel costs

LI Kailei BAI Han YAN Xiang ZHU Manxi WANG Xiuguang

1School of Transportation and Logistics Engineering，Shandong Jiaotong University，Jinan 250357

Abstract In order to solve the problems of high operating cost and poor service quality of school bus due to the scattered distribution of bus stops in rural areas，multi-objective SBRP （School Bus Routing Problem） models were developed for the mixed-load and non-mixed-load scenarios.In the non-mixed-load scenario，a model of the SBRP was developed to optimize the students travel cost and school operating cost，while in the mixed-load scenario，another model of the SBRP was developed to consider the input cost and operation cost of the school bus.Several heuristic algorithms were compared，based on which the simulated annealing algorithm was selected to solve the models，and the horizontal comparison of the solution results based on genetic algorithm were determined.Tests were conducted on an international bench mark case and the constructed models were solved by introducing different search operators into the simulated annealing algorithm，then the proposed approach was applied to the optimal design of school bus routes in Wulian county，Rizhao，Shandong province.The results showed that in the non-mixed-load scenario，compared with the original school bus operation mode，the school bus input，mileage and travel cost were reduced by 28.6％，37.8％ and 35.6％，respectively，and students travel cost was reduced by 4.3％ considering the students perception of school bus service.While in the mixed-load scenario，the proposed approach reduced the school bus input，mileage and travel cost by 37.5％，42.0％ and 35.8％，respectively;due to the complexity of the mixed-load scenario，it is difficult to take the travel cost into account，thus the students travel cost was increased by 0.5％.The proposed SBRP models were verified to be effective and the simulated annealing approach can optimize service quality and reduce operation cost of rural school bus to a greater extent than the genetic algorithm.

Key words highway transportation management;school bus routing problem （SBRP）;mixed-load;simulated annealing;multi-objective;travel cost