評分模型在路網通勤習慣分析中的應用—

1、問題的由來、目標和意義

最近一段時間和公司其它業務部門討論時，發現一個有趣的交通路網問題，車輛從S點行駛到V點共用時40分鐘，這段時間內路網中的卡口攝像頭識別到了車輛通過的信息。如下圖所示：
在這里插入圖片描述
設計師需要通過這些有限的路網數據，分析出當前車輛最可能的行駛路徑，并且基于一段時間（1個月、2個月甚至3個月）內某車輛多個行駛路徑樣本，分析后得到車輛A的通勤習慣數據。能夠支持解決這個問題的基礎數據是有限的，它們包括：

相對靜態的數據：地圖交通網數據（沒有結構化，需研發團隊自行結構化）、道路級別數據、卡口位置數據等
相對動態的數據：從外部得到的周期更新的交通網擁堵、卡口攝像數據（最關鍵的數據）、交通事故數據等

解決這個問題，在業務層面還需要注意以下幾個關鍵點：

1、數據的采集主要通過設置在主道上的卡口攝像頭，或者設置在路口的卡口攝像頭完成。兩者的區別主要在于，前者只能提供車輛車牌信息和行駛方向信息，而后者由于是安裝在路口，所以不止可以提供車牌信息，還能提供車輛在路口可能的轉向信息。

2、由于技術問題、采光問題、清晰度問題，卡口攝像頭做不到100%正確識別車輛車牌信息，也就是說如果卡口攝像頭在一段時間內沒有拍攝到某個車輛的車牌信息，也不能代表這輛車在這段時間內一定沒有行駛過這段道路。

3、根據車輛某一天最可能的行駛軌跡情況，是不能得到車輛一段時間的通勤習慣的，需要多個分析樣本，再利用回歸分析的方式，才能得出車輛在一段時間內的通勤習慣。

車輛可能的行駛路徑信息、通勤習慣信息至少能夠為城市的智慧交通領域提供以下業務支持：

**優化交通流量?：**通過分析通勤習慣數據，交通部門可以識別交通高峰時段和瓶頸路段，從而采取措施進行改善，如調整交通信號燈、增加公交線路或建設新的交通基礎設施，以優化交通流量和提高道路利用效率。
提升公共交通系統效率?：公共交通運營商可以利用通勤習慣數據來優化公交線路和時間表，提高公共交通的準點率和便捷性。例如，通過分析通勤者的出發時間和到達時間，可以調整公交和地鐵的發車頻率和運營時間，以滿足乘客的需求?。
改善城市規劃?：城市規劃者可以基于通勤習慣數據進行更合理的城市布局和基礎設施建設。例如，通過分析通勤路線和交通狀況，可以確定哪些區域需要更多的公共交通設施或道路改善，以減輕交通擁堵和提高居民的生活質量?。
提高通勤者生活質量?：通過減少通勤時間和改善通勤體驗，可以顯著提升通勤者的生活質量和工作效率。例如，通過分析通勤者的出行習慣，可以提供個性化的出行建議和路線規劃，減少通勤時間和疲勞?。

所以通勤習慣分析屬于智慧交通業務中的基礎分析，其分析的結果可以用于支撐智慧交通業務的上層能力。實際上通勤習慣分析屬于OD（Origin-Destination，起止點）分析中的一種具體形式，OD分析主要通過收集和分析數據，識別出行起點和終點之間的車輛流動情況。在交通規劃中，OD分析可以幫助了解交通流量、識別高峰期和瓶頸區，優化交通網絡設計和管理。此外，OD分析也廣泛應用于物流、零售等領域，通過分析貨物流動和顧客行為，提高資源配置和運營效率?。

2、解決問題需要具備的知識結構

2.1、OD分析可能的解決方案剖析

在這里插入圖片描述
上圖將整個問題可能的解決方案剖析成三個部分，第一個部分主要是拍照數據的采集和數據清洗。這個階段要解決的主要問題是，不同型號、不同通訊方式的卡扣攝像頭，如何匯聚數據并初步檢測出錯誤數據。例如一些較新型號的卡口攝像頭自帶5G通訊模塊，可以直接連接到數據采集系統/數據集中平臺，通過MQTT等標準協議傳輸數據。有的卡口攝像頭雖然不具備5G通訊模塊，但是可以統一接入到IoT網關或者集中管控終端上，再由IoT網關或者終端完成數據傳輸。空間路網數據亦是采用類似的思路進行數據采集。

