校車站點布局的仿真模擬

摘 要：文章針對學(xué)生上下學(xué)的路徑問題，基于K-means算法和蟻群算法進行研究，通過使用三階段布局法（確定候選站點、確定初始候選站點的布局方法、站點布局優(yōu)化）確定站點的位置設(shè)置，采用MATLAB仿真軟件對K-means算法、蟻群算法進行模擬，并對調(diào)查數(shù)據(jù)進行分析。文章主要研究這兩種方法下的路徑優(yōu)化方式，通過實驗計算，證明了蟻群算法得出的學(xué)生上下學(xué)路徑要優(yōu)于K-means算法下的路徑，K-means算法使得每條路徑人數(shù)分布不均勻且路程不相近；而蟻群算法使得每條路徑學(xué)生的搭乘數(shù)均等，校車走過的路程相近。

關(guān)鍵詞：MATLAB；K-means算法；蟻群算法；路徑優(yōu)化

中圖分類號：F540.5 文獻標(biāo)志碼：A DOI：10.13714/j.cnki.1002-3100.2024.22.020

Abstract： This paper conducts a study on the path problem of students going to and from school based on K-means algorithm and ant colony optimization. It uses the three-stage layout method （determining candidate stat3ujx3VdVQDUJAMoyf8nAYKCtoCg3EK5o3w/ZikuhB8U=ions， determining the layout method of initial candidate stations， optimizing the station layout） to determine the location of the station. MATLAB simulation software is used to simulate the K-means algorithm and ant colony optimization， and analyze the survey data. The main focus of this article is on path optimization under these two methods. Through experimental calculations， it has been proven that the students' path to and from school under the ant colony optimization is better than that under the K-means algorithm. The K-means algorithm results in uneven distribution of students on each path and uneven distances， while the ant colony optimization ensures that the number of students on each path is equal， and the distance traveled by the school bus is similar.

Key words： MATLAB; K-means algorithm; ant colony optimization; path optimization

收稿日期：2024-04-25

作者簡介：劉曉龍（1991—），男，寧夏吳忠人，寧夏理工學(xué)院機械工程學(xué)院，講師，碩士，研究方向：機械自動化、路徑優(yōu)化；王學(xué)軍（1984—），男，寧夏固原人，寧夏理工學(xué)院機械工程學(xué)院，副教授，碩士，研究方向：智能交通系統(tǒng)、物流系統(tǒng)設(shè)計。

引文格式：劉曉龍，馬旭琴，王學(xué)軍．校車站點布局的仿真模擬[J]．物流科技，2024，47（22）：76-81.

0 引 言

為適應(yīng)城市人口增長帶來的教育需求增加的問題，各大高校近年來逐漸開始擴大辦學(xué)規(guī)模，改善現(xiàn)有教學(xué)環(huán)境，提高教學(xué)質(zhì)量，同時，為了更好地服務(wù)于社會和學(xué)生，保障教師和學(xué)生的工作和學(xué)習(xí)效率，各大高校開始實施校車服務(wù)，合理的站點布局對校車路徑優(yōu)化起著至關(guān)重要的作用。

任騰等（2022）研究了面向冷鏈物流配送路徑優(yōu)化的知識型蟻群算法[1]；柳伍生等（2021）研究了“無人機-車輛”配送路徑優(yōu)化模型與算法[2]；張冬青等（2021）研究了考慮時空相關(guān)隨機行駛時間的車輛路徑問題模型與算法[3]；王勇等（2022）研究了基于客戶信用度的物流配送車輛路徑問題[4]；張春玲等（2021）針對物流配送中心選址問題進行研究[5]；Meng等（2020）將改進的K-均值算法應(yīng)用于公務(wù)車聯(lián)網(wǎng)環(huán)境[6]；Fadda等（2020）針對具有相關(guān)隨機旅行成本的隨機多徑旅行商問題進行了研究[7]；周果等（2022）對于多對多越庫配送綠色車輛路徑問題及算法進行了研究[8]；胡小建等（2022）基于時間窗約束的多人多儲位揀選路徑優(yōu)化模型及改進遺傳算法應(yīng)用進行了研究[9]。

