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

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

中圖分類號(hào)：F540.5 文獻(xiàn)標(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é)院機(jī)械工程學(xué)院，講師，碩士，研究方向：機(jī)械自動(dòng)化、路徑優(yōu)化；王學(xué)軍（1984—），男，寧夏固原人，寧夏理工學(xué)院機(jī)械工程學(xué)院，副教授，碩士，研究方向：智能交通系統(tǒng)、物流系統(tǒng)設(shè)計(jì)。

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

0 引 言

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

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

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

1.1 K-means算法

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

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

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

1.2 K-means算法的模型建立

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

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

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

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

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

1.3 蟻群算法

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

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

1.4 蟻群算法的模型建立

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

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

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

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

2 案例應(yīng)用

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

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

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

3 結(jié)果分析

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

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

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

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

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

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

[5] 張春玲，張敬璇．物流配送中心選址研究[J]．華北理工大學(xué)學(xué)報(bào)（社會(huì)科學(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] 周果，季彬，方曉平．多對(duì)多越庫配送綠色車輛路徑問題及算法研究[J]．鐵道科學(xué)與工程學(xué)報(bào)，2022，19（8）：2202-2210.

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

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

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

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

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

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