改進(jìn)的K-means算法在校車站點(diǎn)布局中的應(yīng)用

趙天天

（1.天津市自然資源調(diào)查與登記中心，天津 300048）

校車站點(diǎn)布局問題是一種服務(wù)于學(xué)生的設(shè)施選址問題，主要用以確定校車車站的位置，并將學(xué)生分配到站點(diǎn)上。校車站點(diǎn)的分布直接決定了學(xué)生到車站的步行距離；而作為校車路徑規(guī)劃問題中的一部分[1]，校車站點(diǎn)布局問題很少被單獨(dú)討論。大多設(shè)施選址研究均以最大人口覆蓋面積或最小運(yùn)行成本為目標(biāo)[2-3]；而校車站點(diǎn)布局往往追求學(xué)生總步行距離最短或以最少的站點(diǎn)數(shù)覆蓋所有的學(xué)生。針對(duì)該問題，國內(nèi)外學(xué)者做了諸多研究，Hassan Z[4]等為達(dá)到總旅行時(shí)間最小化的目的提出了優(yōu)化公交站點(diǎn)的數(shù)學(xué)模型；Johan S[5]以已有的公交站點(diǎn)為潛在校車站點(diǎn)，在其中進(jìn)行選擇，直接將學(xué)生分配到站點(diǎn)上；在研究方法上，任麗[6]利用基于時(shí)空聚類的遺傳算法對(duì)顧客點(diǎn)進(jìn)行聚類，并將他們分配到不同的配送區(qū)域中；張富[7]等提出以最少包含所有數(shù)據(jù)點(diǎn)的圓的中心作為校車站點(diǎn)的方法。然而，大多數(shù)方法除了從已有公交站點(diǎn)中選取外，均較少考慮站點(diǎn)位置應(yīng)在路網(wǎng)上的問題。

本文以學(xué)生到站點(diǎn)步行距離最短為目標(biāo)，提出了聚類算法的目標(biāo)函數(shù)，以一定范圍內(nèi)密度最大點(diǎn)為初始類中心對(duì)K-means 算法進(jìn)行改進(jìn)，并在每次迭代中將類中心投影到路網(wǎng)上，以保證站點(diǎn)位置位于路網(wǎng)中，最后計(jì)算站點(diǎn)位置。

1 改進(jìn)的聚類算法

1.1 聚類算法在校車布局問題中的應(yīng)用

聚類算法主要包括分割法、層次法、基于密度法、基于網(wǎng)格的方法和基于模型的方法[8]。學(xué)生點(diǎn)聚類更適合一種以曼哈頓距離為相似度的圓形簇（類球形）聚類[9]，對(duì)聚類算法的要求相對(duì)簡單。根據(jù)聚類算法的不同特征，本文選用分割法中最經(jīng)典的K-means 算法進(jìn)行聚類。該算法自1955 年被提出后，至今仍被廣泛應(yīng)用[10]。

K-means 算法的思想為：給定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á)式為[11]：

在校車站點(diǎn)布局問題中，聚類的數(shù)據(jù)點(diǎn)為學(xué)生坐標(biāo)，聚類中心為校車站點(diǎn)，聚類的目標(biāo)函數(shù)為每個(gè)學(xué)生到站點(diǎn)的步行距離和最小，數(shù)學(xué)表達(dá)式為：

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

通常聚類算法采用距離函數(shù)（多為歐氏距離）來判斷數(shù)據(jù)之間的相似度，基于距離度量的算法在用于發(fā)現(xiàn)分布均勻的球形簇上很有效；但該算法也有很多缺點(diǎn)，主要包括需要預(yù)先確定K值、嚴(yán)重依賴于初始簇中心點(diǎn)的選取、聚類結(jié)果易受噪音點(diǎn)數(shù)據(jù)的影響、聚類算法無法發(fā)現(xiàn)任意形狀的簇以及易收斂于局部最優(yōu)解等[12]，因此需對(duì)K-means 算法進(jìn)行改進(jìn)。

1.2 改進(jìn)的聚類算法

K-means 算法的主要參數(shù)包括K值、初始中心和距離矩陣[10]。根據(jù)K-means 算法的主要參數(shù)和缺點(diǎn)，本文主要在相似度的計(jì)算方法、K值的確定以及初始中心點(diǎn)的選取上進(jìn)行改進(jìn)。