1 路徑優(yōu)化算法及對應(yīng)的模型建立

1.1 K-means算法

聚類分析，也稱為群分析[10]，是一種統(tǒng)計分析方法，主要通過對已有數(shù)據(jù)進行分類，使具有相似特征的數(shù)據(jù)聚類到一起，分組為不同的簇，同一簇內(nèi)的對象具有相似的屬性，通過不斷迭代來進行聚類，直到滿足某個結(jié)束條件，從而輸出一個聚類結(jié)果。

輪廓系數(shù)（Silhouette Coefficient Index）是一種聚類評估指標(biāo)，用于評估數(shù)據(jù)的聚類效果。輪廓系數(shù)的取值范圍一般為[-1，1]，當(dāng)輪廓系數(shù)接近1時，表示聚類效果較好。輪廓系數(shù)表達式為：

式中，i表示其中的某一個點；a（i）表示i到所有其所屬的簇中其他點的距離；b（i）表示i到某一個不包含它的簇內(nèi)所有點的平均距離。

1.2 K-means算法的模型建立

K-means算法的核心思想為[11]：在給定n個數(shù)據(jù)點{x1，x2，...，xn}中，找到K個聚類中心{a1，a2，...，ak}，使得每個數(shù)據(jù)點與它最近的聚類中心的距離平方和最小，并將該距離平方和稱為目標(biāo)函數(shù)，記為Wn，數(shù)學(xué)表達式為：

在校車站點布局的問題中，數(shù)據(jù)集中聚類的組別數(shù)為已定的站點數(shù)，迭代計算得出的聚類中心為校車站點，聚類目標(biāo)函數(shù)為每個站點之間的距離和最小，數(shù)學(xué)表達式為：

式中，CN為學(xué)生站點數(shù)；Ni為第i個學(xué)生站點（i=1，2，...，CN）；D（CN，Ni）為該站點到第i個車站的距離；Mki=0或1，第k個站點被分配到第i個站點上則為1，否則為0。

一般情況下，聚類算法采用距離函數(shù)（多為歐氏距離）進行計算，判斷數(shù)據(jù)之間的距離，但該算法也有很多缺點，其中包括需要提前人為設(shè)置確定K值、嚴(yán)重依賴于初始簇中心點的選取、聚類算法無法發(fā)現(xiàn)任意形狀的簇以及易收斂于局部最優(yōu)解等，以下為空間之間的距離公式表達式。

n維空間上點a（X11，X12，…，X1n）與b（X21，X22，…，X2n）的歐氏距離數(shù)學(xué)表達式為：

1.3 蟻群算法

蟻群算法的原理是模擬自然界中螞蟻的覓食行為[12]，螞蟻在尋找食物的過程中，會在其所經(jīng)過的路徑上遺留一種叫做信息素的化學(xué)物質(zhì)，這種信息素對于螞蟻來說是一種重要的通信方式，它們可以通過感知信息素的濃度來判斷路徑之優(yōu)劣，從而選擇最優(yōu)路徑。如圖1所示。

影響蟻群算法收斂的主要因素有螞蟻數(shù)量m、信息素因子α、啟發(fā)函數(shù)因子β、信息素揮發(fā)因子ρ、信息素常數(shù)Q、最大迭代次數(shù)t等。如表1所示。

1.4 蟻群算法的模型建立

蟻群算法主要通過模擬自然界螞蟻在覓食過程中分泌的信息素來進行通信和協(xié)作。螞蟻通過感知路徑上的信息素濃度來選擇下一步的移動方向。每個螞蟻都會在移動過程中釋放信息素，這些信息素會隨時間推移逐漸揮發(fā)，也會因為螞蟻經(jīng)過而累積。這種機制使得較短的路徑上信息素濃度逐漸累積，從而引導(dǎo)更多螞蟻選擇這些路徑，最終找到最優(yōu)路徑[13]。

