基于運營和出行成本的校車路徑問題研究

李開雷　白翰　燕翔　朱漫兮　王修光

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

中圖分類號U492.4

文獻標志碼A

0 引言

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

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

1 問題描述與數據介紹

1.1 問題描述

某學區內有若干學校，每所學校擁有一輛或多輛校車，學生只允許在本校站點上下車．學校、乘車站點、場站的數量與坐標已知，每個站點學生數量及該站點學生的目標學校已知，校車數量和校車容量已知．每個站點僅能由一輛校車進行服務且至少一名學生候車．在不混載情景下，同一校車上不能同時乘坐去往不同學校的學生，需要考慮校車到站點的上下車服務時間，以及所有學生在學校規定的時間窗內到達，保證學生出行成本最小，降低校方運營成本;在混載情景下，每輛校車為不同的學校提供服務，同樣需要考慮上下車服務時間，設置學生的最大乘車時間．

1.2 數據介紹

Park等［7］于2012年提出了校車路網布局問題的通用數據測試集，并將校車站點與學校布局的共性總結為RSRB與CSCB兩種類型，其中“R”與“C”分別意為隨機和聚集，“S”與“B”分別表示學校與站點，即RSRB的學校與站點坐標的分布是隨機的，而CSCB將去往不同學校的學生站點進行站點布置時，形成數個集群中心，且不同的學校也集中在同一區域中．

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

2 建立數學模型

2.1 參數和決策變量

2.2 構建模型

2.2.1 不混載情景下線性規劃數學模型

2.2.2 混載情景下線性規劃數學模型

3 求解算法

3.1 算法框架選取

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

3.2 鄰域搜索算子

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

1） PD-Shift：將一對點“P”與“D”從路線1移動至路線2，在移動時需要受到優化目標模型中所有約束的限制，并禁止不可行的移動，其操作示意如圖2所示．

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

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

鄰域搜索的最終結果往往過度關注總里程［20］，與校車行駛路徑優化相比，校車的投入數目才是影響校方運營成本的首要因素．因此每個局部搜索算子完成搜索產生新的鄰域解后，實現Metropolis判斷準則［21］，評價函數為

4 實驗驗證及數據測試

4.1 測試案例及參數設定

參數設置為校車容量Q為66 人，校車平均行駛速度v約32 km／h，考慮到服務水平，規定學生在校車上允許的最大乘車時間為2 700 s，最后設置一個位于中心位置的校車場站0．數據集提供學校坐標、站點坐標以及站點需求等，如表2所示．

4.2 不混載情景下實驗結果分析

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

4.3 混載情景下模型實驗結果分析

多校混載情景下構建模型求解結果的對比數據選擇測試集在同情景下單一模型求解結果，如表4所示．其中Ni，Dmi，Dci，Tci（i=1，2）含義同上．從表4可知，以校車數量與運行里程為目標優化后的模型比單一目標模型總體上更具有優勢，以及PD三種搜索算子的加入使站點之間實現更多的可行交換，對路線的優化明顯提升，因此校車的平均投入量減少7.9％，校車行駛里程平均下降7.6％，行程成本平均下降7.5％，學生出行成本平均上升0.11％．

4.4 實例驗證：五蓮縣校車路徑優化設計

4.4.1 橫向對比結果

不混載情景下遺傳算法和模擬退火算法求解規劃結果如表6所示，混載情景下遺傳算法和模擬退火算法求解規劃結果如表7所示．將模擬退火算法求解模型結果和求解結果橫向對比，不混載情景下，模擬退火算法比遺傳算法的校車數量、行駛里程、行駛成本、出行成本分別平均下降14.28％、19.67％、20.96％、3.60％;混載情景下，模擬退火算法比遺傳算法的校車數量、行駛里程、行駛成本、出行成本分別平均下降7.14％、15.17％、17.14％、2.72％．雖然遺傳算法相對于原校車服務模式不論是混載和不混載情景下校車數量、行駛里程、行駛成本均有所改善，但是相較于模擬退火算法求解結果的優勢略顯不足．

4.4.2 縱向對比結果

不混載和混載情景下校車路網布局結果分別如圖5和圖6所示，輸出的路網布局站點與站點之間為直線連接，需要與實例區域的現狀可通行路網相結合，在輸出的路網布局結果為基礎進行調整，排除無法通行的站點連接路段．

不混載情景下的校車路網布局較原校車服務模式縱向對比，校車的投入數量減少28.6％，而校車運營的成本很大部分都來源于校車的購入，因此校車投入量的減少也從根本上降低了校車投入成本．在運營里程上，不混載情景下優化不同學校服務路徑之間的銜接，使校車行駛里程降低37.8％，行駛成本降低35.6％．考慮使學生出行成本盡可能達到最優，使學生獲得更好的乘車體驗，但到校模式下每輛校車服務具有很強的針對性，故學生出行成本降低4.3％．

混載情景下的校車路網布局較原校車服務模式縱向對比，無論是校車的投入還是校車運營過程中的資金投入都具有較大優勢，校車的投入數量和行駛里程分別減少37.5％、42.0％．而且此情景下校車調用更加靈活，路徑方案之間的交替變換也產生更多的可能，行駛成本下降35.8％．但由于混載情景的復雜性，難以同時兼顧出行成本，也產生了最多的出行時間，在一定程度上降低了校車的服務水平，因此學生出行成本上略微高于原校車服務模式，增加了0.5％．

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

5 結論

文中以農村地區多校SBRP為研究對象，考慮不同情景和優化目標，建立了基于校方運營成本和學生出行成本的不混載SBRP數學模型;考慮校方運營成本，建立了以校方運營成本和投入成本最低為目標的混載SBRP數學模型．利用模擬退火算法和遺傳算法在國際基準測試案例和國內實例進行分析，得出以下結論：

1） 橫向對比分析，無論是不混載情景還是混載情景下，模擬退火算法比遺傳算法的校車數量、行駛里程、行駛成本、出行成本均有所下降，引入不同搜索算子的模擬退火算法求解構建模型的結果較遺傳算法求解結果更具有優勢，對文中構建考慮多種優化目標的模型具有更強的針對性．

2） 縱向對比分析，文中建立的不混載SBRP模型在兼容降低運營成本的同時可以有效提高農村校車的服務水平，保證優化校車的投入和總里程，平均降低行駛里程37.8％，降低校方運營成本分別為28.6％、35.6％，同時考慮學生的出行感知度，減少學生出行成本為4.3％，學生獲得更好的乘車體驗．建立的混載SBRP模型能夠最大程度縮減運營成本分別為37.5％、35.8％，行駛里程降低了42.0％，且校車調用更加靈活，路徑方案之間的交替變換產生更多的可能，更有利于校方運營．

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

參考文獻 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］ 高巍，陳澤穎，李大舟.基于校車數量的無混載校車路線問題模型優化實現［J］.沈陽化工大學學報，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］ 劉夢琪，瞿何舟.基于軌道交通與常規公交組合的出行路徑選擇研究［J］.交通運輸工程與信息學報，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］ 馮煥煥，鄧建華.基于前景值和乘客最優理論的居民公交出行選擇模型［J］.科學技術與工程，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］ 洪越，殷利平.基于遺傳算法的非高斯系統隨機分布控制［J］.南京信息工程大學學報（自然科學版），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］.南京信息工程大學學報（自然科學版），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］ 鄧紹強，郭宗建，李芳，等.基于Metropolis準則的自適應模擬退火粒子群優化［J］.軟件導刊，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］ 李朝遷，裴建朝.新型模擬退火遺傳算法在路徑優化的應用［J］.組合機床與自動化加工技術，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