首先，考慮到北京市城區(qū)的路網(wǎng)結(jié)構(gòu)以矩形環(huán)狀為主，道路多以此為依托，與經(jīng)緯線平行網(wǎng)狀分布，因此采用曼哈頓距離替代歐氏距離量算點(diǎn)與點(diǎn)之間的距離，作為近似路網(wǎng)距離。學(xué)生步行到車站必須經(jīng)過兩個(gè)部分：學(xué)生先由居住地走到最近的路網(wǎng)上（圖1中虛線部分），再沿路網(wǎng)走到車站（圖1 中實(shí)線部分）。

當(dāng)路網(wǎng)與經(jīng)緯線基本平行時(shí)，學(xué)生的步行距離如圖1a 所示；當(dāng)路網(wǎng)與經(jīng)緯線不平行時(shí)，學(xué)生的步行距離如圖1b 所示，學(xué)生到站點(diǎn)的距離會(huì)略大于實(shí)際步行最短距離。

圖1 學(xué)生到站點(diǎn)距離示意圖

其次，在K值的確定和初始中心點(diǎn)選取方面，經(jīng)典的K-means 算法是隨機(jī)選取K個(gè)的中心點(diǎn)，改進(jìn)方法以最大最小距離法最為常見，其原則是使各初始類別之間盡可能的保持最大距離[13]，這樣將使站點(diǎn)的分布過于均勻，并不能保證站點(diǎn)位于學(xué)生密度最大區(qū)域的中心，區(qū)域內(nèi)學(xué)生距離盡可能相同。因此，本文按照點(diǎn)的密度大小來劃分初始類，在ArcGIS 中計(jì)算點(diǎn)的核密度，優(yōu)先選取密度最大的點(diǎn)為第一個(gè)初始類中心，由于密度最大的點(diǎn)附近存在較多密度較大的點(diǎn)，為避免站點(diǎn)之間距離太近，限定在距已知類別點(diǎn)的最近距離大于站點(diǎn)之間的最小距離R的點(diǎn)中選取密度最大的點(diǎn)作為新的類別中心。本文通過限定R值來確定站點(diǎn)個(gè)數(shù)，并未從成本考慮限制站點(diǎn)的最多個(gè)數(shù)。

最后，由于站點(diǎn)需建立在道路上，將在每次迭代中形成的聚類中心投影到路網(wǎng)上，對(duì)學(xué)生進(jìn)行重分配，重新計(jì)算聚類中心，進(jìn)行下一次迭代，直到目標(biāo)函數(shù)收斂。

基于密度法改進(jìn)的K-means 算法的具體步驟為：①將學(xué)生點(diǎn)放置到最近的路網(wǎng)上，并計(jì)算其到最近路網(wǎng)上垂點(diǎn)的距離以及各垂點(diǎn)的核密度；②選取密度最大的點(diǎn)作為第一類中心；③選取其余點(diǎn)中密度最大且到已知類距離大于站間距閾值R的點(diǎn)作為新的類別中心；④循環(huán)步驟③，直到不存在到已知類距離大于站間距閾值R的點(diǎn)為止，形成初始站點(diǎn)；⑤將學(xué)生點(diǎn)分配到曼哈頓距離最近的站點(diǎn)上；⑥計(jì)算每個(gè)站點(diǎn)類學(xué)生點(diǎn)的重心坐標(biāo)，并將其坐標(biāo)改寫成路網(wǎng)上最近坐標(biāo)（即將中心點(diǎn)放置在路網(wǎng)上），計(jì)算學(xué)生點(diǎn)到新的站點(diǎn)坐標(biāo)的距離和；⑦重復(fù)計(jì)算步驟⑤、步驟⑥，直到學(xué)生到站點(diǎn)的距離和不變，即模型中的目標(biāo)方程收斂為止，同時(shí)檢驗(yàn)學(xué)生分配結(jié)果是否滿足模型中的條件。

1.3 站間距的確定

由于校車車站個(gè)數(shù)受站點(diǎn)間最小距離R的限制，因此R值的確定也十分重要。從運(yùn)行成本考慮，站間距越大，車站數(shù)和校車輛數(shù)越少，車輛運(yùn)行時(shí)間越短，耗油量也越少；但間距越大使得學(xué)生到最近站點(diǎn)的步行距離越大[3]，將導(dǎo)致愿意乘坐校車的學(xué)生越少或滿意度降低，從而又使得利益降低。從學(xué)生的角度考慮，校車站點(diǎn)距離起點(diǎn)的位置越近越好，由于學(xué)生的位置是離散的，這樣將導(dǎo)致站間距變小，從而造成校車停車次數(shù)過多，增加了學(xué)生的出行時(shí)間。

