【作者】 刘鑫；

【导师】 李文中； 陆桑璐；

【作者基本信息】 南京大学 ， 计算机软件与理论， 2013， 硕士

【摘要】 随着人们生活水平的提高,城市中的机动车保有量也急剧增加。车辆给人们的出行带来便利的同时,也造成了交通拥堵和环境污染等问题。然而,车辆本身的利用率其实很低。据统计,私家车平均载客人数只有1.63。因此,拼车作为解决以上问题的一个有效手段,越来越受到社会各界的关注。所谓“拼车”,是指几个行程相似的人共享一辆汽车出行,尤其是上下班工作、或外出游玩的人,通常他们有车却一起搭乘以节省费用。通过拼车,人们不仅节省了出行费用,同时也减少了相应污染排放和道路拥堵,是一个双赢的行为。传统意义上的拼车一般只能解决人们的日常出行问题,而无法满足人们非计划的出行需求。而动态的拼车机制可以解决这样的问题。互联网与移动技术的普及,也为解决动态情况下的拼车问题带来了很大的帮助。在动态运行的情况下,通常会有一个集中式的调度系统来记录愿意提供拼车的车辆的状态。人们可以随时随地向调度系统发出自己的出行需求。调度系统在接收到用户的需求后,寻找满足条件的拼车对象。并迅速向相应的用户和车辆反馈匹配结果,在限定的时间内完成一个拼车行为。然而在动态场景下,用户的需求会不断地变化,车辆的状态也在不断地变化。要为用户提供实时、有效的拼车匹配具有一定难度。本文针对动态环境下的拼车问题进行研究,旨在解决在车辆状态和用户请求不断变化时的拼车匹配问题。本文设计了两个动态的拼车算法,一方面可以为乘客提供优化的拼车方案,使得用户在拼车时获得最大的收益；另一方面,可以尽量减少拼车服务的响应时间、减小计算量、提高匹配成功率。本文的主要工作与贡献概括如下：1.针对现有的基于聚类的拼车算法的不足,提出了改进的基于聚类的拼车算法。该算法将道路上的车辆状态加入考虑范围,通过抽象处理将其等价为用户请求,进行聚类操作,从而达到提高拼车算法的请求匹配成功率、并节省行车路程的目的。2.针对基于聚类的改进算法响应时延过大与计算复杂较高等不足,提出了一种基于位置近似的拼车算法。首先,该算法对用户请求进行即时匹配,从而减小算法的响应时延；其次,为了解决计算量过大的问题,该算法提出了相应的位置近似策略以及快速索引策略,从而在对用户的拼车请求进行匹配时,能够迅速地筛选出符合条件的车辆。3.基于真实的出租车数据集,分析了在出租车系统中引入拼车的可行性和必要性。以载客时的运行距离/总运行距离作为参考,出租车总体的平均利用率只有55.49%。针对出租车系统供需矛盾的现状,基于以上算法提出并设计了一个实时的出租车拼车调度系统。使用上海地区出租车的运营数据,对系统进行了仿真测试,实验结果表明：本文提出的基于聚类的改进算法平均比已有的拼车算法的匹配成功率提高5%,响应时延减少10%,同时路程节省率提高了约5%；本文提出的基于位置近似的算法在匹配成功率和路程节省率上可以达到同样效果,并且减少了50%以上的响应时延。更多还原

【Abstract】 The number of private cars is growing rapidly in recent years as a result of eco-nomic growth. However, traffic congestion and environmental concerns require people to use personal automobiles wisely. On the other hand, private car occupancy rates (the number of travelers per vehicle trip) are relatively low; average car occupancies in Europe range from 1.8 for leisure trips to 1.1 for commuters. As a result, the demand for ride-sharing services, which aim to bring together travelers with similar itineraries and time schedules, has increased sharply.By ride-sharing, people can save their travel cost, as well as reduce the exhaust emissions.Traditional ride-sharing systems formally or informally link riders and drivers who travel between the same places at the same time. Dynamic ride-sharing differs from traditional ones in that ride-sharing is arranged on a per trip basis rather than for trips made on a regular basis. Dynamic ride-sharing is a form of ride-sharing that is used for single, one way trips rather than for trips made on a regular basis at the same time.The development of algorithms for optimally matching drivers and riders in real-time may only play a small role in the ultimate success of ride-sharing, but it is central to the concept. Ride-sharing is still in its infancy and an opportunity exists to influence its success. By introducing and formally defining dynamic ride-sharing problems and its objectives, we introduced several methods to solve this question.The contribution of this paper lies in four aspects:1. We proposed an improved method to slove the dynamic ride-sharing problem based on clustering. By taking into account the running vechicles, this method will have a better performance than the old one.2. To slove the response delay problem in the previous methods, we introduced a new algorithm based on position approximating. We divide the area in to grids, and keep a cache for every grid. As a result, we can find the appropriate vehicles in a short time.3. We found out that, in the current taxi systems, the demand and the supply is in severe confliction. So we designed a realtime ride-sharing system for taxis. Then we evaluated this system with real world datasets. The evaluation shows that, our improved methods can help people get a higher satisfaction rate, save more money, while wait for a shorter time.更多还原