面向首都大學生的定制公交線路規劃模型及算法研究

梁宇杰,宋瑞,王宇擎,吳兆田

(北京交通大學 交通運輸學院，北京 100044) *

市面上定制公交存在很多問題，如覆蓋線路缺失，上座率低，難以盈利等[1]，但目前的研究多針對泛用戶群體進行站點，線路優化[2]，或者針對運營模式提供改進，如斐明陽等人提出的實時預約制[3]，鐘燕妹提出的智能化管理[4]等，鮮有從細化需求的角度，優化定制公交的用戶結構，并由此開展具體的模型構建、算法研究和應用改進.筆者認為，用戶群多樣，分布不規律，需求分散，是目前定制公交存在各種問題的一大根本因素，因而本文提出針對特定用戶群體的定制公交線路規劃模型及算法研究.選擇首都大學生作為特定用戶群，一方面是因為大學生多處于郊區，路程遙遠，日常出行，節假日往返火車站等交通需求不易得到滿足，符合集約化交通的服務條件.另一方面是大學生具有結伴出行，出行可誘導，出行彈性高等特點，具有很強的群體性研究價值.

1 大學生出行行為分析

根據大學生的性別、年級、交通出行方式、對定制公交的看法等，進行了問卷的設計.通過在各大高校線上線下投放及回收，分析數據如圖1，得出大學生出行與定制公交的聯系：①出行習慣上，定制公交很好地滿足了市區和郊區大學生的出行習慣，短途則代替普通公交，長途則相當于定制班車，且價格適中、方便快捷，符合大學生的實際經濟情況和出行習慣.②出行心理上，郊區大學生更喜歡將購物和其他目的的出行結合起來形成多目的出行，且多傾向于去城市中心，故日常出行具有一定的游玩休閑性質.開展定制公交旅游專線，不僅可以收集到需求數據，且集約化程度高、聚類效率高、運行周轉率高.③出行需求上，無論是市區高校學生還是郊區高校學生，在往返火車站回家或出游時，都普遍反映存在人流擁擠、大宗行李攜帶不便、換乘麻煩、耗時長、人身財產安全難以保障等問題，如果可以提供直達式交通則有利于緩解這些問題.且通過設置時間窗等算法可實現預約到達時間等功能，使得出行更加高效省時.④交通需求誘導和平臺社交功能上，大學生出行具有從眾性，喜歡結伴出行，集約化的出行方式可以很好地誘導大學生集體出行.若應用于小程序，可提供社交功能，大學生可通過該線上平臺進行交友溝通，這種附加的社會屬性更有利于誘導大學生出行，產生更好的出行效果.⑤出行方式選擇上，結果顯示大學生對直達性的訴求最高，且高于價格因素，可見頻繁換乘已經成為影響大學生出行的重要因素，且大學生普遍愿意犧牲一定的價格來保證直達性，這和定制公交的收費模式不謀而合.

圖1 部分問卷調查結果

2 定制公交站點和線路規劃

針對上述問題，進行具體的模型構建和算法研究，先將乘客出行時間聚類，將出發或到達時間相近的乘客安排到同一趟路線上，對上車點進行聚類規劃.然后找到距離、時間等約束，以總行駛里程最小為目標函數，構建線路規劃模型，通過蟻群算法求解，得到最優解.

2.1 聚類方法分析

2.1.1 聚類步驟

常見的聚類算法方法有K-means, K-Modoids, Clara等，其中K-means算法邏輯思路和實現難度都具有簡單直接的特點，且算法易于理解，在時間和坐標這類低維數據集上有不錯的效果.以K-means聚類算法應用于站點聚類為例，具體步驟如圖2，其中類內誤差平方和計算公式如式(1)[5]，p為簇類Ck中的需求點.

(1)

2.1.2 聚類孤立點的剔除

