QA-Share: Towards Efficient QoS-Aware
Dispatching Approach for Urban Taxi-sharing
Shanfeng Zhang
1,2
, Qiang Ma
2
, Yanyong Zhang
3
, Kebin Liu
2
, Tong Zhu
2
, Yunhao Liu
2
1 Department of Computer Science and Engineering, Hong Kong University of Science and Technology
2 School of Software and TNList, Tsinghua University, Beijing, China
3 Department of Electrical and Computer Engineering, Rutgers University, USA
{shanfeng, maq, yanyong, kebin, tong, yunhao}@greenorbs.com
Abstract—Taxi-sharing allows occupied taxis to pick up new
passengers on the fly, promising to reduce waiting time for
taxi riders and increase productivity for drivers. However, if
not carefully designed, taxi-sharing may cause more harm than
benefit – it becomes harder to strike the balance between
driver’s profit and passenger’s quality of service (e.g. travel time,
number of strangers that share a taxi, etc.). In this paper, we
propose a QoS-aware taxi-sharing system design – QA-Share –
by addressing two important challenges. First, QA-Share aims
to maximize driver profit and user experience at the same time.
Second, QA-Share continuously optimizes these two metrics by
dynamically adapting its schedule as new requests arrive, without
entering an oscillation state.
To address these two challenges, we have formulated the
optimization problem using integer linear programming, and
derived the optimal solution under a small system scale. When
the number of requests and taxis becomes large, we have devised
a heuristic algorithm that has a much faster execution time. We
have also studied how to minimize oscillations caused by schedule
re-calculations by dynamically tuning the update threshold. We
have evaluated our approach with real-world dataset in a Chinese
city – ZhenJiang – which contains the GPS traces recorded
by over 3,000 taxis during a period of three months in 2013.
Our results show that the QoS and profit is increased by 38%
compared to earlier schemes.
I. INTRODUCTION
In modern cities, taxis are playing an increasingly important
role in supporting people’s commute. According to a survey
conducted in New York city [1], over 100 taxi companies op-
erate more than 13,000 taxis in New York, delivering 660,000
passengers every day. They convey more than 25% of the
passengers, accounting for 45% of total transit fares. Though
important, today’s taxi system is far from being efficient:
a common problem is that people often have difficulties in
hailing a taxi during rush hours, while occupied taxis may
still have available seats [2]. This inefficiency becomes much
worse in countries and areas that are still in the process of
urbanization, where the city population increases at a faster
rate than the number of taxis.
This problem has attracted some attention in recent years,
resulting in a proposed solution called ride-sharing, in which
people share a taxi with others who have similar itineraries
and schedules. When a new passenger request arrives, the
taxi-sharing server will try to dispatch a taxi to satisfy the
(a) Request R
1
(P → O) is re-
ceived. Taxi B is better to serve the
request.
(b) Then, request R
2
(Q → O) is
received. It’s better to update the
current schedule.
Fig. 1. Example to show the two challenges
new request while serving its existing requests (if any). Taxi-
sharing has to track passenger requests and taxi locations on a
real-time basis, both of which are highly dynamic and hard to
predict, thus posing great challenges on the underlying system.
Several taxi-sharing schemes have been proposed in the
literature, such as those discussed in [3–6]. However, they all
fall short of the requirements of a scalable taxi-sharing system
that serves real-time user requests. For example, CoRide [5]
focuses on static scenarios in which passengers and taxis are
at the same pick-up location (e.g., an airport). When a new
request arrives, CoRide simply inserts the request to the end
of an occupied taxi’s schedule, or arranges an empty taxi. On
the other hand, T-Share [6] does consider dynamic scenarios,
but its scheduling is rather simplistic: for each new request, it
simply assigns the taxi with the minimum additional driving
distance, without considering the Quality of Service (QoS) for
the passengers on the chosen taxi. Once a sharing schedule is
made, it remains unchanged even though a new schedule may
be more efficient.
In this study, we aim to improve the state-of-the-art taxi-
sharing strategy by addressing two important challenges. The
first challenge we target at is to find balance between enhanc-
ing QoS for passengers (e.g. travel time, number of strangers
that share a taxi, etc.) and maximizing profit for taxi drivers.
As an example, in traditional non-sharing taxi services, greedy
drivers may choose a longer route to increase his/her own
profit, extending the passenger’s travel time. In a sharing
system, if not careful, passenger’s QoS will be hurt even more.
People choose to take taxis for a comfortable, door-to-door
978-1-4673-7331-9/15/31.00
c
2015IEEE
2015 12th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)
978-1-4673-7331-9/15/$31.00 ©2015 IEEE 533
剩余8页未读，继续阅读
资源评论
weixin_38632916
- 粉丝: 4
- 资源: 964
最新资源
- 笔记自动驾驶预测与决策规划-Part8-数据驱动的规划方法
- yolov5目标检测模型的知识补充（基于响应的补充）.zip
- yolov5检测人脸和关键点，只依赖opencv库就可以运行，程序包含C++和Python两个版本的.zip
- Git 2.47.1 arm64
- 新能源汽车充电插口类型识别-YOLOV11标记，可识别Type-2，ccs2的充电标准
- Git 2.47.1 64位
- numpy和malti相关API示例源码
- YOLOv5 采用 Flask 框架，旨在统计交通中的车辆数量.zip
- HMC830寄存器配置的FPGA实现，通过SPI接口时序完成配置
- test5_QQ浏览器压缩包.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
