基于DBSCAN與LOF算法的共享汽車計價和停車點策略分析

李小龍，馬英奇

（1.安徽理工大學 電氣與信息工程學院，安徽 淮南 232001；2.安徽理工大學 計算機科學與工程學院，安徽 淮南 232001）

0 引言

共享汽車是基于互聯網共享經濟、車聯網基礎下的一種新興交通出行服務方式，把更多用戶在出行方面的需求集中為一種汽車共享出行模式。由于共享汽車的使用較為簡單，在手機APP上就能完成注冊、認證、訂車和還車的全部過程，還支持芝麻新型等免押金服務，減少了因交換押金產生的服務糾紛，這種就近取車、靈活換車的方式吸引了大批用戶。但是，這種用車方式給企業增添了很多麻煩[1-2]。在車輛安置問題上，會產生某些地區急需用車而訂不到車的問題，為此企業采用“分時租賃”模式來解決這個問題，但仍存在著企業收益較低，成本花費較大的問題。

1 整體思路

對于定價方案，主要是制定合理的價格，來提高企業的利潤。但要注意價格較低可能會造成更多的共享汽車使用量，同時造成更大的共享車調度時間，更長的員工工作時間和更高的調度成本，調度不合理會更加降低利潤。價格較高可能會造成城市外圍的使用者不再使用共享汽車，轉而去使用地鐵、公交車等其它交通工具，因此，合理的定價更能吸引使用者。首先對附件數據清洗，并找到該城市的人口密度和消費能力與其交通狀況的相關信息，對信息與數據進行預處理，然后建立共享汽車的概率模型，并在以企業最大利潤作為目標函數的基礎上建立多元目標優化模型。由于交通狀況，消費能力，人口密度等不同因素的影響因子不確定，本文在原有模型的基礎上，提出基于DBSCAN算法的模型改進，得到打包改進后的共享汽車分布示意圖并結合前述的多元目標函數，得出部分打包定價結果。

由于共享汽車的停車點是公司租用的，考慮到租賃費用高昂并結合第一階段的數據分布特點，研究是否可以減少停車點的數量，其中共享汽車分布密度對汽車停車點的數量產生影響。先統計一個附件中的各個時區共享汽車停車點的數量，發現在不同的時間段及位置，因為人流量有所不同，這給改變共享汽車停車點的數量帶來了可能性。一般情況下，共享汽車與用戶之間距離較近時能夠吸引用戶選擇，這是由于可以節省用戶的時間和經濟成本。本文采用LOF離群因子對共享汽車的分布密度進行刻畫，對象的局部離群因子，每個共享汽車車輛編號P都被分配一個局部離群因子。

2 共享汽車的概率模型

該概率模型是建立起共享汽車的概率與其他因素的函數關系，在此概率模型的基礎上參考以色列的特拉維夫市的人口、交通狀況、消費能力等相關情況，建立數學模型，給出使得企業利潤最大的共享汽車按小時計價方案。完成共享汽車按小時計價方案因素具體有以下幾個原因：共享汽車離用戶的距離、共享汽車間的離散度、共享汽車到達目的地的難易程度、到達目的地交通便利程度、人口以及消費能力。

3 多目標優化模型的建立

3.1 自變量考慮范圍

在考慮自變量范圍時，需要明確自變量的數量及與因變量的關系，由此可得到邏輯框圖如下圖1所示。

圖1 共享汽車定價邏輯框圖

3.2 約束條件

為了使目標達到最優，對位優化之前的定價總額M與平均成功率N，有如下約束條件：

在執行共享汽車的定價與未被執行的定價之間有一個的區域，本文稱之為合理定價范圍，即被執行的共享汽車定價略微降低或未被執行的共享汽車定價略微提高，在這個范圍內都有可能被執行。設PF為失敗共享汽車的定價，PS為成功共享汽車的定價，合理定價應該滿足：

執行率優化是定價總額一定的情況下執行概率，定價優化是執行率一定情況下的優化執行率，為了使得目標函數量最優化，本文給出的優化模型如下：

其中，Si為 優化后的第i個共享汽車的成功率，Pi為 優化后第i個共享汽車的定價，PFi為第i個共享汽車對應的失敗共享汽車定價，PSi為第i個共享汽車對應的成功共享汽車定價。

3.3 最優函數最優解求解

本文引入最大期望利潤W，設每一個共享汽車商家提供給系統的價格為Q，系統定價為Qi′，該共享汽車執行率為Ri，則最大系統期望利潤可以近似用如下公式估計：

也即能求出期望利潤最大時的定價總額與平均成功率的值。

該模型包含了上文的最優定價選擇以及如何打包與打包共享汽車定價的最優方案，并且對打包方案進行檢測，在實際應用中具有較好的實用性。

4 基于DBSCDN算法的模型改進

改進模型之前，本文需要明確打包的目的，事實上打包的目的與本文上文考慮的兩個因素—執行率與定價密切相關。