在聚類過程中，有一些用戶的需求時間點不同大眾，如果滿足這一小部分人的需求使得整條線路的時間成本很高，這些稱為孤立點，對于這些需求，我們會提前告知乘客其時間不合適，并通過計算給出幾個合適的時間段供其挑選.

下面介紹如何找出這些孤立點.

設有一數據集，通過聚類算法分析后，將分割成k個(k大于實際需要的聚類群體數量)不相交的數據集合V1,V2,…,VK，計算出這k個數據集合的樣本個數為|V1|，|V2|，… ,|VK|; 并假設|V1|<|V2|<… <|VK|;設m為它們的樣本個數的中位數 ，給定閾值參數ε和整數b，若滿足條件：

m/|vb|≥ε

(2)

m/|vb+1|≥ε

(3)

使用上述的K-means方法應用于站點的規劃，由此可得上車所在區域的站點分布情況，同時將各個上車點進行編號，為下一步做準備.

圖2 K-means聚類算法具體步驟

2.1.3 時間聚類和站點規劃

時間聚類屬于一維數據的聚類，而站點規劃屬于二維數據的聚類.先進行時間聚類，將出發或到達時間相近的乘客安排到同一趟路線上.在時間聚類的基礎上，對于同一個時間區間的上車點應用上述K-means方法用于站點的規劃，由此可得上車所在區域的站點情況，同時將各個上車點進行編號，為下一步做準備.

2.2 線路規劃模型建立

該問題可以歸結為車輛路徑問題(Vehicle Routing Problem, VRP)[7]，已知乘客的需求、上下車點、期望到達時間，假設定制公交全程都以平均速度來運行，各站點距離已知，車輛從規劃路線起點的最近的實際公交站場出發，一輛車只能在一條線路運行，每個站點既有上車人數也有下車人數，車輛在站點的停靠時間取決于預約的人數多少，但會有時間懲罰.通過此線路規劃模型，在保證利潤最大化的基礎上，得到k條公交線路的具體路徑，從而得到汽車運行的時刻表，也就是每個乘客的上車時間.

基于問卷調查結果的首都高校多集中于學院路或昌平區大學城，因此上車地較為集中，滿足式(4)的運行路線不會太長.假期的目的地多是景區，因此有式(5)保證所有點都最終到達景區或者火車站的約束.假期中學生對于準時性不太敏感，因此式(9)的懲罰系數取值相對于普通的定制公交較小.

目標函數：

(4)

約束條件：

(1)保證每個停靠點均被服務(人數較多的點，服務次數大于1[2])：

(5)

(6)

(2)保證所有點都最終到達景區或者火車站，設置站點0為景區或者火車站：

(7)

(3)保證車輛載客數不超過車輛的最大載客量：

(8)

(4)時間窗約束：

去景點，軟時間窗：

(9)

去火車站，硬時間窗：

(10)

(5)最低上座率要求[8]：

(11)

式中，rmin表示最低上座率.

(6)約束條件：

園里最先開花的是刺玫和丁香，刺玫在有刺的枝干保護下，開著粉紅花朵，羞澀地躲在滿是尖刺的枝干中，讓人可愛不可及。相比之下，丁香花顯得大方，花烴出枝很高，雪白色的花瓣散著芳香，沁人心脾，一眼望去，整個樹被花包圍著，幾乎看不到葉子，與旁邊的沙果，李子樹開的花相輝映，構成一幅花海樂園。

(12)

2.3 線路規劃模型求解

遺傳算法適合求解離散問題，具備數學理論支持，但存在著漢明懸崖等問題；粒子群算法適合求解實數問題，算法簡單、方便，求解速度快，但存在陷入局部最優等問題；蟻群算法適合在圖上搜索路徑問題，它作為元啟發式算法，是一種算法框架，可以在其基本思想上針對不同問題做改進從而應用到不同問題上去，同時蟻群算法考慮因素全面，收斂速度快，因此本文的問題運用蟻群算法也就最為合適.選取經典的蟻群算法進行求解，并在原有基礎上進行改進.

