基于聚類與SA 算法的應急定制公交路線設計與優化

陳 希，呂 洋

（首都經濟貿易大學，北京 100070）

1 背景

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

2 模型構建

2.1 優化目標

在突發公共衛生事件下，為了更好地保障乘客的出行安全，盡量減少出行時長并使企業的支出流失較少，本文在構建應急定制公交線路優化模型時追求所有應急定制公交總花費最少，目標函數為

2.2 約束條件

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

地區風險系數約束，考慮突發公共衛生事件的影響，為更好地保障乘客的出行安全，每輛定制公交運營路段所經過地區的風險系數總和不得超過安全閾值，即

（N為聚類數目，n為每種聚類中地點數量）

2.3 基本步驟

突發公共衛生事件下應急定制公交線路優化流程如圖2所示。應急公交路線優化前對路網中小區進行聚類，系統聚類和Kmeans 聚類依據每個小區距離公司的最短距離最短距離中紅綠燈數量每個小區距離總站的最短距離最短距離中紅綠燈數量每個小區的員工人數mi，每個小區的風險系數ti為指標，將這些劃分成不同區域后再利用模擬退火算法進行公交線路優化。本文采用spss 進行聚類，采用Matlab 進行三重隨機新解的SA 算法的編程。

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

圖1 最優路線

3 案例分析

本部分以北京市豐臺區中都科技大廈及附近員工居住小區的局部路網為研究對象，考慮新冠肺炎疫情影響，對路網進行篩查，刪掉高風險封閉小區和相關路段，量化路網，見圖2。

圖2 路網示意

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

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

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

表1 北京各類公交的相關參數

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

圖3 最佳路線

4 結束語

基于前面的模擬和實例分析，我們對疫情時期城市公共交通系統運營的優化策略提出如下建議。

對于個人，在疫情得到良好控制，社會復工復產期間，應適當乘坐公共交通工具，以減緩城市交通壓力；個人可以主動向所在單位提出合理的定制公交需求；在疫情期間，個人乘坐公共交通工具時，應當自覺遵守衛生管理條例。

對于公交公司，充分借助科學方法制定最優出行路線與方案，嚴格制定衛生管理條例。最大限度滿足員工出行需求，減少運營成本，為社會疫情防控、減緩交通壓力與復工復產起到切實效果。

對于政府部門，鼓勵便民出行新方式，加強政策引導性和社會宣傳；引入科學的定制化設計方法與手段，建立健全疫情期間定制公交的運營與監管機制；嚴格規范定制公交的運營，頒布衛生管理條例；有關部門需積極推行“網上辦公”，創新服務模式，減少線下辦公接觸，簡化辦公流程。