首先，定義關(guān)鍵變量：i和j為兩個結(jié)點；bi（t）表示t時處于結(jié)點i的螞蟻數(shù)；τij（t）為t時弧段（i，j）上的信息濃度；n表示結(jié)點集；m為整個蟻群中全部螞蟻數(shù)量，；Γ=是在t時處于集合C中元素的信息素集合，設(shè)τij（0）=const，基本蟻群算法中螞蟻尋求最優(yōu)線路是利用有向圖g=（C，L，Γ）實現(xiàn)的。

螞蟻k（k=1，2，...，m）在爬行尋優(yōu)過程中，利用先前螞蟻殘留的信息素濃度選擇線路作為自己移動的方向。為了記憶螞蟻是否已經(jīng)過此結(jié)點，利用禁忌表tabuk記錄螞蟻爬行過的結(jié)點，禁忌表tabuk處于變化中 。螞蟻的迭代過程，主要利用狀態(tài)轉(zhuǎn)移概率進行，那么t時螞蟻k由一個結(jié)點選擇另外一個結(jié)點的狀態(tài)轉(zhuǎn)移概率為：

其中，allowedk={C-tabuk}代表螞蟻尚未走過的結(jié)點；α是代表螞蟻所爬行軌跡重要程度的信息啟發(fā)因子，主要反映了螞蟻在路徑選擇過程中一定程度上參考了之前螞蟻的殘余信息素，而信息啟發(fā)因子的取值大小即為其選擇路徑的強弱，α信息啟發(fā)因子的取值大小即螞蟻選擇該路徑的強度；β對期望啟發(fā)因子而言，代表期望的重要程度，主要體現(xiàn)了螞蟻進行路徑選擇對啟發(fā)信息的重要程度，當(dāng)然，當(dāng)期望啟發(fā)因子取值較大時，它就會向貪婪法則靠攏；ηij（t）為啟發(fā)函數(shù)，ηij（t）=1/dij，式中dij代表每兩個結(jié)點之間的長度或距離，對每個螞蟻k，dij與ηij（t）呈負相關(guān)，dij越小，反而ηij（t）越大，相應(yīng)地，狀態(tài)發(fā)生轉(zhuǎn)移的機率也就越高。很顯然，該啟發(fā)函數(shù)ηij（t）代表螞蟻對從結(jié)點i轉(zhuǎn)移到結(jié)點j的期望程度。

2 案例應(yīng)用

本文選定a中學(xué)作為研究對象，對該學(xué)校的學(xué)生進行統(tǒng)計，得出共有192名學(xué)生乘坐校車?，F(xiàn)選用校車為可乘坐人數(shù)49人的車型。利用MATLAB軟件對現(xiàn)有的21個站點進行路徑規(guī)劃，合理安排車輛數(shù)。

對所有學(xué)生的居住位置進行信息調(diào)查，將學(xué)生所在地劃分為站點，并進行經(jīng)緯度標(biāo)注，這個位置就作為初始校車站點；然后統(tǒng)計在這個位置上車的學(xué)生人數(shù)。具體信息如表2所示。具體的實物圖與MATLAB仿真圖如圖2所示。

由圖2（站點的仿真圖）可知，大部分站點靠近高速公路，道路條件良好，便于接送學(xué)生，只有K村距離公路較遠。

3 結(jié)果分析

3.1 K-means算法的結(jié)果分析

K-means聚類分析算法具有簡單且容易實現(xiàn)的優(yōu)點，但需要事先設(shè)定類簇數(shù)量K，所以在利用該算法解決問題前需要依次設(shè)定K值，利用MATLAB進行仿真得到輪廓系數(shù)，并進行判斷，得出K值為4，最終根據(jù)人數(shù)和距離得到路徑。如圖3和表3所示。

