基于對集的網約出租車供需優化研究

田佳琪

(青島二中, 青島市, 山東省 266061)

基于對集的網約出租車供需優化研究

田佳琪

(青島二中, 青島市, 山東省 266061)

近年來隨著滴滴打車、快的打車等的出現，網約出租車在交通出行方式中的占比在不斷上升，然而存在“供需不匹配”問題，如何能夠優化出租車服務資源的供需配置是一個重要問題。本文基于圖的最大對集理論對出租車數據和打車訂單數據建立數學模型，利用MATLAB軟件求解最大匹配結果，并對全時段出租車資源的“供需匹配”程度進行了分析。

互聯網+；二分圖；最大對集；最大流

1 研究背景與問題提出

目前我國正在大力發展“互聯網+”和大數據技術，并積極推進其與傳統產業的融合。傳統出租車行業的生產力已經無法適應現代社會高效出行的生產關系，因此近年來網約車市場發展迅速，滴滴打車、快遞打車、Uber等打車APP也逐漸盛行。“網約車”就是“互聯網+出租車”，就是利用互聯網進行資源有效配置，對傳統出租車行業進行供給側結構性改革。

利用手機APP發出的訂單，如果未經處理直接發送給出租車，可能出現離乘客距離較遠的或者當前已經載客的出租車搶到了訂單，而距離較近的空載出租車未得到訂單的情況，造成“惡性搶單”，使乘客長時間打不到車。當乘客附近空載出租車較多時，又會出現訂單一發出，附近大量出租車都涌向一個乘客，發生“惡性搶客”，造成資源浪費。因此如何能夠讓出租車快速準確的為乘客服務成為一個重要的問題。

互聯網平臺一般要對訂單和服務車輛進行管理，如果能夠把訂單只發送給距離較近的空載出租車，而屏蔽掉距離較遠的或者已經滿載的出租車，就能使服務資源又快又好的得以分配。那如何利用網站收集的訂單數據、出租車數據和位置數據進行統一的大數據分析成為一個技術上的難題。另外，對于一天的各個時段而言，城市交通存在高峰期和低谷期，出租車的使用量和訂單量也存在高峰期和低谷期。如果能夠獲得高峰和低谷的預測信息，無疑為出租車司機提供了訂單“天氣預報”，也為乘客下單出行提供了幫助。提高了車輛資源和道路資源的使用效率。

2 問題建模

本文以北京市為例，得到的某打車網站數據是以一小時為時間間隔，連續獲取的某個區域內的空載出租車數量和位置數據以及乘客訂單數量和位置數據。然后在所選區域內劃定多個邊長為2公里的正方形片區，在片區內分別統計空載出租車數量和乘客訂單數量，并在整個區域內對空載車數量和訂單數量按片區進行排序。另外，當訂單發出時默認只有在片區內的空載出租車才能提供服務，片區外車輛不做考慮。表1和表2給出了整個區域內排名靠前的空載車片區和訂單片區。

表1 不同位置片區空載出租車數量

表2 不同位置的訂單數量

我們的問題是在片區內對訂單和空載出租車求最優或者說最大的配對數。這與離散數學二分圖理論中求最大對集問題類似。因此本文將利用最大對集理論對此問題進行求解。

3 問題求解

3.1 建立二分圖。假設同一片區內有兩位置點c1和d1其中在c1處有4輛出租車，在d1處有2個乘客，c1和d1由于在同一片區內，所以相距小于2公里，如圖1所示。根據假設建立二分圖，如圖2。點vi和點ui之間連接一條邊的唯一條件是：ui空載且vi和ui間距小于2公里。當不同時段，這個區域內可能有點的變化。如圖3所示，片區內多了1個乘客點v3和3個出租車點u5、u6、u7。

圖1 c1處4輛出租車和d1處的2個乘客

圖2 建立二分圖

3.2 求最大對集匹配。建立二分圖后，需要求最大對集，即一輛車匹配一個乘客。二分圖中車點和乘客點數量較小者決定了最大匹配數。如圖3中乘客數量3決定最大匹配數為3，而v1和u1，v2和u2，v3和u5就是最大對集一個匹配，如圖4所示。凡是邊數大于3的子圖都不是最大對集，但最大對集并不唯一，圖3中還有其他最大對集，如v1和u2，v2和u4，v3和u7也是。找到最大對集就找到了乘客和出租車間的一個優化的服務配置。

圖3 所有出租車和乘客建立二分圖

圖4 相對圖3的一個最大對集

圖5 由圖2中的二分圖構造的賦權圖

圖6 北京市不同時空下的出租車供需匹配程度

4 模型實現

我們應用MATLAB軟件的Graph Theory Toolbox實現問題求解。調用最大對集函數grMaxMatch()，求圖3中的10個點求最大對集。但對于大規模點的圖，grMaxMatch()函數由于其內部算法的原因無法計算。因此需要對模型進行轉化，把求最大對集問題轉化為求最大流問題。以圖2為例，可以增加兩個點S和T，S與v1、v2連接，權重設為1，T與u1、u2、u3、u4連接，權重也設為1，其它權重都設為一個很大的值，如10000，這樣就構成了一個賦權圖，如圖5所示。利用最大流函數graphmaxflow()求從S到T的最大流，中間流過vi和ui間的邊就構成了原二分圖的最大對集。

根據上述原理和算法，還可以求出不同時段乘客與空載出租車的最大匹配數，圖6展示出北京市不同時段出租車的“供需匹配”程度。圖中可以看出，從22:00到5:00這段時間出租車的空載率不斷提高，供給量大于需求量，出租車的供需匹配程度不斷下降，而5:00到9:00為上班的人流量高峰，出租車的供需匹配程度不斷上升，中午13:00到14:00和晚上18:00到19:00分別達到出租車供需匹配程度的峰值，其他時刻供需匹配程度變化不大，僅在11:00到12:00這一時間段內略有下滑。

5 結束語

本文利用二分圖中的最大對集理論作為模型對網約車與乘客間的服務資源供需優化問題進行求解。以北京市網約出租車為例，把真實數據放入Matlab軟件進行計算，求解出結果，并計算了不同時段的供需變化。為出租車司機和乘客的出行決策提供了依據。

[1] 馬化騰.關于以”互聯網+”為驅動,推進我國經濟社會創新發展的建議.全國兩會. 2015.

[2] 維克托·邁爾-舍恩伯格著,盛楊燕,周濤譯.大數據時代—生活、工作與思維的大變革.浙江人民出版社,2012.

[3] 耿素云, 張立昴.離散數學（第五版）北京.清華大學出版社. 2013.

[4] 刁在筠,劉桂真,宿潔,馬建華.運籌學.北京. 高等教育出版社，2007.

[5] http://www.mathworks.com/matlabcentral/ fileexchange/4266-grtheory-graph-theory-toolbox．

Matching Set Optimized Supply and Demand of Internet Ordered Taxi

Tian Jiaqi
(Qingdao second middle school, Qingdao, China, 266061)

Resent years, with the appearance of DD-Taxi or kuaidi-Taxi, ordering taxi on internet is becoming more and more popular, however the supply and demand mismatching of taxi resource is a hard problem. This article apply maximum matching set method with taxi data and order data to modeling the issue, using MATLAB functions solve the problem, and measures the supply and demand matching degree in all time in one day.

internet+; bipartite graph; maximum matching set; maximum flow