Pushkarev B[14]等研究發(fā)現(xiàn)大多數(shù)人不愿意去步行距離超過800 m 的車站，而北京計(jì)劃優(yōu)化調(diào)整地面公交線網(wǎng)，使90% 乘客步行到最近車站距離不超過500 m?？紤]到北京市主干道與次干道路網(wǎng)平均間距為400～1 000 m，本文以500 m 和800 m 作為站點(diǎn)間最小間距，以檢驗(yàn)算法運(yùn)行結(jié)果是否受站間距影響。

2 實(shí)例應(yīng)用

本文以北京市某中學(xué)505 個(gè)學(xué)生點(diǎn)為例，學(xué)生點(diǎn)主要分布于北京市東城區(qū)和朝陽區(qū)；分別利用基于密度法改進(jìn)初始類中心的K-means 算法和基于最大最小距離法改進(jìn)的K-means 算法生成校車站點(diǎn)，并在800 m與500 m 兩種站間距下進(jìn)行對(duì)比分析。在500 m 站間距下基于密度法改進(jìn)的聚類算法結(jié)果中，每次迭代的學(xué)生到站點(diǎn)步行距離總和如表1 所示。

表1 逐次迭代產(chǎn)生的步行距離

每次迭代的學(xué)生到站點(diǎn)步行距離總和呈遞減趨勢，直到兩次迭代結(jié)果相同，生成最終的校車站點(diǎn)坐標(biāo)；其他情況中也出現(xiàn)了同樣的迭代效果。在500 m 站間距下，利用基于密度法改進(jìn)的聚類算法生成的結(jié)果如圖2 所示。

在不同站間距下兩種改進(jìn)方法中，學(xué)生到站點(diǎn)的步行距離如表2 所示。在同一站間距下，基于密度法改進(jìn)初始類中心的K-means 算法使得學(xué)生到站點(diǎn)的距離以及距離方差均較小，站點(diǎn)數(shù)差別不大，迭代次數(shù)約減少50%；800 m 站間距比500 m 站間距生成的站點(diǎn)數(shù)少，學(xué)生總距離和大，不同站間距下，其結(jié)果的變化趨勢不受影響。

圖2 基于密度法改進(jìn)初始類中心的K-means 算法生成的站點(diǎn)分布（500 m 站間距）

表2 學(xué)生到站點(diǎn)的步行距離

對(duì)比各學(xué)生步行距離也可發(fā)現(xiàn)上述相同結(jié)論，如圖3 所示，各學(xué)生到站點(diǎn)的步行距離從小到大順序排列。在同一站間距下，基于密度法改進(jìn)初始類中心的K-means 算法使得絕大多數(shù)學(xué)生步行距離小于基于最大最小距離法改進(jìn)的K-means 算法結(jié)果。當(dāng)限定學(xué)生到站點(diǎn)距離的滿意程度為最小站間距時(shí)，絕大多數(shù)的學(xué)生步行距離使學(xué)生滿意，且利用密度法生成的站點(diǎn)得到更多學(xué)生滿意。最小站間距的改變使得學(xué)生到站點(diǎn)的步行距離變化較大，但兩種算法的比較結(jié)果不受其影響。

圖3 各學(xué)生步行距離

3 結(jié) 語

本文主要針對(duì)校車站點(diǎn)布局問題，利用K-means算法聚類得到車站位置。為保證生成的站點(diǎn)分布在路網(wǎng)上，在聚類算法的迭代中加入了將聚類中心投影到路網(wǎng)上的步驟。本文以學(xué)生總步行距離最短為聚類的目標(biāo)函數(shù)，為使得學(xué)生到站點(diǎn)的步行距離較小，對(duì)K-means 算法選取初始類中心的方法進(jìn)行了改進(jìn)，選取密度最大的點(diǎn)作為初始類中心，替代了最大最小距離法中依照距離的方法，并對(duì)二者進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，在相同站間距下，基于密度法改進(jìn)的聚類算法優(yōu)于基于最大最小距離法的改進(jìn)算法，迭代次數(shù)明顯減少，且不受站點(diǎn)間最小間距限制的影響。該方法還適用于超市班車站點(diǎn)選址、物流配送點(diǎn)選址等問題。