基于聚類與SA 算法的應(yīng)急定制公交路線設(shè)計(jì)與優(yōu)化

陳 希，呂 洋

（首都經(jīng)濟(jì)貿(mào)易大學(xué)，北京 100070）

1 背景

為了在疫情期間最大化利用交通資源并實(shí)現(xiàn)交通資源的供需平衡，以企業(yè)及其輻射的員工居住地為區(qū)塊定制最優(yōu)化的公交線路，是企業(yè)實(shí)現(xiàn)復(fù)工復(fù)產(chǎn)的基礎(chǔ)性支撐。基于此，我們認(rèn)為有必要開展定點(diǎn)定制公交，以更好地匹配需求與供給，實(shí)現(xiàn)突發(fā)公共衛(wèi)生事件下的定制公交線路優(yōu)化，多種乘車組合在最大程度上為企業(yè)員工提供了價(jià)格最優(yōu)，滿足更多集約用車需求。

2 模型構(gòu)建

2.1 優(yōu)化目標(biāo)

在突發(fā)公共衛(wèi)生事件下，為了更好地保障乘客的出行安全，盡量減少出行時(shí)長并使企業(yè)的支出流失較少，本文在構(gòu)建應(yīng)急定制公交線路優(yōu)化模型時(shí)追求所有應(yīng)急定制公交總花費(fèi)最少，目標(biāo)函數(shù)為

2.2 約束條件

乘客上座人數(shù)約束，考慮突發(fā)公共衛(wèi)生事件的影響，為更好地保障乘客的出行安全，每輛應(yīng)急定制公交所載乘客數(shù)不超過其安全閾值，即

地區(qū)風(fēng)險(xiǎn)系數(shù)約束，考慮突發(fā)公共衛(wèi)生事件的影響，為更好地保障乘客的出行安全，每輛定制公交運(yùn)營路段所經(jīng)過地區(qū)的風(fēng)險(xiǎn)系數(shù)總和不得超過安全閾值，即

（N為聚類數(shù)目，n為每種聚類中地點(diǎn)數(shù)量）

2.3 基本步驟

突發(fā)公共衛(wèi)生事件下應(yīng)急定制公交線路優(yōu)化流程如圖2所示。應(yīng)急公交路線優(yōu)化前對(duì)路網(wǎng)中小區(qū)進(jìn)行聚類，系統(tǒng)聚類和Kmeans 聚類依據(jù)每個(gè)小區(qū)距離公司的最短距離最短距離中紅綠燈數(shù)量每個(gè)小區(qū)距離總站的最短距離最短距離中紅綠燈數(shù)量每個(gè)小區(qū)的員工人數(shù)mi，每個(gè)小區(qū)的風(fēng)險(xiǎn)系數(shù)ti為指標(biāo)，將這些劃分成不同區(qū)域后再利用模擬退火算法進(jìn)行公交線路優(yōu)化。本文采用spss 進(jìn)行聚類，采用Matlab 進(jìn)行三重隨機(jī)新解的SA 算法的編程。

代入算法得到最終結(jié)果（所有結(jié)果詳見附錄），應(yīng)派一輛最大載客量大于164人的公交車遍歷全部小區(qū)，最優(yōu)路線為，1-5-4-3-2-7-6-8，最小費(fèi)用為328.1元。最優(yōu)路線如圖1所示：

圖1 最優(yōu)路線

3 案例分析

本部分以北京市豐臺(tái)區(qū)中都科技大廈及附近員工居住小區(qū)的局部路網(wǎng)為研究對(duì)象，考慮新冠肺炎疫情影響，對(duì)路網(wǎng)進(jìn)行篩查，刪掉高風(fēng)險(xiǎn)封閉小區(qū)和相關(guān)路段，量化路網(wǎng)，見圖2。

圖2 路網(wǎng)示意