3.2 蟻群算法的結(jié)果分析

通過設(shè)置不同的參數(shù)，利用MATLAB軟件得到，在不同參數(shù)數(shù)值下，各代最短距離與平均距離對比圖，以及優(yōu)化最短距離圖得到各參數(shù)的取值如表4所示。各參數(shù)下經(jīng)過迭代次數(shù)與距離以及最短路徑圖如圖4所示。

由圖5的路徑圖得出該校學(xué)生乘坐校車的站點路線及人數(shù)如表5所示。

4 結(jié) 論

針對校車路徑問題，討論K-means聚類算法和蟻群算法這兩種方法。通過對兩種算法進行建模，針對調(diào)查實例學(xué)校的數(shù)據(jù)進行初始計算，采用MATLAB軟件對數(shù)據(jù)進行仿真，對路徑進行求解，最終得出每種算法下的路徑數(shù)和車輛數(shù)，通過最后的仿真得知應(yīng)用蟻群算法得出的路徑較優(yōu)，最終得出該學(xué)校需要購置車容量為49人的客車4輛。

參考文獻：

[1] 任騰，羅天羽，李姝萱，等．面向冷鏈物流配送路徑優(yōu)化的知識型蟻群算法[J]．控制與決策，2022，37（3）：545-554.

[2] 柳伍生，李旺，周清，等．“無人機-車輛”配送路徑優(yōu)化模型與算法[J]．交通運輸系統(tǒng)工程與信息，2021，21（6）：176-186.

[3] 張冬青，郭釗俠，張殷杰．考慮時空相關(guān)隨機行駛時間的車輛路徑問題模型與算法[J]．四川大學(xué)學(xué)報（自然科學(xué)版）， 2021，58（6）：181-189.

[4] 王勇，范舉，劉永，等．基于客戶信用度的物流配送車輛路徑問題研究[J]．運籌與管理，2022，31（8）：77-84.

[5] 張春玲，張敬璇．物流配送中心選址研究[J]．華北理工大學(xué)學(xué)報（社會科學(xué)版），2021，21（5）：23-29.

[6] MENG Xiangxi， LYU Jianghua， MA Shilong．Applying improved K-means algorithm into official service vehicle networkingenvironment and research[J]．Soft Computing， 2020， 24（11）： 8355-8363.

[7] FADDA E， TIOTSOP L F， MANERBA D，et al．The stochastic multipath traveling salesman problem with dependent random travel costs[J]．Transportation Science，2020，54（5）：1372-1387.

[8] 周果，季彬，方曉平．多對多越庫配送綠色車輛路徑問題及算法研究[J]．鐵道科學(xué)與工程學(xué)報，2022，19（8）：2202-2210.

[9] 胡小建，周瓊，宋旭東，等．基于時間窗約束的多人多儲位揀選路徑優(yōu)化模型及改進遺傳算法應(yīng)用研究[J]．計算機集成制 造系統(tǒng)，2022，28（11）：3354-3364.

[10] 薛德琴，張永強，王笑雨，等．基于聚類分析的協(xié)同配送中心選址研究[J]．物流工程與管理，2021，43（11）：56-58，40.

[11] 徐昊源，繆鴻志．基于K-means聚類的生鮮自提柜選址及配送方案優(yōu)化[J]．物流技術(shù)，2022，41（11）：50-54.

[12] 唐慧玲，唐恒書，朱興亮. 基于改進蟻群算法的低碳車輛路徑問題研究[J]．中國管理科學(xué)，2021，29（7）：118-127.

[13] 韓孟宜，丁俊武，陳夢覃，等．基于混合遺傳算法的應(yīng)急物資配送路徑優(yōu)化[J]．科學(xué)技術(shù)與工程，2021，21（22）：9432-9439.

[14] 耿振余，陳治湘，黃路煒，等．軟計算方法及其軍事應(yīng)用[M]．北京：國防工業(yè)出版社，2015.