(a) 揮發函數a (b) 揮發函數b (c) 揮發函數c圖3 信息素濃度和揮發系數函數關系圖

各個需求點之間的距離構成距離鄰接矩陣，隨機形成第一種公交運行方案，更新信息表，反復迭代多次得到滿意解.

在基本蟻群算法中，對信息素的強度沒有限制，因而易陷入局部最優點.改進的蟻群算法對信息素的強度給予一定的限制，從而大大改善了算法的性能.信息素揮發函數對算法的性能有直接的影響，在實驗中曾試過如圖3所示的3種類型函數(X軸為信息素濃度，Y軸為揮發系數)[9].在信息素啟發因子α=1，期望啟發因子β=2，最大迭代次數Z=1 000等其他條件都相同的條件下，對于三種信息素揮發函數進行對比，如表1.通過比較，發現信息素揮發函數c在最優路徑長度和迭代次數上都優于信息素揮發函數a、b,因此采用信息素揮發函數c,具體求解過程[10]如圖4.

表1 三種信息素揮發函數對比

圖4 求解過程

3 案例分析

根據初期的問卷調查數據，選擇由北京市高校前往北京西站的大學生出行需求數據作為研究案例，進行高校定制公交時間聚類、站點規劃和線路規劃的研究，驗證了本文所述算法的有效性.首先，通過K-means 算法對學生們的出行數據進行聚類分析，先通過時間聚類，獲得兩個聚類簇，通過調查問卷8∶00～10∶00的數據隨機抽選了80個需求點，然后通過站點聚類，得到上車點19個，如表2所示，這些上車點地圖的相對位置如圖5所示.

圖5 聚類后的站點位置圖

表2 上車點及上車人數

算法參數為：種群數為20,迭代次數取1000，信息素強度為0.1.這19個上車點包括終點北京西站，每兩個點之間的距離通過電子地圖獲得.

定制公交最大載客量取普通大巴的平均容量，為45人.在定制公交角度定義上座率等同于一般公交的滿載率，從服務水平和收益性角度出發，根據文獻[11]提供的平峰高峰滿載率等級，選取中值0.75作為A等最低上座率要求.使用本文的算法進行求解，最終得到的定制公交線路規劃方案如表3.如圖6為定制公交線路在地圖的具體路線.其中淺色線路為線路1，深色線路為線路2.

表3 定制公交線路方案

圖6 規劃線路的具體路線

從運行結果可以看出，兩條線路幾乎均等地分配了所有需求點，且上座率高達91%和87%.解決了以往定制公交線路覆蓋率低，上座率低且運行效率不高的問題，實際的需求響應落實較好，兩條線路的能力得到充分應用.優于傳統定制公交選擇出行需求聚集性高的線路，充分考慮到乘客的時間出行差異，滿足了大部分乘客的需求，也增加了經濟收益.

4 模型實際應用

(a) 預約頁面 (b) 查詢路線頁面

(c)社交頁面 (d) 預定成功頁面圖7 定制公交小程序界面

5 結論

通過對大學生出行行為與定制公交關系的研究，可以看出大學生群體對定制公交有著很大的潛在需求，但這部分需求在大眾群體中往往被忽略，導致定制公交大學生市場空缺，因此針對特定人群的定制化研究顯得很有必要.

確定目標人群大學生后，結合該人群行為特征及分布狀況，構建特定的線路規劃模型，利用改進的蟻群算法進行求解，可以得到較高的上座率，與現有的定制公交線路規劃模型對比有明顯效果，可見人群專一化以后不僅提高了運行效率，也增加了經濟收益.同時，針對年輕人特點，在應用小程序層面提供了社交功能，凸顯了用戶專一化的服務優化，即如果不針對特定人群，這一社交功能將很難開展.

因此，本文以大學生群體作為切入點，進行具體的定制公交線路規劃模型及算法研究，并提出一定的應用改進，為定制公交用戶專一化深入研究提供思路.