這些原始數據都將在數據采集系統/物聯數據集中平臺進行歸集，后者顯然需要兼容各種數據傳輸方式，并完成初步的數據清洗操作。從本文描述的需要解決的問題來說，這些原始數據主要就是各個交通卡口的車牌數據、時間數據、車輛行駛方向數據，等等。顯然數據采集系統并不負責完成OD軌跡實時分析，也并不是本文討論的重點。（如果需要詳細了解這部分內容，可以參考《軟件設計不是CRUD（21）：在流式數據處理系統中進行業務抽象落地——需求分析》等文章）

基礎數據準備完畢后，會在湖倉一體化的數據存儲平臺進行存儲，以便支持后續的數據分析過程。數據分析的關鍵過程在流式分析平臺上完成，也就是說討論如何分析得到更匹配真實情況的OD軌跡，甚至如何基于多份OD軌跡樣本分析得到單臺車輛在一個較長時間段內的通勤習慣，就是討論在流式分析平臺上對數據分析的詳細設計。這是解決問題的關鍵設計部分，也是本文（和后續幾篇文章）的重點內容。

整個問題可能的解決方案，還有第三個結構部分，就是基于已分析數據向外提供數據應用能力的平臺。數據應用平臺至少可以基于軌跡數據、出行習慣數據，以及自身AI分析后得到的其它擴充數據，向上層業務系統/第三方系統提供諸如城市路網規劃、擁堵預測與緩解、高峰管制優化、路口信號優化等多種多樣的業務支持。雖然這也不是本文討論的重點，但讀者可以明確知道OD分析在智慧交通應用中的意義和重要程度。

2.2、知識準備

本文不討論技術選型本身，技術選型僅是表象，不同技術經歷、技術背景的工程師對于技術選型都有自己的理解，在選型要點和細節上都會有所區別。所以讀者進需要知曉上圖中涉及的中間件即可：

Kafka：Kafka作為在數據分析場景下，在多個中間件之間實時傳輸數據的消息隊列，相信大家不會陌生。在解決本問題的技術架構中，Kafka負責多個任務，包括作為攝像頭向數據采集平臺/物聯數據集中平臺傳輸卡口監控數據的一種渠道、作為數據采集和清洗后，向湖倉一體化的存儲方案傳輸數據的一種渠道。
Flink：Flink是一款開源流式數據處理框架，主要用于實時數據流的處理和分析。Flink的核心是用Java和Scala編寫的分布式數據流引擎，旨在實現數據流上的有狀態計算?。Flink大量應用在對數據分析有較強實時性要求、較大數據量要求的分析場景。除了本身提供的流式分析特性外，Flink也支持數據的批處理，這也是為什么上圖中所示的技術方案中，類似通勤習慣這樣的周期性批處理分析，我們也放到了Flink中。
StarRocks：StarRocks內部通過MPP計算框架完成SQL的具體執行工作。MPP框架本身能夠充分的利用多節點的計算能力，整個查詢并行執行，從而實現很好的交互式分析體驗。 StarRocks作為一款湖倉一體化的數據存儲和計算平臺，可以支持與Hive，MySQL，Elastic serach存儲方案無縫構建外表。

本文的重點是介紹啟發式搜索在交通通勤領域的應用，更具體的說，是解決啟發式搜索如何有效降低遍歷搜索算法的計算成本，提高問題的解決效率。所以以下“圖”結構中的基礎算法知識，需要讀者掌握（本文不會講解這些基礎知識，會直接認為讀者已掌握）：

加權有向圖：?加權有向圖?是一種圖論中的數據結構，它是在有向圖的基礎上，每條邊都賦予了一個權重值。這個權重值，一般和應用場景有關。在交通應用場景中每個頂點代表兩個或者多個路段的交匯點（可能是十字路口、丁字路口、匝道、隧道出入口、高速出入口等），每條邊代表一個獨立的路段，每條邊越高的權重，代表出于主觀或客觀的原因車輛行駛時對路段越高的選擇度。
圖的最小搜索樹：在一個加權有向圖中，如果存在一棵各邊權重和最小的生成樹，那么這棵樹就被稱為最小生成樹。生成樹是原圖的一個子集，包含圖中所有頂點，但僅有n-1條邊（n為頂點數），這些邊構成了一棵無環的樹。
兩個頂點的所有路徑：既是通過一種算法，找到圖結構中兩個頂點間所有的聯通路徑。這種算法一般是某種遍歷算法，因為只有了解了圖中每個頂點的具體聯通情況，才能找出所有聯通路徑，這就導致要找到兩個頂點所有路徑的算法時間復雜度一般會比較高——O(N²)
兩個頂點的加權最短路徑：在加權有向圖中，從頂點s到頂點t的最短路徑是所有從s到t的路徑中權重最小的那條路徑。
遍歷搜索：遍歷搜索，也稱為暴力搜索，是一種簡單但全面的搜索策略。它不考慮任何智能或優化，只是逐個訪問數據結構中的每個節點，直到找到目標值或遍歷完所有節點。這種搜索策略適用于沒有任何特殊性質的數據結構，如普通的樹或圖。在遍歷搜索中，常見的兩種方法是深度優先搜索（DFS）和廣度優先搜索（BFS）。
啟發式搜索：是一種更智能、更高效的搜索策略。它使用問題相關業務知識來指導搜索過程，以提高搜索效率。具體到圖的交通應用場景中，啟發式搜索考慮的就是交通常識、駕駛習慣等因素。這種策略在現實業務場景和深度學習中更為適用，常見于最優解、可能性等問題的處理。