路網(wǎng)中有中都科技大廈（編號(hào)為1），有美域家園，大成南里，青塔小區(qū)，科興佳園，蓮怡園，太平橋小區(qū)，西局欣園，豐益小區(qū)，南開西里小區(qū)，程莊小區(qū)，五里店北里共12個(gè)小區(qū)（編號(hào)分別為2～11），有北大地公交總站（編號(hào)分別為13），最短路徑mij，紅綠燈數(shù)量qij。應(yīng)急出行的員工人數(shù)mi分別為2—13人，3—8人，4—19人，5—12人，6—7人，7—15人，8—21人9—14人，10—11人，11—9人，12—2人，路網(wǎng)中的中風(fēng)險(xiǎn)地區(qū)為2，5，12小區(qū)，低風(fēng)險(xiǎn)地區(qū)為3，4，6，7，8，9，10，11小區(qū)。

我們選擇豐臺(tái)區(qū)常用的幾種類型的公交車作為定制公交車，分別為東風(fēng)超龍EQ6668G5，宇通ZK6775HG2，宇通ZK6935HG2，海格KLQ6119GAE5，福田歐輝BJ6128C8BJD，最大載客量xi和耗油量H 如下表 所示。P=5.12L/ 元，S 消殺=20 元/ 次，S 保險(xiǎn)=4100元/年，S工資=4500元/月，S保養(yǎng)=10000元/年，S折舊=10000元/年，即S 其他=233.5元/次。中風(fēng)險(xiǎn)地區(qū)的風(fēng)險(xiǎn)系數(shù)t 中=0.4，低風(fēng)險(xiǎn)地區(qū)風(fēng)險(xiǎn)系數(shù)t 低=0.1，安全閾值T1=1.2，T2=0.6xi。

模擬退火算法中，初始溫度為1000，最大迭代次數(shù)為1000，每個(gè)溫度下的迭代次數(shù)為500，溫度衰減系數(shù)為0.95。

表1 北京各類公交的相關(guān)參數(shù)

考慮新冠肺炎疫情影響下，員工下班時(shí)（上班過程反過來），應(yīng)急定制公交線路優(yōu)化方案為聚類平均DBI為0.3705，平均DBI 較小，聚類效果較好。總路程53.9公里，總花費(fèi)791.5元，上座率控制在60%以下，實(shí)現(xiàn)距離最優(yōu)，成本最優(yōu)，風(fēng)險(xiǎn)最優(yōu)的定制公交路線設(shè)計(jì)。路線見圖3。

圖3 最佳路線

4 結(jié)束語

基于前面的模擬和實(shí)例分析，我們對(duì)疫情時(shí)期城市公共交通系統(tǒng)運(yùn)營的優(yōu)化策略提出如下建議。

對(duì)于個(gè)人，在疫情得到良好控制，社會(huì)復(fù)工復(fù)產(chǎn)期間，應(yīng)適當(dāng)乘坐公共交通工具，以減緩城市交通壓力；個(gè)人可以主動(dòng)向所在單位提出合理的定制公交需求；在疫情期間，個(gè)人乘坐公共交通工具時(shí)，應(yīng)當(dāng)自覺遵守衛(wèi)生管理?xiàng)l例。

對(duì)于公交公司，充分借助科學(xué)方法制定最優(yōu)出行路線與方案，嚴(yán)格制定衛(wèi)生管理?xiàng)l例。最大限度滿足員工出行需求，減少運(yùn)營成本，為社會(huì)疫情防控、減緩交通壓力與復(fù)工復(fù)產(chǎn)起到切實(shí)效果。

對(duì)于政府部門，鼓勵(lì)便民出行新方式，加強(qiáng)政策引導(dǎo)性和社會(huì)宣傳；引入科學(xué)的定制化設(shè)計(jì)方法與手段，建立健全疫情期間定制公交的運(yùn)營與監(jiān)管機(jī)制；嚴(yán)格規(guī)范定制公交的運(yùn)營，頒布衛(wèi)生管理?xiàng)l例；有關(guān)部門需積極推行“網(wǎng)上辦公”，創(chuàng)新服務(wù)模式，減少線下辦公接觸，簡化辦公流程。