打包對執行率的影響：在打包過程中，并不是隨機打包距離近的點，而是盡量將預計不能成功執行（執行率低的點）和能成功執行（執行率高的點）進行打包，這樣能大大提高執行率低的點的執行率[3]。

打包對定價的影響：打包的任務點定價總和應該小于三個任務點分別定價的總和。事實上打包成功率較高的任務點對于系統盈利來說是不利的，打包對系統盈利的好處是提高平均成功率從而提高期望利潤[4]。

盡量聯合成功執行率高的與低的共享汽車點并打包，同時，考慮到實際共享汽車執行用戶不可能一次性乘坐多輛共享汽車，本文規定打包共享汽車數量上限不超過4個。對于打包完的集合，需要根據其周圍的用戶分布以及用戶情況來判斷打包是否合理，并將不合理的包打散[5-6]。

本文將某個區域的三個預打包共享汽車T1、T2、T3，兩個用戶a1、a2，此時他們的用戶得分半徑不能覆蓋任何一個共享汽車，即不合理打包。加入用戶a3，其用戶得分半徑覆蓋到原T3，即合理打包。

在尋找打包共享汽車最近的用戶，先確定多共享汽車中心點，其GPS坐標由共享汽車的平均經度與平均緯度確定。尋找該中心點最近的用戶距離，將該用戶到這若干個共享汽車的折線距離轉換成直線，示意圖如下圖2所示。a1為距離相應共享汽車最近的用戶，且其用戶得分半徑覆蓋共享汽車。本文將該用戶的軌跡T1→T2→T3→T4距離a1至的直線距離其中T4'的直線距離：

圖2 共享汽車等效距離示意圖

在共享汽車的定價方案確定之前，本文先猜測定價p由兩部分組成，即共享汽車本身價值p1與路途費用p2。而對于打包共享汽車來說，共享汽車本身價值p1沒有發生變化，變化的為路途費用p2，設a1與T1、T2、T3、T4共享汽車的直線距離分別為d1、d2、d3、d4，打包后a1到四個共享汽車的等效距離為a1至T4'的直線距離D。此時，路途費用P2'的算方式如下（假設路途費用與路途距離成正比）：

設共享汽車i本身價值x、路途費用y與定價Pi服從的函數關系如下：

其中D為等效距離，di為用戶到原i個共享汽車的距離。

將數據導入到MATLAB中記為X，通過程序檢驗聚類結果個數，調整聚類結果到合適區間，下圖3為DBSCAN模型求解的圖示結果。

圖3 DBSCAN模型求解的圖示結果

本文根據原數據對定價方式進行擬合判斷，得到每個打包任務較為合理的定價。本文列出部分任務的定價如下表1所示：

表1 部分打包定價結果展示

5 LOF算法的建立

LOF算法通常是用來判斷局部異常的離群點，本文嘗將離群因子作為停車點的數量的規律估計的一個因素。離群因子的算法流程如下：

（1）計算共享汽車車輛編號p的k距離。共享汽車p的k距離dk(p)為p到某個臨近的共享汽車q之間的距離，q是離P最近的第k個共享汽車。

（2）計算p的k距離鄰域Nk(p)，Nk即離點p最近的k個共享汽車組成的集合。

（3）計算p相對于共享汽車q的可達距離dk(p,q)，給定自然數k，p相對于q的可達距離為p到q點的距離dk(p,q)，d與dq中的較大值：

（4）計算p的局部可達密度P(p)，p的局部可達密度等于共享汽車點p的平均可達距離的倒數：

（5）計算共享汽車點p的局部離群因子O：

離群因子數值越大，該共享汽車點的周圍共享汽車分布密度越小，該點越離群；反之，離群因子數值越小，該共享汽車點分布密度越大，該點離群程度越小。離群因子針對共享汽車與共享汽車及用戶之間的分布關系。由于離群因子直接判斷共享汽車局部密度，比直接判斷共享汽車與共享汽車之間的距離更加能體現共享汽車分布的情況。將離群因子通過變換轉換為每個點的定價得分因子，可進行下一步定價規律的研究。

6 模型結果分析

通過LOF算法并結合第一階段的數據分布特點可知，在LOF值大即離群程度越大的地方，可以適當減少停車位的數量，在LOF值小即離群程度越小的地方，由于交通便捷，人口密度較大，共享汽車停車位的數量不宜減少。據此本文做出改進后的部分離散共享汽車停車位的分布示意如下圖4所示。

圖4 改進后的部分離散共享汽車停車位的分布圖

7 結語

本文考慮到的共享汽車計價方案優化影響因素較多，建立的機理模型適應性較強，回歸效果良好。使用一系列創新算法，實際表現良好，如研究共享汽車停車點時采用了LOF離群因子進行分析；在研究共享汽車計價時，對DBSCAN算法進行改進，接著對打包后的包進行可行性分析，與原方案對比后發現表現良好。采用的LOF離群度檢驗的算法對推廣用于電子商務犯罪檢測、網絡入侵檢測、生態系統失調檢測和公共衛生醫療等領域中，具有一定的啟發作用。