3、問題概要分析

3.1、可能性問題與最優解問題的區別

有的讀者會疑問，本文開頭提出的問題和目前導航服務廠商提供的多途徑點規劃功能類似，為什么不直接使用地圖廠商提供的相關服務，而要作為一個基礎問題自己解決呢？這里暫時不分析業務、安全等層面的考慮，單從問題本身的性質來說，這兩個問題就存在較大區別：

多途經點規劃和可能的OD軌跡分析，兩個問題的研究場景不一樣。前者是在交通行為還沒有發生的情況，在滿足多個途徑點位的要求下，尋找一個最優解；后者是在交通行為已經發生的情況下，基于交通網的各種歷史狀態和經過的點位，推導出多種可能性作為分析樣本。再基于一段較長時間后，對足夠多的樣本進行多次回歸等方式，找到可能性中的最可能得情況。前者屬于單純的最優解問題，后者屬于可能性問題。

可能性問題：可能性問題關注的是某個事件或情況發生的概率或存在的程度。這通常涉及到對不確定性的評估和預測。很明顯通過有限的數據在交通路網上還原點位A到點位B可能的路徑，就屬于可能性問題。可能性問題得到的解并不是最優解，而是根據目前現狀后得到最有可能的情況。

最優解問題：最優解是指在問題或情境中能找到的最佳或最理想的解決方案。這個定義涵蓋了在一定條件下，沒有任何其他解能比這個解更優越，即達到了問題解決的極限狀態。

3.2、對問題進行分析

推測可能的行駛軌跡，并最終得出駕駛習慣，可以通過以下步驟，結合流處理過程和批處理過程進行問題的解決：
在這里插入圖片描述

對交通地圖進行結構化處理

地圖的數據結構本質上是一種加權有向圖，且圖中存在環狀結構。要解決地圖上的問題，首先需要將地圖進行結構化。實際工作中，這個步驟可以由技術團隊自行完成——描述成二維矩陣或者二維表（鄰接表），也可以借助市場上成熟的中間件產品，例如PostgreSQL with PostGIS 、Neo4j、Cassandra等數據庫都對地理空間數據有專門的存儲格式和能力支持。作為后續的技術方案演練，本文將自行構建鄰接表來進行空間數據的結構化描述。
利用具有通勤業務特點的DFS/BFS算法，求A點到B點權值較大的多條可能路徑

這是非常關鍵的步驟，也是本文討論的技術核心之一。由于上文已經描述了可能性問題和最優解問題的區別，所以后續內容不再解釋為什么核心算法不是諸如Dijkstra這樣的最優解算法，而重點放在討論如何結合啟發式信息對常規DFS/BFS算法進行優化，以尋求各種可能的結果。

（導航軟件中，這條紅色的目標方向輔助線，到底有什么作用？僅僅是為了識別方向嗎？）

另外，在尋找可能路徑的過程中，由于路徑權重涉及多個領域的基礎數據，且這些基礎數據并沒有一個規范的評分方式，所以確認路徑的過程中，就可能使用熵權法對每條路徑進行確權，并且需要保證這些評分維度，可以進行擴展。
利用模糊綜合評價法，對路徑進行打分，分數最高者為最可能路徑

由上一步驟得到的可能路徑如果只有一條，那么就不需要進行本步驟。如果存在多條可能路徑，則需要利用綜合評分法，找到其中評分最高的一條路徑，作為最可能路徑。綜合評分涉及的評分維度至少包括實際時間和線路預計時間的差異，因為不同的業務場景可能存在的差異，參與綜合評分的維度允許進行擴展。
通過以上分析方式，積累一定規模的路徑樣本（例如1個月、2個月），通過線性回歸方式，求得車輛A在一定時間周期內的通勤習慣。

通過以上3個步驟，可以得到特定車輛某一次的可能行駛軌跡，但是僅僅一次或者有限的幾次行駛軌跡是無法確認車輛駕駛者的駕駛習慣的，需要一個較長時間段的多個軌跡作為分析樣本，分析后才能得出駕駛習慣。