田佳琪

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

基于對(duì)集的網(wǎng)約出租車(chē)供需優(yōu)化研究

田佳琪

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

近年來(lái)隨著滴滴打車(chē)、快的打車(chē)等的出現(xiàn)，網(wǎng)約出租車(chē)在交通出行方式中的占比在不斷上升，然而存在“供需不匹配”問(wèn)題，如何能夠優(yōu)化出租車(chē)服務(wù)資源的供需配置是一個(gè)重要問(wèn)題。本文基于圖的最大對(duì)集理論對(duì)出租車(chē)數(shù)據(jù)和打車(chē)訂單數(shù)據(jù)建立數(shù)學(xué)模型，利用MATLAB軟件求解最大匹配結(jié)果，并對(duì)全時(shí)段出租車(chē)資源的“供需匹配”程度進(jìn)行了分析。

互聯(lián)網(wǎng)+；二分圖；最大對(duì)集；最大流

1 研究背景與問(wèn)題提出

目前我國(guó)正在大力發(fā)展“互聯(lián)網(wǎng)+”和大數(shù)據(jù)技術(shù)，并積極推進(jìn)其與傳統(tǒng)產(chǎn)業(yè)的融合。傳統(tǒng)出租車(chē)行業(yè)的生產(chǎn)力已經(jīng)無(wú)法適應(yīng)現(xiàn)代社會(huì)高效出行的生產(chǎn)關(guān)系，因此近年來(lái)網(wǎng)約車(chē)市場(chǎng)發(fā)展迅速，滴滴打車(chē)、快遞打車(chē)、Uber等打車(chē)APP也逐漸盛行。“網(wǎng)約車(chē)”就是“互聯(lián)網(wǎng)+出租車(chē)”，就是利用互聯(lián)網(wǎng)進(jìn)行資源有效配置，對(duì)傳統(tǒng)出租車(chē)行業(yè)進(jìn)行供給側(cè)結(jié)構(gòu)性改革。

利用手機(jī)APP發(fā)出的訂單，如果未經(jīng)處理直接發(fā)送給出租車(chē)，可能出現(xiàn)離乘客距離較遠(yuǎn)的或者當(dāng)前已經(jīng)載客的出租車(chē)搶到了訂單，而距離較近的空載出租車(chē)未得到訂單的情況，造成“惡性搶單”，使乘客長(zhǎng)時(shí)間打不到車(chē)。當(dāng)乘客附近空載出租車(chē)較多時(shí)，又會(huì)出現(xiàn)訂單一發(fā)出，附近大量出租車(chē)都涌向一個(gè)乘客，發(fā)生“惡性搶客”，造成資源浪費(fèi)。因此如何能夠讓出租車(chē)快速準(zhǔn)確的為乘客服務(wù)成為一個(gè)重要的問(wèn)題。

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

2 問(wèn)題建模

本文以北京市為例，得到的某打車(chē)網(wǎng)站數(shù)據(jù)是以一小時(shí)為時(shí)間間隔，連續(xù)獲取的某個(gè)區(qū)域內(nèi)的空載出租車(chē)數(shù)量和位置數(shù)據(jù)以及乘客訂單數(shù)量和位置數(shù)據(jù)。然后在所選區(qū)域內(nèi)劃定多個(gè)邊長(zhǎng)為2公里的正方形片區(qū)，在片區(qū)內(nèi)分別統(tǒng)計(jì)空載出租車(chē)數(shù)量和乘客訂單數(shù)量，并在整個(gè)區(qū)域內(nèi)對(duì)空載車(chē)數(shù)量和訂單數(shù)量按片區(qū)進(jìn)行排序。另外，當(dāng)訂單發(fā)出時(shí)默認(rèn)只有在片區(qū)內(nèi)的空載出租車(chē)才能提供服務(wù)，片區(qū)外車(chē)輛不做考慮。表1和表2給出了整個(gè)區(qū)域內(nèi)排名靠前的空載車(chē)片區(qū)和訂單片區(qū)。

表1 不同位置片區(qū)空載出租車(chē)數(shù)量

表2 不同位置的訂單數(shù)量

我們的問(wèn)題是在片區(qū)內(nèi)對(duì)訂單和空載出租車(chē)求最優(yōu)或者說(shuō)最大的配對(duì)數(shù)。這與離散數(shù)學(xué)二分圖理論中求最大對(duì)集問(wèn)題類(lèi)似。因此本文將利用最大對(duì)集理論對(duì)此問(wèn)題進(jìn)行求解。

3 問(wèn)題求解

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

圖1 c1處4輛出租車(chē)和d1處的2個(gè)乘客

圖2 建立二分圖

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

圖3 所有出租車(chē)和乘客建立二分圖

圖4 相對(duì)圖3的一個(gè)最大對(duì)集

圖5 由圖2中的二分圖構(gòu)造的賦權(quán)圖

圖6 北京市不同時(shí)空下的出租車(chē)供需匹配程度

4 模型實(shí)現(xiàn)

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

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

5 結(jié)束語(yǔ)

本文利用二分圖中的最大對(duì)集理論作為模型對(duì)網(wǎng)約車(chē)與乘客間的服務(wù)資源供需優(yōu)化問(wèn)題進(jìn)行求解。以北京市網(wǎng)約出租車(chē)為例，把真實(shí)數(shù)據(jù)放入Matlab軟件進(jìn)行計(jì)算，求解出結(jié)果，并計(jì)算了不同時(shí)段的供需變化。為出租車(chē)司機(jī)和乘客的出行決策提供了依據(jù)。

[1] 馬化騰.關(guān)于以”互聯(lián)網(wǎng)+”為驅(qū)動(dòng),推進(jìn)我國(guó)經(jīng)濟(jì)社會(huì)創(chuàng)新發(fā)展的建議.全國(guó)兩會(huì). 2015.

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

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

[4] 刁在筠,劉桂真,宿潔,馬建華.運(yùn)籌學(xué).北京. 高等教育出版社，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