基于对集的网约出租车供需优化研究

田佳琪

(青岛二中, 青岛市, 山东省 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